Procedural generation of building interiors (part 3)

This post follows on from part 1 and part 2.

We pick up with the procedural generation able to allocate areas for rooms and hallways but without all the hallways connecting up.

With that statement I’m sneakily assuming that we need the hallways to all connect. I could have decided to allow room-to-room navigation but it seemed like it might end up harder to guarantee that all rooms would end up reachable that way. In the spirit of “learn by doing” I chose to trust my hunch and see where it lead. I could always backtrack if necessary.

Before I could connect up hallways, how could I detect if hallways were connected in the first place?

Thankfully, answering the question “are all these things connected?” is not an uncommon problem in programming. The solution is to implement a flood-fill algorithm such as you get in drawing programs. Pick a starting square, colour in all the directly connected squares. Next repeat those steps for the squares just coloured in. Keep going until there are no more squares left to colour in.

Solving one problem in programming frequently throws up another problem. In this case, how should I pick the starting square?

I chose to take a quick and easy solution rather than worry about perfecting a small detail. I realised I could specially allocate some space for a “starting room” in such a way that I knew it would always touch a hallway, then just start the flood-fill from the bottom-leftmost connecting hallway square.

In this screenshot the starting room is shown top right in pink. Compared to all the previous screenshots the hallways here are black, which indicates they’ve been successfully flood-filled.

Had there been any purple hallway squares left we would know that the hallways did not connect. I forgot to grab a screenshot where this was the case — frustrating but not so much that I’m going to go back and recreate one!

Putting this into practice I added a scan for unconnected hallways after the flood-fill. I realised that the very first unconnected hallway square found could always be used to start a connecting hallway that travelled upwards. This worked because the inner hallways would always be below the outer hallways given the scan proceeded left-to-right and top-to-bottom.

As with the starting room location, this was a simplification. Connecting hallways could be positioned in a number of different ways but it was more important to keep moving towards a complete generation. If the complete generation turned out not to be possible, effort on these finer details would have been wasted.

By performing another flood-fill starting from this connecting square, followed by another scan for unconnected hallway squared, the process could be repeated to see if all the hallways were connected yet.

Repeated enough times, eventually no unconnected hallways should remain.

In part 4 we will leave hallways behind for a while and start worrying about dividing the allocated room space up into separate rooms.