A*寻路算法的实现

A*寻路算法是一种启发式搜索算法，用于在图形（如地图）中找到从起点到终点的最短路径。以下是一个基本的A*寻路算法的实现，其中使用了一个优先队列来存储待扩展的节点。

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 __eq__(self, other):
        return self.x == other.x and self.y == other.y

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

def astar(maze, start, end):
    # 初始化起点和终点节点
    start_node = Node(start[0], start[1])
    end_node = Node(end[0], end[1])
    
    # 创建开放列表和关闭列表
    open_list = []
    closed_list = []

    # 将起点加入开放列表
    open_list.append(start_node)

    # 开始寻路循环
    while len(open_list) > 0:
        # 从开放列表中找到f值最小的节点
        current_node = min(open_list)
        open_list.remove(current_node)
        closed_list.append(current_node)

        # 判断是否到达终点节点
        if current_node == end_node:
            path = []
            while current_node is not None:
                path.append((current_node.x, current_node.y))
                current_node = current_node.parent
            return path[::-1]

        # 获取当前节点相邻的节点
        children = []
        for new_pos in [(0, -1), (0, 1), (-1, 0), (1, 0)]:
            node_pos = (current_node.x + new_pos[0], current_node.y + new_pos[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]] != 0:
                continue

            # 创建新节点并计算f值
            new_node = Node(node_pos[0], node_pos[1])
            new_node.parent = current_node
            new_node.g = current_node.g + 1
            new_node.h = ((new_node.x - end_node.x) ** 2) + ((new_node.y - end_node.y) ** 2)
            new_node.f = new_node.g + new_node.h
            children.append(new_node)

        # 将子节点加入开放列表
        for child in children:
            if child in closed_list:
                continue
            for open_node in open_list:
                if child == open_node and child.g > open_node.g:
                    continue
            open_list.append(child)

    # 未找到路径
    return None

在上述实现中，Node类表示一个节点，其中包含节点的坐标、g值、h值和f值，以及指向父节点的指针。astar函数接受一个迷宫（表示障碍物和可行路径）以及起点和终点的坐标，并返回从起点到终点的最短路径。该函数使用一个优先队列来存储待扩展的节点，并在每次迭代中找到f值最小的节点进行扩展。在扩展节点时，该函数会计算每个相邻节点的f值，并将它们添加到开放列表中。如果找到终点节点，则该函数会回溯父节点以计算最短路径。如果未找到路径，则该函数返回None。