DFS迷宫生成算法异常：C++实现生成多独立区域问题排查

问题重现 #

使用C++实现的DFS迷宫生成算法始终生成多个独立区域，迷宫以Node对象的二维向量表示，期望生成全连通的迷宫，但实际输出存在断开区域（例如右下角区域与主区域完全隔离）。

核心错误点 #

• 迷宫索引完全颠倒：generate_full_maze创建的maze是maze[x][y]对应坐标(x,y)的节点，但carve_walls中所有访问均写成maze[y][x]，导致节点访问错位，邻居判断彻底失效，这是迷宫断开的核心原因。
• 参数值传递导致修改无效：carve_walls的maze和is_visited的visited均为值传递，函数内的修改仅作用于副本，原迷宫数据完全未被更新。
• 重复创建起始节点：main中重新创建startNode覆盖原有节点，造成内存泄漏且节点实例不一致。
• 随机数未初始化：std::random_shuffle无种子导致每次生成的随机序列固定，且该函数在C++17已被弃用。

修复后的完整代码 #

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

class Node {
public:
    int x;
    int y;
    Node* parent;
    Node(int x, int y, Node* parent = nullptr) 
        : x(x), y(y), parent(parent) {} // 使用初始化列表更规范
};

// 创建迷宫：maze[x][y]对应坐标(x,y)的节点
std::vector<std::vector<Node*>> generate_full_maze(int columns, int rows) {
    std::vector<std::vector<Node*>> maze(columns, std::vector<Node*>(rows));
    for (int x = 0; x < columns; x++) {
        for (int y = 0; y < rows; y++) {
            maze[x][y] = new Node(x, y);
        }
    }
    return maze;
}

// 打印迷宫：按x,y顺序遍历
void print_maze(const std::vector<std::vector<Node*>>& maze) {
    int columns = maze.size();
    int rows = maze[0].size();
    for (int x = 0; x < columns; x++) {
        for (int y = 0; y < rows; y++) {
            Node* node = maze[x][y];
            std::cout << node->x << "," << node->y << " ";
            if (node->parent != nullptr) {
                std::cout << "Parent: " << node->parent->x << "," << node->parent->y << std::endl;
            } else {
                std::cout << "Parent: None" << std::endl;
            }
        }
    }
}

// 检查节点是否已访问：传递引用避免复制
bool is_visited(int x, int y, const std::vector<Node*>& visited) {    
    for (const Node* node : visited) {
        if (node->x == x && node->y == y) {
            return true;
        }
    }
    return false;
}

// 打通迷宫墙壁：传递maze的引用，直接修改原数据
void carve_walls(int maxx, int maxy, std::vector<std::vector<Node*>>& maze) {
    std::vector<Node*> visited;
    std::stack<Node*> stack;

    // 起始节点：(0,0)对应maze[0][0]
    Node* start = maze[0][0];
    visited.push_back(start);
    stack.push(start);

    // 初始化随机引擎（替代已弃用的random_shuffle）
    unsigned seed = std::chrono::system_clock::now().time_since_epoch().count();
    std::default_random_engine rng(seed);

    while (!stack.empty()) {
        Node* current_cell = stack.top();
        stack.pop();

        std::vector<Node*> neighbours;

        // 按x,y坐标正确获取邻居
        if (current_cell->x > 0) { // 左邻居：x-1, y
            neighbours.push_back(maze[current_cell->x - 1][current_cell->y]);
        }
        if (current_cell->x < maxx - 1) { // 右邻居：x+1, y
            neighbours.push_back(maze[current_cell->x + 1][current_cell->y]);
        }
        if (current_cell->y > 0) { // 上邻居：x, y-1
            neighbours.push_back(maze[current_cell->x][current_cell->y - 1]);
        }
        if (current_cell->y < maxy - 1) { // 下邻居：x, y+1
            neighbours.push_back(maze[current_cell->x][current_cell->y + 1]);
        }

        // 使用shuffle替代已弃用的random_shuffle
        std::shuffle(neighbours.begin(), neighbours.end(), rng);

        for (Node* neighbour : neighbours) {
            if (!is_visited(neighbour->x, neighbour->y, visited)) {
                neighbour->parent = current_cell;
                visited.push_back(neighbour);
                stack.push(neighbour);
            }
        }
    }
}

int main() {
    int columns = 5;
    int rows = 5;
    std::vector<std::vector<Node*>> maze = generate_full_maze(columns, rows);

    // 移除重复创建的startNode，直接使用generate_full_maze生成的节点
    carve_walls(columns, rows, maze);

    print_maze(maze);

    // 内存清理：按x,y顺序遍历释放
    for (int x = 0; x < columns; x++) {
        for (int y = 0; y < rows; y++) {
            delete maze[x][y];
        }
    }

    return 0;
}

修复说明 #

1. 修正索引对应关系：所有maze访问统一为maze[x][y]，与坐标(x,y)一一对应，确保邻居节点获取正确。
2. 改为引用传递：carve_walls的maze和is_visited的visited均改为const引用，避免副本开销，确保修改作用于原数据。
3. 移除重复节点创建：直接使用generate_full_maze生成的起始节点，避免内存泄漏和实例不一致。
4. 替换随机数实现：用std::shuffle配合系统时间种子的随机引擎，替代已弃用的std::random_shuffle，保证随机序列的随机性。

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