无限迷宫生成算法

Question

我搜索了很多迷宫算法收集网站，但没有一个能满足我需要的以下条件。

为了明确，我需要一个无限迷宫生成算法，其遵循以下规则：

1. 生成一个“完美迷宫”，即：
   1. 二维和基于网格
   2. 每个网格都是空格或墙壁
   3. 每两个空格之间都有一条路径，且只有一条路径
   4. 没有2x2的正方形全是空格/墙壁（使其看起来漂亮）
2. 可以提供类似于f(s, x, y)的函数，其中s用于随机种子或类似的东西
   1. 返回(x, y)处的网格类型
   2. 对于0~(32768或其他)范围内的不同s，给出不同的结果
3. 无限（可能受到64位整数的限制）
4. 允许额外的空间（我的意思是在程序中）

澄清：

1. 这里的无限含义：类似于这样的东西

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: filled with walls
choose a grid, tag it and add it to list
while (list is not empty)
{
    choose <x> randomly from the list
    delete <x> from the list
    if (<x> is tagged)
    {
        delete <x>
        continue
    }
    tag <x>
    if(number of surrounding walls ≤ 1)
    {
        add 4 surrounding walls to list
    }
}

某些满足第1点和第3点的内容 我们从Eller算法开始

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。

- Rratic

---

你所说的 "infinite" 是指在 64 位内的任意维度，还是真正的无限大？ - 500 - Internal Server Error

展示你所尝试的，告诉我们你所遇到的问题。我已经展示了我所搜索的内容，我写了一些算法，但是它们并没有取得任何进展。顺便说一下，这个问题无法分割，很抱歉。 - Rratic

@RBarryYoung已添加 - Rratic

@user58697 我相信我可以做到这一点。我并没有将其视为限制，而是作为功能描述。无论如何，我认为除了“没有所有墙壁2x2单元格”之外，我都可以做到一切。 - RBarryYoung

经过一些努力，任务1和3可以完成（稍后我会进行编辑），而困难的部分是任务2。顺便说一下，“不全是2x2的单元格”对于迷宫来说相当普遍。 - Rratic

Answer 1

这个问题似乎有些令人不知所措：有无限多个无限迷宫，我们可以将自己限制在许多不同的范围内（比如说，如果我们想要一个大约100万×100万的正方形），并且仍然在任何两个空间之间有唯一路径（以及其他条件）。让我们把它分解成更小的部分。

假设我们能够构建一个7×7的迷宫块，并且能够在其周围建立一堵墙，其中有一到两个门。然后我们只需要用螺旋连接这些正方形块：一个中央正方形，顶部有一个门，以及一个带有每个两个门的逆时针螺旋方向的块序列：

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

---

有两种一般情况：

• '直'段，其中两个门位于相对的两侧
• '拐角'段，其中螺旋转向并且门位于相邻的两侧。

我们希望使这些部分通用，以便我们可以混合和匹配迷宫并使它们适配在一起。为此，我们将使用此模板：

1. 边框规则：每个正方形的底部和左侧都是墙壁，除了每个侧面的中心。
2. 自由空间规则：除非规则1或3所要求，否则迷宫正方形的顶部和右侧不允许有墙壁。
3. 门规则：当两个迷宫相遇时，如果会议是螺旋的一部分，则两个中心侧面都将开放（换句话说，交叉发生在边界的中心）。否则，位于下方或左侧的迷宫应在此边界的中心处设置墙壁。

这有一个示例，展示了一个“直”的水平连接器的模板，用蓝色标出（所有迷宫都是7x7）。X表示墙壁，O表示需要开放（两个迷宫之间的交叉点/开放门）。红色X是规则1的边界，紫色X是规则3中被阻塞的门。

每个迷宫的中心5x5可定制。我们必须确保在我们的迷宫中没有无法到达的方格或2x2相等的方格，因为上述规则保证了迷宫相遇的地方是正确的。

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

一个角落的例子：

我同样绘制了每种可能连接的示例，以确保始终可以连接：对于每种块类型（包括特殊的中心块），都有许多可能的连接方式。

---

现在，让我们来看一下如何基于一个种子生成无限多的迷宫。假设您至少创建了每个连接块的2个示例（有2个直线连接器和4个角落连接器），虽然您可以只制作一个连接块并进行反射。（实际上，您只需要2个不同的连接类型示例。）

给定任何种子二进制字符串，例如10110，让它代表我们在制作迷宫螺旋时使用哪个示例块的选择，从第一张图片开始计数。‘0’表示使用第一个示例，‘1’表示使用第二个示例。然后，您可以无限地重复/扩展二进制字符串（10110 10110 ...）。由于这是周期性的，因此我们可以使用一些数学方法，找出序列中任何点的块类型。

我省略了连接类型的数学模式：对于逆时针螺旋，这很容易计算。根据此模式，并且约定点x，y =（0,0）是螺旋起始迷宫块的左下角，您可以计算出任意x和y的“墙壁或空间”。该迷宫是无限的：您还可以将边界限制为螺旋中任何完整的奇数正方形的迷宫，即（7 *（2n + 1））^ 2 个单元格，其中n为正数。

该迷宫的框架模式可定制，但解决起来并不是很困难，因为规则性意味着您只需要在本地解决它。 7没有什么特别之处;如果要使局部迷宫块更大更复杂，则任何至少为7的奇数都应该使用相同的规则。

- kcsquared

---

看起来不错，我稍后会写代码然后“接受”并点赞。 - Rratic

我改进了算法，使得迷宫块内部可以使用种子随机生成。 - Rratic

@Rratic 非常棒，你使用了其中一个其他 迷宫算法生成里面的部分吗？将你的代码发表为自己的答案可能很值得。 - kcsquared

很好，这很简单，请注意，一个有限的完美迷宫（没有整墙边缘）在边缘的特定位置有空间。 - Rratic

好的，我在内部使用了一个4块断开算法，但可能不在那个链接中。 - Rratic

Answer 2

我想我需要详细解释一下我的答案。

这是JavaScript代码：

// C-flavour random
let gsrand = 0
function srand(x) { gsrand = x }
function rand() {
    gsrand = (gsrand*1103515245+12345)&0xffffffff
    return gsrand>>16 & 32767
}

class Chunk{
    matrix
    constructor() {
        // suppose the map is divided into 64×64 chunks
        this.matrix = new Uint8Array(4096)
    }
}

Chunk.prototype.put = function(x, y, type) {
    this.matrix[x<<6|y] = type == 'space' ? 0 : 1
}

/* * * Core * * */
Chunk.prototype.generate__infmaze_4 = function(lx, ly, rx, ry) { // split the map recursively
    let x0 = rx - lx
    let y0 = ry - ly
    // room small enough (width = 1)
    if(x0==0 || y0==0) {
        for(let i = lx; i <= rx; i++) {
            for(let j = ly; j <= ry; j++) this.put(i, j, 'space')
        }
        return
    }
    let mx = lx+2*(rand()%(x0>>1))+1
    let my = ly+2*(rand()%(y0>>1))+1
    for(let i = lx; i <= rx; i++) this.put(i, my, 'wall')
    for(let i = ly; i <= ry; i++) this.put(mx, i, 'wall')
    // split the map into four smaller rooms
    this.generate__infmaze_4(lx, ly, mx-1, my-1)
    this.generate__infmaze_4(lx, my+1, mx-1, ry)
    this.generate__infmaze_4(mx+1, ly, rx, my-1)
    this.generate__infmaze_4(mx+1, my+1, rx, ry)
    // three exits serve as passages through rooms
    let d = rand()%4
    let myl = (my-ly+1) >> 1
    let myr = (ry-my+1) >> 1
    let mxl = (mx-lx+1) >> 1
    let mxr = (rx-mx+1) >> 1
    if(d == 0) {
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 1) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else if(d == 2) {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ry - 2*(rand()%myr), 'space')
    }
    else {
        this.put(lx + 2*(rand()%mxl), my, 'space')
        this.put(rx - 2*(rand()%mxr), my, 'space')
        this.put(mx, ly + 2*(rand()%myl), 'space')
    }
}
Chunk.prototype.generate__infmaze = function(x, y) {
    // chunks are isolated at first
    for(let i = 0; i < 64; i++) {
        this.put(i, 0, 'wall')
        this.put(0, i, 'wall')
    }
    // use the seed
    srand((x<<15 + y) ^ seed<<3)
    this.generate__infmaze_4(1, 1, 63, 63)
    // break the isolation between chunks
    let r1 = rand()%32
    this.put(2*(rand()%32) + 1, 0, 'space')
    this.put(0, 2*(rand()%32) + 1, 'space')
}

如果你想符合规则，只需让 f(s, x, y) 中的 s（即 srand 使用的种子）成为参数，并缓存由 new Chunk().generate__infmaze 生成的数据。

如果你已经注意到这不符合规则 1.3，你也会发现很容易修复它（只需更改破坏区块隔离的部分，但可能看起来不太好 :）。

演示（seed = 0，(0, 0) ⇒ (63, 63)）：

#############################.##################################
#.................................#.............................
#######.#########################################.##############
#...........#...#.#.#.........#.#.#.......................#.#.#.
###.#####.#.#.#.#.#.###.#####.#.#.#.#####################.#.#.#.
#.......#.#.#.#...#.#.#.#.#...#.#.#.#...#.......#.#.......#.#.#.
#####.###.###.#.#.#.#.#.#.###.#.#.#.#.###.###.###.#####.###.#.#.
#.#.#.#.#.#...#.#.#.....#.#.#.#.#.#.#.....#...............#.#...
#.#.#.#.#.#.###.#.#.###.#.#.#.#.#.#.#.#.#.###.#####.#######.#.#.
#.#.#.#.#.#.#.#.#...#...#...#...#.#.#.#.#.#.......#.........#.#.
#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###########.###########.#.#.
#.#.#.#.#...#...#.#.#...#.#...#.#.#.#...................#.#.#.#.
#.#.#.#.#.#.###.#.#.#########.#.#.#.#.#.#.#####.#######.#.#.#.#.
#.#...#.#.#.#...#.#.....#.....#.#.#.#.#.#.#...........#.#.#.#.#.
#.#.#.#.#.#.#####.#########.###.#.#.#.#.#.###.###########.#.#.#.
#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#...#.....#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.###.#.###.#.#.#.#.
#.#.#.#.#.#.#.#...#.#.#...#.#.#.#.#.#.#...#.#.........#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.###########.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#...#...#.#.#.#.#.#.#.#.............#.#.#.
#####.###.#.#.#.###.#.###.#.###.#.#.#.#.#.#####.#########.#.#.#.
#...#.#.#.#.#...#.#...#.......#.#...#...#.#.............#.#.#.#.
#.###.#.#.#.#.#.#.#.#.#.#####.#.#.#########################.#.#.
#.......#.#.#.#...#.#.#...#...#.#.#.......................#.#.#.
#.#.#.###.#.#.#.#####.#######.#.#.#######################.#.#.#.
#.#.#...#.#.#.#...#...........#.#.#...........................#.
#########.###################.#.#.###########################.##
#.......#.#.#.......#.........#.#.#.#...............#.....#.#.#.
#.#####.#.#.#.#.#######.#######.#.#.#.###############.#####.#.#.
#.#...#.#...#.#.#...#.#.#.....#.#.#.#.........#.....#.....#.....
#.#.#.#.#.#.#.#.###.#.#.#.#####.#.#.###.#########.#######.#.#.#.
#...#.#.#.#.#.#.#.#.#.........#.#.#.#.........#.....#.......#.#.
###.###.#.#.#.#.#.#.#.#.#######.#.#.###.#######.#####.#####.#.#.
#.....#.#.#.#.#.#.#.#.#.......#.#.#.................#.....#.#.#.
###.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#############.#######.#####.#.
..#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...#.#.#...#...#.#.....#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.###.#.#.#.#.#.###.#.#.#.#####.#.#.#.
#...#.#.#.#.#.#.....#.#.#.#...#.#.#.#.#.#...#...#.#.#...#.#.#.#.
#.#.#.#.#.#.#######.#########.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.
#.#.#.#.#.#.#.#...#.#...#.#...#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.#.....#.#.#.#.#.#...#...#.#.
#######.###.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#####.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#...#.....#.#.#.#.#.#.#.#.....#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.###.#.#.#.#.#.#.#.###.###.###.#.#.#.#.#.#.#.#.#.
#.#.#...#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#...#.#.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.###.#####.#.#.#.#.#.###.#####.#.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#.#.#.#.#...#.#.#.
#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.###.#.#.#.#######.#.
#.#.#.#.#.#.#.#.#...#.#.#.#...#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.#.
#.###.#.#.#.#####.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.
#...#.#.#.#.#...#.....#.#.#.#.#.#.#.#.#.#.......#.#.#.#.#.#.#.#.
###.#.#.#.#.#.#.###.#.#.#.#.#.#.#.#.#.#.###########.#.#.#.#.#.#.
#.#.#.#.#.#.#.#.#.#.#.......#.#.#.#...#.#...............#.#.#.#.
#.#.#.#.#.#.#.###.#.###.#.#.#.#.#.###############.###.#.#.#.#.#.
#.....#.....#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.....#...#.#.#...#.#.#.
#######.#.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#######.#.#####.#.#.#.
#.....#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...........#.#...#...#.#.
###.###.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#########.#.#.#.#.#.#.
#.......#...#.......#.#.#.#.#.#.#.#.#...#...#.......#.#...#.#.#.
#.#################################.#.###.#.#####.#.#.#.#.#.#.#.
#...............................#.#.#...#.#.#.....#.#.#.#.#.#.#.
###########################.###.#.#.#.#####.#.#####.#.#.#.#.#.#.
#.............................#...#.....#.........#.#.#.#.#.#.#.

- Rratic