游戏常见算法——A*算法

概念你已经走过的路有多长​ —— 这叫 g 值实际代价。你猜剩下的路还有多远​ —— 这叫 h 值启发式估计。A* 算法每次都会选 总花费最小g h的方向去探索这样既能保证最终找到最短路径又比盲目的广度优先搜索快得多。关键术语启发式函数对于网格地图常用的启发式有曼哈顿距离四方向移动|dx| |dy|欧几里得距离任意方向sqrt(dx² dy²)只要 h(n) 不大于真实剩余代价可采纳性A* 就能保证找到最短路径。曼哈顿距离是最常用的可采纳启发式。代码importheapqclassNode:网格中的一个节点def__init__(self,x,y):self.xx self.yy self.gfloat(inf)# 起点到此的实际代价self.h0# 启发式估计代价self.ffloat(inf)# g hself.parentNone# 用于回溯路径def__lt__(self,other):returnself.fother.fdefheuristic(a,b):曼哈顿距离作为启发式returnabs(a.x-b.x)abs(a.y-b.y)defa_star(grid,start,end): grid: 二维列表0可走1障碍 start, end: (x, y) 坐标 返回: 路径列表 [(x,y), ...] 或 None rows,colslen(grid),len(grid[0])# 创建节点矩阵nodes[[Node(x,y)foryinrange(cols)]forxinrange(rows)]# 起点和终点start_nodenodes[start[0]][start[1]]end_nodenodes[end[0]][end[1]]start_node.g0start_node.hheuristic(start_node,end_node)start_node.fstart_node.gstart_node.h open_list[]heapq.heappush(open_list,start_node)closed_setset()# 四个方向上下左右directions[(-1,0),(1,0),(0,-1),(0,1)]whileopen_list:currentheapq.heappop(open_list)# 到达终点ifcurrentend_node:path[]whilecurrent:path.append((current.x,current.y))currentcurrent.parentreturnpath[::-1]# 反转得到从起点到终点closed_set.add((current.x,current.y))# 检查邻居fordx,dyindirections:nx,nycurrent.xdx,current.ydy# 边界检查ifnx0ornxrowsorny0ornycols:continue# 障碍物检查ifgrid[nx][ny]1:continue# 已在 closed list 中if(nx,ny)inclosed_set:continueneighbornodes[nx][ny]tentative_gcurrent.g1# 假设每步代价为1iftentative_gneighbor.g:# 找到了更好的路径neighbor.parentcurrent neighbor.gtentative_g neighbor.hheuristic(neighbor,end_node)neighbor.fneighbor.gneighbor.h# 如果邻居不在 open list 中则加入否则堆会自动处理重复因为已更新fheapq.heappush(open_list,neighbor)returnNone# 无路径# ---------- 测试 ----------if__name____main__:# 0 空地, 1 障碍grid[[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0]]start(0,0)end(9,9)patha_star(grid,start,end)ifpath:print(找到路径共 {} 步.format(len(path)-1))forpinpath:print(p,end - )print(终点)# 可视化visual[[.for_inrange(10)]for_inrange(10)]foriinrange(10):forjinrange(10):ifgrid[i][j]1:visual[i][j]█for(x,y)inpath:visual[x][y]*visual[start[0]][start[1]]Svisual[end[0]][end[1]]Eforrowinvisual:print( .join(row))else:print(无法到达终点)