House layout/maze generator

Now that I don’t make games for a living I find that I’m more inclined to do so in my free time. Nothing even approaching a releasable standard, but it keeps me amused, and is an excuse to mess around with network programming. Occasionally I’ll inflict a messy prototype on my friends at a LAN party, and I’ll probably write more about them here at some point.

For one prototype I needed some kind of random ‘house’ layout, with rooms and corridors and the like. Procedural maze generators seem to be one of those things that most programmers end up writing at some point, and as mine works reasonably well for what it is I thought I’d share it in case it’s useful for anyone. The code isn’t particularly efficient for large, deep layouts, but it’s quick enough for what I need it for.

The code

First of all, here’s the full code. I don’t think there are any external dependencies except for a RandBool() function, so it should pretty much compile (although I haven’t tested it stand-alone):

housegenerator.cpp , housegenerator.h

Here is a 50×40 tile layout that it generated:

Each tile is brown for wall, orange for a room, grey for hallway, and the light crosses are the doors (I’m a programmer, not an artist…). Let’s see how it works.

The algorithm

I started from this pseudocode, referenced from this Stack Exchange question about house generation, and finished it off and made a few tweaks.

The idea is to generate a series of hallways and rooms, and add doors so that the layout is fully connected (every room is accessible from every other room). This is accomplished by repeatedly subdividing the space, first to create hallways, and then to create rooms. There are a number of stages:

1. Start by filling in the entire map with wall. We want to subdivide the entire map, except for the one-tile outer wall boundary, so initialise the queue of Areas with this.
2. While there are still Areas in the queue, take the front one and subdivide it. If we don’t have enough hallway yet (defined as a fraction of the final map being hall tiles) and the area is big enough, carve out a straight line for the hall and add the blocks on either side back into the queue. Otherwise, if the Area is big enough, cut it in two along a random line and add both bits to the queue. Otherwise, carve out the final room.
3. Now we have all the hallways and rooms, but they’re not joined. The next thing to do is connect the hallways to each other. Check the ends of each hall, and if there is more hallway the other side of the end wall, carve out the wall. All hallways are now guaranteed to be connected.
4. Now we need to put doors in. Add all the rooms to another queue of unconnected rooms. While the queue isn’t empty, take the first room and pick a random start point and work your way around the edge, checking if a door here would open onto a hallway. If so, place a door. If not, do the same again, except this time check for possible doors into rooms that are already connected (e.g. aren’t in the queue). If no doors were placed, re-add the room to the back of the queue.

And that’s about it. Eventually all rooms will have doors to either hallways or other connected rooms. Here are a couple more layouts:

Configurable options

There are a few variables at the top of the file that can be tweaked.

• MaxHallRate. This is the fraction of the map that is allowed to be hallway. Set to 1.0 to keep subdividing until the individual rooms are too small to subdivide further. This will result is a very flat connection graph, where nearly all rooms are connected directly to a hallway. Set it to 0.0001 (not zero or it infinite loops) to create a single piece of hallway. The connection graph here will be very deep, creating more of a maze-like layout.
• HallDoorProb. When a door is placed between a room and a hallway, this is the probability that more walls will be tested for creating additional doors. Set to 1.0 to always create doors in walls with hallway alongside, and 0.0 to only create one door.
• RoomDoorProb. Similarly for doors to other rooms, this controls the probability of extra doors being created. Set both of these probabilities to zero to create a connection tree (with no loops) – there will only be one way of traversing doors to get from any room to any other room.
• MaxRoomSize. This is the size below which rooms will no longer be subdivided. A bigger number mean bigger rooms.

From a house to a maze

Houses are generally well connected – it’s usually quick to get from any room to any other room, so there are often lots of doors or loops (except for my house, which seems designed to maximise journey times…). Mazes are supposed to be hard to navigate, with many dead ends and only one route through. Luckily enough, this algorithm supports creating both.

Hallways are the main backbone of the connectivity. Having many hallways greatly reduces the average number of doors that must be passed on any journey. Reducing hallways will make your layout more maze-like. You could remove all hallways entirely by modifying the start room to be of Hall type, but I haven’t implemented this.

Setting both door probabilities to zero will ensure the connected graph is a tree. This maximises the average number of doors traversed per journey.

Reducing the room size could be used to maximise the number of doors (although the layouts are less interesting with very small rooms.

Here is an example of a large maze-like layout I generated:

Enjoy solving that one!

Downloadable demo

If you want to play around with the generator but don’t have your own code to plug it into, here’s a Windows demo executable you can download:

http://35.170.75.192/files/HouseGenerator.zip

Disclaimer: This was written in my Mirror game engine, and is a quick hack-job to have something runnable. As such it starts and connects to a local multiplayer server, and requests network access. Feel free to deny access as it doesn’t do anything, but taking all that stuff out would have been a fair amount of work. Just so you’re aware.

There is also a bug with using hardware acceleration on some systems that I never got to the bottom of. So if HouseGen.exe doesn’t work, try HouseGen_warp.exe which uses a software renderer. The joys of PC development when you only have one machine…

Usage: Use the RunMe.bat file to edit the generation parameters (and change the .exe is required). The four generation parameters plus width and height are specified, and can be happily changed.