Unity3D Maze 迷宫生成算法

1个月前 (01-07 09:05)阅读1回复0
zaibaike
zaibaike
  • 管理员
  • 注册排名1
  • 经验值165935
  • 级别管理员
  • 主题33187
  • 回复0
楼主

情况: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

0
回帖

Unity3D Maze 迷宫生成算法 期待您的回复!

取消