Project1

标题: 自动生成的迷宫 [打印本页]

作者: guoxiaomi 时间: 2020-5-10 15:24
标题: 自动生成的迷宫
本帖最后由 guoxiaomi 于 2022-6-10 00:47 编辑

v0.6.2版本下载：https://7niu.gxmatmars.com/p1/pyramid_v0.6.2.zip
演示视频：https://www.bilibili.com/video/BV115411h7nd

最近开了个新坑，唯一的打怪地图是金字塔，因为懒得画地图，就搞了个随机生成。这样其实你在金字塔里上下层也是进的同一张地图，就很省事：

特殊设定：
1. 有些正方形的区块是“房间”，里面可以放些特殊的事件，图上地板颜色不一样
2. 有些宽度为1的横条或者竖条，两端被称为“角落”，角落里可以放宝箱或者是上下层的楼梯
3. 墙上开洞的地方（见下）可以放小怪，这样你必须打倒他们才能继续探索

算法是递归分割：在房间里画一个墙，然后墙上开个洞，这样就变成了2个房间，使用同样的方法直到无法画新的墙为止……不过还是有一些具体的细节需要处理这里就不提了

90x90的地图

作者: Mono_kyrin 时间: 2020-5-10 23:38
好像在天干宝典上看过

作者: enghao_lim 时间: 2020-5-11 01:21
我当年也写了个随机地图，结果测试游戏的时候把自己给搞疯了，最后乖乖的去画地图

，结果地图没画完就弃坑了

。
PS：我的随机生成是每次进入地图后才随机生成 XD。

作者: 89444640 时间: 2020-5-11 08:26
本帖最后由 89444640 于 2020-5-11 08:36 编辑

是个很强的方法，但是这种只有墙壁和敌人的迷宫会绕到吐

，
还是手动画吧ORZ
迷宫如果不是有很多事件场景单调了的话，可能让人走着犯困吧。
我为了让迷宫不单调，初期最大的那个迷宫
从这样修成了这样，

原件丰富了，而且管道不同遮挡增加了层次感。
xiaom兄的适合西林那种迷宫，游戏目的就是绕迷宫，内部结构单调，但是敌人和处理丰富而且死了就全没。
如果可能，这种迷宫我喜欢拆墙XD

作者: 九夜神尊 时间: 2020-5-13 23:25
脑子里面一直有一个想法，但是生活让我几乎不可能完成。
Random Word
整个游戏都是随机生成的，玩法类似于塞尔达传说那样的，要用到大量的随机生成谜题的算法。
你若有心开坑，我把已经归纳好的算法给你。

作者: guoxiaomi 时间: 2020-5-14 00:06
本帖最后由 guoxiaomi 于 2020-5-19 03:36 编辑

既然有人回复了，就顺便晒一下新坑里的金字塔，这个金字塔各层都是在游戏里随机生成的。不知道视频上传是否成功？

作者: Im剑侠客 时间: 2020-5-14 05:23
我要玩，我要玩！xiaomi兄做好了记得@我啊(●°u°●) 」

作者: fux2 时间: 2020-5-14 06:05
随机地图的本身实现不是太重要，重要的是合理性，这个数据真的难以安排

作者: guoxiaomi 时间: 2020-5-19 03:37
不会走迷宫？只要坐上扫地机器人，进入扫地模式……

作者: chd114 时间: 2020-5-24 23:40

guoxiaomi 发表于 2020-5-14 00:06
既然有人回复了，就顺便晒一下新坑里的金字塔，这个金字塔各层都是在游戏里随机生成的。不知道视频上传是否 ...

点进来能听到声音，但是看不到视频在哪

作者: b565185756 时间: 2020-5-25 07:42
郭兄大人依旧是神！

作者: if216 时间: 2020-5-25 08:07
代码和demo不拿出来贡献或者卖吗？

作者: guoxiaomi 时间: 2020-5-25 16:06
本帖最后由 guoxiaomi 于 2020-5-25 17:29 编辑

自动生成迷宫的demo：http://7niu.gxmatmars.com/p1/pyramid-0.1.zip。

这个版本应该是没有扫地机器人，墙壁也是同一个格子，缓存和效率都不理想，但是自动生成迷宫的核心代码基本定型了。

现在在写迷宫里的战斗，然后还要结合战斗做一些宝箱/敌人/房间的设计。等全部做完了就开源工程吧~

素材都是steam上买的，所以不能拿去用……

作者: SailCat 时间: 2020-5-26 01:27

作者: guoxiaomi 时间: 2020-5-26 02:09
本帖最后由 guoxiaomi 于 2020-5-26 02:42 编辑

SailCat 发表于 2020-5-26 01:27

我在设置的时候为了让地图好看点，做了3个改动：
1. 对所有可以生成墙的位置进行随机，这样房间分割时会倾向于创建平行于短边的墙
2. 正方形的房间不再递归，比较小就生成房间后续使用。如果比较大就直接中间全部掏空变成环形，这样应该可以减少玩家探索的压力？
3. 对于中等的房间(w+h<32)，有一定的概率不再递归，让迷宫不再那么方方正正，递归层数越大这个概率越高

然后我还生成了大量的楼梯和宝箱(~Lengthscale^1.5)，期望玩家能有一些短期的目标不会那么无聊

但是非常大的地图(>200x200)探索起来仍然很痛苦，能找到向下的楼梯基本上5min起，毕竟“迷宫”本来就是一件反人类的设计

作者: b565185756 时间: 2020-5-26 21:59

感觉可以做成一个自动扫地走迷宫，但是不需要玩家任何操作，只是静静的看着他走到多少层，因为是无限生成，所以可以一直走到999999999999999999999999999999层，反正挂机就行了。

作者: 九夜神尊 时间: 2020-5-26 23:11
重要的一个理论，就是倒过来生成。
当你生成一个最小单元的迷宫后，再增加时，只需要确认在原基础上增加图块后也合理即可，这样使用归纳法，可以确定最终的迷宫也合理。
例如随机推箱子地图，先随机出地图，目标，箱子。箱子在目标上然后随机移动一个箱子，只要移动后的箱子可以被还原，那当前地图就合理，继续移动，只要每次移动都合理，那么最终的地图就一定合理。

添加钥匙，开关，解锁等谜题的思路也一样，不过这时候不是随机移动了，是随机触发事件。
你需要一个侦察兵功能的对象，就是根据当前的状态，所有能探寻到的地方，然后逆向随机生成谜题，只要确认上一次状态合理，这一次状态可以回到上一次状态，那么生成的地图最终是合理的。

作者: guoxiaomi 时间: 2020-5-27 05:16
本帖最后由 guoxiaomi 于 2020-5-27 05:43 编辑

九夜神尊发表于 2020-5-26 23:11
重要的一个理论，就是倒过来生成。
当你生成一个最小单元的迷宫后，再增加时，只需要确认在原基础上增加图 ...

大概理解了你的想法。这就跟数独游戏一样，首先要创建一个填好的数独，然后一步一步的从里面移除一些数字，最终成为一个有一定难度的数独谜题。我称这个为谜题的“逆向设计”，这是一个很自然的方案，但个人认为这个方案的有自己的适用范围。

因为“逆向设计”有 2 个缺点：
其一，是难以控制问题的难度，因为这个思路只能保证“有解”，却难以保证是“唯一解”或者是“最优解”。举2个例子：比如游戏是还原魔方，从拼好的魔方一步步随机打乱，比如...20步吧。然而这个谜题的真实难度远不止20步就能解决的，套用常见的魔方公式通常需要上百步才能还原，而不懂魔方的人甚至会无法解决此问题。再比如，非单连通的迷宫里有门和钥匙。从迷宫的深处出发，依次执行关门，放钥匙，去关另一个门，放另一个钥匙...的行动。但由于迷宫里的房间有多个门，可能存在一条巧妙的路径，可以不用上全部的钥匙就能打开最终的宝箱。

其二，效率的问题，如果要尝试逆向模拟角色的行为，实现起来思路会比“正向设计”更复杂。参见https://rpg.blue/thread-481929-1-1.html，十字分割算法就是典型的“正向设计”，而深度优先遍历算法就有一点“逆向设计”的味道了。在生成巨大迷宫的时候，两者的执行效率天差地别。

所以这里我还是想说说如何做“正向设计”。根据我们现有的数学知识，可以知道有些谜题是可解的，并且难度可控。比如R7里的拼图谜题。在初始结构的逆序数和结尾的逆序数相同的时候，谜题一定有解（反之则无），而解决谜题的方法只需要从左上角一行一列的拼起来慢慢做就行了。再比如常见的猜数字游戏，这个游戏也被认为是难度可控。汉诺塔也算一个吧。难度再高一点的，比如扫雷，扫雷也是正向设计的谜题，并且有一定的概率无解（要靠蒙）。（纸牌可能就不是正向设计的谜题了，因为随机搞一个常常无解，寻找生成有解方案的算法，可能不如逆向设计来的快。）

当然，很多这样的谜题都只能以小游戏的形式出现，因为其结构太“数学”而不适合成为RPG世界的“任务”，但是如果能找到适用的场景，正向设计会更简单可控。

总结我对逆向设计的看法：逆向设计只在以下情况下适用——谜题的解较少或者唯一。

最后提一个正向设计的idea，我设计了一个哥德巴赫赌博机，当你投入X硬币的时候，它会随机加码X-2X的硬币，并告诉你总硬币是Z（偶数），然后你宣称将获得的收益是P个硬币，如果P和Z-P都是素数，你就可以拿走P个硬币，否则就是0收益。根据哥德巴赫猜想，这个素数P是一定存在的。至于你赚不赚得到钱，就凭你的本事了。

作者: guoxiaomi 时间: 2020-6-21 16:32
现在你可以在迷宫里打奶奶了：

未来大致会按照这种思路去设计装备、怪物和迷宫房间的事件，总之现在应该难度比较低，有兴趣可以下载一试：pyramid-0.3.1.zip

作者: guoxiaomi 时间: 2020-6-29 21:53
v0.5.2版本发布！新增了一些迷宫的事件，并且优化了存档结构。迷宫的核心框架应该不会大改了，接下来就要安心做数值，设计各种道具、装备和任务……

下载地址（未脱离RTP）：pyramid-0.5.2.zip

再稍微做几个版本就发到游戏发布区吧……

欢迎光临 Project1 (https://rpg.blue/)