自动生成迷宫的4种算法风格

SailCat

1. 最小生成树算法

该算法速度适中(O((m+n)4logmn))，特点是将所有单元格最终挂在同一棵树上实现完全连通

2. 十字分割算法

该算法速度是所有算法中最快的(O(3logmn))，但生成的迷宫也是所有算法中最“规整”的，很多U形回路

3. 深度优先遍历算法

该算法速度偏慢(O(4mn))，对主路径有加权，故迷宫难度偏小，主路是一条非常曲折的路径，岔路一般不会太长

4. prim算法

该算法速度偏慢(O(4mn))，探索完全随机，故迷宫难度偏大，会有很长很长的死路和断头路，岔路常常长于主路


示例均为20X15大小的迷宫，在XP中显示为62x62，如果用VA能小一点，应该是42x47可以放下

问题来了，你们喜欢哪种风格的迷宫？

guoxiaomi

是不是搞个投票？目测更喜欢最小生成树……

考虑到生成房间的情况，十字分割优势很大。十字分割生成房间是很自然的，提前终止递归就可以了，但是其他的算法就得更仔细的考虑吧？

89444640

喜欢3，用鼠标绕了一下，岔路挺远的，不过视觉上舒服一些，如果不是故意多出口，就不会迷路，其他路线都放宝箱就行，不过死路看上去都很远的样子。
1的话试了一下，即使不告诉出口在哪里，也可以走到目的地，因为是全连通的，不过没死路感觉差点啥。
2太垂直的路太长了，4看上去有很多很值的垂直死路。同屏能看到好多条垂直死路就不会往死胡同里走了
说起来不生成一些4*4  6*6之类的方块形房间吗？

chd114

不考虑往迷宫加别的东西的情况下，毫无疑问不考虑4···2是个人觉得比较好的了
话说回来不考虑来个5吗——先画一个迷宫，然后分成多个区域（或者地图），最后玩家玩的时候进入的迷宫实际上是这些区域（地图）重新组成的

寂静的夜里

难道不该是全都要吗
或许可以让用户自己输入一些参数来进行改变

冷俊逸

感觉都不如手画的好看
还不如设计个判断迷宫好坏的模型，然后用进化算法暴力拟合。

Mono_kyrin

prim……我都快把图论忘光了
最小生成树吧，其他的U型回路太多了
感觉还有很多可以优化的地方，比如加入3x3,4x4,6x6的小房间，加入高低差，加入事件等
要是真能搞出来的话，RM下的rougelike就不远了

SailCat

改进了一下评估算法，防止在算法二（十字分割）的时候出现大量U形回路

RUBY 代码复制

# 确定分割方向 水平/垂直/十字
    split_x = (w.to_f / h <= 1.618)
    split_y = (h.to_f / w <= 1.618)

# 确定分割方向 水平/垂直/十字


    split_x = (w.to_f / h <= 1.618)


    split_y = (h.to_f / w <= 1.618)

不要问为什么是1.618，问就是根号５－１

SailCat

Mono_kyrin 发表于 2020-5-27 12:06
prim……我都快把图论忘光了
最小生成树吧，其他的U型回路太多了
感觉还有很多可以优化的地方，比 ...

小房间很容易搞，不论哪个算法都很容易，高低差……这个没必要吧，本来兼容不同版本RM的地图风格就很难，墙高如果再不用默认值，随便一个小迷宫做出来都是很大的地图

walf_man

感觉1和3不错，2和4感觉长长的太多了