I am trying to generate dungeons for a small project and I decided to take this approach: 1/ each room can open in four directions (North West South and East) 2/ I initialize the algorithm with a single room. 3/ while I need new rooms: 3.1/ I generate a new disconnected room. 3.2/ I pick a already existing room with remaining closed directions and connect the new room to it.
While it's easy to implement, I am trying now to layout those rooms on a minimap. Rooms are connected by hallways.
The reason it's not trivial is that, from a room R1, you can have a path like this: NESS. This should lead to a room lower (closer to the South) than R1 was if (and only if) R1 has no path E. If you have a path like this: NESWNESWNESW... (A spiral) you end up with longer hallways at the beginning of the spiral and shorter as you progress into it.
I would like to avoid steering if possible. By that I mean physic-like simulation where I would loop over problematic areas and increase hallways length until there is no more conflicts. I think there must exist a deterministic algorithm (a recursive one I think).
I think another formulation of the problem would be: how to draw a tree where each node has at most three child so each transition is axis aligned ? (With a constraint that a transition N goes upward, W goes left etc).
Also, I am aware that dividing the hallways length by two at each step would solve the problem somehow (assuming rooms with no size) but it does not respect the previous mention, that NESS should ends up lower than R1.
Thanks in advance. If it's not clear enough I can post pictures.
P.S.: it may resemble this question Grid based graph layout (Stackoverflow proposed this topic as I was creating my question) But it remained unanswered.
Edit: 
Let's use this example.
The numbers show the generation order.
Now, as it's shown here you also have the layout, i.e. the location of each room. It's what I am trying to find.
Let's say we keep growing this maze and we select the room 8 and the direction West (left). As is, it will conflict with 9. But we can increase the length of the hallway between 3 and 2 (or 2 and 0) to solve that.
If we select 7 and west, a solution could be to increase (0,1) but another solution would be to increase (1,7).
If 8 were growing North (up), we would need to increase (0,5) etc.
I hope it's a bit clearer.
