Unity3D Maze 迷宫生成算法

LiteralliJeff · 发表于 2022-5-31 15:04

环境：Unity2021.1.14 语言：C#
总起

本文的源代码可以在以下网址的TestMaze中找到：
https://github.com/anguangzhihen/TestOdinInspector
《人工智能与游戏》关于PCG文章的末尾提供了一个生成迷宫的练习：
https://catlikecoding.com/unity/tutorials/maze/
该练习对Unity中使用的常规技术讲解的十分详细，很适合刚接触Unity的新手，当然本文不会对Unity过多的展开。

该工程的主要代码在TestMaze中，游戏开始会启动一个协程，用于创建地板（Cell）和墙壁，我们主要聚焦的就是这生成步骤的实现。后续原文的实现中还会有装饰画、门、合并房间的内容，我这边就不继续了。

原文默认使用的生成算法是随机深度优先算法，这属于PCG算法中的树搜索内容（我们常用的A*是广度优先搜索的变种，所以A*也属于树搜索），而进化算法属于搜索算法的大类，但它们不过构建搜索树，只会从全局角度考虑完整的解决方案。
而本文主要介绍针对Maze生成常用的一些算法，主是树搜索算法，而运用到的一些原理会涉及图论的知识。
算法

随机深度优先算法
该算法会随机探索方向生成通路，直到四面没有生成空间，就会回溯之前生成节点继续随机探索。

最小生成树 Prim算法
算法实现原理其实跟随机深度优先算法类似，只不过没有回溯的过程，而是每次随机挑选已经生成Cell再随机选方向生成。
最小生成树算法除了Prim算法，Kruskal算法也能生成类似的迷宫。这类算法生成迷宫更加的破碎，而随机深度优先算法则会有很多长走廊。

均匀生成树威尔逊随机游走擦除算法
该算法原理是随机挑选一个未生成Cell作为起始点，然后随机选择方向开始“游走”，直到碰到了已经生成Cell作为终点，走过的路径就作为通道进行生成。
它生成迷宫的破碎程度在上两个算法之间。
这个算法最大的问题在于效率很低，特别是生成特别大型的迷宫，它会在未走过的区域来回游走，导致一直连通不到已生成的路径（当然我们可以通过一些trick进行优化）。
Aldous-Broder算法也是通过均匀生成树来生成迷宫，但它的效率比威尔逊算法更差。

二叉树算法
该算法需要选择一个起点，并决定好方向，这边的方向是左上，因此整体迷宫会有左上的趋势，最终在右边和下边合为一整个迷宫。
通过该算法生成的迷宫结构上会比较类似，但好处是不需要额外的存储空间。

Eller算法
该算法可能是最神奇的算法，它不需要额外的存储空间，通过随机合并集合就能无限向下生成迷宫。
这个算法的实现我卡了一段时间，其实不复杂，关键在于先将所有的墙生成出来，然后通过砸墙的方式合并邻居。

其他算法：
1. 递归除法，该算法类似之前文章提到的空间分割法；
2. 元胞自动机；
3. Hunt and Kill算法，随机深度优先搜索的优化版本，舍弃栈结构。
参考

《人工智能与游戏》
https://catlikecoding.com/unity/tutorials/maze/
https://en.wikipedia.org/wiki/Maze_generation_algorithm
https://www.bilibili.com/video/BV1dz411e7WG
https://weblog.jamisbuck.org/archives.html
https://en.wikipedia.org/wiki/Loop-erased_random_walk

		自动登录	找回密码
密码			立即注册

Unity3D Maze 迷宫生成算法

本帖子中包含更多资源