A* 算法在停止之前仅探索几个节点 - 没有到达目标节点

Question

我正在尝试实现 A* 算法，但它在完全停止之前只到达三个节点。

这是算法代码：

def AStar(start_node, end_node):
    openSet = PriorityQueue()
    openSet.enequeue(0, start_node)

    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()  # Doesn't work yet

        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)

这是输出的示例：

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)

在它只是停止代码而没有到达目标坐标（玩家坐标）之前

lmk 如果您对代码有任何疑问， 谢谢你。

Answer 1

您的代码仅检查起始节点的邻居，当您调用

find_neighbors

时，您总是使用

start_node

您应该使用

current

来代替：

for neighbour in find_neighbors(current, graph):
    # your code