Miklix

威尔逊算法迷宫生成器

已出版: 2025年2月16日 UTC 19:34:51

迷宫生成器使用威尔逊算法来创建完美的迷宫。该算法以相同的概率生成给定大小的所有可能迷宫,因此理论上可以生成许多混合布局的迷宫,但由于走廊较短的迷宫比走廊较长的迷宫更多,因此您会更经常看到这些迷宫。

为了使尽可能多的人能够访问本页面,本页面由英文机译而成。遗憾的是,机器翻译技术尚不完善,因此可能会出现错误。如果您愿意,可以在此处查看原始英文版本:

Wilson's Algorithm Maze Generator

Wilson 算法是一种循环擦除随机游走方法,可生成均匀生成树来创建迷宫。这意味着给定大小的所有可能迷宫都有同等的可能性生成,使其成为一种无偏迷宫生成技术。Wilson 算法可以被认为是 Aldous-Broder 算法的改进版本,因为它可以生成具有相同特征的迷宫,但运行速度要快得多,因此我在这里没有费心实现 Aldous-Broder 算法。

完美迷宫是指从迷宫中的任何一点到其他任何一点都只有一条路径的迷宫。这意味着你不会兜圈子,但你会经常遇到死胡同,不得不掉头回去。

这里生成的迷宫地图包括一个没有起点和终点位置的默认版本,因此您可以自行决定起点和终点位置:从迷宫中的任何一点到其他任何一点都有解法。如果你想获得灵感,可以启用建议的起点和终点位置,甚至可以查看两者之间的解法。


生成新迷宫








关于威尔逊算法

使用循环擦除随机墙生成均匀生成树的 Wilson 算法由 David Bruce Wilson 创建。

Wilson 最初于 1996 年在研究概率论中的随机生成树和马尔可夫链时引入了该算法。尽管他的工作主要在数学和统计物理学领域,但该算法后来被广泛用于迷宫生成,因为它能够生成完美均匀的迷宫。

威尔逊算法如何生成迷宫

威尔逊算法通过使用随机游走迭代地从未访问的单元中开辟路径,确保最终的迷宫完全连通而没有任何循环。

步骤 1:初始化

  • 从布满墙壁的网格开始。
  • 定义所有可能的传代细胞的列表。

第 2 步:选择随机起始单元格

  • 选取任意一个单元格并将其标记为已访问。这在生成过程中用作迷宫的起点。

步骤 3:循环擦除随机游走

  • 选择一个未访问的单元格并开始随机游走(朝随机方向移动)。
  • 如果步行到达已经访问过的单元格,则删除路径中的所有循环。
  • 一旦步行连接到已访问区域,就将路径上的所有单元标记为已访问。

步骤4:重复,直到访问所有单元格

  • 继续选择未访问的单元格并进行随机游动,直到每个单元格都成为迷宫的一部分。
分享至 Bluesky在 Facebook 上分享在 LinkedIn 上分享在 Tumblr 上分享分享至 X在 LinkedIn 上分享在Pinterest上固定

米克尔·邦·克里斯滕森

关于作者

米克尔·邦·克里斯滕森
迈克尔 是 miklix.com 的创建者和所有者。他拥有 20 多年的专业计算机程序员/软件开发人员经验,目前全职受雇于一家大型欧洲 IT 公司。不写博客时,他把业余时间花在各种兴趣、爱好和活动上,这在一定程度上反映在本网站涵盖的各种主题上。