A星寻路算法在QQ华夏中的应用
一、背景：
QQ华夏地图的特点：
因为QQ华夏地图是基于华夏的时间收费版本，为了让玩家能在游戏里更多的消耗时间，以前的地图都设计得很迂回，大量使用了高地等复杂地形。
华夏远程寻路先前的版本使用的是导航点寻路，在地图上配置一些导航点，组成导航网络，这个方式有以下一些问题：
1. 对每一个地图都需要配置导航网络，维护困难
2. 配置复杂，导航点的配置对寻路行为的影响难以预测
3. 寻路表现行为怪异（需要先奔上最近的导航点，然后依据导航网络寻路）
二、游戏对寻路的要求：
1. 不要求最优路径，大体上符合最优路径即可
2. 客户端能流畅工作
三、寻路算法的选择：
1. 在一个地图里，从一个点到另一个点，最简单的算法，无疑是深度优先搜索，或者广度优先搜索，这类搜索的弊端是，没有利用目标点信息，属于蛮力搜索，效率不高；
2. 在广度优先搜索的基础之上，利用到目标点的位置信息，加入启发函数，就形成了A*算法；
A*寻路算法的时间复杂度大概是O(N*log(N))，QQ华夏里比较大的地图尺寸有 600*400，对于客户端来说完全是能够承受的。
四、A*算法介绍
A*算法，作为启发式算法中很重要的一种，被广泛应用在最优路径求解和一些策略设计的问题中。而A*算法最为核心的部分，就在于它的一个估值函数的设计上；
启发函数的定义：
f(n)=g(n)+h(n)
其中f(n)是每个可能试探点的估值，它有两部分组成：
一部分，为g(n)，它表示从起始搜索点到当前点的代价（通常用某结点在搜索树中的深度来表示）。
另一部分，即h(n)，它表示启发式搜索中最为重要的一部分，即当前结点到目标结点的估值。
五、A*算法在华夏中的实现方式：
地图上的每个tile做为一个寻路结点，每个结点有路径评估值F，以及一个指向父结点的指针。使用hash_map，建立2个结点列表 (Open list – 待检查列表， Closed list – 已检查列表)，key 由 坐标x,y组合而成，value为x,y对应的结点对象。当终点加入到Closed list时，就说明寻路成功，从终点依据结点的父节点指针可以回溯到起点，得到整个路径。算法流程如下图所示：
在以上流程中，最费时的就是寻找F值最小结点，是整个算法中的核心，为了快速的搜索到F值最小的结点，游戏里维护一个map, F值为Key，按从小到大排序，key对应的Value是一个保存了结点索引的list，通过这种结构，可以快速的定位到当前F值最小的结点。如下图所示：
六、寻路实例分析：
地图：QQ华夏琅琊盆地（大小：300 * 460）
1. 从左上到中间高地，使用工作机，平均耗时 430ms，大致路径如下图，
2. 从右下到左上，使用工作机，平均耗时 480ms，大致路径如下图，
上面2个图已经是超远距离寻路了，对一个玩家来说，使用并不是非常频繁，几百毫秒的时间也是可以接受的；中远距离寻路，一般时间都在几十毫秒以内，完全满足游戏的需求。
问答：
Q : 寻路过程中有动态阻挡该如何处理?
A : 远程寻路后，会把路程分段。在角色移动过程中，每一段会使用近距离寻路算法重新运算，找到合适的路径。