python a星寻路

A星寻路算法是一种启发式算法，用于在图形地图中找到从起点到终点的最短路径。下面是一个简单的 Python 实现：

import heapq

# 定义节点类
class Node:
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.g = 0
        self.h = 0
        self.f = 0
        self.parent = None

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

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

# 定义 A* 寻路函数
def astar(start, end, grid):
    open_set = []
    closed_set = set()
    heapq.heappush(open_set, start)

    while open_set:
        current = heapq.heappop(open_set)

        if current == end:
            path = []
            while current.parent:
                path.append((current.x, current.y))
                current = current.parent
            path.append((start.x, start.y))
            return path[::-1]

        closed_set.add(current)

        for d in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            x = current.x + d[0]
            y = current.y + d[1]

            if x < 0 or x >= len(grid) or y < 0 or y >= len(grid[0]) or grid[x][y] == 1:
                continue

            neighbor = Node(x, y)
            neighbor.g = current.g + 1
            neighbor.h = abs(neighbor.x - end.x) + abs(neighbor.y - end.y)
            neighbor.f = neighbor.g + neighbor.h

            if neighbor in closed_set:
                continue

            if neighbor in open_set:
                if neighbor.g > current.g + 1:
                    neighbor.g = current.g + 1
                    neighbor.f = neighbor.g + neighbor.h
                    neighbor.parent = current
            else:
                neighbor.parent = current
                heapq.heappush(open_set, neighbor)

    return None

在这个实现中，我们定义了一个 Node 类来表示节点，并且实现了一个 `__lt__` 方法以便使用 heapq 进行节点的排序。在 astar 函数中，我们使用一个 open_set 堆来存储已经探索但还没有被扩展的节点，并使用一个 closed_set 集合来存储已经扩展过的节点。在每次迭代中，我们弹出 open_set 中 f 值最小的节点作为当前节点，然后扩展它的四个邻居节点。如果邻居节点已经在 closed_set 中，我们跳过它；如果邻居节点已经在 open_set 中，我们更新它的 g 值和 f 值并将其父节点设为当前节点；如果邻居节点不在 open_set 中，我们将其加入 open_set 并将其父节点设为当前节点。如果在搜索过程中找到了终点，我们就可以根据每个节点的父节点指针来回溯路径。