关于地牢房间过程生成是否能生成环的思考

得出的结论是几乎不能。

背景

过程生成地牢各个房间并用走廊进行连接。房间已有模版,形状各不相同,每个房间都有4个门的摆放位置,位置对于每个房间来说是固定且可获取的,但每个房间的门的摆放位置各不相同。从那里进行走廊连接。

如图所示。
loop
分析是否能做到房间之间连成一个环等于分析设计地牢房间连接的规则:一个房间是否可以有多个父房间?如果允许,那就可以形成环,如果不允许,那就不能。

房间连接流程

process
如图:

  1. 放置入口房间E,位置固定在(0,0)。
  2. 遍历E的子房间列表,一个一个地放置。走廊也视作房间。
  3. 循环摆放入口房间的子房间,子房间也一样循环摆放它的子房间。摆放时可能会出现和已经摆放好的房间重叠的情况,这时候更换模版再试。

分析

将入口房间视作拥有一个不需要放置的根结点前继。那么每个房间都只能拥有一个父房间,因为每个房间都是相对父房间的位置放置,多个父房间的位置约束几乎不能成功生成。除非直接设计成那样。

案例比较

以撒和饥荒哈姆雷特的迷宫都能过程生成,但每个房间都是一样尺寸的矩形,且没有走廊,每个房间门的放置位置也都是一样的。