轴对齐图布局：地牢房间网络的确定性可视化算法需求

问题梳理 #

我当前的地牢生成规则：

• 每个房间支持北、西、南、东四个方向的连接
• 从单个房间开始初始化
• 新增房间流程：
  1. 生成新的独立房间
  2. 选一个还有未开放方向的已有房间，将新房间与其连通

现在需要在小地图上布局这些带走廊的房间，核心痛点：

• 像NESS这类路径，只有当起始房间R1没有东向路径时，最终必须指向一个比R1更靠南的房间
• 螺旋路径NESWNESW…会出现起始段走廊过长、后续段过短的问题
• 不想用物理模拟式的迭代调整（循环扫冲突区加走廊长度直到没冲突），希望用确定性递归算法
• 这个问题本质就是：怎么画一棵每个节点最多3个子节点、所有连接都是轴对齐（N向上、W向左等）的树
• 试过走廊长度逐次减半的方法，但满足不了NESS的位置约束

补充场景：参考带生成顺序编号的迷宫图，继续扩展时：

• 房间8向西延伸会和房间9冲突，可拉长3-2或2-0的走廊解决
• 房间7向西延伸，可调整0-1或1-7的走廊长度
• 房间8向北延伸则需要调整0-5的走廊长度

确定性递归布局方案 #

核心逻辑 #

给每个房间记录边界范围和已用方向标记，递归扩展时严格遵循位置约束，确保路径方向和空间位置对应。

具体步骤 #

1. 根节点初始化

   • 把第一个房间（R0）放在坐标(0, 0)，边界设为[0,0]到[w,h]（w/h是房间的宽高），四个方向都标记为未使用。

2. 递归扩展规则
   给已有房间R加新房间R'时：

   • 先做方向校验：要扩展的方向D必须是R未使用过的（符合生成规则）。
   • 空间分配按分支来：
     • 先定一个基础走廊长度L（比如设成房间宽度的2倍，保证不会和房间本身重叠）
     • 根据R的分支数量调整走廊长度：
       • 如果是R的第一个分支，走廊长度用L，直接按方向偏移坐标（比如向南的话，R'的y坐标就是R的y坐标减去L再减去房间高度）
       • 如果是第二个分支，走廊长度用L/2，而且偏移时要避开第一个分支的空间
       • 如果是第三个分支，走廊长度用L/4，同样避开前两个分支的空间
     • 强制执行NESS的位置约束：处理到NESS的最后一步（向南）时，先查起始房间R1有没有东向路径：
       • 如果R1没东向路径，强制R'的y坐标（南为负方向）比R1的y坐标小，确保更靠南
       • 如果R1有东向路径，按分支规则调整位置，但必须保证不跟其他房间冲突

3. 预检查冲突，确定性调整
   在算出R'的坐标前，先检查R'的边界会不会和已有的房间/走廊重叠：

   • 如果重叠，直接把当前路径上某个祖先节点的走廊长度翻倍（比如L→2L→4L），直到不重叠
   • 这个调整是确定性的，不用遍历所有冲突，只需要调整当前扩展路径的祖先走廊（比如示例里房间8向西延伸时，调3-2或2-0的走廊，就是给祖先加长度腾空间）

方案优势 #

• 完全确定性：每一步的坐标计算都基于递归分支顺序和方向约束，没有随机调整
• 满足NESS的位置要求：通过起始房间的方向标记直接判断，强制位置关系
• 解决螺旋路径长度失衡：分支走廊长度按2的幂次递减，再结合祖先走廊的确定性调整，能让螺旋各段长度比例可控

内容的提问来源于stack exchange，提问作者David Keller