相关项目 repo 地址： https://github.com/hit9/quadtree-pathfinding。
主体思路 ¶
我们知道，在一个 2D 网格上进行 A* 寻路的话，需要把网格建模成双向有向图，然后对这个图应用 A* 算法。 如果网格比较大，是比较费时的，所以我开始考虑如何优化。
注：我曾写了一个小项目，用来可视化几种常见的寻路算法 https://github.com/hit9/path-finding-visualizer 。
A* 算法的主要优化点之一是：减少下一步扫描的邻居节点的数量，也就是常说的 open_set （也有的叫 open_list）。我觉得关键还是要把扫描到的点的数量降低下去。
由于前面学习了 四叉树 的知识点，我有一个有趣的思路：
- 把整个 2D 网格用四叉树进行划分，划分的条件是，每个小矩形要么不包含障碍物、要么只包含障碍物。
- 对于不包含障碍物的小矩形，其中任意两点直线最短。
- 对于小矩形之间，建立连接的出入口关卡 (gate) 进行连接，所有的关卡构成一个有向图。
其中，所谓「小矩形」就是四叉树的叶子节点。
这样，一张 2D 网格地图的建模情况如下图所示，其中：
- 整个网格被四叉树不断分割，红色的是障碍物。每个四叉树叶子节点中要么全是障碍物、要么全不是障碍物。
- 两个相邻的叶子节点之间，会选取一些紧邻的点，作为关卡，在图中就是紫色的方格。
那么，在寻路的时候，主体思路十分简单：
- 先把起始点和终点加入到关卡的有向图中。
- 然后对所有关卡的单元格组成的有向图进行 A* 寻路。
- 最后填充小矩形内的直线。
这里面有两步：先找关卡路由点、最后再填充细节路径点。
下图中，我们加入起点 Start 和 目标 Target 后，A* 算法可以找出来所有路过的关卡点：
最后，由于任何两个关卡点之间的最短路径一定是直线，只需要直接相连就可以了：
连直线的算法，直接采用著名的 Bresenham 算法，测试下来这一步速度非常快。 此外，推荐一个网页，对于 Bresenham 算法 有很简洁的实现：https://members.chello.at/easyfilter/bresenham.html。
这样的思路下：
- 路径不再是最优，但是接近最优。
- 寻路分为了两层：先在 Gate 层寻路，最后再填充节点内的路径。
可以看到，在第一层寻路的时候，参与寻路的点，最多只是所有紫色的关卡，而其余白色的区域，是不参与寻路的。这也就是优化点。 而画直线是非常非常快的，是一个线性时间复杂度的过程。
进一步优化 ¶
事实上，还可以进一步优化，代价就是进一步牺牲最优性。
我又加入了一层抽象图，作为一种可选的过程，可以先对所有四叉树节点进行寻路。展开来说：
- 相邻的四叉树叶子节点之间建立有向边，取各自的中心作为代表。
- 寻路时，先在节点构成的图上寻路，得到一条有效的 NodePath .
- 然后再挑选 NodePath 上可能涉及的关卡，再进行关卡层的寻路 。
- 最后填充关卡之间的直线。
因为空旷节点的数量，相比关卡的数量，要少的多，所以会更快。
另外，加入这一层之后，还有两个好处：
- 更快的判断可达性。
- 第二层参与寻路的关卡大大减少。
下图中，黄色的是第一层节点图中的寻路结果：
在实际实现中，这一步是可选的。 测试下来，带有节点层寻路优化的情况下，对于比较大的地图，速度还可以。
值得说明的是，在实际的实现中，都是支持动态新增和删除障碍物的。 这根本上源自我做的那个 quadtree 带来的支持。动态新增或删除障碍物会增量化地更新四叉树， 而寻路这里已经订阅了叶子节点的动态变化情况，进而增量化的修改节点和关卡这两层抽象的有向图的结构。
带大小的寻路智能体 ¶
实际寻路中，通常会有几种不同大小的智能体，而我们之前讨论的都是假定 1x1 大小的 agent 进行寻路。
对我帮助很大的一篇文章是这个（原文已经不见，但是 web archive 上还有）：Clearance-based Pathfinding and Hierarchical Annotated A* Search。 这篇文章中介绍了一种 Clearance-based 的寻路方法，也讨论了一些不同地形的支持。
所谓 Clearance-based 的方法，就是要计算一个「最小障碍物距离」的场，通俗地说，就是做一个 2D 数组，这个数组中的每一项是一个数字，表示距离它最近的障碍物的距离。 文章中也说了，常用的是一种叫做 brushfire 的算法，但是它并非真正的 clearance，存在反例。作者介绍了一种新的所谓 “true-clearance” 的思路，我对这个方法做了改进实现。
主要的改进点是，支持地形的动态变化。就好比游戏中，我们建造一个房屋建筑的时候，会影响寻路的地图。
在 github 上我写了一个很小的项目: https://github.com/hit9/true-clearance-field。
比如说下图中，参与寻路的智能体大小是 2x2 的，始终以智能体的左上角单元格作为其位置，所谓 “true-clearance” 就是说一个单元格距离右下方的最近的障碍物的距离。 下图中的红色的是障碍物，方格中的数字就是要计算的 “true-clearance” 的值。
下图是一个动态维护的示意图，一个细节是，寻路的智能体的大小通常会有一个上限，并不会太大。所以这个最小障碍物距离的场的维护是有限传播的。 也就是说，修改一个地形后，并不会刷新全局，而是只会刷新附近的有限区域。
细节上，实现这个 true-clearance-field 算法是参考了 LPA* 算法， 这是一种在起点和终点不变的情况下，可以在地形变化时增量计算 A* 寻路的算法。
回到我们的四叉树寻路上来，有了这个「最小障碍物距离场」的支持，那么 任何一个带有大小的智能体寻路问题，其实都可以等效为一个 1x1 大小智能体寻路的问题。 因为，对于大小为 S 的智能体而言，如果一个方格的 true-clearance 的值是小于 S 的，代表这个方格是不可通过的。那么就相当于这里是一个「障碍物」。 所以，问题如此简化：
- 四叉树优化的寻路算法，只专注解决
1x1大小的智能体寻路问题。保持简单。 - 通过
true-clearance场，把多规格大小的智能体寻路问题，简化到1x1规格的问题上去。
如此简化的代价就是，我们需要对每一种会用到的智能体规格，都建一张四叉树地图与之对应。 这样的缺点有：
- 内存占用会更高。
- 维护地形的时候，需要把每一张四叉树地形都维护一遍。
我想了很多其他思路，但是都非常复杂。最终我还是选择了这样的方式，也就是保持基础算法的简单。
不同的地形 ¶
对于不同的地形，处理上如法炮制，但是会相对简单一些。
因为智能体可行走的地形类型不同，不能行走的地形全部视作障碍物，简化到 0 或 1 二值地形（也就是只有障碍物和非障碍物）的基础寻路模型上去。
思路仍然是，对于可能出现的地形，建立与之对应的四叉树地图。
- 下图分别是单元格大小是
10x10，智能体大小是20x20，可行走区域是 白色的陆地 的寻路情况：
- 下图分别是单元格大小是
10x10，智能体大小是20x20，可行走区域是 白色的陆地 和 蓝色的水 的寻路情况：
优化其实并没有多少，好在实际中和寻路相干的地形分类的并没有那么复杂，吧~。
代码实现中，每一种地形用一个 2 的幂来表示，就是说不同的比特位标识不同的地形。然后用比特的 OR 或操作来表示选用多种地形。
enum Terrain {
Land = 0b001, // 1
Water = 0b010, // 2
Building = 0b100, // 4
};
qdpf::QuadtreeMapXSettings settings{
{10, Terrain::Land}, // e.g. soldiers
{20, Terrain::Land}, // e.g. tanks
{10, Terrain::Land | Terrain::Water}, // e.g. seals
{20, Terrain::Water}, // e.g. boats
};
综合两种因素 ¶
综合「大小」和「地形」两种因素：
- 对于地形因素来说，每种地形组合内，不论智能体的大小，可以共享一张 true-clearance 场。
- 对于智能体规格因素来说，每种 { 规格 + 地形 } 的组合，都要对应一张四叉树地图。
每一张距离场关于「障碍物」的定义都与它所支持的地形有关，比如说：
true_clearance_fields[Land] => true_clearance_field1
此时这个 true_clearance_field1 内陆地是可行走的，但是 Water 区域算作障碍物。
对于四叉树地图也是类似的，比如说：
quadtree_maps[3][Land | Water] => quadtree_map1
此时这个 quadtree_map1 内陆地和水的区域都是可行走的，障碍物只有 Building 一种，而且 clearance 值小于 3 的区域也会算作障碍物。
对于同一种对地形组合，一张距离场和一批不同智能体规格的四叉树地图对于「障碍物」的理解是一致的。 当地形变化时，距离场会带动这一批四叉树地图的更新，具体来说是：
- 首先更新每一张距离场，更新变化区域的 clearance 值。
- 对于距离场传播到的附近区域，触发相应的一批四叉树的维护。
- 四叉树维护进一步带动关卡图和节点图的维护。
反过来，如果地形的变化，不会影响到距离场关于障碍物的理解，那么 clearance 值就不会变化。此时也不应该、也不会影响到相关的四叉树地图的更新。
遗留问题 ¶
目前有一些遗留问题：
- 路径看起来有的时候有点奇怪。
- 如何实现动态权重 A* （这一步主要是测试下来并没有太大优化效果）。
- 如何用四叉树的好处支持流场寻路？
- 实际上，跨节点的空白区域还是有的（但是这个优化起来可能会打破设计的基本思路、引入复杂点）。
- 既然 A* 已经支持了，那么 LPA* 增量寻路也可以看一下是否可以支持。
最后，欢迎给 star ： https://github.com/hit9/quadtree-pathfinding
本文原始链接地址： https://writings.sh/post/pathfinding-quadtree-astar
