使用DFS生成并求解迷宫时路径始终相同且必存在路径的问题

我用DFS算法生成随机迷宫并求解，按设计每次运行应该生成不同的迷宫，但实际每次生成的路径都一样，而且不管怎么跑都有可行路径。以下是C++代码和输出示例：

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

const int SIZE = 10;

enum Direction {
    TOP,
    RIGHT,
    BOTTOM,
    LEFT
};

struct Cell {
    bool visited;
    bool walls[4];  // top, right, bottom, left

    Cell() {
        visited = false;
        std::fill(walls, walls + 4, true);
    }
};

int getRandomNumber(int min, int max) {
    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(min, max);
    return dis(gen);
}


bool isValidCell(int row, int col) {
    return (row >= 0 && row < SIZE && col >= 0 && col < SIZE);
}

void removeWall(Cell& current, Cell& next, Direction direction) {
    current.walls[direction] = false;

    if (direction == TOP)
        next.walls[BOTTOM] = false;
    else if (direction == RIGHT)
        next.walls[LEFT] = false;
    else if (direction == BOTTOM)
        next.walls[TOP] = false;
    else if (direction == LEFT)
        next.walls[RIGHT] = false;
}

void generateMaze(std::vector<std::vector<Cell>>& maze, int row, int col) {
    static const int dx[] = {0, 1, 0, -1};  // right, down, left, up
    static const int dy[] = {-1, 0, 1, 0};

    maze[row][col].visited = true;

    std::vector<int> directions = {TOP, RIGHT, BOTTOM, LEFT};
    std::shuffle(directions.begin(), directions.end(), std::mt19937(std::random_device()()));

    for (int direction : directions) {
        int newRow = row + dy[direction];
        int newCol = col + dx[direction];

        if (isValidCell(newRow, newCol) && !maze[newRow][newCol].visited) {
            removeWall(maze[row][col], maze[newRow][newCol], static_cast<Direction>(direction));
            generateMaze(maze, newRow, newCol);
        }
    }
}

void generateMaze(std::vector<std::vector<Cell>>& maze) {
    generateMaze(maze, 0, 0);
}

void displayMaze(const std::vector<std::vector<Cell>>& maze) {
    for (int row = 0; row < SIZE; ++row) {
        for (int col = 0; col < SIZE; ++col) {
            std::cout << "+";
            std::cout << (maze[row][col].walls[TOP] ? "---" : "   ");
        }
        std::cout << "\n";

        for (int col = 0; col < SIZE; ++col) {
            std::cout << (maze[row][col].walls[LEFT] ? "|" : " ");
            std::cout << "   ";
        }
        std::cout << "|\n";
    }

    for (int col = 0; col < SIZE; ++col) {
        std::cout << "+---";
    }
    std::cout << "\n";
}

bool solveMazeDFS(std::vector<std::vector<Cell>>& maze, int row, int col, std::vector<std::pair<int, int>>& path) {
    static const int dx[] = {0, 1, 0, -1}; // right, down, left, up
    static const int dy[] = {-1, 0, 1, 0};
    if (!isValidCell(row, col) || maze[row][col].visited)
        return false;

    maze[row][col].visited = true;

    if (row == SIZE - 1 && col == SIZE - 1) {
        // Reached the end of the maze
        path.push_back(std::make_pair(row, col));
        return true;
    }

    for (int direction = 0; direction < 4; ++direction) {
        int newRow = row + dy[direction];
        int newCol = col + dx[direction];

        if (solveMazeDFS(maze, newRow, newCol, path)) {
            // Found a valid path, add the current cell to the path
            path.push_back(std::make_pair(row, col));
            return true;
        }
    }

    return false;
}

bool solveMaze(std::vector<std::vector<Cell>>& maze, std::vector<std::pair<int, int>>& path) {
    // Reset the visited flag of cells in the maze
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            maze[i][j].visited = false;
        }
    }

    // Start solving the maze from the beginning
    return solveMazeDFS(maze, 0, 0, path);
}


int main() {
    std::vector<std::vector<Cell>> maze(SIZE, std::vector<Cell>(SIZE));
    generateMaze(maze);
    displayMaze(maze);
    std::vector<std::pair<int, int>> path;
    if (solveMaze(maze, path)) {
        std::cout << "Solution:\n";
        for (int i = path.size() - 1; i >= 0; --i) {
            std::cout << "(" << path[i].first << ", " << path[i].second << ")";
            if (i > 0)
                std::cout << " -> ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "No solution found.\n";
    }
    
    return 0;
}

输出示例：

+---+---+---+---+---+---+---+---+---+---+
|           |                           |
+---+---+   +   +---+---+---+---+---+   +
|       |   |   |                   |   |
+   +---+   +   +   +---+---+---+   +   +
|   |       |               |       |   |
+   +   +---+   +---+---+   +   +---+   +
|   |   |       |       |   |   |       |
+   +   +---+   +   +   +---+   +---+   +
|   |       |   |   |       |       |   |
+   +---+   +---+   +---+   +   +   +   +
|   |       |       |       |   |   |   |
+   +   +---+   +---+   +---+---+   +   +
|       |       |                   |   |
+   +---+   +---+---+---+---+---+---+   +
|       |                   |       |   |
+---+   +---+---+   +---+   +---+   +   +
|   |           |   |       |       |   |
+   +---+---+   +---+   +---+   +---+   +
|                       |               |
+---+---+---+---+---+---+---+---+---+---+
Solution:
(0, 0) -> (0, 1) -> (0, 2) -> (0, 3) -> (0, 4) -> (0, 5) -> (0, 6) -> (0, 7) -> (0, 8) -> (0, 9) -> (1, 9) -> (2, 9) -> (3, 9) -> (4, 9) -> (5, 9) -> (6, 9) -> (7, 9) -> (8, 9) -> (9, 9)

问题原因分析 #

1. 随机数生成器重复初始化导致随机性失效 #

在generateMaze函数中，每次调用std::shuffle时都新建std::mt19937生成器，并用std::random_device()()初始化。部分平台下std::random_device可能返回固定值，且重复创建生成器会导致随机序列一致，最终打乱方向的结果固定，生成的迷宫也就完全相同。

2. DFS迷宫生成算法本身保证存在路径 #

你使用的递归DFS迷宫生成算法，本质是构建覆盖所有单元格的生成树，从起点(0,0)可遍历到所有单元格，因此必然存在起点到终点(9,9)的路径，这是算法固有特性，并非bug。

修复方案 #

修复随机数生成问题 #

将随机数生成器改为静态/全局变量，仅初始化一次，避免重复创建导致的随机性丢失：

修改generateMaze函数内的shuffle逻辑：

// 定义静态随机生成器，仅初始化一次
static std::mt19937 gen(std::random_device{}());

std::vector<int> directions = {TOP, RIGHT, BOTTOM, LEFT};
std::shuffle(directions.begin(), directions.end(), gen);

同时，getRandomNumber函数也存在相同问题，建议统一使用同一个生成器：

static std::mt19937 gen(std::random_device{}());

int getRandomNumber(int min, int max) {
    std::uniform_int_distribution<int> dis(min, max);
    return dis(gen);
}

修改后每次运行程序，shuffle结果会不同，生成的迷宫墙分布也会随机变化。

额外优化：修复求解函数穿墙问题 #

当前求解函数未判断墙是否存在，会直接尝试四个方向，导致“穿墙”走无效路径。需在solveMazeDFS的循环中增加墙的判断：

for (int direction = 0; direction < 4; ++direction) {
    // 墙存在则跳过该方向
    if (maze[row][col].walls[direction]) continue;
    int newRow = row + dy[direction];
    int newCol = col + dx[direction];

    if (solveMazeDFS(maze, newRow, newCol, path)) {
        path.push_back(std::make_pair(row, col));
        return true;
    }
}

内容的提问来源于stack exchange，提问作者ThisIsMe