A*算法仅探索少量节点即终止，未抵达目标节点问题排查

我正在实现A*算法，但算法遍历3个节点后就完全停止，无法抵达目标节点。以下是相关代码：

A*算法实现代码 #

def AStar(start_node, end_node):
    openSet = PriorityQueue()
    openSet.enequeue(0, start_node)  # 方法名拼写错误，应为enqueue

    infinity = float("inf")

    gCost = {}
    fCost = {}
    cameFrom = {}

    for node in graph:
        gCost[node] = infinity
        fCost[node] = infinity
    gCost[start_node] = 0
    fCost[start_node] = heuristic(start_node, end_node)

    while not openSet.isEmpty():
        current = openSet.dequeue()

        if current == end_node:
            RetracePath(cameFrom, end_node)

        # 错误：始终遍历起始节点的邻居，而非当前节点的邻居
        for neighbour in find_neighbors(start_node, graph):
            tempGCost = gCost[current] + 1

            if tempGCost < gCost[neighbour]:
                cameFrom[neighbour] = current
                gCost[neighbour] = tempGCost
                fCost[neighbour] = tempGCost + heuristic(neighbour, end_node)

                if not openSet.contains(neighbour):
                    openSet.enequeue(fCost[neighbour], neighbour)  # 同样存在拼写错误

        print(f"Came from: {cameFrom}\nCurrent: {current}")
    return False

查找相邻节点的代码 #

def find_neighbors(node, graph):
    x, y = node
    neighbors = []

    right_neighbor = (x + 1, y)
    left_neighbor = (x - 1, y)
    lower_neighbor = (x, y + 1)
    upper_neighbor = (x, y - 1)

    if right_neighbor in graph:
        neighbors.append(right_neighbor)
    if left_neighbor in graph:
        neighbors.append(left_neighbor)
    if lower_neighbor in graph:
        neighbors.append(lower_neighbor)
    if upper_neighbor in graph:
        neighbors.append(upper_neighbor)
    # 错误：缺少return语句，无法返回邻居列表

运行输出示例 #

Enemy coords: (6, 2)
Player coords: 10, 2
Enemy neighbours: [(7, 2), (6, 3)]
Priority Queue: [[0, (6, 2)]]
Priority Queue: [[4, (7, 2)]]
Priority Queue: [[4, (7, 2)], [6, (6, 3)]]
Came from: {(7, 2): (6, 2), (6, 3): (6, 2)}
Current: (6, 2)
Came from: {(7, 2): (6, 2), (6, 3): (6, 2)}
Current: (7, 2)
Came from: {(7, 2): (6, 2), (6, 3): (6, 2)}
Current: (6, 3)

问题修复方案 #

1. 核心错误：遍历邻居时使用错误节点 #

原代码始终调用find_neighbors(start_node, graph)，导致每次循环只处理起始节点的邻居，后续节点的邻居从未被加入优先级队列，队列耗尽后程序停止。需改为：

for neighbour in find_neighbors(current, graph):

2. 修复方法名拼写错误 #

将所有enequeue改为正确的enqueue，否则无法将节点正确加入优先级队列。

3. 补充find_neighbors的return语句 #

在find_neighbors函数末尾添加return neighbors，否则无法返回有效邻居列表。

4. 找到目标节点后终止程序 #

当current == end_node时，调用RetracePath后需立即返回结果，避免无效循环：

if current == end_node:
    path = RetracePath(cameFrom, end_node)
    return path

修正后的核心循环代码：

while not openSet.isEmpty():
    current = openSet.dequeue()

    if current == end_node:
        path = RetracePath(cameFrom, end_node)
        return path

    for neighbour in find_neighbors(current, graph):
        tempGCost = gCost[current] + 1

        if tempGCost < gCost[neighbour]:
            cameFrom[neighbour] = current
            gCost[neighbour] = tempGCost
            fCost[neighbour] = tempGCost + heuristic(neighbour, end_node)

            if not openSet.contains(neighbour):
                openSet.enqueue(fCost[neighbour], neighbour)

    print(f"Came from: {cameFrom}\nCurrent: {current}")

内容的提问来源于stack exchange，提问作者iaivazovski