Project1

标题: 自动生成迷宫的4种算法风格 [打印本页]

作者: SailCat 时间: 2020-5-26 03:21
标题: 自动生成迷宫的4种算法风格
本帖最后由 SailCat 于 2020-5-26 03:36 编辑

1. 最小生成树算法

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

2. 十字分割算法

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

3. 深度优先遍历算法

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

4. prim算法

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

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

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

作者: guoxiaomi 时间: 2020-5-26 06:11
本帖最后由 guoxiaomi 于 2020-5-26 06:28 编辑

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

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

作者: 89444640 时间: 2020-5-26 07:04
本帖最后由 89444640 于 2020-5-26 07:12 编辑

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

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

作者: 寂静的夜里 时间: 2020-5-27 00:46
难道不该是全都要吗
或许可以让用户自己输入一些参数来进行改变

作者: 冷俊逸 时间: 2020-5-27 09:53
感觉都不如手画的好看
还不如设计个判断迷宫好坏的模型，然后用进化算法暴力拟合。

作者: Mono_kyrin 时间: 2020-5-27 12:06
本帖最后由 Mono_kyrin 于 2020-5-27 12:11 编辑

prim……我都快把图论忘光了

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

作者: SailCat 时间: 2020-5-28 13:59

改进了一下评估算法，防止在算法二（十字分割）的时候出现大量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 时间: 2020-5-28 14:01

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

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

作者: walf_man 时间: 2020-5-28 17:06
感觉1和3不错，2和4感觉长长的太多了

作者: myownroc 时间: 2020-5-28 22:53
本帖最后由 myownroc 于 2020-5-28 23:00 编辑

啊这，这个话题我好几年前就水过了
https://rpg.blue/thread-374569-1-1.html
https://rpg.blue/thread-369475-1-1.html

不过，说到迷宫/地图生成算法，还是自动细胞机算法和voronoi图算法得劲

作者: 冷俊逸 时间: 2020-6-3 23:18
http://donjon.bin.sh/4e/dungeon/
"import mazeGenerator"

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