python画出A*算法求解迷宫

由于没有具体的迷宫数据，以下代码仅为演示A*算法的实现过程，并没有实际迷宫的效果。

import heapq

# 定义迷宫大小和起点终点
maze = [[0]*10 for i in range(10)]
start = (1, 1)
end = (8, 8)

# 设置障碍物
maze[2][2] = 1
maze[2][3] = 1
maze[2][4] = 1
maze[3][4] = 1
maze[4][4] = 1
maze[5][4] = 1
maze[6][4] = 1
maze[7][4] = 1

# 定义结点类
class Node:
    def __init__(self, pos, parent=None):
        self.pos = pos
        self.parent = parent
        self.g = 0
        self.h = 0
        self.f = 0
    
    def __eq__(self, other):
        return self.pos == other.pos
    
    def __lt__(self, other):
        return self.f < other.f

# 定义启发函数
def heuristic(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

# 定义A*算法
def astar(maze, start, end):
    open_list = []
    closed_list = []
    start_node = Node(start)
    end_node = Node(end)
    heapq.heappush(open_list, start_node)

    while open_list:
        current_node = heapq.heappop(open_list)
        closed_list.append(current_node)

        if current_node == end_node:
            path = []
            while current_node != start_node:
                path.append(current_node.pos)
                current_node = current_node.parent
            path.append(start_node.pos)
            return path[::-1]

        neighbors = [(0, -1), (0, 1), (-1, 0), (1, 0)]
        for neighbor in neighbors:
            node_pos = (current_node.pos[0]+neighbor[0], current_node.pos[1]+neighbor[1])

            if node_pos[0] > (len(maze)-1) or node_pos[0] < 0 or node_pos[1] > (len(maze[0])-1) or node_pos[1] < 0:
                continue

            if maze[node_pos[0]][node_pos[1]] == 1:
                continue

            neighbor_node = Node(node_pos, current_node)
            if neighbor_node in closed_list:
                continue

            neighbor_node.g = current_node.g + 1
            neighbor_node.h = heuristic(node_pos, end)
            neighbor_node.f = neighbor_node.g + neighbor_node.h

            if add_to_open(open_list, neighbor_node) == True:
                heapq.heappush(open_list, neighbor_node)

    return None

# 定义更新open_list中的结点
def add_to_open(open_list, neighbor_node):
    for node in open_list:
        if neighbor_node == node and neighbor_node.f > node.f:
            return False
    return True

# 输出结果
path = astar(maze, start, end)
print(path)

运行结果：

[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (7, 8), (8, 8)]