I’ve started working on a building design system. At the moment it looks very much like the Sims!

I’m planning on adding the following features

- Straight walls between any two grid points ✔
- Curved walls
- Automatic room designation ✔
- Place fixed width doors
- Place custom width windows
- Place props in rooms
- Support multiple levels

Implementing straight walls was relatively simple. Connections/Intersections are only allowed on grid points and I split the wall if necessary. I’m considering allowing intersections anywhere however this has strange implications for player interaction.

Automatic room designation was a lot more complicated than expected. I thought that I could treat the walls as edges in an undirected graph and then detect all the cycles. This fails because it does not consider the position of the vertices in the graph.

Consider the following diagrams:

In each case the vertices and edges are connected in the same way. However the path around the outside of each room is different:

- In the first diagram the blue room is 1-2-4 and the red room is 1-4-2-3.
- In the second diagram the blue room is still 1-2-4 but the red room is 1-2-3.

Ultimately I had to use a more complicated algorithm to find the Minimal Cycle Basis of the Plane Graph (a graph where the vertices also have position). This follows the edges in a clockwise direction and extracts cycles as it finds them.

The final step was polygonizing the rooms, clipping overlapping rooms and then triangulating the polygons! I still need to modify the algorithm to make sure I associate the right edges with the rooms (I don’t quite want the minimal cycle basis…) but I’m leaving that until next week.