jjzjj

Unity3D Maze 迷宫生成算法

暗光之痕 2024-07-02 原文

环境:Unity2021.1.14 语言:C#

总起

本文的源代码可以在以下网址的TestMaze中找到:

https://github.com/anguangzhihen/TestOdinInspector

《人工智能与游戏》关于PCG文章的末尾提供了一个生成迷宫的练习:

Maze, a Unity C# Tutorial

该练习对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算法,随机深度优先搜索的优化版本,舍弃栈结构。

参考

《人工智能与游戏》

Maze, a Unity C# Tutorial

https://en.wikipedia.org/wiki/Maze_generation_algorithm

【硬核干货】图论到底是个什么玩意儿?图论入门:树与生成树 (Graph Theory: Tree and Spanning Tree)_哔哩哔哩_bilibili

The Buckblog

https://en.wikipedia.org/wiki/Loop-erased_random_walk

 

有关Unity3D Maze 迷宫生成算法的更多相关文章

  1. ruby - 使用 RubyZip 生成 ZIP 文件时设置压缩级别 - 2

    我有一个Ruby程序,它使用rubyzip压缩XML文件的目录树。gem。我的问题是文件开始变得很重,我想提高压缩级别,因为压缩时间不是问题。我在rubyzipdocumentation中找不到一种为创建的ZIP文件指定压缩级别的方法。有人知道如何更改此设置吗?是否有另一个允许指定压缩级别的Ruby库? 最佳答案 这是我通过查看ruby​​zip内部创建的代码。level=Zlib::BEST_COMPRESSIONZip::ZipOutputStream.open(zip_file)do|zip|Dir.glob("**/*")d

  2. ruby - 在 jRuby 中使用 'fork' 生成进程的替代方案? - 2

    在MRIRuby中我可以这样做:deftransferinternal_server=self.init_serverpid=forkdointernal_server.runend#Maketheserverprocessrunindependently.Process.detach(pid)internal_client=self.init_client#Dootherstuffwithconnectingtointernal_server...internal_client.post('somedata')ensure#KillserverProcess.kill('KILL',

  3. ruby - 如何使用 Ruby aws/s3 Gem 生成安全 URL 以从 s3 下载文件 - 2

    我正在编写一个小脚本来定位aws存储桶中的特定文件,并创建一个临时验证的url以发送给同事。(理想情况下,这将创建类似于在控制台上右键单击存储桶中的文件并复制链接地址的结果)。我研究过回形针,它似乎不符合这个标准,但我可能只是不知道它的全部功能。我尝试了以下方法:defauthenticated_url(file_name,bucket)AWS::S3::S3Object.url_for(file_name,bucket,:secure=>true,:expires=>20*60)end产生这种类型的结果:...-1.amazonaws.com/file_path/file.zip.A

  4. ruby-on-rails - Ruby on Rails - 为文本区域和图片生成列 - 2

    我是Rails的新手,所以请原谅简单的问题。我正在为一家公司创建一个网站。那家公司想在网站上展示它的客户。我想让客户自己管理这个。我正在为“客户”生成一个表格,我想要的三列是:公司名称、公司描述和Logo。对于名称,我使用的是name:string但不确定如何在脚本/生成脚手架终端命令中最好地创建描述列(因为我打算将其设置为文本区域)和图片。我怀疑描述(我想成为一个文本区域)应该仍然是描述:字符串,然后以实际形式进行调整。不确定如何处理图片字段。那么……说来话长:我在脚手架命令中输入什么来生成描述和图片列? 最佳答案 对于“文本”数

  5. ruby-on-rails - 如何生成传递一些自定义参数的 `link_to` URL? - 2

    我正在使用RubyonRails3.0.9,我想生成一个传递一些自定义参数的link_toURL。也就是说,有一个articles_path(www.my_web_site_name.com/articles)我想生成如下内容:link_to'Samplelinktitle',...#HereIshouldimplementthecode#=>'http://www.my_web_site_name.com/articles?param1=value1¶m2=value2&...我如何编写link_to语句“alàRubyonRailsWay”以实现该目的?如果我想通过传递一些

  6. ruby-on-rails - 如何在 Rails 3 中创建自定义脚手架生成器? - 2

    有这些railscast。http://railscasts.com/episodes/218-making-generators-in-rails-3有了这个,你就会知道如何创建样式表和脚手架生成器。http://railscasts.com/episodes/216-generators-in-rails-3通过这个,您可以了解如何添加一些文件来修改脚手架View。我想把两者结合起来。我想创建一个生成器,它也可以创建脚手架View。有点像RyanBates漂亮的生成器或web_app_themegem(https://github.com/pilu/web-app-theme)。我

  7. 报告回顾丨模型进化狂飙,DetectGPT能否识别最新模型生成结果? - 2

    导读语言模型给我们的生产生活带来了极大便利,但同时不少人也利用他们从事作弊工作。如何规避这些难辨真伪的文字所产生的负面影响也成为一大难题。在3月9日智源Live第33期活动「DetectGPT:判断文本是否为机器生成的工具」中,主讲人Eric为我们讲解了DetectGPT工作背后的思路——一种基于概率曲率检测的用于检测模型生成文本的工具,它可以帮助我们更好地分辨文章的来源和可信度,对保护信息真实、防止欺诈等方面具有重要意义。本次报告主要围绕其功能,实现和效果等展开。(文末点击“阅读原文”,查看活动回放。)Ericmitchell斯坦福大学计算机系四年级博士生,由ChelseaFinn和Chri

  8. 区块链之加解密算法&数字证书 - 2

    目录一.加解密算法数字签名对称加密DES(DataEncryptionStandard)3DES(TripleDES)AES(AdvancedEncryptionStandard)RSA加密法DSA(DigitalSignatureAlgorithm)ECC(EllipticCurvesCryptography)非对称加密签名与加密过程非对称加密的应用对称加密与非对称加密的结合二.数字证书图解一.加解密算法加密简单而言就是通过一种算法将明文信息转换成密文信息,信息的的接收方能够通过密钥对密文信息进行解密获得明文信息的过程。根据加解密的密钥是否相同,算法可以分为对称加密、非对称加密、对称加密和非

  9. Unity 热更新技术 | (三) Lua语言基本介绍及下载安装 - 2

    ?博客主页:https://xiaoy.blog.csdn.net?本文由呆呆敲代码的小Y原创,首发于CSDN??学习专栏推荐:Unity系统学习专栏?游戏制作专栏推荐:游戏制作?Unity实战100例专栏推荐:Unity实战100例教程?欢迎点赞?收藏⭐留言?如有错误敬请指正!?未来很长,值得我们全力奔赴更美好的生活✨------------------❤️分割线❤️-------------------------

  10. FOHEART H1数据手套驱动Optitrack光学动捕双手运动(Unity3D) - 2

    本教程将在Unity3D中混合Optitrack与数据手套的数据流,在人体运动的基础上,添加双手手指部分的运动。双手手背的角度仍由Optitrack提供,数据手套提供双手手指的角度。 01  客户端软件分别安装MotiveBody与MotionVenus并校准人体与数据手套。MotiveBodyMotionVenus数据手套使用、校准流程参照:https://gitee.com/foheart_1/foheart-h1-data-summary.git02  数据转发打开MotiveBody软件的Streaming,开始向Unity3D广播数据;MotionVenus中设置->选项选择Unit

随机推荐