无限迷宫生成算法

Question

我搜索甚至访问了一个迷宫算法收集网站，但没有满足我要求的以下陈述。
为了清楚起见，我需要一个无限迷宫生成算法：

生成 perfect maze ，也就是说，
1. 2d,grid-based
2. 每个方格是space/wall
3. 每 2 space 链接并且只有一个路径
4. 没有 2x2 正方形是全部 space/wall
提供一个f(s,x,y)，其中s用于random seed或类似的东西
1. returns (x,y) 处的正方形类型
2. 对于0~（32768左右）内的不同s，给出不同的结果
无限（虽然可能受限于 64 位 int）
允许额外的space（我的意思是在程序中）

澄清：

此处无限的含义：类似这样

function f(s,x,y){
    // for each x,y it gives a result, so we consider it "infinite"
    return (s*x+y)%32768<30 ? "wall" : "space";
}

这是一个有限算法（满足1）

init:all walls
choose a square,flag it and add to list
while(list not empty)
{
    chose randomly from list
    delete from list
    if(there's a flag)
    {
        delete it
        continue
    }
    make a flag
    if(surrounding wall num≤1)
    {
        add 4 surrounding walls to list
    }
}

某事满足 1 和 3
我们从埃勒算法开始

it is generated row by row, and saves a set of regions

first row:all regions into a set,wall between regions(randomly)
while(not last row){
    foreach(neighbour regions){
        if(not in the same set){
            break their wall and merge the regions(randomly)
        }
    }
    foreach(region){
        break the wall below(randomly,and at least one does this)
    }
    generate next row
    for this row:{
        foreach(region){
            if(connected with above){
                merge to prev-set
            }
        }
        throw away prev-prev-set
    }
}
last row:connect all regions that are not in the same set

如果我们从圆心开始，一圈一圈地生成，可以无限大；遗憾的是我们有规则 2.

Answer 1

这个问题似乎有点难以解决：无限多的无限迷宫，这样我们就可以将自己限制在多个不同的范围内（比如，如果我们想要一个大约 100 万 x 100 万的正方形）并且仍然有独特的路径任意两个 space（以及您的其他条件）。让我们把它分解成更小的部分。

假设我们可以构建一个 7 x 7 的正方形迷宫块，并且能够在它周围制作一个边界墙，在我们想要的边界上有一个或两个门。那么我们所要做的就是将这些方块连接成螺旋状：一个顶部有一个门的中央正方形，以及一个逆时针螺旋的方块，每个方块有两个门，在螺旋方向：

（每个编号的方框是一个 7x7 的迷宫）

一般有两种情况：

'Straight' 件，其中两个门在相对的两侧，并且
'Corner' 件，其中螺旋转弯和门在相邻的边上。

我们想让这些部分通用，这样我们就可以混合搭配迷宫并将它们组合在一起。为此，我们将使用此模板：

边界规则：每个方块的底部和左侧都是墙，每边的中心除外。
免费 space 规则：除非规则 1 或 3 要求，否则迷宫正方形的顶部和右侧不允许有墙壁。
门规则：两个迷宫相遇的地方，如果相遇是螺旋的一部分，则中心两侧都将打开（换句话说，交叉点发生在边界的中心）。否则，另一个迷宫下方或左侧的迷宫应在此边界的中央有一堵墙。

太多了，让我们看一个例子。这里我们有一个 'straight' 水平连接器的模板，以蓝色突出显示（所有迷宫都是 7 x 7）。 X 表示墙，O 表示需要打开（两个迷宫之间的交叉 point/open 门）。红色 X 是规则 1 的边界，紫色 X 是规则 3 的封锁门。

每个迷宫的中心 5 x 5 是可定制的。我们必须确保只有在我们的迷宫中 没有不可访问的正方形或等于 2x2 ，因为上述规则保证了迷宫相遇的地方。

适合上述模板的一个可能的迷宫（有很多）：

以角件为例：

我已经为每个可能的连接绘制了类似的示例，以确保它总是可能的：对于每种棋子类型（包括特殊的中心棋子），有很多可能的方法可以做到这一点。

现在，如何根据一个种子生成无限多的无限迷宫。假设您为每个连接件创建了至少 2 个示例（有 2 个直连接器和 4 个角），尽管您可以只制作一个并反映它。（实际上，您只需要一种连接类型的 2 个不同示例。）

给定任何种子二进制字符串，例如10110，让这表示我们在制作迷宫螺旋时选择使用哪个示例块，如第一张图片所示。 “0”表示使用我们的第一个示例作为此连接器； '1' 表示我们使用第二个。然后，您可以无限地重复 this/extend 二进制字符串 (10110 10110 ...)。由于这是周期性的，我们可以使用一些数学计算出序列中任意点的片段类型。

我省略了连接类型模式的数学运算：逆时针螺旋很容易计算出来。给定这种模式，并且约定点 x,y = (0,0) 是螺旋开始迷宫块的左下角，您可以计算出任意 x 和 y 的 'wall or space'。这个迷宫是无限的：您还可以将边界限制为螺旋形迷宫中任何完整的奇数正方形，即 (7*(2n+1))^2 个正 n 的单元格。

这个迷宫的框架模式是可以定制的，但不是很难解决，因为规律性意味着你只需要在本地解决它。 7 没什么特别的；如果你想让局部迷宫块更大更复杂，任何至少 7 的奇数都应该同样适用于相同的规则。

无限迷宫生成算法

Infinite maze generating algorithm

algorithm

maze