11、C++项目实战：迷宫生成与求解算法

迷宫生成与求解，听起来像是个玩具项目对吧？
说实话，我当年刚入行时也这么想。直到有一次在游戏公司面试，面试官让我现场实现一个随机迷宫生成器，我才发现——
这玩意儿背后藏着图论、随机算法、回溯搜索，甚至还能扯到寻路优化。
嗯，从那以后，我再也不敢小看迷宫了。

今天这个项目，我们就来手写一个完整的迷宫生成与求解系统。
我会带你从零开始，用 C++ 把这两件事都搞定。

项目目标

  • 随机生成一个 N×M 的迷宫（保证有解）
  • 用深度优先搜索（DFS）求解迷宫路径
  • 输出迷宫地图和路径到控制台
  • 代码结构清晰，方便扩展

核心知识点

知识点说明
二维数组与坐标建模用二维数组表示迷宫格子
并查集 / 随机拆墙生成迷宫的核心思路
DFS 回溯求解路径的标准方法
栈与递归DFS 的两种实现方式
随机数生成保证每次生成的迷宫不同

迷宫建模思路

迷宫本质上是一个网格图。
每个格子有四面墙：上、下、左、右。
生成迷宫的过程，说白了就是「拆掉一些墙，让所有格子连通，但不要形成环路」。

我个人习惯用两个二维数组来建模：

  • grid[row][col]：存储格子的状态（是否被访问过）
  • walls[row][col][4]：存储四面墙是否存在（1 表示有墙，0 表示已拆）

你想想看，这样建模之后，生成和求解都变得很直观。

迷宫生成算法：随机 DFS

生成迷宫最经典的方法就是随机 DFS。
流程很简单：

  1. 从起点开始，标记为已访问
  2. 随机选择一个未访问的邻居
  3. 拆掉中间的墙，递归进入邻居
  4. 如果所有邻居都已访问，回溯

这样走完一遍，所有格子都会被访问一次，而且恰好形成一棵树——
没有环路，每个格子都有唯一路径到达起点。

核心要点：
随机 DFS 生成的迷宫，天然保证有解，而且解是唯一的。
我在项目中遇到过一个问题：如果随机性不够，迷宫会呈现明显的「走廊」倾向。
解决办法是每次打乱邻居顺序时，用 std::shuffle 而不是简单的随机交换。

代码实现：迷宫生成

#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <stack>

struct Cell {
    bool visited = false;
    bool walls[4] = {true, true, true, true}; // 上 右 下 左
};

class Maze {
public:
    Maze(int rows, int cols) : rows(rows), cols(cols) {
        grid.resize(rows, std::vector<Cell>(cols));
        gen.seed(std::random_device{}());
    }

    void generate() {
        std::stack<std::pair<int,int>> stk;
        int r = 0, c = 0;
        grid[r][c].visited = true;
        stk.push({r, c});

        while (!stk.empty()) {
            auto [cr, cc] = stk.top();
            auto neighbors = getUnvisitedNeighbors(cr, cc);
            if (neighbors.empty()) {
                stk.pop(); // 回溯
            } else {
                std::shuffle(neighbors.begin(), neighbors.end(), gen);
                auto [nr, nc] = neighbors[0];
                removeWall(cr, cc, nr, nc);
                grid[nr][nc].visited = true;
                stk.push({nr, nc});
            }
        }
    }

    void print() const {
        // 打印迷宫到控制台
        for (int r = 0; r < rows; ++r) {
            // 打印上墙
            for (int c = 0; c < cols; ++c) {
                std::cout << (grid[r][c].walls[0] ? "+---" : "+   ");
            }
            std::cout << "+\n";
            // 打印左右墙
            for (int c = 0; c < cols; ++c) {
                std::cout << (grid[r][c].walls[3] ? "|   " : "    ");
            }
            std::cout << "|\n";
        }
        // 打印底墙
        for (int c = 0; c < cols; ++c) {
            std::cout << "+---";
        }
        std::cout << "+\n";
    }

private:
    int rows, cols;
    std::vector<std::vector<Cell>> grid;
    std::mt19937 gen;

    std::vector<std::pair<int,int>> getUnvisitedNeighbors(int r, int c) {
        std::vector<std::pair<int,int>> res;
        if (r > 0 && !grid[r-1][c].visited) res.push_back({r-1, c});
        if (r < rows-1 && !grid[r+1][c].visited) res.push_back({r+1, c});
        if (c > 0 && !grid[r][c-1].visited) res.push_back({r, c-1});
        if (c < cols-1 && !grid[r][c+1].visited) res.push_back({r, c+1});
        return res;
    }

    void removeWall(int r1, int c1, int r2, int c2) {
        if (r2 == r1 - 1) { grid[r1][c1].walls[0] = false; grid[r2][c2].walls[2] = false; }
        if (r2 == r1 + 1) { grid[r1][c1].walls[2] = false; grid[r2][c2].walls[0] = false; }
        if (c2 == c1 - 1) { grid[r1][c1].walls[3] = false; grid[r2][c2].walls[1] = false; }
        if (c2 == c1 + 1) { grid[r1][c1].walls[1] = false; grid[r2][c2].walls[3] = false; }
    }
};

小技巧：
打印迷宫时，我习惯用 +--- 和 | 来画墙。
这样在终端里看起来非常清晰，而且调试时一眼就能看出墙有没有拆对。

迷宫求解：DFS 寻路

生成完迷宫，下一步就是求解。
求解的思路其实更简单：从起点出发，沿着可走的路径一直走，走到死胡同就回溯。

我建议用栈来模拟递归，避免递归深度过大导致栈溢出。
尤其是迷宫规模较大时，递归版本很容易崩。

std::vector<std::pair<int,int>> solve(Maze &maze) {
    int rows = maze.getRows(), cols = maze.getCols();
    std::vector<std::vector<bool>> visited(rows, std::vector<bool>(cols, false));
    std::stack<std::pair<int,int>> stk;
    std::vector<std::pair<int,int>> path;

    stk.push({0, 0});
    visited[0][0] = true;

    while (!stk.empty()) {
        auto [r, c] = stk.top();
        path.push_back({r, c});

        if (r == rows-1 && c == cols-1) {
            return path; // 到达终点
        }

        // 检查四个方向是否有路
        bool moved = false;
        // 上
        if (r > 0 && !maze.hasWall(r, c, 0) && !visited[r-1][c]) {
            stk.push({r-1, c}); visited[r-1][c] = true; moved = true;
        }
        // 右
        if (c < cols-1 && !maze.hasWall(r, c, 1) && !visited[r][c+1]) {
            stk.push({r, c+1}); visited[r][c+1] = true; moved = true;
        }
        // 下
        if (r < rows-1 && !maze.hasWall(r, c, 2) && !visited[r+1][c]) {
            stk.push({r+1, c}); visited[r+1][c] = true; moved = true;
        }
        // 左
        if (c > 0 && !maze.hasWall(r, c, 3) && !visited[r][c-1]) {
            stk.push({r, c-1}); visited[r][c-1] = true; moved = true;
        }

        if (!moved) {
            stk.pop(); // 死胡同，回溯
            path.pop_back();
        }
    }

    return {}; // 无解（理论上不会发生）
}

注意：
我曾经在求解时犯过一个低级错误——
忘记检查墙是否存在，结果路径直接穿墙而过。
所以每次移动前，一定要调用 hasWall() 确认那面墙已经被拆掉了。

知识体系总览

下面这张图，是我为你梳理的迷宫生成与求解的完整知识结构：

迷宫生成与求解 迷宫生成 迷宫求解 随机 DFS 拆墙逻辑 二维数组建模 随机数生成 DFS 回溯 栈模拟递归 路径记录 墙检测

扩展思路

  • 更复杂的生成算法：比如 Prim 算法、Kruskal 算法，生成的迷宫风格不同
  • 更高效的求解：BFS 可以找到最短路径，适合需要最优解的场景
  • 可视化：结合 SFML 或 Qt，把迷宫画成图形界面，效果更直观
  • 文件读写：把迷宫保存到文件，下次直接加载，不用重新生成

个人建议：
如果你想把迷宫项目写到简历上，建议至少加上 BFS 求解和可视化。
这样既能展示算法能力，又能展示工程能力，面试官会更有兴趣。

好了，迷宫生成与求解的核心内容就这些。
代码量不大，但涉及的知识点很扎实。
你可以先跑通生成部分，再慢慢加上求解和可视化。
遇到问题别急，多打印几次迷宫地图，墙的位置对不对一目了然。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →