游戏开发中的寻路（一）

本文说明了游戏开发中的寻路算法。从BFS到Dijkstra到A*以及A*的变体等。

大部分参考这篇由浅入深的文章^[1]

BFS

寻路算法大部分都是从图论算法中发展而来。其中最简单的就是BFS。这也是在学习寻路算法时最先遇到的算法。

BFS的优点：

写法简单
给定起点，可以同时算得图中所有点到起点的最短路径

缺点：

性能不够好。要遍历整个图中所有的点O(mn)
只能在无权图中生效。这包含两个条件：
- 任意格子到相邻格子的耗时必须一样（一般都记为1）
- 对于Tilemap这种格子都是方的来说，只能四向移动不能八向移动（因为斜角的格子耗时是$\sqrt{2}$倍，导致含有额外权重）

这些缺点导致BFS的应用场景极少。但BFS是所有寻路算法的基石。其他算法都是从BFS上扩展出来的。

我们都知道，BFS其实是通用的图搜索算法，具体用这个算法做什么是看具体场景。所以我们有一个通用BFS实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
template <typename T>
void BFS(const Graph<T>& graph, std::queue<T*>& queue, std::function do_something_with_node) {
    while (!queue.empty()) {
        const T* node = queue.front();
        for (Graph::Node* nearby_node : graph.GetNearbyNodes(value)) {
            if (nearby_node->m_visited) {
                continue;
            }
            nearby_node->m_visited = true;
            do_something_with_node(nearby_node, ...);	// do something here
            queue.push_back(nearby_node);
        }
        queue.pop();   
    }
}

这就是纯粹的BFS的实现逻辑：通过将某个节点的临近节点推入队列中来实现。已经推入过的节点要标记其被访问了（m_visited = true）以防止其某个邻居节点再次将其推入造成死循环。

这里一般会在do_something_with_node(node)里对当前弹出的node做一些操作。

而对于寻路算法，do_something_with_node的实现是直接将当前节点指向其父节点：

1
2
3
4
5
6
void do_something_with_node(Graph::Node* nearby_node, Graph::Node* parent) {
    nearby_node->m_parent = parent;
}

// 在BFS中具体的调用为：
do_something_with_node(nearby_node, node);

显然，随着BFS的“洪水”逐渐淹没整个图，所有的节点都会有自己的父节点。父节点则是洪水淹过来时的方向。

下面是一个 BFS 寻路的交互式演示，你可以左键格子设置起点/终点，右键设置墙壁，然后逐步观察 BFS 的扩散过程：

Dijkstra算法

BFS只能处理无权图。带有权重的图需要使用Dijkstra算法处理。

具体可看参考^[2]，很直观。

Dijkstra的唯一缺点是不能处理Cost为负数的节点（可使用Bellman-Ford算法进行处理）。

Dijkstra算法本质是贪心算法，其在BFS上进行扩展，使用优先队列而不是普通队列。优先队列每次弹出的是到起点路径最短的节点。

所有节点记录自己到起点的Cost。所有节点初始的Cost为$+\infty$，只有起点$S$的Cost是0。

具体的算法是：

遍历当前点$A$周围的4（或者8）个点$B_i$，计算他们到起点的$Cost_i = Cost_{S\rightarrow A} + Cost_{A \rightarrow B_i}$，如果$Cost_i$比当前$B_i$的Cost小，那么更新$Cost_{B_i} = Cost_i$并将$B_i$的父节点指向$A$，然后将$B_i$放入优先队列中
重复上述步骤直到优先队列为空

他的核心思路就是用优先队列替换原来BFS的普通队列，以贪心的方式每次都找到最近的路径。如果新路径比旧路径更短就用新路径替换旧路径。

伪代码（只展示思路不是最优内存）为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
template <typename T>
struct PQEntry {
    float m_cost{};	// 离起点的Cost
    Graph<T>::Node* m_node{};
    
    bool operator<(const PQEntry& o) const { return m_cost < o.m_cost; }
};

using PriorityQueue = std::priority_queue<PQEntry, std::geater>;	 // 按离起点Cost最短排序

template <typename T>
void Dijkstra(const Graph<T>& graph,
         const std::unordered_map<Graph<T>::Node*, PQEntry>& entries,  // 所有节点和对应PQEntry的信息
         PriorityQueue<PQEntry>& queue) {
    while (!queue.empty()) {
        PQEntry& data = queue.front();
        for (auto& nearby_node : data.m_node->GetNearbys()) {
            float cost = nearby_node->GetCost(); // 从相邻节点走到这个节点的Cost
            float totle_cost = data.m_cost + cost; // 从起点走到当前节点的Cost
            PQEntry& nearby_node_pq_entry = entries[nearby_node];
            // 判断是否cost更少一些？
            if (totle_cost < nearby_node_pq_entry.GetCost()) {
                nearby_node_pq_entry.SetCost(totle_cost);
                // 只要找到更新的路径就放入优先队列
                queue.push(nearby_node_pq_entry);
            }
        }
        queue.pop();
    }
}

这里和BFS寻路的区别为：

使用优先队列而不是普通队列
不需要m_visited，使用cost比较替代了m_visited的功能

下面是一个 Dijkstra 寻路的交互式演示，地图上有三种不同 Cost 的地形（颜色越深 Cost 越高），你可以观察 Dijkstra 如何优先探索低 Cost 区域：

斜角穿墙的处理

如果Dijkstra存在8方向寻路，那么可能存在斜角穿墙的问题:

穿墙问题处理

解决方法是在计算cost的时候看一下是不是正在斜着走。如果是，看一下旁边有没有墙，如果有墙就标记斜着走的这个块的Cost为$+\infty$。这样Dijkstra可以从旁边绕过去（或者两边都有墙就不从这里走，此路不通了）：

穿墙问题处理

使用Heap代替PriorityQueue

在Dijkstra算法中，可能存在同一个节点压入两次queue中：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
下面A~I都是空白的寻路地面，以3x3方式排列
ABC
DEF
GHI
假设现在Queue里面是E：
1. 弹出E
2. 找到E周围的8格
    1. 假设先找到C。更新C的Cost然后压入Queue
    2. 然后找到B，一样压入Queue
    3. 其他节点依次操作
3. 弹出C。找C周围的8格。这个时候又找到B，并且E->C->B的Cost比E->B的Cost小，那么要更新B的Cost再压入Queue
    
此时Queue里面就有两个B，重复
 

如果想要去重，可以考虑使用Heap数据结构。

C++本身提供Heap的支持，但比较小众，我放在参考^[3]了。

注意：去重并不是理论上必做的事情。因为后压入的节点的Cost一定比之前的小，所以即使弹出之前的节点他也不会更新任何Cost，相当于没做事情。去重只是为了防止又找一遍老节点的nearby节点。

提前退出

Dijkstra是从BFS上扩展而来。BFS会找到图中所有点到起点的最短路径。Dijkstra也是如此。

但在游戏开发中，我们经常只需要找到单点的最短路径。在使用Dijkstra时，如果已经找到目标点的最短路径，那么直接终止算法即可。这就是提前退出。

注意和BFS的提前退出条件不一样：

BFS：当发现某个点的邻居为目标点时就可以直接退出了（此时算法会设置目标点的父，然后直接退出，目标点不用压入队列）
Dijkstra：当从queue中弹出的点为目标点时可直接退出（也就是说目标点压入过队列）

贪婪最佳优先搜索

对于单源最短路径。我们希望能尽可能地朝向目标点搜索以减少其他不必要的搜索。这时，我们可以给Dijkstra算法一个启发式函数(Heuristic Function)，这个启发式函数告诉Dijkstra当前搜索的点离目标点有多近。在Tilemap地图上可以使用曼哈顿距离：

1
2
3
float HeuristicFn(Vec2I current_position, Vec2I target_position) {
    return std::abs(target_position.x - current_position.x) + std::abs(target_position.y - current_position.y);
}

然后将此启发函数的返回值作为节点的Cost，堆/优先队列每次弹出的是Cost最小的那个。

这样就等于告诉Dijkstra：永远朝着距离目标最近的点进行贪婪搜索。

但这种算法不一定能找到真的最短路径。但优点就是快。

下面是一个贪婪最佳优先搜索的演示：

下面是一个反例，此时无法找到最短的路径：

A*算法

在基于贪婪最佳优先搜索的Dijkstra算法的基础上，通过修改启发式函数，我们可以直接得到A*算法。

A*算法的启发式函数由三部分组成：

g：当前节点到起点的确定Cost（即初始Dijkstra算法中的Cost）
h(heuristic)：当前节点到终点的启发式搜索算法（一般是到终点的曼哈顿距离）
f：$f = g + h$是节点的总Cost，我们最后使用的Cost就是f

当$h$总是0时，A*退回到Dijkstra算法。

当$g$总是0是，A*退回到基于贪婪最佳优先搜索的Dijkstra算法。

编码过程和Dijkstra没区别。

差分启发式算法（ALT）

可参考^[4]。

又称ATL(A* Landmark Triangle inequality)。通过选取更好的启发式函数来优化A*。

传统的曼哈顿距离启发函数有一个问题。如果起点在胡同里，终点则在墙对面（就比如上面说的贪婪最佳优先搜索的反例）。这个时候，曼哈顿距离启发函数会让A*优先搜索离终点近的点（也就是先往墙那边搜索），这样会导致很多无效搜索。

而ATL可以一定程度上解决这个问题。主要步骤为：

在地图上预先标上点$L_i$
使用Dijkstra或其他算法，构建网格上所有点到$L_i$的最短距离（不需要记路径，$i$个点有$i$份数据）
启发式函数的返回值是，对当前节点$n$和目标$goal$,$h(n, goal) = \max(dist_{L_i \rightarrow n} - dist_{L_i \rightarrow goal})$

这个算法直观的理解是，地标$L_i$是一个辅助算法判断搜索方向的东西。就好比你让朋友去天安门旁边的某个景点，你可以和他说先到天安门（或者往天安门的方向走），然后在天安门附近再找一样。这样就避免了曼哈顿距离带来的问题。

这里启发式函数的推导由三角不等式得到：

对于当前点$n$，地标$L$和终点$E$。这三者可以构成一个三角形。由三角不等式可得：

$$ \begin{aligned} & |LE| \le |nL| + |nE| \Rightarrow \\ & |LE| - |Ln| \le |nE| \end{aligned} $$

也就是说当前点到终点的Cost，最低最低都是地标到终点的距离减去地标到当前点距离。那么我们就可以用这个保底作为启发式函数的返回值，以便于A*沿着这个路径走。

那么当有多个地标$L_i$时，显然要计算他们之中的最大值作为保底。

而$|LE|$和$|Ln|$可从预构建的地图上所有点到$L$的最短距离的数据中获得。

最远点采样算法

地标可以自己手动标识。但也有自动化标定方法。

最远点采样法就是这样：

随机选取第一个地标$L_1$（一般在地图边缘选取，以保证$L_1$本身的效果足够好）
找到距离$L_1$最远的点作为第二个地标$L_2$（可用Dijkstra算法找到）
找到距离$L_1, L_2$最远点作为第三个地标$L_3$
其他地标总是找到距离之前地标最远的点

那么如何找到距离前$i$个地标最远的点呢？

定义$minDist(n) = \min(dist(n, L_i))$为某个点$n$到所有地标的最近点。那么距离所有地标的最远点定义就是

$$ \max(minDist(n)) $$

也就是距离所有地标最近距离都是最大的那一个点。

算法步骤为：

遍历图中每一个点$n_i$，计算$minDist_i = \min(dist(n_i, L_i))$，然后找$\max(minDist_i)$所在的那个点就是最远点了

这是游戏开发中常用的自动选点算法，高效效果又好。原始论文⁴不是用这个算法，感兴趣可以自己看。

流场寻路算法（Flow Field）

其实就是利用Dijkstra算法算出的结果进行多人寻路。

流场算法要处理的问题是：给定终点，让地图上多个移动物体向终点寻路。

如果使用A*的话，需要为每个移动物体都计算一次寻路，物体多了就慢。而Flow Field算法只是先用Dijkstra算出地图上所有点到终点的最短路径然后使用而已。

跳点算法JPS（Jumping Point Search）

这篇文章^[5]说的很好，我这里只简单说一下。

A*基于BFS。但在搜索路径时，两点之间的最短路径可能有很多条，而且这些路径都是等价的。由于A*基于BFS的特性，他有可能将这些等价路径都搜索到。这就浪费了时间。

JPS就是尽量减少对等价路径的搜索。

JPS要求网格是均匀的，即：

同类方向代价一致

就是上下左右四方向的所有格子Cost都一致。斜角的四个方向所有格子Cost一致。但是这两类之间的Cost不需要一样。

所以JPS可以处理斜着走的问题。即使斜走的Cost是横着走的$\sqrt{2}$倍。

在均匀网格中JPS的性能比A*快非常非常多，开有大量开阔地带的地图尤其如此（听说有10~40倍的差距）。一般用在有多个房间或者大量空地，空地之间由走廊连起来的地图。对于那种紧凑的迷宫型地图性能没有那么好。

动态地图寻路

当地图改变时（增加/删除了节点，或者节点Cost改变）原有的路径可能会失效，此时必须更新路径。

对于A*来说大部分游戏就是直接重算。但也有其他方法：

惰性A*重算

不是在地图改变时重算。而是当走到被堵住的地方时才重算。这种算法需要在人物移动的时候每帧检查下一个移动到的节点处是否被物体遮挡。如果遮挡了就以当前点为起点重算A*。

这种方法的缺点是，有些时候堵住的是关键路径（比如人物要进入城堡，城堡有两个离得很远的入口$A,B$。此次寻路路径从$A$口进入。人物走到一半时$A$口被堵住了。此时人物不知情仍旧往$A$口走，直到走到$A$口发现被堵住才触发重算）。这个时候可以在非寻路层做一些操作（比如标识关键阻塞点，当这些点被阻塞就立刻通知需要的人进行重算）

HPA*

原论文名是"Near Optimal Hierarchical Path-Finding"。一个较好的教程是^[6]，此教程不仅说明了HPA*，也说明了Annotated A*算法。

从论文名称可以直到这个算法的特点：

近似最优：不总是能找到最优解
分层：将地图分成多块进行搜索

这个算法主要是非常快速。

D与LPA

只是简单介绍一下，一般不会在游戏中使用。D*和LPA*可以使用现有的A*算法的数据，当地图改变时动态地计算新道路。

一般不会在游戏中使用。这两个算法是给机器人用的。机器人面对的都是未知地图，其不停地移动，感知新地图细节。等价于运行时生成新地图信息了。而游戏中地图一般都是静态的，只有很少数的改变（比如开门，关门等）。使用D*和LPA*往往受益并不高。

只有在那种超大地图，寻路很多并且地形不断变化的游戏中需要（比如FPS游戏，里面很多炮火可以导致地形变形等）。

和物体大小相关的寻路

A*只能告诉我们两个点之间的最短路径。但他不能告诉我们物体是否真的能走过这条路（比如寻路需要通过一条狭窄走廊，但大物体根本挤不进去）。

这时就可以用Annotated A*算法。其本质是预先在地图上标记不同尺寸的物体能走过的路径，然后将这些信息传给A*。

此文章⁶说的很详细了，不再赘述。

游戏开发中的寻路（一）

相关文章：