分层A*寻路算法：大型地图高效寻路解决方案

分层A*寻路算法：大型地图高效寻路解决方案

导读：在电子游戏开发中，高效的寻路算法是实现智能NPC行为的关键。本文将介绍一种适用于大型地图的高效寻路算法——分层A寻路算法（HPA），它通过将地图划分为多个区域并在各个区域之间建立过渡点的方式，实现了寻路效率的大幅提升。

一、前言

经典的寻路算法A寻路被广泛用于电子游戏中，虽然其搜索出来的路径通常被认为是最优的，但是当地图是复杂的大型地图时，A寻路却面临搜寻效率低下的问题。对此，分层A寻路（HPA）应运而生。HPA*通过将地图划分为多个区域并在各个区域之间建立过渡点的方式实现高效的寻路。

二、比较

HAP在面临复杂的大地图时其寻路效率相比A有大幅的提升，但这并不是没有代价的。HAP搜索出的路径相比A其优度会有所降低，此外，由于HPA需要对地图进行划分并存储之间的联系，故而会需要进行预处理并且占用更多的内存。因此，HAP与A*相比会具有以下优点：

1. 面对复杂的大型地图时搜寻速度有大幅提升；
2. 无需等待路径被完全搜索出来在行动（即可以边走边找）。

同时具有以下缺点：

1. 需要对地图进行预处理；
2. 会占用更多的内存；
3. 实现起来更复杂；
4. 路径优度有所降低；
5. 地图更新时需要更多的处理。

三、实现

（一）、预处理

要进行分层A*寻路首先需要对地图进行分层。

图1.

100x100的地图，以10x10为一个簇被分为10x10个簇。其中绿色表示起点，红色表示终点，黑色表示无法通行的障碍物，紫色表示过渡点，蓝色线条为外部链接，棕色线条为内部链接。

以图1中的地图为例，我们将其中相邻的10x10个地图视为一个簇（cluster），从而构建了一个新的10x10的抽象地图。但是新的抽象地图中相邻单元的联系并不像原始地图中那般简单，为此，我们特地定义入口（entrance）e是符合以下条件的路径单元：

1. 边界限制条件：e位于两个簇的交接处且不会位于地图的边界处。
2. 对称条件：若t∈e，则有symm(t)∈e。其中symm(t)表示相邻簇中与t相邻的路径单元。
3. 无障碍条件：e不包含障碍物。
4. 最大值条件：只要以上条件符合，则入口会在两个方向上延伸。

有了入口的定义，则可以在入口中找出一个或两个过渡点（transitions)。如果入口宽度小于指定值，则取入口的终点为过渡点，反之取入口的两端为过渡点，此实例中该值为6。

之后，需要在同一簇内的过渡点建立内部链接，在相邻簇中的相邻过渡点建立外部链接（见图1）。链接即为从某一过渡点到另一过渡点的路径，这一路径可通过A*算法（或其他方式）得出。路径的花费需要被储存，路径本身也可以选择是否储存。若是，则可使得后续寻路更加高效，但会占用更多内存。示例代码中储存了这些路径。

（二）、搜索路径

预处理完毕后即可实时的搜索路径。要搜索给定起点到给定终点的路径，首先需要将起点与起点所在簇的所有过渡点建立链接，终点也做同样的处理。这样，起点与终点就和由簇组成的抽象地图建立了链接。然后通过在已经构建了的链接中使用A*算法（或其他方式）找到由起点通向终点的抽象路径。

抽象路径应当是由起点、终点和过渡点构成的，然后通过搜索各过渡点间的具体路径就可以得到起点至终点的实际路径。

最终搜索出的路径可能不是最优的，因此如果对路径有更高的要求可以通过其他方式进一步地优化路径。

（三）、更多的层次划分

图2.

将相邻的2x2一级簇组合为一个二级簇，进一步得到一个由5x5的二级簇构成的抽象地图。其中紫色路径单元为二级簇的过渡点。

可以通过将相邻的一级簇组合成一个二级簇，来进一步划分地图。二级簇中的过渡点的建立与一级簇中的相同，不同的是簇与簇之间的链接不是具体的路径，而是由一级簇中的过渡点构成的抽象路径。

要将起点与二级簇相链接，需相将起点与一级簇链接，在通过一级簇的过渡点与二级簇的各个过渡点建立抽象的链接。终点相同。

搜索路径时首先搜索出二级抽象地图上的抽象路径，再进一步获取一级抽象地图上的抽象路径，最后获取具体地图上的具体路径。同理可以推出更多层次划分的步骤。

（四）、更新地图

当地图发生更新时，抽象地图中的过渡点也应进行更新。假设更新的区域可以被一个最小的矩形区域包围，该矩形区域用其左上角和右下角表示为（（x，y），（z，w））。则所有与（（x-1，y-1），（z+1，w+1））（对于任意超过地图边界的值，取距离该值最近的边界）矩形相交的簇是应当被更新的。之所以要扩大矩形是因为过渡点具有对称性，如果更新的区域导致一个簇的过渡点发生变化，则与其相邻的外部过渡点也应当被更新。

以上更新原则应当被应用于所有抽象层级。各个过渡点之间的链接也应当要更新。

四、实例代码

示例代码网址：https://github.com/sea-sky-coder/HPAStar-In-Unity

五、参考文献

Adi Botea，Martin M¨uller，Jonathan Schaeffer —— 《Near Optimal Hierarchical Path-Finding》