Pigeon Hole Stepping

For 7DRL this year I developed a new map generation algorithm called Pigeon Hole Stepping.

Fill the map with walls

This map generation algorithm relies on negative building techniques. This concept will make more sense as the later steps are explained.

Dig Hallways

Essentially, we can assume that hallways that are parallel to each other are at least the length of a single room and up to two rooms apart in distance. Because of this assumption, we can make a random walker that will move around with this restriction in mind until map is filled completely.

Allocate Rooms

Assuming the fact that every room is enclosed by a door space, we need to space the rooms from the hallways by one negative space. With this restriction in mind, we can dig all negative space that is not touching a hallway up to the distance of max room size away. This will make it look like huge strangely shaped rooms, this is normal.

Partition Rooms

The next step is to separate this humongeous rooms into acceptable sizes. This can be done more realistically by allowing an occasional wandering walker so the rooms aren't always square. As we create these rooms, we need to add them to an array of rooms so we can identify them later.

Build Doors

In order to access the rooms, we iterate through the array of rooms and randomly choose a location in the room to see if it is touching a wall. If it is see if there is a hallway on the other side of the wall. If there is, build the door and go to next room in array. If there isn't a wall or cooridor on the other side of the wall then mark that part of the room as visited and randomly choose another location in the room. If we have chosen all locations in the room and it still does not touch a cooridor, then mark the room for removal.