用A*算法求解最短路径迷宫的python代码

以下是一个示例实现：

from queue import PriorityQueue

class Maze:
    def __init__(self, maze):
        self.maze = maze
        self.width = len(maze[0])
        self.height = len(maze)

    def is_valid(self, x, y):
        return x >= 0 and x < self.width and y >= 0 and y < self.height and self.maze[y][x] == 0

    def get_neighbors(self, x, y):
        neighbors = []
        if self.is_valid(x - 1, y):
            neighbors.append((x - 1, y))
        if self.is_valid(x + 1, y):
            neighbors.append((x + 1, y))
        if self.is_valid(x, y - 1):
            neighbors.append((x, y - 1))
        if self.is_valid(x, y + 1):
            neighbors.append((x, y + 1))
        return neighbors

    def heuristic(self, current, goal):
        return abs(current[0] - goal[0]) + abs(current[1] - goal[1])

    def solve(self, start, goal):
        frontier = PriorityQueue()
        frontier.put(start, 0)
        came_from = {}
        cost_so_far = {}
        came_from[start] = None
        cost_so_far[start] = 0

        while not frontier.empty():
            current = frontier.get()

            if current == goal:
                break

            for next in self.get_neighbors(current[0], current[1]):
                new_cost = cost_so_far[current] + 1
                if next not in cost_so_far or new_cost < cost_so_far[next]:
                    cost_so_far[next] = new_cost
                    priority = new_cost + self.heuristic(goal, next)
                    frontier.put(next, priority)
                    came_from[next] = current

        path = []
        current = goal
        while current != start:
            path.append(current)
            current = came_from[current]
        path.append(start)
        path.reverse()

        return path

maze = Maze([
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [0, 0, 0, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0]
])

path = maze.solve((0, 0), (4, 4))
print(path)

在这个示例中，我们首先定义了一个 `Maze` 类，它可以接受一个二维数组作为参数来表示迷宫。我们还定义了一些辅助方法，如 `is_valid` 方法来检查一个位置是否是有效的（即没有超出边界并且不是障碍物），以及 `get_neighbors` 方法来获取一个位置的邻居。我们还定义了一个启发式函数 `heuristic`，它计算一个位置到目标位置的曼哈顿距离作为估计距离。

在 `solve` 方法中，我们使用优先队列来存储要探索的位置，并使用 `came_from` 和 `cost_so_far` 字典来跟踪路径和每个位置的实际成本。我们开始将起始位置放入优先队列中，然后从队列中取出位置并探索其邻居，更新成本和路径信息。如果邻居还没有被访问过，或者通过当前位置到达邻居的成本比之前更低，那么我们会将邻居加入队列中。我们一直重复这个过程，直到达到目标位置。

最后，我们可以调用 `solve` 方法来找到起始位置到目标位置的最短路径，并将其打印出来。在这个示例中，我们使用一个简单的 5x5 迷宫，其中 0 表示空白，1 表示障碍物。我们将起始位置设置为 `(0, 0)`，目标位置设置为 `(4, 4)`。