Algorithm
：
A*
在地图中两点间找出一条路径，如果存在至少一条路径，在各种不同的算法中
A*
将找到最短路径，而且相比之下算法速度快。
A*
是一种可控的算法，是一种启发式搜索算法，也就是说算法本身不会盲目的搜索路径，而是估计一个最佳的考察方向，进行搜索。
在
A*
寻路算法中，我们从起点开始，检查相邻方格的方式，向外扩展直到找到目标。
我们做如下操作开始搜索：
1.
从起点开始，并且把它作为待处理的第一个点存入一个
“
开启列表
”
。开启列表就像一张购物清单。尽管现在列表里只有一个元素，但以后就会多起来。你的路径可能会通过它包含的方格，也可能不会。基本上，这是一个待检查方格的列表。
2.
从开启列表中取出一个代价最小的点
关于代价值的计算
F = G + H
这里：
* G =
从起点，沿着产生的路径，移动到当前节点的移动耗费。
* H =
从网格上那个方格移动到终点的预估移动耗费。这经常被称为启发值
如果开启列表为空则说明路径没有找到，结束搜索。如果取到这个节点，则将这个结点加入到
”
关闭列表
”
，如果这个点是终点，则结束搜索。如果不是终点就把这个点作为当前点。
3.
按照八个方向查找与当前点相邻的节点，如果是可以移动的点（寻找起点周围所有可到达或者可通过的方格，跳过有墙，水，或其他无法通过地形的方格）
a.
如果新考核的点在
”
关闭列表
”
中，并且从当前点到达这个点的
G
值更小则
将这个点作为当前点的孩子节点
更新这个点的
G
值
更新这个点所有孩子节点的父节点指针、
G
值、
F
值
b.
如果新考核的点在
”
开启列表中
”
，并且从当前点到达这个点的
G
值更小则
将这个点作为当前点的孩子节点
更新这个点的
G
值
c.
将这个点作为当前点的孩子节点，计算这个点的
G
、
H
、
F
值，将这个节点加入到
”
开启列表
”
中。
4
．跳回第二步周而复始，直到
”
开启列表
”
为空，或者将终点加入到
”
关闭列表
”
流程图:
算法优化：
算法中消耗分析
1.
节点的内存分配与释放
节点的内存分配与释放非常频繁，大规模搜索的时候通常需要数千个节点乃至上万个节点。所以很有必要做内存管理。考虑用
placement new
来分配内存减少分配与释放的开销，但是需要在程序运行开始就事先分配好内存。每个节点大约
20
字节左右，正常的情况下一张稍大的地图有
1500x1500
大小
2,250,000
格，那么最坏情况下，需要内存约
40,000k
，所以如果一开始就分配这么多内存是不现实的，所以只能限制一个内存分配极值，比如一次分配一兆，如果用完就结束搜索。但如果游戏一开始就分配
1
兆内存用于寻路，实际上有可能一直都不需要大规模搜索，所以最好有增长方式的内存管理。
另一个方案是每次分配一批节点所需内存，用完了再增长，分配粒度越大命中效果也会更好些。
2.
从开启列表中取出一个代价最小的点
从开启列表中取出一个代价最小的点需要比较并遍历所有在开启表中节点。优化的做法是在每次插入开启表的时候都将节点插入在表的最前端，这样每次从前端取就可以避免遍历的开销，但是分析证明，每次节点的值改变都需要重新排序，一次大循环中可能需要多次排序，而每次大循环只会取一次代价最小节点，所以这一次的遍历相比开销要比排序小的多。
3.
查找考核点是否在关闭列表
查找考察点是否在关闭或者开启列表中都需要遍历整张表，优化的办法是选择合适的数据结构。
相比使用
vector
插入和删除的速度会很慢，但是访问和遍历的速度很快，但如果
vector
预先分配内存，内存命中会很高，访问和遍历也会更快，插入和删除如果用
swap
也会相对较快。
使用
list
插入和删除速度会很快，但是遍历会很慢，内存命中也会比较差。如果算法中对表的插入比遍历频繁，可以考虑使用
list
。
经过测试发现，瓶颈在表的遍历与搜索上，
vector
无论有多快搜索速度都是线性的而且随着节点的增加，遍历时间也随之线性增长，而
map
的查找速度是常数级的，
Hash map
查找的时间复杂度为
O(1)
，即使用
STL
的
map
也会有
O(log (n))
比线性查找
O(n)
快很多，
map
永远是稳定的。
4.
如果已经存在在列表中并且当前
G
值最小则更新其
G
值和这个考核点所有的孩子节点的
G
值和父节点指针。
遍历孩子节点需要递规来完成搜索整棵树，开销在于函数调用，所以采用栈的方式来模拟递规。
5.
查找考核点是否在开启列表，如果在开启列表则更新这个节点。
6.
函数调用带来的开销，所有检测函数都做成内联函数，封装后的
A*
需要对外开放一个检测函数指针，可以实现函数对象来做检测函数，函数对象的可以内联
operator
操作符。
A*
带来的其他问题
A*
在最坏的情况下会广度搜索地图，花费很多时间才能找到终点，尤其是目标点为掩码（即无论如何到达不了的终点），所以通常情况下要对寻路时间加以限制，但是限制时间短了可能找不到目标点，限制时间长了又可能影响游戏帧率，比如在在游戏
Mouse Hold
的情况下，寻路是频繁进行的。一个经验值是
20
毫秒，对有效的目标点搜索超过
20
毫秒都没有找到有效的路径就放弃搜索，找一个离目标最近的终点即可。
但是时间限制可能存在硬件不同而效果不同的问题，对于不同的
cpu
来说，相同的时间搜索的范围会不一样，另一个选择是利用循环次数来限制。
对于目标点为掩码的处理，与其让
A*
进行超时搜索不如在开始设置目标点的时候就计算一个离目标点最近的可以到达的点。可以从目标点为中心一圈一圈向外搜索，直到搜索到一个可以到达的点（非掩码
…
）为止，这比起直接用
A*
消耗要小的多。
算法的进一步改进
1.
需要更快的速度
a.
改进数据结构
当前使用的是
STL
的
map
，是使用红黑树来管理内存的而不是真正的
Hash Map
，如果改为
HashMap
，效率可能会再有一些改进。
b.
分时计算
如果需要更快速的得到路径，需要分时计算。一开始就计算出一条快速路径，可能只有几步，只是一个大概的方向，然后让角色开始按照这条路径开始行进，与此同时继续计算完整路径。
2.
需要更优的路径
如果需要更优的路径，可以做进一步对路径进行修正，也就是在搜索好的路径上面选取一个点为目标再次进行搜索，找到更短路径。这也意味着运算时间更长，这时候就需要在性能和更好的效果上取一个平衡点。