问题：人物处于游戏地图的某个位置的时候，我们用鼠标点击另一个相对较远的位置时，人物会自动绕过很多障碍物走过去，玩过游戏的你，不知是否知道这个功能是如何实现的？
解题思路：在最优出行路线规划问题中，如果图非常大，那么Dijkstra最短路径算法的执行耗时会很多。但是真实软件开发中，面对超级大的地图和海量的寻路请求，算法的执行效率太低，这显然无法接受。实际上，像出行路线规划问题，真实软件开发中的问题，一般情况下，我们都不需要非得求最优解。在权衡路线规划质量和执行效率的情况下，我们只需要寻求一个次优解就足够了。那如何快速找到一个条接近于最短路线的次优路线呢？
这个快速的路径算法，就是A*算法。在Dijkstra算法的实现思路中，我们使用一个优先级队列，来记录已经遍历到的顶点以及这个顶点与起点的路径长度。顶点与起点路径长度越小，就越先被从优先级队列取出来扩展，这样可能会出现路径与终点跑偏的情况。
这里我们可以通过这个顶点跟终点之间的直线距离（欧几里得距离），来近似地估计这个顶点跟终点的路径长度。这个距离专业的叫法是启发函数。由于欧几里得距离的计算公式，会涉及比较耗时的开根号计算，我们一般通过另外一个更加简单的距离计算公式，那就是曼哈顿距离。曼哈顿距离=两点之间横纵坐标的距离之和。
Dijkstra算法原来只是单纯通过顶点与起点之间的路径长度，来判断谁先出队列，现在有了顶点与终点的路径长度估计值，我们就可以通过两者之和，来判断哪个顶点该最先出队列。综合两部分，我们就能有效避免跑偏的情况，这个函数专业叫法是估价函数。
A*算法与Dijkstra算法不同：优先级队列出队顺序不同，Dijkstra算法通过与起点之间路径长度来确认，A*算法通过估价函数来确认；终止条件不同，Dijkstra算法需要终点出队列才算结束，A*算法只需要遍历到终点就结束。
游戏中的地图并不像我们现实生活中的那样，存在规划非常清晰的道路，更多的是宽阔的荒野，草坪等。所以我们可以换一种抽象的思路，把整个地图分割成一个一个的小方块。在某一个方块上的人物，只能往上下左右四个方向的方块上移动。如果我们把每个方块看作一个顶点，两个方块相邻，我们就可以在它们之间，连两条有向边，并且边的权值都是1。这个问题就转换为在一个有向有权图中，找某个顶点到另一个定点的路径问题。
网友评论