概述

场景中寻路，是mmorpg项目中最常见的功能之一了，寻路NPC、寻路任务、寻路好友，都需要一种合适的算法，计算出一条最优的路径，而A*算法被认为是其中最有效的一种算法。在本人参与的项目中，使用的同样也是A*算法，再配合项目使用的编辑器，可以方便的绘制寻路方格信息，导出成寻路方格数据。

重点

首先，先明确所谓的A*算法是什么：

A*算法是一种静态路网中求解最短路径最有效的直接搜索方法，算法中的距离估算值与实际值越接近，最终搜索速度也越快。

而这里的预估值，即F = G + H公式所算出的代价F。我们需要做的就是计算当前方格周围8个方格的移动代价,选择其中代价最小的方格作为下一个行动点，以此反复，直到到达终点。

G值计算：从起点移动到指定方格的移动代价

使横向和纵向的移动代价为10000，斜角的移动代价为14142，并优先选择与前一方向相同方向的方格，所以方向不同的方格移动代价另加上8200。

H值计算：从指定的方格移动到终点的估算成本

使用Manhattan计算方式，即从当前方格横向或纵向移动到达目标所经过的方格数，忽略对角移动，然后把总数乘以 10000。

步骤

1. 把起点加入open list。
2. 重复如下过程：
   1. 取出open list中F值最小的方格，把它作为当前要处理的方格。
   2. 把当前方格移到close list。
   3. 计算当前方格相邻8个方格的移动代价： 如果它是不可抵达的或者它在close list中，忽略它。否则，做如下操作:
      1. 如果它不在open list中，则加入到open list，并且将当前方格设置为父节点，记录该方格的F，G和H值。
      2. 如果它已在open list中，检查这条路径(即经由当前方格到达它那里)是否更好。以G值为参考，更小的G值表示这是更好的路径。如果是，把它的父节点设置为当前方格，并重新计算它的G和F值。
      3. 按F值大小重新对open list从小到大排序。
3. 寻路结束。当把终点加入到open list中，此时路径已经找到了；或者open list中无可用的下一移动方格，此时没有路径。
4. 保存路径。从终点开始，沿着父节点移动直至起点，记录每个方向改变点，就形成了一条完整的路径。

补充

1. 寻路失败处理

   当出现还未将终点加入到open list，且open list中又无可用的下一移动方格，此时寻路失败，将终点位置设为当前方格位置。这样做是为了，在寻路失败的情况下也能获得一条前往终点就近点的路径。

2. open list排序问题

   在项目中,地图往往是很大的，那么方格数据也就越多，加入open list的方格也会很多，那么就会带来open list排序消耗的问题。在项目中的做法是：

   1. 插入新方格时，从栈尾开始使用二分法插入，使栈顶方格F值始终最小。时间复杂度为O(n)。
   2. 取出栈顶方格后，用栈尾方格从栈顶开始使用二分法重新插入open list。时间复杂度为O(n)。

资料

1. A* Pathfinding for Beginners