a*算法python代码寻路

A*算法是一种常用的寻路算法，可以用于计算机游戏等应用中。它在Dijkstra算法的基础上增加了一些启发式函数，以提高搜索效率。以下是一个简单的Python代码实现：

import heapq

class Node:
    def __init__(self, x, y, reachable):
        self.x = x
        self.y = y
        self.reachable = reachable
        self.parent = None
        self.g = 0
        self.h = 0
        self.f = 0

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

class AStar:
    def __init__(self, grid):
        self.grid = grid
        self.open = []
        self.close = []

    def get_path(self, start, end):
        start_node = Node(start, start, True)
        end_node = Node(end, end, True)
        if not self.grid.is_reachable(end_node.x, end_node.y):
            return None

        heapq.heappush(self.open, start_node)
        while len(self.open) > 0:
            current_node = heapq.heappop(self.open)
            self.close.append(current_node)

            if current_node.x == end_node.x and current_node.y == end_node.y:
                path = []
                while current_node.parent is not None:
                    path.append((current_node.x, current_node.y))
                    current_node = current_node.parent
                path.append((start_node.x, start_node.y))
                return path[::-1]

            neighbors = self.grid.get_neighbors(current_node.x, current_node.y)
            for neighbor in neighbors:
                if neighbor.reachable and neighbor not in self.close:
                    g = current_node.g + 1
                    h = ((neighbor.x - end_node.x) ** 2) + ((neighbor.y - end_node.y) ** 2)
                    f = g + h
                    if neighbor in self.open:
                        if neighbor.g > g:
                            neighbor.g = g
                            neighbor.h = h
                            neighbor.f = f
                            neighbor.parent = current_node
                            heapq.heapify(self.open)
                    else:
                        neighbor.g = g
                        neighbor.h = h
                        neighbor.f = f
                        neighbor.parent = current_node
                        heapq.heappush(self.open, neighbor)

        return None

class Grid:
    def __init__(self, width, height):
        self.width = width
        self.height = height
        self.nodes = [[Node(x, y, True) for y in range(height)] for x in range(width)]

    def get_neighbors(self, x, y):
        neighbors = []
        if x > 0:
            neighbors.append(self.nodes[x-1][y])
        if x < self.width - 1:
            neighbors.append(self.nodes[x+1][y])
        if y > 0:
            neighbors.append(self.nodes[x][y-1])
        if y < self.height - 1:
            neighbors.append(self.nodes[x][y+1])
        return neighbors

    def is_reachable(self, x, y):
        return self.nodes[x][y].reachable

以上代码是一个基于堆优化的A*算法实现，其中Node表示一个节点，Grid表示一个网格，AStar表示A*算法的实现类。get_path方法接受起点和终点作为参数，返回一条从起点到终点的路径。