自动生成的迷宫

guoxiaomi

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的地图

guoxiaomi

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

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

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

guoxiaomi

现在你可以在迷宫里打奶奶了：

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

guoxiaomi

九夜神尊 发表于 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是一定存在的。至于你赚不赚得到钱，就凭你的本事了。

九夜神尊

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

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

b565185756

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

guoxiaomi

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

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

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

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

SailCat

guoxiaomi

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

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

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

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

if216

代码和demo不拿出来贡献或者卖吗？