首先使用DFS递归回溯生成迷宫地图，保证连通性；再通过A*算法实现最短路径寻路，结合g和h值评估节点优先级；最后整合生成与寻路逻辑到主循环，实现角色移动与AI自动寻径，构成迷宫游戏核心框架。
开发一个C++迷宫游戏，核心在于二维地图的生成和角色在迷宫中的寻路逻辑。这两部分直接影响游戏的可玩性和智能性。下面从地图生成和寻路算法两个方面，介绍实用的实现思路和代码结构。
二维迷宫地图生成：深度优先搜索（DFS）算法
使用递归回溯法（基于DFS）生成自然连通的迷宫地图，保证从起点到终点有且至少一条通路。
基本思路：从起点开始，随机选择一个未访问的方向“打通”墙壁，进入下一个格子，直到无法前进时回溯。重复此过程直到所有可达格子都被访问。
地图通常用二维数组表示，例如0表示通路，1表示墙。
立即学习“C++免费学习笔记（深入）”；
示例代码片段：
#include <vector>
#include <cstdlib>
#include <ctime>
<p>const int WIDTH = 21; // 必须为奇数，便于处理墙
const int HEIGHT = 21;</p><p>std::vector<std::vector<int>> maze(HEIGHT, std::vector<int>(WIDTH, 1));
// 方向：上、右、下、左
int dx[4] = {0, 2, 0, -2};
int dy[4] = {-2, 0, 2, 0};</p><p>void generateMaze(int x, int y) {
maze[y][x] = 0; // 当前位置设为通路</p><pre class='brush:php;toolbar:false;'>// 随机打乱方向顺序
std::vector<int> dirs = {0, 1, 2, 3};
for (int i = 3; i > 0; i--) {
int j = rand() % (i + 1);
std::swap(dirs[i], dirs[j]);
}
for (int d : dirs) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx > 0 && nx < WIDTH-1 && ny > 0 && ny < HEIGHT-1 && maze[ny][nx] == 1) {
maze[y + dy[d]/2][x + dx[d]/2] = 0; // 打通中间墙
generateMaze(nx, ny);
}
}
}
// 调用方式：srand(time(0)); generateMaze(1, 1);
寻路算法：A* 算法实现最短路径
当玩家或AI需要自动寻路时，A*算法是高效的选择。它结合了Dijkstra的广度优先搜索和启发式函数（如曼哈顿距离），优先探索更接近终点的方向。
A*算法核心：每个节点计算 f = g + h
- g：从起点到当前点的实际步数
- h：当前点到终点的预估距离（启发值）
- f：总代价，用于优先级排序
使用优先队列（最小堆）管理待探索节点，避免重复访问，直到找到终点。
简化实现思路：
struct Point {
int x, y, g, h;
bool operator<(const Point& p) const {
return (g + h) > (p.g + p.h); // 优先队列用最大堆，反向比较
}
};
<p>int heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离
}</p><p>std::vector<std::pair<int, int>> findPath(int start_x, int start_y, int end_x, int end_y) {
std::priority_queue<Point> pq;
std::vector<std::vector<bool>> visited(HEIGHT, std::vector<bool>(WIDTH, false));
std::vector<std::vector<int>> g_val(HEIGHT, std::vector<int>(WIDTH, INT_MAX));
std::vector<std::vector<std::pair<int, int>>> parent(HEIGHT, std::vector<std::pair<int, int>>(WIDTH, {-1, -1}));</p><pre class='brush:php;toolbar:false;'>pq.push({start_x, start_y, 0, heuristic(start_x, start_y, end_x, end_y)});
g_val[start_y][start_x] = 0;
int dx[] = {0, 1, 0, -1};
int dy[] = {-1, 0, 1, 0};
while (!pq.empty()) {
Point cur = pq.top(); pq.pop();
int x = cur.x, y = cur.y;
if (visited[y][x]) continue;
visited[y][x] = true;
if (x == end_x && y == end_y) break;
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (nx < 0 || nx >= WIDTH || ny < 0 || ny >= HEIGHT) continue;
if (maze[ny][nx] != 0) continue; // 不是通路
if (visited[ny][nx]) continue;
int new_g = g_val[y][x] + 1;
if (new_g < g_val[ny][nx]) {
g_val[ny][nx] = new_g;
parent[ny][nx] = {x, y};
pq.push({nx, ny, new_g, heuristic(nx, ny, end_x, end_y)});
}
}
}
// 回溯路径
std::vector<std::pair<int, int>> path;
int x = end_x, y = end_y;
while (x != -1 && y != -1) {
path.push_back({x, y});
auto [px, py] = parent[y][x];
x = px; y = py;
}
reverse(path.begin(), path.end());
return path;
}
整合到游戏主循环
将地图生成和寻路算法嵌入游戏主逻辑中，例如：
- 启动时调用 generateMaze(1, 1) 生成迷宫
- 设置玩家起始位置和目标位置（如 (1,1) 到 (WIDTH-2, HEIGHT-2)）
- 玩家移动时，可用键盘控制；AI移动时调用 findPath 获取路径并逐步执行
- 用简单的字符绘制地图：' ' 表示通路，'#' 表示墙，'P' 表示玩家
可通过循环打印二维数组实现简单渲染：
void printMaze(int px, int py) {
for (int i = 0; i < HEIGHT; i++) {
for (int j = 0; j < WIDTH; j++) {
if (i == py && j == px) std::cout << "P";
else std::cout << (maze[i][j] ? "#" : " ");
}
std::cout << "\n";
}
}
基本上就这些。迷宫生成和A*寻路构成了这类游戏的核心骨架，后续可扩展加入陷阱、道具、多关卡等机制。关键是理解二维数组的索引逻辑和算法的边界处理。
