我试图在我的寻路可视化解决方案中包含一个迷宫生成,以便生成当前应用程序可以处理的迷宫。
我找到了一个结构很好的网站,里面有很多迷宫生成算法,但我主要关注一个: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
备注
您看到的屏幕截图来自程序的单独运行,因此它们有所不同。我希望你能明白这一点。
最佳答案
与您获得灵感的链接相比,您的墙壁占据了一个单元格的空间。避免您的问题的最简单方法是您的墙壁只能放置在两列/行中的一列/行上。
这就是“薄壁”迷宫会产生的结果
这是厚墙的等价物(你正在使用什么)
如您所见,它们的网格大小不同,第一个是 3x3,最后一个是 5x5,没有边框(编辑因为你的没有边框)。
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)));
/!\尚未测试
关于c++ - 迷宫生成算法设计(递归除法),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63577921/