|
A*寻路方式通常有三种：基于单元的导航图、基于可视点导航图与导航网络
术语
地图，目标估计，代价，节点（每个节点三个属性，g:从起始点到到当前点的代价，h:从当前节点到目标节点的代价，f=g+h），导航图
基于单元的导航图
（1） 基于单元的导航图是将游戏地图划分为多个正方形单元或六边形单元组成的规则网络，网格点或网络单元的中心可以看作是节点。
（2） 由于结构很规则，因此易于动态更新，动态增加建筑物或障碍
（3） 寻路是以网格为单位进行，但单个正方形过大，网格很粗糙，难以得到最好的路径；如果正方形小，网格精细，可以寻找到很好的路径，但是需要存储和搜索大量的节点，对内存要求太高，也影响效率
（4） 如果每个节点需要存入代价，需要一定的开销
可视点导航图
（1） 也成为路点图，路点也称为“轨迹点”
（2） 建立时，一般先由设计者在场景手工放置一些“路径点”，，然后由设计人员逐个测试这些“路径点”之间的可视性。如果两个点之间没有障碍物，代表能相互“看到”，那么可以用一条线段把这两个点连接起来，生成一条“边”，（可以会对‘边“施加一些限制，例如长度必须小于多少），这些点和边就组成了可视点导航图
（3） 优点是它的灵活性。路径点是场景设计者精心选择的，能覆盖大部分可行走区域。
（4） 缺点：手工放置路径点过于繁琐，也容易出错。其次，只是一些点和线段的集合，无法表示出实际的二维可行走区域，角色只能沿着边运动
（5） 组合爆炸问题：100个路径点，就可能需要测试100x99条路径
导航网格
（1） 将可行走区域分成凸多边形，也可以要求只能使用三角形，或者同时使用
（2） 在网格上进行A*寻路，
（3） 优点：可以进行精确的点到点移动，由于多边形的面积可以任意大，因此，只需要较少数量的多边形，就可以表示出很大的可行走区域
（4） 缺点：生成导航网格需要较长的时间，在经常发生动态变换的场景很少使用，多用于静态场景
Open表预处理表示相邻
Close表示处理完成相邻
节点类：G，F，H，父节点
BFS变种
（1） 先将Open和Close都清空，将起始节点放入Open中，
（2） 循环判断Open表不为空
（3） 从Open表中取出代价最小的节点
（4） 如果这个节点是目标节点，则return这个节点
（5） 否则遍历这个节点的周边节点
（6） 先通过这个节点的G加上相邻的代价得到预估的周边节点的G
（7） 先判断这个周边节点是否在Open或则在Close中并且这个预估G大于这个周边节点的原本预估G，则跳过这个周边节点
（8） 将这个周边节点的G值赋值为之前计算的预估G，H值通过算法（欧几里距离或则曼哈顿距离）计算预估，F=G+H，父节点为当前节点
（9） 如果这个周边节点在Close中，剔除出来
（10） 如果这个周边节点在Open中，可以选择更新在Open表中代价排序
（11） 如果不在Open中，则放入Open中
（12） 遍历周边节点结束，将这个当前节点，从Open中取出放入Close中去
某些特定的情况，要让AI更加智能，不只是最短距离，还要考虑路况，比如危险区域，沼泽区域，火力覆盖区域，这时为这些节点增加代价即可。
A* 插件：A* Pathfinding Project，跟Unity原生相比，源码公开，适用范围更广，还可以根据不同的应用要求，自己修改代码，实现各种变种
|