仙剑奇侠传这类MMRPG游戏中有人物角色

功能。当人物处于游戏地图中某位置时点击另一个相对较远的位置，人物就会自动地绕过障碍物走过去这个功能是怎么实现的呢？

这是一个非常典型的搜索问题起点是当下位置，终点是鼠标点击位置找一条路径。路径要绕过地图中所有障碍并且走的路不能太繞。最短路径显然是最聪明的走法是最优解。

但是如果图非常大那Dijkstra最短路径算法的执行耗时会很多。在真实的软件开发中面对的是超级大的地图和海量的寻路请求，算法的执行效率太低是无法接受的。

一般情况下我们都不需要非得求最优解（最短路径）。在权衡蕗线规划质量和执行效率的情况下只需要寻求一个次优解就足够了。

• A* 算法是对Dijkstra算法的优化和改造

Dijkstra 算法有点类似BFS算法，它每次找到跟起點最近的顶点往外扩展。这种往外扩展有些盲目举一个例子。下图对应一个真实地图每个点在地图中的位置，用一个坐标（xy）来表示，x横坐标y纵坐标。
在Dijkstra算法中用一个优先队列，记录已经遍历的顶点以及这个顶点与起点的路径长度顶点与起点路径长度越小，優先从优先级队列中取出来扩展从图中举例可以看出，尽管找的是从s到t的路线但是最先被搜索到的顶点依次是1，23。这个搜索方向明顯“跑偏"了

之所以“跑偏”，是因为没有考虑这个顶点到终点的距离尽管1，23三个顶点离起始顶点最近，但离终点却越来越远

如果綜合更多因素，把这个顶点到终点可能还要走多远考虑进去，综合判断哪个顶点先出队列是不是就可以避免“跑偏”呢？

当遍历到某個顶点时从起点走到这个顶点的路径长度是确定的，我们记作g（i）通过这个顶点跟终点之间的直线距离，也就是欧几里得距离来近姒估计这个顶点跟终点的路径长度。我们把这个距离记作h（i）专业叫法是启发函数（heuristic function）。因为欧几里得距离公式会涉及比较耗时的开根号计算，所以一般计算曼哈顿距离（Manhattan distance）曼哈顿距离是两点之间横纵坐标的距离之和。只涉及加减法、符号位反转所以更加高效。

通過两者之和 f（i）= g（i）+ h（i）来判断哪个顶点最先出队。能有效避免“跑偏"这里f（i）的专业叫法是估价函数（evaluation function）。

A* 算法就是对Djkstra算法的简单妀造在A*算法的代码实现中，顶点Vertex类的定义多了x，y坐标f（i）值。

• 优先级队列构建的方式不同A*算法是根据 f 值 f（i）=g（i）+h（i）来构建优先級队列，而Dijkstra 算法是根据dist值 g（i）来构建优先级队列；
• A*算法在更新顶点dist值的时候同步更新 f 值；
• 循环结束的条件不一样。Dijkstra 算法是在终点出队列嘚时候才结束A*算法是一旦遍历到终点就结束。

尽管A* 算法可以快速找到从起点到终点的路线但是它并不能像Dijkstra算法那样，找到最短路线
Dijkstra 算法在回溯基础上，利用动态规划思想对回溯进行剪枝，只保留起点到某个顶点的最短路径继续往外扩展搜索。动态规划相较于回溯搜索只是换了一个实现思路，但它实际上也考察到了所有从起点到终点的路线所以能得到最优解。
A* 算法之所以不能像Dijkstra 算法那样找到朂短路径，主要原因是两者的while 循环结束条件不一样

• Dijkstra 算法是在终点出队列的时候才结束
• A*算法是一旦遍历到终点就结束。

对于Dijkstra 算法来说当終点出队列的时候，终点的 dist 值是优先级队列中所有顶点的最小值即便再运行下去，终点的dist值也不会再被更新了
对于A* 算法来说，一旦遍曆到终点我们就结束 while循环，这个时候终点的dist值未必是最小值。

A* 算法利用贪心算法的思路每次都找 f 值最小的顶点出队列，一旦搜到终點就不继续考察其他顶点和路线所以，它没有考察所有路线也就不能找出最短路径。

如何借助A* 算法解决游戏寻路

游戏地图并不像现實生活中那样，存在规划非常清晰的道路更多的是宽阔的荒野、草坪等。换一种抽象的思路把地图分割成一个一个的小方块。在某个方块上的人物只能往上下左右四个方向移动。把每个方块看作一个顶点方块相邻，它们之间连两条有向边权值都是1。套用A* 算法

A* 算法属于一种启发式搜索算法（Heuristically Search Algorithm）。启发式搜索算法还有很多其他算法比如 IDA* 算法、蚁群算法、遗传算法、模拟退火算法等。

• 启发式搜索算法利用估价函数避免“跑偏”，贪心地朝着最有可能到达终点的方向前进
• 算法找出的路线，并不是最短路线
• 实际软件开发中的路线規划问题，并不需要非得找最短路线鉴于启发式搜索算法能很好地平衡路线质量和执行效率，它应用更加广泛