※ 引述《yokann ( )》之铭言：
: 以前玩暗黑破坏神 玩世纪帝国
: 甚至是更早的如勇者斗恶龙怪物仙境
: 都有随机地城系统
: 但是暗黑开一场关非常快
: 要马上能按规律乱数生成所有物件/掉宝/怪物
: 感觉很吃运算？
: 还是其实这个难度很低且不吃效能？
: 毕竟Gameboy的勇者斗恶龙怪物仙境都能有乱数地图了
: 有没有相关背景的人能说明一下
产生地下城的做法在 1980 左右就有了，你去找 roguelike 建立地下城的
算法就能看到好几种不同做法。
最简单的难度是真的很低，1980 年代就能做到移动到下层才产生新地下城
了，以现在的机器来说，除非你建立一张超大地图像 CDDA 那样，才有可能
在建立地图的时候就有效能问题。
我这边举例两个最简单的算法。
第一种很直觉，先随机建立两个房间，然后将两个房间用通道连起来，从
第三个房间开始，一建立好就跟上一个房间用通道连起来。
这种做法可能做出两个重叠一部分的房间，如果你想确保房间都不会重叠，
建立好房间就检查有没有碰撞发生，有就删掉新房间。
第二种就把一个空白地图做分割，每一刀都把一个区块分成两个空白区块，
完成之后你会得到一张有很多不同大小的长方形的地图，把长方形当成房间
再用通道相连，就能得到一个保证不会碰撞的地下城了。
这个你用 BSP trees 下去找就能找到范例。

房间内物件也也可以用机率权重计算敌人/宝物/陷阱的数量

之前是看到用波函数塌陷算法

所以玛奇的地下城具体来说是怎么生出来的?好像不完全是这两种?

玛奇偏1，先构筑房间再找道路

我想不太到要怎么自动生成钥匙房跟锁房而不会彼此卡死

首先一定要现有一个入口侧跟出口侧，而钥匙一定要在入口侧区域能连通的地方，就不会卡死了

当然以玛奇地下城的做法，应该在构筑时先生出房间与通路，再一个个去算合理锁上的门，并确保所有开启机关都是与入口侧相邻就好从头目房开始上锁，只要被上锁的区域就不允许生出下一道锁门的钥匙大概就行了

玛奇以前常常生一堆垃圾图，走了大老远结果是死路

大概有想法了 先生出地图后 从BOSS的锁开始随机决定每个房间是锁还是钥匙还是灯柱 并确保一定要先有锁才有钥匙倒著把整个地城走完就做完了 感谢

玛奇经常绕了地图最外圈结果啥都没有不然就是钥匙和门在最远的两头

先生成“路径”再去生成房间跟锁就好了