Python实现A*（A星）算法遍历二维网格逻辑错误排查求助

核心问题列表 #

• Node节点相等判断逻辑完全错误：当前__eq__方法仅通过f值判断两个节点相等，正确逻辑应为坐标location相同即代表同一网格节点。该错误会导致节点是否在开放/关闭列表的判断完全失准，大量节点包括[2,2]位置的节点会被误判为已存在，不会被加入列表处理。
• 总代价计算与路径更新逻辑错误：Node类中self.g错误存储了单步移动代价，而非起点到当前节点的总移动代价，路径更新的判断条件也完全不符合A*逻辑，导致无法正确更新更优路径。
• 邻居边界判断存在隐患：判断纵向（y轴）边界时错误使用了len(grid[0])，应改为len(grid)，当前正方形网格未触发异常，替换为矩形网格会直接越界报错。
• 主循环迭代次数不足：仅设置了6次迭代，不足以遍历到[2,2]位置以及终点，应改为循环到开放列表为空或找到目标节点为止。
• 节点扩展逻辑顺序错误：先判断开放列表再判断关闭列表的顺序颠倒，多余逻辑导致节点更新失效。

修复后完整代码 #

import math
import heapq

class Node:
    def __init__(self, location, parent, step_cost, goalLocation):
        self.location = location
        self.parent = parent
        # g为起点到当前节点的总代价
        if not isinstance(parent, Node):
            self.g = step_cost
        else:
            self.g = parent.g + step_cost
        self.h = math.sqrt((location[0] - goalLocation[0]) ** 2 + (location[1] - goalLocation[1]) ** 2)
        self.f = self.g + self.h

    def __eq__(self, other):
        # 坐标相同即同一节点
        return isinstance(other, Node) and self.location == other.location

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

    def __str__(self):
        return f"Location: [{self.location[0]},{self.location[1]}] | TotalCost:{self.g}"

    def __repr__(self):
        return f"Location: [{self.location[0]},{self.location[1]}] | TotalCost:{self.g}"

def getNeighbors(location, grid):
    neighbors = []
    max_y = len(grid) - 1
    max_x = len(grid[0]) - 1
    # 上
    if location[1] != 0 and grid[location[1] - 1][location[0]] != 0:
        neighbors.append([location[0], location[1] - 1])
    # 左
    if location[0] != 0 and grid[location[1]][location[0] - 1] != 0:
        neighbors.append([location[0] - 1, location[1]])
    # 下
    if location[1] != max_y and grid[location[1] + 1][location[0]] != 0:
        neighbors.append([location[0], location[1] + 1])
    # 右
    if location[0] != max_x and grid[location[1]][location[0] + 1] != 0:
        neighbors.append([location[0] + 1, location[1]])
    return neighbors

def expandNode(node, grid, clist, olist, goalLocation):
    neighbors = getNeighbors(node.location, grid)
    for n in neighbors:
        child = Node(n, node, grid[n[1]][n[0]], goalLocation)
        # 已在关闭列表直接跳过
        if child in clist:
            continue
        # 检查开放列表中是否已有同节点
        exist_node = next((item for item in olist if item == child), None)
        if exist_node:
            # 新路径代价更小则更新
            if child.g < exist_node.g:
                olist.remove(exist_node)
                heapq.heappush(olist, child)
        else:
            heapq.heappush(olist, child)

# 网格定义：0为障碍，其他值为移动代价
grid = [[0, 2, 1, 3], # 右上角[3,0]为起点
        [1, 1, 1, 0],
        [0, 4, 1, 3],
        [1, 1, 1, 1]] # 左下角[0,3]为终点

goalLocation = [0, 3]
startLocation = [3, 0]

firstNode = Node(startLocation, None, grid[startLocation[1]][startLocation[0]], goalLocation)
olist, clist = [], []
heapq.heappush(olist, firstNode)

step = 0
found = False
while olist:
    node = heapq.heappop(olist)
    print(f"当前弹出节点：{node}")
    print(f"第{step}步 | 开放列表：{olist}")
    print(f"第{step}步 | 关闭列表：{clist}\n")
    if node.location == goalLocation:
        found = True
        print("已找到终点，最优路径回溯：")
        path = []
        while node:
            path.append(node.location)
            node = node.parent
        print(" -> ".join([f"[{x},{y}]" for x,y in reversed(path)]))
        break
    clist.append(node)
    expandNode(node, grid, clist, olist, goalLocation)
    step += 1

if not found:
    print("无可达路径")

运行效果说明 #

修复后代码可以正常生成[2,2]位置的Node对象，会完整遍历所有可达节点，最终输出从起点到终点的最优路径，路径回溯功能也可正常工作。

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