总结A*算法在游戏开发中的实现和设计
在阅读了以下有关A*算法的入门级介绍之后，自己打算再整理一遍，以便消化和进一步理解。
A*算法描述
- 1.将起始点添加至待处理集合A（原文中的OpenList）
- 2.循环重复以下步骤
- a)寻找待处理集合A中F值最低的节点b；
- b)将节点b从待处理集合A中移除，并添加至已处理集合B（原文中的ClosedList）
- c)检测与节点b邻接的节点，进行以下处理：
①如果节点已经在集合B中，则不做任何处理；
②如果节点不在集合A中，则按照以下步骤处理：
——操作1：标记节点的父节点为当前节点b，并计算F/G/H的值；
——操作2：将节点添加至集合A。
③如果节点已经存在集合A中，则临时计算从当前节点b到该节点的F/G值，如果F值更小，则更新该节点的信息，既：更新节点的F/G，并修改其父节点为当前节点b（这表明从节点b到达该点为当前更好的路径）。
- 3.循环终止的条件
-
a)目标节点已经被添加至集合A(也可以控制成被添加至集合B作为条件)
或
b)还未找到目标节点时，集合A已经被掏空（集合A没有备选项了），此时表明这样的路径不存在。 - 4.保存路径
- 从目标路径的父节点开始一层一层向上直到起始点。
算法细节注释
- 1.循环工作的第一步：挑选代价消耗F最小的节点
- 公式F=G+H
*G：代表了从生成路径前一个节点移动到该节点需要花费的行动代价(movement cost)
*H：代表了从该节点到最后目标节点的预估行动代价(estimated movement cost)。这里指的是通过启发式的引导，进行代价估算。
- 2.循环工作的第二步：添加到已处理集合B的含义
- 被步骤一挑选过后的点，都确定了其最短路径，故而，添加至集合B表明今后这些点都不需要被重新计算。
- 3.循环工作的第三步：添加、更新节点的含义
- a)添加沿着路径通过当前点能够访问到的新的节点；
- b)更新沿着当前的路径是否能以更小代价到达之前能到达的点。
实现相关
数据结构
地图 基本结构：
| 主要属性 | 解释 |
|---|---|
| accessible | 是否可达（如障碍物不可达） |
| type | 可以利用标注类型来指明从相邻节点到达该节点的代价（如平地到山丘花费的代价） |
| isVisited | 标记是否在“待处理集合A(OpenList)”中 |
| isShortest | 标记是否在“已处理集合B(ClosedList)”中 |
| Value_F | 代表按照已记录的路径到达该节点花费的总代价 |
| Value_G | 代表按照已记录的路径到达该节点花费的行动代价 |
| Value_H | 代表当前节点到目标节点的预估代价 |
| Node* father | 指向父亲节点的指针 |
子算法
- 1.流程(2.a)的过程实际上能理解成不断从一个集合中寻找最小值
-
相关的算法有很多，可以根据实际情况加以挑选。
- 简单遍历，逐一扫描：效率低，但适合解决小地图寻路问题
- 维护有序的集合：每次寻找都直接读取最小值，但是插入以后需要调整（比遍历方法效果更好）
- Binary heap：在大多数场合比一般的方法快2~3倍，并且在长路径问题中效率呈几何级增长（十倍以上）
设计相关
- 地形间移动代价
- 通常在游戏中会涉及到多种地形，例如湿地、山丘等，这些地形不算障碍物，但通常会设计较高的内移动代价。更复杂的还有，不同地形切换的消耗代价也许也会不同（例如，从水路切换到陆地也许需要支付很大的代价）。
- 我们可以简单的通过给地形增加类型，用以进一步标明相关代价消耗的关系。在计算行动代价G的值时，将其考虑在内即可。
- 影响映射(influence mapping)
- 这个概念类似于战棋游戏中ZOC（zone of control）的概念。
- 举个例子：
在战棋游戏中，原本你控制的一支部队能在平原上移动10步，但是由于在通向目的地的路径周围存在敌军部队，所以在经过敌方部队相邻（敌方控制区内）的路径格时，会花费巨大的额外代价，导致寻路结果的改变。
- -
- 通过这种方式，还可以避免出现AI寻路时一味追求最短路径而忽略可能存在的危险，让游戏看上更合理。
- 那么如果考虑到这一点因素，计算总代价F值时，可以加入ZOC的影响因子。
- 多个单位的路径重叠
- A*算法的一个缺点在于，当多个单位试图抵达位置接近的目标时，会出现多个单位采用相同或相似的路径。这种情况会让单位拥堵在几条“热门的捷径”上，显然不符合游戏仿真。
- 那么如何解决这个问题呢？
可以给已经被单位”claimed”(此路是我开)的路径增加惩罚因子(penalty)，在一定程度上分散减少各个单位的碰撞（通过增加路径消耗的代价，减少别的单位选取该路径的机率）。注意，惩罚因子的设计要合理，以避免路径不可达的情况（代价太大以至于几乎没有别的单位会选取该路径）。
如果有必要的话，也可以仅给接近目标点的部分路径格子增加惩罚因子，而不是路径上的所有节点。这样更贴近现实情况：大家从乡间小路聚向市中心，离市中心越近才越堵，很远的地方几乎不会相互影响。
- 模拟未探索的区域
- 在游戏中可能会碰到这样的情况：AI似乎总是知道前往目的地的最佳路径，而其实这条路径所在的范围还“未被探索”（处于战争迷雾中）。
- 这样“聪明”到不真实的体验的确很糟糕。
- 我们可以为每个玩家增加”knownWalkability”数组，用以包含已探索的区域信息。使用这种方法，在考虑其单位寻路时，可以模拟出“探索”的效果，而当目标完全暴露 在已知区域时，A*算法又能正常执行。
- 更光滑的路径
- A*算法生成的最短路径的确是最小代价的路径，但有的时候，我们可能出于各种理由，想要一条较为光滑的路径。
- 有几种方法可以解决这个问题。
- 例如，在计算路径时可以增加转向惩罚因子，以减小选取走斜边的概率。另外，也可以分析生成的路径，选取邻接的节点替换斜边节点以实现更光滑的效果（这种情况相当于牺牲了部分所谓的“行动力”换取更优雅的路线）。
- 非方形搜索区域
- 在作者给的例子里，使用的简单的2D方形图。这样简单的设置使得描述地形单位的关系变得十分简单。但是，我们也可以使用不规则形状的区域。
设想一下在冒险棋的游戏中，不同国家间的移动。你可以设计一个像那样的寻路关卡，为此，可能需要建立一个国家相邻关系的表格以及和从一个国家移动到另一个国家的G值。同时也要考虑如何估计H。
与此类似，你也可以为固定地形的地图创建航路点系统(waypoint system)。航路点可以横穿一条路径，在地牢游戏里可能代表 了一条路或隧道。游戏的设计者通常会预设好这些航路点，当两个航路点之间的直线路径上不存在障碍时，视为该两点邻接。
在应用中的不足
- 1.会穿透路径中碰撞到的其他单位
- 在多个单位都在移动的情况下，往往需要处理在移动过程中碰到其他单位的情况。这种情况下需要设计新的方法生成路径，如简单的上下左右绕过等。即，为了补足这种缺陷，需要单独再添加碰撞检测的代码以及相关新路径生成方法。
- 2.大量寻路单位占据了大量CPU时间
-
这几乎是寻路问题的通病。但是可以通过以下策略缓解：
- 使用更小的地图或控制寻路单位的数量
- 不要让多个单位同时寻路，取而代之的方法是将他们加入队列，将各个寻路过程分散在几个游戏周期中。如果游戏以40周期每秒的速度运行，没人能察觉到。但当大量寻路单位计算自己的路径的时候，玩家会发觉游戏的速度变慢了。
- 使用更大的地图分块，以降低寻路中需要搜索的网格总数。(Consider using larger squares (or whatever shape you are using) for your map. This reduces the total number of nodes searched to find the path)。我的理解是，在一定条件小，可以把几个小格当成一个大格来处理，而移动到邻接的网格就相当于移动到刚才几个小格的中心位置。如果有必要，可以设计两个寻路系统，这通常也是专业的寻路做法：使用大块作为长路径选择，而当接近目标时，使用适用更小的块的另一种方法以产生更精细（小范围内看出最短）的路径。
- 考虑常用的长路径，可以预先计算并保存好。在需要使用时，直接查询。
- 预设好那些不可达的点。并在调用A*算法寻路前，检验目标点是否可达。
- 在一些类似“迷宫”游戏的环境下，设计地图时，可以人为标注一些只会到达“死角”的网格，以此暗示AI此路不通，不必尝试通过此格的路径。当然，如果开发者足够有把握，也能加入自动标注类似路径网格的算法。
与Dijkstra’s Algorithm比较
Dijkstra算法与A*算法十分类似：不过在Dijkstra算法中不用考虑H，所以该算法属于非启发式算法。它沿着外围各个方向逐步扩张搜索，所以通常Dijkstra在到达目标位置前会搜索大量的区域，故而比A*算法效率低。
那么什么情况下，我们更愿意选择Dijkstra算法呢？
设想一下你现在创建了一个采集资源的单位，它从它的位置开始搜索离它最近的资源，此时地图上有多个目标点，但它只想找到距离最近的点。此时，Dijkstra算法比A*算法表现更好，因为在使用A*算法时，搜索前我们无法固定一个启发式的值H，而只能通过循环的方式对于每一个资源都找到一条最短路径，最后再从中选取一条最短的路径，而这效率明显不高。