c++ - 迷宫生成算法设计(递归除法)

Question

我试图在我的寻路可视化解决方案中包含一个迷宫生成，以便生成当前应用程序可以处理的迷宫。
我找到了一个结构很好的网站，里面有很多迷宫生成算法，但我主要关注一个:http://weblog.jamisbuck.org/2011/1/12/maze-generation-recursive-division-algorithm
我的编程语言知识主要是 C++，而我拥有的应用程序是用 C++ + SDL2.0 构建的。
我的“网格”(2D 矩阵)由“单元格/节点”组成，由窗口表面上呈现的框纹理表示。每个“细胞”可以处于不同的状态 - 障碍 == 它是一堵墙 - 白色状态 == 它是 channel 。
我面临的一个问题是，我的“ channel ”有时会被随机生成的下一堵墙挡住——这会导致无法解决的迷宫。
问题是如何避免生成的墙不会阻塞先前打开的 channel ？
代码:

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 平铺 map 上的“完成迷宫”:
Finished algorithm
备注
您看到的屏幕截图来自程序的单独运行，因此它们有所不同。我希望你能明白这一点。

Answer 1

与您获得灵感的链接相比，您的墙壁占据了一个单元格的空间。避免您的问题的最简单方法是您的墙壁只能放置在两列/行中的一列/行上。
这就是“薄壁”迷宫会产生的结果

这是厚墙的等价物(你正在使用什么)

如您所见，它们的网格大小不同，第一个是 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)));

/!\尚未测试