VisualGMQ的博客

游戏开发中的寻路（一）

 Game Development  2955  6   

本文说明了游戏开发中的寻路算法。从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为负数的节点。

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

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

具体的算法是：

  1. 遍历当前点$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$放入优先队列中
  2. 重复上述步骤直到优先队列为空

他的核心思路就是用优先队列替换原来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寻路的区别为：

  1. 使用优先队列而不是普通队列
  2. 不需要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没区别。

  1. A算法简介 --- Introduction to the A Algorithm 

  2. 彻底搞懂 Dijkstra 最短路径算法_哔哩哔哩_bilibili 

  3. std::make_heap - cppreference.com 

updatedupdated2026-08-082026-08-08