用Python代码实现a*算法游戏自动寻路

以下是一个简单的Python代码实现a*算法游戏自动寻路的示例：

import heapq

def heuristic(a, b):
    # 计算两点间的曼哈顿距离
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def astar(start, goal, graph):
    # 初始化起点和终点的f值
    start_f = heuristic(start, goal)
    goal_f = 0
    
    # 初始化起点的g值和f值
    open_list = [(start_f, start)]
    g_score = {start: 0}
    f_score = {start: start_f}
    
    while open_list:
        # 获取当前f值最小的点
        current_f, current = heapq.heappop(open_list)
        
        if current == goal:
            # 找到了终点，返回路径
            path = []
            while current in graph:
                path.append(current)
                current = graph[current]
            return path[::-1]
        
        # 遍历当前点的邻居
        for neighbor in graph.get(current, []):
            # 计算邻居的g值
            tentative_g = g_score[current] + 1
            
            if neighbor not in g_score or tentative_g < g_score[neighbor]:
                # 更新邻居的g值和f值
                g_score[neighbor] = tentative_g
                h_score = heuristic(neighbor, goal)
                f_score[neighbor] = tentative_g + h_score
                heapq.heappush(open_list, (f_score[neighbor], neighbor))
                graph[neighbor] = current
    
    # 没有找到路径，返回空列表
    return []

# 用一个字典来表示地图，'x'表示障碍物，'g'表示终点
graph = {'A': ['B', 'C'],
         'B': ['D', 'E'],
         'C': ['F', 'G'],
         'D': [],
         'E': ['H'],
         'F': [],
         'G': [],
         'H': ['I'],
         'I': ['J'],
         'J': ['K'],
         'K': ['L'],
         'L': ['M'],
         'M': ['g'],
         'g': []}

start = 'A'
goal = 'g'

path = astar(start, goal, graph)
print(path)

在这个示例中，我们使用了一个字典来表示地图，其中每个键都是一个节点，对应的值是它的邻居。我们使用了一个heuristic函数来计算两点之间的曼哈顿距离，以作为估价函数来帮助a*算法搜索最短路径。我们使用了一个优先队列（实现为堆）来按照f值排序并选择下一个要扩展的节点。我们使用了一个字典来记录每个节点的g值和f值，以及每个节点的父节点，以便在找到路径后可以回溯出完整的路径。最后，我们测试了代码并输出了找到的路径。