轴对齐的图形布局

问：

我正在尝试为一个小项目生成地牢，我决定采用这种方法： 1/ 每个房间可以向四个方向开放（北、西、南、东） 2/ 我用一个房间初始化算法。 3/ 当我需要新房间时： 3.1/ 我生成了一个新的断开连接的房间。 3.2/ 我选择一个已经存在的房间，并有剩余的关闭方向，并将新房间连接到它。

虽然它很容易实现，但我现在正在尝试在小地图上布局这些房间。 客房由走廊相连。

它之所以不平凡，是因为从房间 R1 开始，你可以有这样的路径：NESS。当（且仅当）R1 没有路径 E 时，这应该会导致一个房间比 R1 更低（更靠近南方）。 如果你有这样的路径：NESWNESWNESW...（螺旋）在螺旋开始时，你最终会得到更长的走廊，而当你进入螺旋时，走廊会更短。

如果可能的话，我想避免转向。我的意思是类似物理的模拟，我会在有问题的区域上循环，并增加走廊的长度，直到不再发生冲突。 我认为必须存在一种确定性算法（我认为是一种递归算法）。

我认为问题的另一种表述是：如何绘制一棵树，其中每个节点最多有三个子节点，以便每个过渡都轴对齐？ （有一个约束，即过渡 N 向上，W 向左，以此类推）。

此外，我知道在每一步将走廊长度除以 2 会以某种方式解决问题（假设房间没有大小），但它不尊重前面提到的，NESS 最终应该低于 R1。

提前致谢。如果不够清楚，我可以发布图片。

PS：它可能类似于这个问题基于网格的图形布局（Stackoverflow 在我创建问题时提出了这个主题） 但仍然没有得到答复。

编辑：让我们使用这个例子。 数字表示生成顺序。 现在，如图所示，您还拥有布局，即每个房间的位置。这就是我试图找到的。

假设我们继续发展这个迷宫，我们选择房间 8 和向西（左）。按原样，它将与 9 冲突。但是我们可以在 3 到 2（或 2 到 0）之间增加走廊的长度来解决这个问题。

如果我们选择 7 和西，一个解决方案可能是增加 （0,1），但另一个解决方案是增加 （1,7）。

如果 8 向北增长（向上），我们需要增加 （0,5） 等。

我希望它更清楚一点。