1 行代码生成随机迷宫,概率编程语言登 GitHub 热榜,作者曾开发著名 WFC 算法
消息来源:baojiabao.com 作者: 发布时间:2024-05-17
探索游戏中的迷宫很有趣,然而玩多了就没啥"新鲜感"了?
没错,如果游戏迷宫差别不大,时间一久就容易熟悉地图,降低了探索的乐趣。
现在,一个"横空出现"的概率编程语言 MarkovJunior 解决了这一问题:
利用马尔科夫算法,随机生成批量迷宫,没有一个是重复的,你永远也不知道玩到的下一个迷宫长什么样子:
不仅是 2D 迷宫,就连需要搭建好几层地图的 3D 迷宫,也能随机生成:
这个项目一出,立刻上了 GitHub 热榜,不到一周就已经收获 2.6k Star。
有网友感叹,用这个编程语言就能直接给 RPG 游戏或动作游戏生成建筑了。
Keras 的作者也对这个概率编程语言挺感兴趣:
来看看它的原理究竟是什么、又是如何随机生成各种迷宫的。
基于马尔科夫算法构造
据作者介绍,这套概率编程语言借鉴了马尔科夫算法(Markov algorithms)。
(MarkovJunior 这个名字,也是以提出马尔科夫算法的数学家 Andrey Markov 命名)
具体来说,这套概率编程语言由一系列特定规则(Rewrite Rules,重写规则)组成,是一个有序列表。
它在生成一个(迷宫)模型的过程中,会利用马尔科夫算法实现"随机生成",再通过制定一系列特定规则,决定生成模型的类别,例如是迷宫、地形图,还是电路图等。
马尔科夫链具有"无记忆"性质,即下一状态的概率分布只能由当前状态决定,在时间序列中它前面的事件均与之无关。
所以,这些特定规则究竟长啥样?
例如,一个最简单的规则,就是将"黑色"色块重写为"白色"色块,直到最终填满整个模型:
又例如,执行将"白-黑"色块重写为"白-白"色块的规则,结合马尔科夫算法,就能得到一个概率生成模型:
再例如,基于"推箱子游戏"的规则,
△ 推箱子游戏
就能用这批小红点随机将白色方块"搬运"到指定地点:
像这样的特定规则还有很多,都包含在 MarkovJunior 中。
那么,我们究竟要怎么利用这些规则,来生成一个随机(迷宫、电路图等)模型呢?
2D / 3D 迷宫、地形图和电路图都能画
先以随机生成一个 2D 迷宫为例:
从图片中来看,这个迷宫算法会自动生成一个"起始点"红点,在一块黑色地图中随机探索并重写路径,最终填满整个地图,完成一个有始有终、也有分岔口的"迷宫"。
这样的随机迷宫,MarkovJunior 随手就能做出一大把,只需要基于两个规则:
第一个规则,将"红-黑-黑"色块随机重写为"绿-绿-红"色块。
第二个规则,在第一个规则被"卡住",也就是没有符合条件的可选项时,自动执行将"红-绿-绿"色块随机重写为"白-白-红"色块。
这样一来,算法就能通过第一个规则生成随机路径,并通过第二个规则回溯还没有经过的路径、生成岔路口,最终遍历整个黑色地图,生成一套"2D 迷宫"。
还有更简单的思路,将所有"白-黑-黑"替换成"白-A-白",其中 A 是一个中间态,不作为起点,在迷宫生成完成后被替换为白色。
据作者表示,利用这个规则,1 行代码就能随机生成 2D 或 3D 迷宫。
▲ 3D 迷宫长这样
基于这样的思路,换套规则组合方法,还能生成随机地形图。
例如,试图生成一块河流地形图,就只需要利用上面的生成模型方法,再添加一些其他的重写规则,就能搞出一个随机河流图来:
除了地形图、简单的 2D / 3D 迷宫,更复杂的 3D 建筑也能搞定,只需要在两层 2D"迷宫"之间的随机位置生成一批"楼梯":
嗯,连电路图都能画……
据作者介绍,只要灵活运用这些规则,就能用 MarkovJunior 随机生成各种各样的建筑和图画。
可以说是非常好用了。
还是著名 WFC 算法的作者
这个概率编程语言的作者 Maxim Gumin,是一名独立游戏开发者。
他搞过最有名的项目,应该是一套叫做"波函数坍缩算法"(WaveFunctionCollapse,WFC)的东西,目前在 GitHub 上已经有 18.7k Stars。
这套 WFC 算法是他受量子力学中"波函数坍缩"概念的启发自创出来的,目前已经被应用到一些游戏中,如《城镇叠叠乐》(Townscaper)等。
Maxim Gumin 并未透露更多自己的信息,但我们能在他的主页上看到,这位老哥自称"概率模型之王,程序化生成の弥赛亚,驯服马尔科夫链的人……"(手动狗头)
从 GitHub 来看,这些年他一直专注于将各种数学算法应用于程序化生成中,做出各种有意思的模型。
说不定你玩过的游戏中,有一些已经用过他开发的算法了。
项目地址:
https://github.com/mxgmn/MarkovJunior
2022-12-19 17:52:43相关文章
- 美国法院裁定阿里须为Squishmallows玩具侵权案答辩
2023-12-28 19:59:34
- 小米汽车传员工3700人 雷军称小米汽车不可能卖9万9
2023-12-28 19:41:57
- 国家新闻出版署:认真研究《网络游戏管理办法(草桉徵求意见稿)》关切 实行前进一步完善
2023-12-28 19:14:56
- 天猫新规可以无条件申请“仅退款”了?淘宝天猫又离狗多多零元购近了一步
2023-12-28 18:57:55
- 印度以打击金融犯罪为由逮捕了两名 vivo 高管
2023-12-26 16:49:01
- 在国外微信收不到国内信息?微信和WeChat将被拆分
2023-12-15 10:40:15
- 苹果iPhone15 系列手机发布最新消息 预计上市发布时间9月
2023-08-06 23:21:02
- 华为将发布鸿蒙HarmonyOS4操作系统 功能五大升级支持设备清单
2023-08-06 23:17:37
- 整治自媒体网红账号 400万粉丝网红发布擦边视频被无限期封禁
2023-07-12 09:56:09
- 网传微信文件传输助手是真人是真的吗?微信官方回应
2023-06-27 15:53:32
- 电信移动送手机成了“信用购”?你上了运营商的贷款套路了吗?
2023-06-12 17:18:55
- 中国电信广东地区崩了无信号 客服回应已在核实处理
2023-06-08 15:39:04
- 消息称小米新能源汽车价格表正讨论定价区间:双版本不同配置,高配或超 35 万元
2023-03-06 12:56:03
- 华为因制裁被传或分拆剥离手机业务? 内部人士回应:可能性不大.
2023-03-05 23:26:41
- OPPO正式发布安第斯智能云,让终端更智能
2023-02-24 16:02:27
- 华为与OPPO签订全球专利交叉许可协议 包括5G蜂窝通信专利
2023-02-24 16:02:26
- 老蛙将推MINI镜头新品:目前未知具体规格 官宣将于12月20日发布
2023-02-24 16:02:26
- 首发全新35mm定制光学系统 努比亚Z50性能同样强悍
2023-02-24 16:02:25
- Redmi K60屏幕细节曝光:全系标配2K护眼柔性直屏+5000mAh大容量电池
2023-02-24 16:02:25
- OPPO Find N2今天发 合金金属折叠屏更轻了
2023-02-24 16:02:24