c++迷宫随机生成算法

迷宫的随机生成算法有多种方法，其中一个常见的方法是使用深度优先搜索（DFS）算法。下面是一个使用C++实现的迷宫随机生成算法的示例：

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

using namespace std;

// 迷宫的大小（假设为正方形）
const int SIZE = 10;

// 迷宫格子的状态
enum class CellState {
    Wall,
    Path
};

// 迷宫格子的结构体
struct Cell {
    int row, col;
    CellState state;

    Cell(int r, int c, CellState s) : row(r), col(c), state(s) {}
};

// 获取一个随机数
int getRandomInt(int min, int max) {
    static random_device rd;
    static mt19937 gen(rd());
    uniform_int_distribution<> dis(min, max);
    return dis(gen);
}

// 初始化迷宫
void initializeMaze(vector<vector<Cell>>& maze) {
    for (int i = 0; i < SIZE; ++i) {
        maze.push_back(vector<Cell>());
        for (int j = 0; j < SIZE; ++j) {
            maze[i].push_back(Cell(i, j, CellState::Wall));
        }
    }
}

// 判断一个格子是否在迷宫的边界内
bool isInBounds(int row, int col) {
    return row >= 0 && row < SIZE && col >= 0 && col < SIZE;
}

// 获取一个格子的邻居格子
vector<Cell*> getNeighbors(const Cell& cell, const vector<vector<Cell>>& maze) {
    vector<Cell*> neighbors;

    // 上
    if (isInBounds(cell.row - 1, cell.col)) {
        neighbors.push_back(&maze[cell.row - 1][cell.col]);
    }
    // 下
    if (isInBounds(cell.row + 1, cell.col)) {
        neighbors.push_back(&maze[cell.row + 1][cell.col]);
    }
    // 左
    if (isInBounds(cell.row, cell.col - 1)) {
        neighbors.push_back(&maze[cell.row][cell.col - 1]);
    }
    // 右
    if (isInBounds(cell.row, cell.col + 1)) {
        neighbors.push_back(&maze[cell.row][cell.col + 1]);
    }

    return neighbors;
}

// 使用深度优先搜索算法随机生成迷宫
void generateMaze(vector<vector<Cell>>& maze) {
    stack<Cell*> stack;
    Cell* current = &maze[0][0];
    current->state = CellState::Path;

    do {
        vector<Cell*> unvisitedNeighbors;
        vector<Cell*> neighbors = getNeighbors(*current, maze);

        // 寻找未访问的邻居
        for (Cell* neighbor : neighbors) {
            if (neighbor->state == CellState::Wall) {
                unvisitedNeighbors.push_back(neighbor);
            }
        }

        if (!unvisitedNeighbors.empty()) {
            // 随机选择一个未访问的邻居
            int randomIndex = getRandomInt(0, unvisitedNeighbors.size() - 1);
            Cell* next = unvisitedNeighbors[randomIndex];

            // 打开墙，连接当前格子和下一个格子
            int wallRow = (current->row + next->row) / 2;
            int wallCol = (current->col + next->col) / 2;
            maze[wallRow][wallCol].state = CellState::Path;
            next->state = CellState::Path;

            stack.push(current);
            current = next;
        }
        else if (!stack.empty()) {
            current = stack.top();
            stack.pop();
        }
    } while (!stack.empty());
}

// 打印迷宫
void printMaze(const vector<vector<Cell>>& maze) {
    for (int i = 0; i < SIZE; ++i) {
        for (int j = 0; j < SIZE; ++j) {
            if (maze[i][j].state == CellState::Wall) {
                cout << "■ ";
            }
            else {
                cout << "  ";
            }
        }
        cout << endl;
    }
}

int main() {
    vector<vector<Cell>> maze;
    initializeMaze(maze);
    generateMaze(maze);
    printMaze(maze);

    return 0;
}

此示例使用深度优先搜索算法随机生成迷宫。它首先初始化一个大小为SIZE的迷宫，然后从起点开始，不断选择一个未访问的邻居格子，打开墙，连接两个格子，直到无法继续前进或者所有格子都被访问过为止。最终打印出生成的迷宫。注意，此示例中迷宫的大小为10x10，你可以根据需要调整SIZE的值。