Recrusive Division递归分割算法

　　递归分割算法的基本思路是首先将整个迷宫都看做是迷宫单元格，任意选取一个偶数行、偶数列作为墙壁进行分割。随后，在墙壁上随机的取三个点将墙壁打通（这里我选取的是奇数行/列的点进行打通的，这样可以避免本次打通的墙又被后面生成的墙给堵住）。具体的效果如下图所示：

 

然后，对生成的四个子区域再进行相似的操作，直到最后不能再进行分隔为止。最终生成的迷宫效果图如下图所示：

 

可以看出该方法生成的迷宫比较规则，有较多的直线通路。

Code：

void CreatMaze::RDHelp(int x1, int x2, int y1, int y2, int count)
{
    if (x2 - x1 < 2 || y2 - y1 < 2) return;
    // m的取值范围为[l, r]
    // 偶数行是墙
    int xm = RDRand1(x1, x2, count);
    int ym = RDRand1(y1, y2, count);
    for (int i = y1; i <= y2; ++i) this->maze[xm][i] = 0;
    for (int j = x1; j <= x2; ++j) this->maze[j][ym] = 0;
    // 随机的在四面墙上选择四个砖块，然后从四个砖块中选择三个
    // 打通，从而使整个迷宫变得连通
    int y3 = RDRand2(y1, ym - 1, count);
    int y4 = RDRand2(ym + 1, y2, count);
    int x3 = RDRand2(x1, xm - 1, count);
    int x4 = RDRand2(xm + 1, x2, count);
    std::vector<std::pair<int, int> > v;
    v.push_back(std::make_pair(xm, y3));
    v.push_back(std::make_pair(xm, y4));
    v.push_back(std::make_pair(x3, ym));
    v.push_back(std::make_pair(x4, ym));
    int pos = rand() % 4;
    for (int i = 0; i < 4; ++i) {
        if (i != pos) {
            this->maze[v[i].first][v[i].second] = 1;
        }
    }
    
    RDHelp(x1, xm - 1, y1, ym - 1, count + 2);
    RDHelp(x1, xm - 1, ym + 1, y2, count + 3);
    RDHelp(xm + 1, x2, y1, ym - 1, count + 4);
    RDHelp(xm + 1, x2, ym + 1, y2, count + 5);
    
}

// 在偶数行选取要生成的墙
int CreatMaze::RDRand1(int x, int y, int seed)
{
    srand(seed);
    int ans = 0;
    ans = rand() % (y - x) + x;
    // 返回x和y之间的一个偶数
    if (ans % 2 != 0) ans += 1;
    return ans;
}

// 在奇数行选取要打通那一面墙壁
int CreatMaze::RDRand2(int x, int y, int seed)
{
    if (x >= y) return x;
    srand(seed);
    int ans = rand() % (y - x) + x;
    if (ans % 2 == 0) ans += 1;
    return ans;
}

 

Randomized Prim's Algorithm随机Prim算法

　　Prim算法是生成最小生成树的一种常见算法，其具体的做法是：维护一个已经访问过的节点的集合，从这个几何中的点所连接的其它不在该集合中的点中选择一个距离最小的点，加入该集合，直到所有的点都加入到该集合中为止，一句话可以概括为：归并结点。

　　随机Prim算法生成迷宫的方法与之相似，首先将迷宫看作是由迷宫单元和墙所组成的网格，如下图所示：

 

 

　　然后，选取一个点作为起点，然后将该点周围的未被访问过的边加入到一个列表中，只要列表中还有元素，就做如下循环：

• 从列表中随机的选取一条边（这是与DFS算法的最大区别之处，这样做可以使生成的迷宫更加的自然，分叉更多）
• 如果该边所连接的迷宫单元只有一个被访问过
  • 将未被访问过的迷宫单元作为当前单元格
  • 将当前单元所连接的四条边中未被访问过的边加入到集合中
  • 在集合中删除之前所选取的那条边
• 如果该边所连接的两个迷宫单元都已被访问过
  • 在集合中删除这条边

　　最后，生成的迷宫如下图所示：

 

 　　可以看出，用这种方法生成的迷宫分支较多，且没有太多的直线通路，更加的符合平时我们所认知的迷宫。

Code：

void CreatMaze::RP() {
    struct Cell
    {
        int x;
        int y;
        std::pair<int, int> next;
    };
    std::vector<Cell> v;
    int x = 1, y = 1;
    visited[x][y] = 1;
    int dir[5] = { 0, 1, 0, -1, 0 };
    for (int i = 0; i < 4; ++i) {
        int nx = x + dir[i];
        int ny = y + dir[i + 1];
        if (isValid(nx, ny)) {
            visited[nx][ny] = 1;
            Cell cell;
            cell.x = nx;
            cell.y = ny;
            cell.next.first = nx + dir[i];
            cell.next.second = ny + dir[i + 1];
            v.push_back(cell);
        }
    }
    int count = time(0) % 1000;
    while (v.size() > 0) {
        count++;
        srand(count);
        int pos = rand() % v.size();
        Cell temp = v[pos];
        int x = temp.next.first;
        int y = temp.next.second;
        if (isValid(x, y)) {
            this->maze[temp.x][temp.y] = 1;
            visited[x][y] = 1;
            for (int i = 0; i < 4; ++i) {
                int nx = x + dir[i];
                int ny = y + dir[i + 1];
                if (isValid(nx, ny)) {
                    visited[nx][ny] = 1;
                    Cell cell;
                    cell.x = nx;
                    cell.y = ny;
                    cell.next.first = nx + dir[i];
                    cell.next.second = ny + dir[i + 1];
                    v.push_back(cell);
                }
            }
        }
        int len = v.size();
        for (int i = pos + 1; i < len; ++i) {
            v[i - 1] = v[i];
        }
        v.resize(len - 1);
    }
}