迷宫生成算法设计（递归划分）

Question

我正在尝试在我的寻路可视化解决方案中包含一个迷宫生成器，以便生成关于当前应用程序可以处理的内容的迷宫。

我找到了一个结构很好的网站，里面有一堆迷宫生成算法，但我主要关注一个：http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm

我的编程语言知识主要是 C++，我的应用程序是用它 + SDL2.0 构建的。

我的“网格”（2D 矩阵）由“cells/nodes”组成，由 window 表面上渲染的框纹理表示。每个“细胞”可以处于不同的状态 - 障碍物 == 它是一堵墙 - 白色状态 == 它是通道。

我面临的问题是我的“通道”有时会被随机生成的下一堵墙挡住——这会导致无法解决的迷宫。

问题是如何避免生成的墙不会阻挡先前打开的通道？

代码：

void RecursiveDivision::divide(NodesMap* map, int x, int y, int width, int 

height, Orientation orientation, SDL_Renderer* renderer)
{
    if (width < 2|| height < 2)
    {
        return;
    }

    bool wallIsHorizontal = orientation == Orientation::Horizontal ? true : false;

    //Where the wall is
    int wX = x  + (wallIsHorizontal ? 0 : rand() % (width-1));
    int wY = y + (wallIsHorizontal ? rand() % (height-1): 0);
    //Where the passage is
    int pX = wX + (wallIsHorizontal ? (rand() % width) : 0);
    int pY = wY + (wallIsHorizontal ? 0 : (rand() % height));
    //How long is the wall
    int wallLenght = (wallIsHorizontal ? width : height);
    //On whitch axis will the wall be drawn
    int dX = wallIsHorizontal ? 1 : 0;
    int dY = wallIsHorizontal ? 0 : 1;
    //Draw the wall
    for (int i = 0; i < wallLenght; ++i)
    {
        if (wX != pX || wY != pY)
        {
            map->getNode(wX, wY)->hardChangeState(NodeState::OBSTACLE);
        }
        
        wX += dX;
        wY += dY;
    }

    //Render the current state
    map->render(renderer, nullptr);
    SDL_RenderPresent(renderer);
    
    int nX = x; int nY = y;
    int w = wallIsHorizontal ? width : (wX - x);
    int h = wallIsHorizontal ? (wY - y ) : height;
    divide(map, nX, nY, w, h, chooseOrientation(w, h), renderer);

    nX = wallIsHorizontal ? x : (wX + 1);
    nY = wallIsHorizontal ? (wY + 1) : y;
    w = wallIsHorizontal ? width : (x + width - wX -1);
    h = wallIsHorizontal ? (y + height - wY-1 ) : height;
    divide(map, nX, nY, w, h, chooseOrientation(w, h),renderer);
}

示例：

2 step from the start of algorithm

示例 - 20x20 瓦片地图上的“完成的迷宫”：

Finished algorithm

备注

您看到的屏幕截图来自程序的单独运行，因此它们有所不同。希望你能明白我的意思。

Answer 1

与您受到启发的 link 相比，您的墙壁采用 space 一个单元格。避免您的问题的最简单方法是您的墙只能放置在两个中的一个 column/row 上。

这就是“薄壁”迷宫的结果

这是厚壁的等效物（您正在使用的）

如你所见，它们的网格大小不一样，第一个是 3x3，最后一个是 5x5，没有边框（因为你的没有边框所以编辑了）。

您需要有奇数边的网格。如果它基于薄迷宫，则将边扩大 2 * n - 1，其中 n 是薄迷宫边的长度*
只在奇数行和奇数列上放置墙（从索引 0 开始）
在偶数行和偶数列的墙上放置开口

To resume, you can place walls

o o o o o
o o o o o <- here
o o o o o
o o o o o <- here
o o o o o
  ^   ^
here  here

(*) 2n - 1 是无边界的，否则使用 2n + 1

如何在您的代码中实现：

    const int truewidth = (width-1)/2;
    const int trueheight = (height-1)/2;
    //Where the wall is
    int wX = x  + (wallIsHorizontal ? 0 : 2 * (rand() % (truewidth)) + 1);
    int wY = y + (wallIsHorizontal ? 2 * (rand() % (trueheight)) + 1: 0);
    //Where the passage is
    int pX = wX + (wallIsHorizontal ? 2 * (rand() % (truewidth)) : 0);
    int pY = wY + (wallIsHorizontal ? 0 : 2 * (rand() % (trueheight)));

/!\ 尚未测试

迷宫生成算法设计（递归划分）

Maze generation algorithm design (Recursive Division)

c++

algorithm

recursion

maze

matrix