python实现A*算法

以下是一个简单的 Python 实现 A* 算法的代码示例：

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
    
class AStar:
    def __init__(self, start, end, obstacle_list, width, height):
        self.start = Node(start[0], start[1])
        self.end = Node(end[0], end[1])
        self.obstacle_list = obstacle_list
        self.width = width
        self.height = height

    def run(self):
        open_list = []
        closed_list = []

        heapq.heappush(open_list, self.start)
        
        while open_list:
            current_node = heapq.heappop(open_list)

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

            closed_list.append(current_node)

            for x_offset, y_offset in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
                neighbor_node = Node(current_node.x + x_offset, current_node.y + y_offset)

                if neighbor_node.x < 0 or neighbor_node.x >= self.width or \
                   neighbor_node.y < 0 or neighbor_node.y >= self.height or \
                   neighbor_node in self.obstacle_list:
                    continue

                if neighbor_node in closed_list:
                    continue

                neighbor_node.g = current_node.g + 1
                neighbor_node.h = abs(neighbor_node.x - self.end.x) + abs(neighbor_node.y - self.end.y)
                neighbor_node.f = neighbor_node.g + neighbor_node.h
                neighbor_node.parent = current_node

                if neighbor_node in open_list:
                    for i, n in enumerate(open_list):
                        if n == neighbor_node and neighbor_node.g < n.g:
                            open_list[i] = neighbor_node
                            heapq.heapify(open_list)
                            break
                else:
                    heapq.heappush(open_list, neighbor_node)

        return None

在这个示例中，我们定义了一个 Node 类来表示地图上的节点。我们还定义了一个 AStar 类来实现 A* 算法。在 AStar 类的 run 方法中，我们使用堆来实现 open_list，并在每次迭代中选择 f 值最小的节点进行扩展。我们还使用一个 closed_list 来存储已经访问过的节点，这样我们就可以避免重复扩展节点。在每次迭代中，我们计算当前节点的所有邻居节点的 f 值，并将它们加入 open_list 中。如果相邻节点已经在 closed_list 中，或者是障碍物，我们将跳过它们。如果相邻节点已经在 open_list 中，我们将比较它们的 g 值，并将 g 值更小的节点放在 open_list 中。如果相邻节点不在 open_list 中，我们将将其加入 open_list 中。

最终，如果我们从起点到终点找到了一条路径，我们将按顺序返回所有经过的节点。如果我们无法找到一条路径，我们将返回 None。

注意，这只是一个简单的实现示例。在实际应用中，你可能需要考虑更多的细节，例如节点的权重、启发式函数的选择、更复杂的障碍物等等。