C++实现DFS迷宫寻路算法：从原理到游戏开发实践-三亩地-编程学习日记

1. 项目概述：当游戏角色自己“想”走路

做游戏，尤其是那种有地图、有障碍物的游戏，比如经典的RPG、战棋或者迷宫探险，一个绕不开的核心功能就是“自动寻路”。你点一下地图上的某个位置，你的角色就得自己绕过树木、墙壁、河流，找到一条最短（或至少是可达）的路走过去。这个功能看似简单，背后却是一整套算法的智慧。对于刚接触游戏开发或者算法的新手来说，可能会觉得头大：地图数据怎么存？障碍物怎么判断？路径怎么找？

别担心，我们今天就来拆解这个“黑盒子”，而且是用一种对新手极其友好的算法——深度优先搜索（DFS）。你可能会在算法书里看到DFS被描述成“一条路走到黑，撞了南墙再回头”，听起来有点笨，但在游戏开发的某些场景下，它恰恰是理解寻路原理、进行快速原型开发的最佳入门选择。我们将完全使用C++来实现，从零开始，一步步构建一个可运行的、带可视化反馈的迷宫自动寻路Demo。你会发现，那些看似高深的游戏AI，起点可能就是这么清晰直白。

2. 核心思路：为什么选择DFS作为寻路算法的起点？

在实现之前，我们得先搞清楚为什么从DFS开始。寻路算法家族很庞大，比如大名鼎鼎的A*（A-Star）算法，效率高，是商业游戏中的主流；还有广度优先搜索（BFS），能找到最短路径。那为什么我们偏偏挑中了DFS呢？

2.1 DFS的算法思想与游戏寻路的直观映射

DFS的核心思想是“深度优先”。想象一下你在玩一个真实的迷宫，策略是：选择一条岔路一直走下去，直到死胡同，然后退回上一个岔路口，尝试另一条没走过的路。这个“尝试-深入-回溯”的过程，就是DFS。

在二维网格地图（这是游戏中最常用的地图表示方式之一）中，这个映射非常直观：

“当前位置”：就是你的游戏角色所在的格子。
“岔路”：就是当前格子上、下、左、右四个（或八个，包括斜角）可以行走的相邻格子。
“死胡同”：就是当前格子的所有相邻格子要么是墙（障碍），要么都已经被访问过。
“回溯”：当走到死胡同时，退回到上一个格子，看看还有没有其他路可走。

这种思想非常符合人类在未知环境中探索的直觉，也使得DFS的代码逻辑相对简单、清晰，易于理解和实现。对于新手来说，先掌握这种“笨办法”，能打下坚实的递归和回溯思维基础。

2.2 DFS在游戏开发中的适用场景与局限

当然，DFS不是万能的。理解它的适用场景和局限，比学会写代码更重要。

适用场景：
1. 地图探索与迷雾系统：在需要探索整个地图所有可达区域的场景下，DFS是一种自然的选择。它可以系统地访问每一个连通的可走格子，非常适合用来实现战争迷雾的揭开逻辑。
2. 解谜游戏与路径存在性判断：在一些谜题游戏中，玩家或AI只需要判断“从A点能否到达B点”，而不关心具体路径长短。DFS完全胜任，且实现简单。
3. 快速原型与算法教学：当你需要验证游戏地图逻辑、或者向团队解释寻路的基本概念时，一个DFS寻路demo是最快上手的工具。
主要局限：
1. 路径非最优：DFS找到的路径，很可能是绕远的，因为它不保证找到的是最短路径。它找到的只是“一条”路径，而且这条路径的特性严重依赖于搜索时选择邻居的顺序（比如先向上还是先向右）。
2. 性能问题：在最坏情况下（比如一个大而空的迷宫），DFS可能会探索所有可能的路径，导致时间复杂度很高。如果地图很大且没有障碍，它可能像没头苍蝇一样乱转很久才找到目标。

注意：正因为这些局限，在大型、对性能要求高的实时游戏中，DFS很少作为主力寻路算法。但它是学习A等更高级算法不可或缺的阶梯。A算法可以看作是结合了BFS（保证找到最短路径）和启发式搜索（提高效率）的升级版，而DFS和BFS正是其两大理论基础。

2.3 方案设计：我们将构建一个什么样的Demo？

为了让学习过程有成就感，我们将构建一个控制台版本的迷宫自动寻路程序。它包含以下功能：

地图表示：用一个二维字符数组来表示迷宫，比如‘#’代表墙（不可走），‘.’代表路（可走），‘S’代表起点，‘E’代表终点。
手动模式：可以先用键盘（如WASD）控制一个符号在迷宫中移动，感受一下地图。
自动模式：核心功能。启动后，程序使用DFS算法自动寻找从‘S’到‘E’的路径。
路径可视化：寻路成功后，在地图上用特殊的标记（比如‘*’）显示出找到的路径。
回溯过程可视化（可选进阶）：可以清晰地看到算法“尝试-回溯”的过程，这对理解DFS至关重要。

这个Demo将完全使用标准C++实现，不依赖任何图形库，确保环境配置最简单。我们将从最基础的地图数据结构和递归函数开始。

3. 从零开始：C++环境与项目基础搭建

在深入代码之前，确保有一个可用的C++开发环境。对于新手，我强烈推荐使用Visual Studio Code (VSCode)配合MinGW编译器，它轻量、免费且跨平台。

3.1 开发环境快速配置

如果你还没有环境，可以按以下步骤操作：

安装MinGW：去MinGW官网下载安装器，选择安装gcc和g++组件（用于编译C/C++代码）。安装后，将MinGW的bin目录（例如C:\MinGW\bin）添加到系统的PATH环境变量中。
安装VSCode：从官网下载安装。
安装VSCode插件：在扩展商店搜索并安装“C/C++”扩展（由Microsoft发布）。
验证安装：打开终端（VSCode里按Ctrl+），输入g++ --version`，如果显示版本信息，说明配置成功。

实操心得：环境配置是新手的第一道坎。如果遇到“microsoft visual c++ 14.0 or greater is required”这类错误，通常是因为你试图用Python的某些包（如pip install某些需要编译的库）而不是在编译C++。对于纯C++项目，MinGW的g++足够了。如果真需要MSVC，可以去Visual Studio官网下载“生成工具”而不是完整的IDE。

3.2 项目文件结构与基础代码框架

在你的工作目录下，我们创建一个简单的项目。主要就一个.cpp文件，比如dfs_maze.cpp。

我们先搭建一个最基础的框架，包含地图定义和打印函数：

#include <iostream> #include <vector> using namespace std; // 定义地图常量 const char WALL = '#'; const char PATH = '.'; const char START = 'S'; const char END = 'E'; const char VISITED = 'V'; // 访问过的标记 const char SOLUTION = '*'; // 最终路径标记 // 地图尺寸 const int ROWS = 10; const int COLS = 10; // 方向数组：上，右，下，左 (顺时针方向) // 分别对应行偏移和列偏移 const int DIRS[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 打印地图函数 void printMaze(const vector<vector<char>>& maze) { for (int i = 0; i < ROWS; ++i) { for (int j = 0; j < COLS; ++j) { cout << maze[i][j] << ' '; } cout << endl; } cout << "------------------------" << endl; } int main() { // 初始化一个10x10的迷宫地图 // 使用vector方便动态大小，这里我们先固定为ROWS x COLS vector<vector<char>> maze(ROWS, vector<char>(COLS, PATH)); // 先全部初始化为路 // 设置一些墙 // ... (这里先留空，后面我们会填充一个具体的迷宫) // 设置起点和终点 maze[1][1] = START; maze[8][8] = END; cout << "初始迷宫：" << endl; printMaze(maze); // 后续的寻路逻辑将在这里添加 // ... return 0; }

这段代码做了几件事：

用有意义的常量代替魔术数字（如‘#’），提高代码可读性和可维护性。
使用vector<vector<char>>表示二维地图，比原生二维数组更安全、灵活。
定义了方向数组DIRS，这是处理网格移动的经典技巧，能避免写四段重复的上下左右判断代码。
printMaze函数用于随时查看地图状态，这对调试至关重要。

3.3 设计一个用于测试的迷宫

让我们设计一个简单的迷宫，填充到main函数里：

// 在main函数内，初始化maze之后，设置起点终点之前，添加墙壁 // 设置外围一圈为墙 for (int i = 0; i < ROWS; ++i) { maze[i][0] = WALL; maze[i][COLS-1] = WALL; } for (int j = 0; j < COLS; ++j) { maze[0][j] = WALL; maze[ROWS-1][j] = WALL; } // 设置内部的一些墙，构造一个简单迷宫 maze[2][2] = WALL; maze[2][3] = WALL; maze[2][4] = WALL; maze[3][4] = WALL; maze[4][4] = WALL; maze[5][4] = WALL; maze[5][3] = WALL; maze[5][2] = WALL; maze[6][2] = WALL; maze[7][2] = WALL; maze[7][3] = WALL; maze[7][4] = WALL; maze[7][5] = WALL; maze[7][6] = WALL; maze[3][6] = WALL; maze[4][6] = WALL; maze[5][6] = WALL; maze[6][6] = WALL; // 设置起点和终点 maze[1][1] = START; maze[8][8] = END;

编译并运行这个程序，你应该能在控制台看到一个有边框和内部障碍的迷宫，起点在左上区域，终点在右下区域。这就为我们后续的寻路准备好了舞台。

4. DFS寻路算法的核心实现与逐行解析

现在进入最核心的部分：实现DFS算法。我们将采用递归的方式，这是实现DFS最直观、最简洁的方法。

4.1 递归函数的定义与参数设计

递归函数dfs需要知道：当前在哪（坐标），要去哪（终点坐标），当前的地图状态，以及最重要的——如何记录走过的路径。

// DFS递归寻路函数 // 参数：当前坐标 (x, y)， 迷宫地图的引用， 终点坐标 (endX, endY) // 返回值：bool类型，表示从当前点是否能找到一条到达终点的路径 bool dfs(int x, int y, vector<vector<char>>& maze, int endX, int endY) { // 1. 边界检查与障碍检查：如果当前位置是墙或者已经访问过，则此路不通 if (x < 0 || x >= ROWS || y < 0 || y >= COLS || maze[x][y] == WALL || maze[x][y] == VISITED) { return false; } // 2. 终止条件：如果已经到达终点，则成功找到一条路径 if (x == endX && y == endY) { maze[x][y] = SOLUTION; // 将终点标记为路径的一部分 return true; } // 3. 标记当前节点为已访问，防止重复访问陷入循环 // 注意：起点‘S’需要特殊处理，我们不应该覆盖它 if (maze[x][y] != START) { maze[x][y] = VISITED; } // 可选：打印当前状态，观察搜索过程（调试用） // system("cls"); // Windows清屏，Linux/Mac用 system("clear"); // printMaze(maze); // this_thread::sleep_for(chrono::milliseconds(100)); // 需要#include <thread>和<chrono> // 4. 递归探索四个方向 for (int i = 0; i < 4; ++i) { int nextX = x + DIRS[i][0]; int nextY = y + DIRS[i][1]; // 如果从这个方向能走到终点 if (dfs(nextX, nextY, maze, endX, endY)) { // 回溯成功！将当前点也标记为解决方案路径的一部分 if (maze[x][y] != START) { // 起点保持‘S’ maze[x][y] = SOLUTION; } return true; // 向上层传递成功信号 } } // 5. 如果四个方向都走不通，则回溯 // 注意：这里我们通常不“取消访问标记”（即从VISITED改回PATH）， // 因为对于判断路径存在性，一个点走不通，以后任何路径再走到这个点也还是走不通。 // 这可以避免无限递归，大幅提升效率。这被称为“记忆化”或“剪枝”。 // 但如果需要找出所有可能路径，则需要取消标记。 return false; }

4.2 算法步骤的深度解读

让我们拆解上面这个关键的递归函数：

边界与合法性检查（第1步）：这是递归的“安全阀”。任何递归函数首先都要检查输入是否有效，防止数组越界或访问非法内存。同时检查当前格子是否是墙(WALL)或已访问过(VISITED)，如果是，则直接返回false，表示此路不通。
终止条件（第2步）：这是递归的“目标”。如果当前坐标就是终点坐标，那么我们已经成功抵达。此时，我们将终点标记为路径(SOLUTION)并返回true。这个true会像多米诺骨牌一样，沿着调用链一路返回回去。
标记当前节点（第3步）：在尝试探索邻居之前，先把当前格子标记为VISITED。这是防止算法在原地打转、陷入无限递归的关键！想象一下，如果你从A点走到B点，如果不标记B点已访问，那么下一步从B点又可能走回A点，如此循环往复，程序就“死”了。
递归探索邻居（第4步）：使用for循环和方向数组DIRS，依次尝试向上、右、下、左四个方向移动。对每一个邻居坐标(nextX,nextY)，递归调用dfs函数。这里的逻辑是：“我不知道从当前点能不能到终点，但我可以问问我的邻居们：‘你们谁能到终点？’”。如果某个邻居的dfs调用返回了true，那就说明通过这个邻居能到达终点。
回溯与路径记录（第4步内与第5步）：这是最精妙的部分。当某个邻居的dfs返回true时，意味着找到了一条从该邻居到终点的通路。那么，当前点自然也是这条通路的一部分。所以，我们在if语句里面将当前点也标记为SOLUTION，然后返回true。如果四个邻居的dfs调用都返回false，说明从当前点出发的所有方向都是死胡同，那么函数最终返回false，表示此路不通。上层函数收到false后，就会尝试下一个方向。这个过程就是“回溯”。

4.3 在主函数中调用DFS并显示结果

现在，我们需要在main函数中找到起点，然后启动DFS搜索。

int main() { // ... [之前的迷宫初始化代码] ... cout << "初始迷宫：" << endl; printMaze(maze); // 寻找起点坐标 int startX = -1, startY = -1; for (int i = 0; i < ROWS; ++i) { for (int j = 0; j < COLS; ++j) { if (maze[i][j] == START) { startX = i; startY = j; break; } } if (startX != -1) break; } // 寻找终点坐标 int endX = -1, endY = -1; for (int i = 0; i < ROWS; ++i) { for (int j = 0; j < COLS; ++j) { if (maze[i][j] == END) { endX = i; endY = j; break; } } if (endX != -1) break; } if (startX == -1 || startY == -1 || endX == -1 || endY == -1) { cerr << "错误：未找到起点或终点！" << endl; return 1; } cout << "开始DFS自动寻路..." << endl; // 调用DFS函数 bool found = dfs(startX, startY, maze, endX, endY); if (found) { cout << "寻路成功！路径已用 '" << SOLUTION << "' 标出：" << endl; // 将起点重新标记回来（因为dfs过程中可能被覆盖） maze[startX][startY] = START; printMaze(maze); } else { cout << "寻路失败！起点与终点之间没有通路。" << endl; printMaze(maze); } return 0; }

编译并运行完整的程序。如果迷宫设计得有通路，你应该能看到一条由‘*’连成的路径从‘S’蜿蜒通向‘E’。注意观察这条路径，它很可能不是最短的，这正是DFS的特点。

5. 功能增强与可视化：让寻路过程“动”起来

控制台输出静态的最终结果虽然正确，但不够直观。我们可以通过一些简单的技巧，让DFS的搜索和回溯过程可视化，这对于理解和调试算法有巨大帮助。

5.1 实现搜索过程动画

思路是：在dfs函数中，每当我们标记一个点（访问或作为路径），就清屏并重新打印整个迷宫，然后让程序暂停一小段时间。

// 需要包含的头文件 #include <thread> #include <chrono> // 修改dfs函数，在标记访问和找到路径时加入可视化 bool dfs(int x, int y, vector<vector<char>>& maze, int endX, int endY) { // 边界与障碍检查（同前） if (x < 0 || x >= ROWS || y < 0 || y >= COLS || maze[x][y] == WALL || maze[x][y] == VISITED) { return false; } if (x == endX && y == endY) { maze[x][y] = SOLUTION; // 可视化：显示找到终点的瞬间 system("cls"); // Windows系统。Linux/Mac用 system("clear"); printMaze(maze); this_thread::sleep_for(chrono::milliseconds(500)); return true; } // 标记当前点为已访问 char originalChar = maze[x][y]; // 保存原始字符，如果是起点‘S’需要保留 if (maze[x][y] != START) { maze[x][y] = VISITED; } // 可视化：显示探索过程 system("cls"); printMaze(maze); this_thread::sleep_for(chrono::milliseconds(100)); // 控制动画速度 for (int i = 0; i < 4; ++i) { int nextX = x + DIRS[i][0]; int nextY = y + DIRS[i][1]; if (dfs(nextX, nextY, maze, endX, endY)) { // 回溯，标记路径 if (maze[x][y] != START) { maze[x][y] = SOLUTION; } // 可视化：显示回溯确定路径的过程 system("cls"); printMaze(maze); this_thread::sleep_for(chrono::milliseconds(100)); return true; } } // 如果所有方向都不通，返回false // 注意：这里我们保留了VISITED标记，不擦除。这是为了效率（剪枝）。 return false; }

注意事项：频繁的清屏(system(“cls”))和打印对于大型地图会影响性能，且system函数调用存在安全性和可移植性问题。这里仅用于教学演示。在生产环境或需要更优可视化的项目中，应该使用专门的图形库（如SFML、SDL2）或游戏引擎来实现。

5.2 路径记录与输出

上面的动画显示了过程，但最终我们可能还想知道路径的具体坐标序列。我们可以通过一个额外的数据结构来记录路径。

// 使用一个向量来存储路径上的点坐标 struct Point { int x, y; }; vector<Point> finalPath; // 全局变量或通过引用传递 // 修改dfs函数，增加path参数用于记录路径 bool dfs(int x, int y, vector<vector<char>>& maze, int endX, int endY, vector<Point>& path) { if (x < 0 || x >= ROWS || y < 0 || y >= COLS || maze[x][y] == WALL || maze[x][y] == VISITED) { return false; } // 将当前点加入临时路径 Point curPoint = {x, y}; path.push_back(curPoint); if (x == endX && y == endY) { // 找到终点，当前path就是一条完整路径 // 注意：由于DFS的特性，第一条找到的路径就被记录下来了，但它不一定是最短的。 // 如果需要最短路径，需要记录所有路径并比较长度，或者使用BFS。 maze[x][y] = SOLUTION; return true; } if (maze[x][y] != START) { maze[x][y] = VISITED; } for (int i = 0; i < 4; ++i) { int nextX = x + DIRS[i][0]; int nextY = y + DIRS[i][1]; if (dfs(nextX, nextY, maze, endX, endY, path)) { if (maze[x][y] != START) { maze[x][y] = SOLUTION; } return true; // 找到路径，直接返回，path中已记录了这条路径 } } // 此路不通，回溯时需要将当前点从路径中移除 path.pop_back(); return false; } // 在main函数中调用 vector<Point> solutionPath; bool found = dfs(startX, startY, maze, endX, endY, solutionPath); if (found) { cout << "寻路成功！路径坐标序列（从起点到终点）：" << endl; for (const auto& p : solutionPath) { cout << "(" << p.x << ", " << p.y << ") "; } cout << endl << "路径长度（步数）：" << solutionPath.size() - 1 << endl; // 减去起点 // ... 打印地图 ... }

这样，我们不仅能在地图上看到路径，还能获得具体的坐标序列和步数。

6. 从DFS到更优算法：BFS与A*的引子

通过上面的实现，我们已经深刻理解了DFS寻路的工作原理和特点。作为游戏开发者，我们当然不会止步于此。DFS找到的路径往往又长又绕，而游戏中我们通常希望角色走最短路径。这时就需要引入新的算法。

6.1 广度优先搜索（BFS）：寻找最短路径的保证

BFS的思想是“层层推进”。它从起点开始，先访问所有距离为1步的邻居，再访问所有距离为2步的邻居，以此类推。这就像在水里扔一块石头，涟漪一圈圈扩散出去。BFS天然保证，当它第一次访问到终点时，所走过的路径就是最短路径（在网格地图且每步代价相同时）。

BFS通常使用队列（Queue）来实现，而非递归。伪代码思路如下：

将起点放入队列，并标记为已访问。
当队列不为空时： a. 从队列中取出一个点（当前点）。 b. 如果当前点是终点，成功结束。 c. 否则，将当前点的所有未访问且可走的邻居点放入队列尾部，并记录这些邻居点的“前驱点”是当前点（用于最后回溯出路径）。
如果队列空了还没找到终点，则失败。

BFS的空间复杂度通常比DFS高，因为它需要存储每一层的节点。

6.2 A*算法：效率与最优性的平衡

A*算法是游戏工业界寻路的实际标准。它结合了BFS的最优性保证和DFS（或最佳优先搜索）的效率导向。

A*的核心是引入了一个估价函数 F = G + H：

G：从起点到当前节点的实际移动代价。
H：从当前节点到终点的预估代价（启发函数）。在网格中，常用曼哈顿距离或欧几里得距离。
F：节点的综合优先级。A*算法总是优先探索F值最小的节点。

它使用优先队列（Priority Queue）来实现。伪代码思路：

将起点加入优先队列（按F值排序）。
当优先队列不为空时： a. 取出F值最小的节点（当前节点）。 b. 如果是终点，结束。 c. 遍历邻居，计算每个邻居的G、H、F值。如果该邻居未被访问，或找到了到达它的更优路径（G值更小），则更新其信息并将其加入优先队列。

A*算法在启发函数H满足一定条件（可采纳性、一致性）时，既能找到最短路径，又能比BFS搜索更少的节点，效率高得多。

6.3 如何在我们现有代码基础上改造？

我们的DFS代码已经搭建了良好的基础：地图表示、边界检查、方向移动。要改为BFS或A*，主要改变的是搜索的数据结构和节点扩展的逻辑。

数据结构：将递归调用栈，改为显式的queue<pair<int, int>>（BFS）或priority_queue<Node>（A*）。
路径记录：需要额外的一个二维数组predecessor来记录每个节点的“父节点”（从哪个节点走过来），以便在找到终点后回溯出完整路径。
状态标记：同样需要visited数组来避免重复访问。

实操心得：学习算法，最好的方式就是对比实现。我强烈建议你在完成DFS后，尝试用C++实现BFS版本的寻路。你会发现，核心的地图遍历逻辑是相通的，只是“下一格选谁”的策略不同。这能让你真正理解“算法”是如何通过不同的数据组织方式来解决同一类问题的。

7. 常见问题、调试技巧与性能考量

在实际编写和运行这个DFS寻路程序时，你可能会遇到一些问题。这里总结一些常见坑点和解决思路。

7.1 栈溢出（Stack Overflow）

这是递归DFS最常见的问题。如果迷宫非常大或者非常复杂（路径极长），递归深度可能超过系统默认的栈大小，导致程序崩溃。

解决方案1：增大栈空间（不推荐作为根本解决）。某些编译器支持编译选项（如GCC的-Wl,--stack,<size>）。

解决方案2：改用迭代（显式栈）实现DFS。这是更通用的方法。你可以使用stack<pair<int, int>>来手动模拟递归过程，从而避免系统调用栈的限制。

bool dfs_iterative(int startX, int startY, ...) { stack<pair<int, int>> stk; stk.push({startX, startY}); // 还需要一个额外的数据结构来记录每个节点的父节点，用于回溯路径 vector<vector<pair<int, int>>> parent(ROWS, vector<pair<int, int>>(COLS, {-1, -1})); // ... 类似BFS，但用栈，后进先出 }

解决方案3：使用BFS或A*。这两种算法通常使用堆内存（队列/优先队列），不容易出现栈溢出问题。

7.2 路径显示异常或找不到路径

检查地图边界和初始化：确保起点‘S’和终点‘E’没有被墙‘#’覆盖，且坐标在数组有效范围内。
检查方向数组和移动逻辑：确认DIRS数组定义正确，nextX和nextY的计算没有错误。
检查访问标记逻辑：这是最容易出错的地方。确保在递归函数开头正确判断了maze[x][y] == VISITED。同时，在找到终点回溯标记路径时，要跳过起点，否则起点的‘S’会被覆盖成‘*’。
验证迷宫连通性：用一个更简单的、肉眼可见有通路的迷宫测试，排除地图设计错误。

7.3 算法效率低下（针对大型地图）

我们实现的DFS基础版本有一个优化点：没有在回溯时取消VISITED标记。这实际上是一种“剪枝”（Pruning），因为对于一个点，如果从它出发的所有方向都探索过了且没找到终点，那么之后从其他路径再走到这个点也注定是死胡同。这避免了大量重复搜索，极大地提升了效率。

对比实验：你可以尝试修改代码，在dfs函数最后返回false之前，将maze[x][y]从VISITED改回PATH。然后在一个有多个环路的迷宫里测试，你会发现程序运行时间可能成指数级增长，甚至无法结束。这就是“剪枝”的重要性。

7.4 从控制台到真实游戏引擎

在真实的游戏开发中（如Unity、Unreal Engine、Godot），寻路算法的核心思想不变，但实现环境不同：

地图表示：游戏引擎中地图通常不是简单的字符网格，而是用导航网格（NavMesh）或者更复杂的数据结构（如八叉树）来表示可行走区域，精度更高，能处理斜坡、楼梯等复杂地形。
算法集成：引擎通常内置了成熟的导航系统（如Unity的NavMesh、Unreal的Navigation Mesh）。你只需要设置好场景的静态几何体作为障碍，生成NavMesh，然后调用Agent.SetDestination()即可，底层已经用高度优化的C++代码实现了A*等算法。
性能与多线程：商业游戏中的寻路请求可能非常多（成百上千的NPC），需要将寻路任务放到工作线程中，避免阻塞主游戏线程。引擎的导航系统通常已经处理好了这些。
动态障碍：我们的Demo是静态迷宫。游戏中常有动态障碍物（比如其他移动的单位、临时关闭的门）。这需要寻路系统支持动态更新导航图或使用局部避障算法（如RVO、势场法）进行微调。

尽管如此，亲手实现一遍基础的DFS/BFS/A*，对于理解引擎黑盒子里在发生什么、以及当需要自定义寻路逻辑（比如策略游戏中单位有特殊的移动规则）时，具有不可替代的价值。它让你从API调用者，变成了原理的掌控者。下次当你在游戏里点击地图时，你看到的将不再是一个简单的移动指令，而是一幅算法在虚拟世界中为你精心绘制的最优路径图。

日记详情

C++实现DFS迷宫寻路算法：从原理到游戏开发实践