A* 算法学习

在游戏中有一个很常见地需求就是要让一个角色从A点走向B点我们期望是让角色走最少的路。嗯大家可能会说直线就是最短的。没错但大多数时候A到B中间都会出现一些角色无法穿越的东西比如墙、坑等障碍物。这个时候怎么办呢是的我们需要有一个算法来解决这个问题算法的目标就是计算出两点之间的最短路径而且要能避开障碍物。1. A*简介A算法是启发式算法重要的一种主要是用于在两点之间选择一个最优路径而A的实现也是通过一个估值函数。2. FGHG表示该点到起始点位所需要的代价H表示该点到终点的曼哈顿距离。F就是G和H的总和而最优路径也就是选择最小的F值进行下一步移动后边会做详细介绍3. 曼哈顿距离上图中这个熊到树叶的曼哈顿距离就是蓝色线所表示的距离这其中不考虑障碍物假如上图每一个方格长度为1那么此时的熊的曼哈顿距离就为9。起点 (X1, Y1)终点 (X2, Y2)H|X2-X1||Y2-Y1|我们也可以通过几何坐标点来算出曼哈顿距离还是以上图为例左下角为(0, 0)点熊的位置为(1, 4)树叶的位置为(7, 1)那么H|7-1||1-4|9。4. 算法流程A算法现在被广泛应用与电脑游戏中的路径规划问题。我们就以此为例来介绍A算法的具体实施步骤。如下图所示其中A表示起点B表示终点黑色的实心方块表示障碍物。此外我们假设水平或垂直方向上相邻的两个方块之间距离是10那么对角线方向上相邻的两个方块距离就约是14。算法开始我们首先搜索A相邻的所有可能的移动位置对应于图中的绿色方块。每个方块左上角的值G表示该点到A的距离右上角值为H注意H不能大于该点到B的距离所以这里的H就取其到B的距离。最后还要计算一个F值FHG。然后像Dijkstra算法一样我们选一个F值最小的节点来做继续搜索。也就是上图中A的邻域中位于左上角的值F42。然后更新该节点的领域值。这时你会发现出现了三个F值都等于48的节点。到底应该选择哪一个来继续接下来的搜索呢这时需要考察它们中的那个H值最小结果发现H24是最小的所以下面就要从该点出发继续搜索。于是更新该节点的邻域方块中的值。这个时候再找出全局F值最小的点结果发现有两个为48而且它们的H值也相当于是随机选取一个作为新的出发点并更新其邻域值例如选择右上方的方块然后在从全局选取F最小的更新其邻域值于是有此时全局F最小的值为54而且F54的节点有两个所以我们还是选择其中H值最小的来做更新。于是更新该节点邻域方块中的值。这里你需要注意的一个地方是F54的红色节点下方邻域 (F68) 的方块中G38。但是从A到该节点的最短路径应该是30。这是因为目前程序所选择的路径是下图中紫色线路所规程出来的路径其G的增长序列是14→24→38。不过不要紧只要继续执行算法更新全局F值为最小节点 (F54) 的方块上面的G值就会给更新为正确的值了。此时全局F值最小的方块中F60所以更新该节点邻域方块中的值。现在全局F值最小的有两个都为68此时先更新H最小的。这是其实程序已经发现左侧F68的节点并不能引导一条更短的路径。于是接下来就要转向右侧F68的节点并以此为新起点搜索路径。最终反复执行上述过程你就会得到如下图中蓝色方块所示的一条最短路径。5. Python实现5.1. 算法思路A*算法实际是由广度优先遍历和Dijkstra算法演变而来的广度优先遍历主要是通过从起点依次遍历周围的点而寻找最优的路径Dijkstra基本思路跟广度优先遍历一样只不过给每次遍历的点增加了一个权值用于表明当前移动了多少距离然后每次从移动最短距离的点开始遍历A*在Dijkstra算法增加了一个期望值启发函数h最优化遍历节点的数量。广度优先遍历-Dijkstra算法-A*算法。其他寻路相关的算法也很多如JPS跳点算法但解决问题的侧重点不同关键是针对具体问题选择合适的算法。我们先来看一下地图橙点为起始点和终点本文中g为已走过的距离h为期望距离、启发值。文中会频繁使用这两个概念。A*算法中的h根据实际地图的拓扑结构可选用以下三种距离假设A与B点横纵坐标距离x和y曼哈顿距离只允许4个方向移动AB的距离为x y对角距离允许8方向移动AB的距离为x y (sqrt(2) - 2) * min(x, y)欧几里得距离允许任意方向移动AB的距离为sqrt(pow2(x) pow2(y))网格结构常用的便是8方向移动所以我们这边会选择对角距离作为h。5.2. 数据结构我在处理程序问题一般是先定义数据结构然后再补充算法本体。我们这次先从底层的数据结构逐级往上定义。从点、路径到整个地图我这边只展示关键的数据结构代码# 点的定义 class Vector2: x 0 y 0 def __init__(self, x, y): self.x x self.y y # 树结构用于回溯路径 class Vector2Node: pos None # 当前的x、y位置 frontNode None # 当前节点的前置节点 childNodes None # 当前节点的后置节点们 g 0 # 起点到当前节点所经过的距离 h 0 # 启发值 D 1 def __init__(self, pos): self.pos pos self.childNodes [] def f(self): return self.g self.h # 地图 class Map: map None # 地图0是空位1是障碍 startPoint None # 起始点 endPoint None # 终点 tree None # 已经搜寻过的节点是closed的集合 foundEndNode None # 寻找到的终点用于判断算法结束 def __init__(self, startPoint, endPoint): self.startPoint startPoint self.endPoint endPoint row [0]*MAP_SIZE self.map [] for i in range(MAP_SIZE): self.map.append(row.copy()) # 判断当前点是否超出范围 def isOutBound(self, pos): return pos.x 0 or pos.y 0 or pos.x MAP_SIZE or pos.y MAP_SIZE # 判断当前点是否是障碍点 def isObstacle(self, pos): return self.map[pos.y][pos.x] 1 # 判断当前点是否已经遍历过 def isClosedPos(self, pos): if self.tree None: return False nodes [] nodes.append(self.tree) while len(nodes) ! 0: node nodes.pop() if node.pos pos: return True if node.childNodes ! None: for nodeTmp in node.childNodes: nodes.append(nodeTmp) return False5.3. 具体实现A*算法的大概思路是从起始点开始遍历周围的点专业点的说法是放到了一个open集合中而我们这边的变量名叫做willProcessNodes从open集合中寻找估值即使用 Vector2Node.f() 函数计算的值最小的点作为下一个遍历的对象重复上面的步骤直到找到了终点。具体实现# 地图 class Map: def process(self): # 初始化open集合并把起始点放入 willProcessNodes deque() self.tree Vector2Node(self.startPoint) willProcessNodes.append(self.tree) # 开始迭代直到找到终点或找完了所有能找的点 while self.foundEndNode None and len(willProcessNodes) ! 0: # 寻找下一个最合适的点这里是最关键的函数决定了使用什么算法 node self.popLowGHNode(willProcessNodes) if self.addNodeCallback ! None: self.addNodeCallback(node.pos) # 获取合适点周围所有的邻居 neighbors self.getNeighbors(node.pos) for neighbor in neighbors: # 初始化邻居并计算g和h childNode Vector2Node(neighbor) childNode.frontNode node childNode.calcGH(self.endPoint) node.childNodes.append(childNode) # 添加到open集合中 willProcessNodes.append(childNode) # 找到了终点 if neighbor self.endPoint : self.foundEndNode childNode # 广度优先直接弹出先遍历到的节点 def popLeftNode(self, willProcessNodes): return willProcessNodes.popleft() # dijkstra寻找g最小的节点 def popLowGNode(self, willProcessNodes): foundNode None for node in willProcessNodes: if foundNode None: foundNode node else: if node.g foundNode.g: foundNode node if foundNode ! None: willProcessNodes.remove(foundNode) return foundNode # A*寻找f g h最小的节点 def popLowGHNode(self, willProcessNodes): foundNode None for node in willProcessNodes: if foundNode None: foundNode node else: if node.f() foundNode.f(): foundNode node if foundNode ! None: willProcessNodes.remove(foundNode) return foundNode我们可以看到在寻找点的时候使用了popLowGHNode这是使用A*的关键函数可以替换成上面两个函数使用不同的算法。以下展示使用不同算法的效果。广度优先遍历绿点代表遍历过的蓝点代表路径结果Dijkstra算法A*算法在A*的实现中h的计算也是个重要的参数像是本文上面中使用真实的预估距离作为h为了方便我们称该值为dh 0即Dijkstra算法h d预估值有一定的用处但相比 h d 而言性能较差h d性能最优并且能找到最佳路径h d性能可能进一步优化也可能更差但不一定是最优路径h g变成了最佳优先搜索。可以尝试调节Vector2Node.D查看效果。6. MATLAB实现function [route,numExpanded] AStarGrid(input_map, start_coords, dest_coords) % Run A* algorithm on a grid. % Inputs : % input_map : a logical array where the freespace cells are false or 0 and % the obstacles are true or 1 % start_coords and dest_coords : Coordinates of the start and end cell % respectively, the first entry is the row and the second the column. % Output : % route : An array containing the linear indices of the cells along the % shortest route from start to dest or an empty array if there is no % route. This is a single dimensional vector % numExpanded: Remember to also return the total number of nodes % expanded during your search. Do not count the goal node as an expanded node. % set up color map for display用一个map矩阵来表示每个点的状态 % 1 - white - clear cell % 2 - black - obstacle % 3 - red visited 相当于CLOSED列表的作用 % 4 - blue - on list 相当于OPEN列表的作用 % 5 - green - start % 6 - yellow - destination cmap [1 1 1; ... 0 0 0; ... 1 0 0; ... 0 0 1; ... 0 1 0; ... 1 1 0; ... 0.5 0.5 0.5]; colormap(cmap); % variable to control if the map is being visualized on every % iteration drawMapEveryTime true; [nrows, ncols] size(input_map); % map - a table that keeps track of the state of each grid cell用来上色的 map zeros(nrows,ncols); map(~input_map) 1; % Mark free cells map(input_map) 2; % Mark obstacle cells % Generate linear indices of start and dest nodes将下标转换为线性的索引值 start_node sub2ind(size(map), start_coords(1), start_coords(2)); dest_node sub2ind(size(map), dest_coords(1), dest_coords(2)); map(start_node) 5; map(dest_node) 6; % meshgrid will replicate grid vectors nrows and ncols to produce % a full grid % type help meshgrid in the Matlab command prompt for more information parent zeros(nrows,ncols);%用来记录每个节点的父节点 % [X, Y] meshgrid (1:ncols, 1:nrows); xd dest_coords(1); yd dest_coords(2); % Evaluate Heuristic function, H, for each grid cell % Manhattan distance用曼哈顿距离作为启发式函数 H abs(X - xd) abs(Y - yd); H H; % Initialize cost arrays f Inf(nrows,ncols); g Inf(nrows,ncols); g(start_node) 0; f(start_node) H(start_node); % keep track of the number of nodes that are expanded numExpanded 0; % Main Loop while true % Draw current map map(start_node) 5; map(dest_node) 6; % make drawMapEveryTime true if you want to see how the % nodes are expanded on the grid. if (drawMapEveryTime) image(1.5, 1.5, map); grid on; axis image; drawnow; end % Find the node with the minimum f value,其中的current是index值需要转换 [min_f, current] min(f(:)); if ((current dest_node) || isinf(min_f)) break; end; % Update input_map map(current) 3; f(current) Inf; % remove this node from further consideration numExpandednumExpanded1; % Compute row, column coordinates of current node [i, j] ind2sub(size(f), current); % ********************************************************************* % ALL YOUR CODE BETWEEN THESE LINES OF STARS % Visit all of the neighbors around the current node and update the % entries in the map, f, g and parent arrays % action[-1 0; 1 0; 0 -1; 0 1];%上下左右 for a1:4 expand[i,j]action(a,:); expand1expand(1,1); expand2expand(1,2); %不超出边界不穿越障碍不在CLOSED列表里也不是起点则进行扩展 if ( expand11 expand1nrows expand21 expand2nrows map(expand1,expand2)~2 map(expand1,expand2)~3 map(expand1,expand2)~5) if ( g(expand1,expand2) g(i,j)1 ) g(expand1,expand2) g(i,j)1; f(expand1,expand2) g(expand1,expand2)H(expand1,expand2); parent(expand1,expand2)current; map(expand1,expand2)4; end end end %********************************************************************* end %% Construct route from start to dest by following the parent links if (isinf(f(dest_node))) route []; else route [dest_node]; while (parent(route(1)) ~ 0) route [parent(route(1)), route]; end % Snippet of code used to visualize the map and the path for k 2:length(route) - 1 map(route(k)) 7; pause(0.1); image(1.5, 1.5, map); grid on; axis image; end end end参考文献[Unity] A-Star(A星)寻路算法 - 我爱我家喵喵 - 博客园A*算法详细讲解以及实现_zha_zha_wei的博客-CSDN博客_a*算法实现Python A*算法的简单实现_暗光之痕的博客-CSDN博客_a*算法python实现