Python实现A*算法无法返回存在路径的问题求助

以下是代码中导致问题的关键错误及修复方案：

1. NODE类排序方法拼写错误 #

__lt__方法中调用了不存在的other.fcost()（小写c），但类中定义的方法是fCost()（大写C），这会导致堆排序时抛出AttributeError，中断搜索流程，最终返回None。

修正后的__lt__方法：

def __lt__(self, other):
    return self.fCost() < other.fCost()

2. 路径回溯使用错误节点 #

搜索到目标位置时，当前的current_node才是带有完整父节点链的路径节点，而初始创建的goal_node没有父节点信息，直接传入会导致回溯失败。

修改search方法中的目标判断逻辑：

if current_node.position == goal_node.position:
    return self.retracePath(start_node, current_node)  # 用current_node代替goal_node

3. OPEN堆节点判断逻辑错误 #

OPEN堆存储的是(fCost, node)元组，直接用neighbour in OPEN判断永远为False（元组和节点对象无法匹配）。需要新增集合跟踪OPEN中的节点，避免重复入堆。

优化后的search方法：

def search(self, start_node, goal_node):
    OPEN = []
    OPEN_SET = set()  # 记录OPEN中的节点
    CLOSED = set()
    start_node.h_cost = self.findManhattanDistance(start_node, goal_node)
    heapq.heappush(OPEN, (start_node.fCost(), start_node))
    OPEN_SET.add(start_node)
    
    while OPEN:
        current_cost, current_node = heapq.heappop(OPEN)
        OPEN_SET.remove(current_node)
        CLOSED.add(current_node)

        if current_node.position == goal_node.position:
            return self.retracePath(start_node, current_node)

        for neighbour in self.getNeighbours(current_node):
            if neighbour.isObstacle or neighbour in CLOSED:
                continue
            new_g_cost = current_node.g_cost + 1
            if new_g_cost < neighbour.g_cost or neighbour not in OPEN_SET:
                neighbour.g_cost = new_g_cost
                neighbour.h_cost = self.findManhattanDistance(neighbour, goal_node)
                neighbour.parent = current_node

                if neighbour not in OPEN_SET:
                    heapq.heappush(OPEN, (neighbour.fCost(), neighbour))
                    OPEN_SET.add(neighbour)

    return None

4. 可选优化：邻居节点生成逻辑 #

合并方向循环，简化代码（符合贪吃蛇只能上下左右移动的逻辑）：

def getNeighbours(self, node):
    neighbours = []
    directions = [(-1,0), (1,0), (0,-1), (0,1)]  # 上下左右四个方向
    for dx, dy in directions:
        new_x = node.position[0] + dx
        new_y = node.position[1] + dy
        if 0 <= new_x < 16 and 0 <= new_y < 16:
            neighbours.append(NODE((new_x, new_y), node.g_cost + 1, float('inf'), node, False))
    return neighbours

完整修复代码 #

import heapq
from pygame import Vector2

class NODE:
    def __init__(self, position, g_cost, h_cost, parent, isObstacle):
        self.position = position
        self.g_cost = g_cost
        self.h_cost = h_cost
        self.parent = parent
        self.isObstacle = isObstacle

    def __eq__(self, other):
        return self.position == other.position

    def __lt__(self, other):
        return self.fCost() < other.fCost()

    def __hash__(self):
        return hash(self.position)

    def fCost(self):
        return self.g_cost + self.h_cost

class ASTAR:
    def __init__(self):
        pass

    def getNeighbours(self, node):
        neighbours = []
        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        for dx, dy in directions:
            new_x = node.position[0] + dx
            new_y = node.position[1] + dy
            if 0 <= new_x < 16 and 0 <= new_y < 16:
                neighbours.append(NODE((new_x, new_y), node.g_cost + 1, float('inf'), node, False))
        return neighbours

    def findManhattanDistance(self, node1, node2):
        x1, y1 = node1.position
        x2, y2 = node2.position
        return abs(x1 - x2) + abs(y1 - y2)

    def search(self, start_node, goal_node):
        OPEN = []
        OPEN_SET = set()
        CLOSED = set()
        start_node.h_cost = self.findManhattanDistance(start_node, goal_node)
        heapq.heappush(OPEN, (start_node.fCost(), start_node))
        OPEN_SET.add(start_node)
        
        while OPEN:
            current_cost, current_node = heapq.heappop(OPEN)
            OPEN_SET.remove(current_node)
            CLOSED.add(current_node)

            if current_node.position == goal_node.position:
                return self.retracePath(start_node, current_node)

            for neighbour in self.getNeighbours(current_node):
                if neighbour.isObstacle or neighbour in CLOSED:
                    continue
                new_g_cost = current_node.g_cost + 1
                if new_g_cost < neighbour.g_cost or neighbour not in OPEN_SET:
                    neighbour.g_cost = new_g_cost
                    neighbour.h_cost = self.findManhattanDistance(neighbour, goal_node)
                    neighbour.parent = current_node

                    if neighbour not in OPEN_SET:
                        heapq.heappush(OPEN, (neighbour.fCost(), neighbour))
                        OPEN_SET.add(neighbour)

        return None

    def retracePath(self, start_node, goal_node):
        path = []
        current_node = goal_node

        while current_node != start_node:
            path.append(current_node.position)  # 可选：只存储坐标，方便贪吃蛇使用
            current_node = current_node.parent

        path.append(start_node.position)
        path.reverse()

        return path

astar = ASTAR()
start_node = NODE((0, 0), 0, 0, None, False)
goal_node = NODE((8, 8), 0, 0, None, False)
print(astar.search(start_node, goal_node))

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