Map Generation

My original idea for Lost Crypts was to have all the levels be designed by hand. I had a number of good reasons for this:

• Hand-made levels allow for greater control and more interesting design;
• Less development work;
• Easier to test.

But there are significant downsides. The main one is that they have a very high "design time" to "play time" ratio. Once you've played a level, playing the exact same level is less rewarding-- there's no sense of mystery of what's around the next corner.

After Alpha 5, I decided to change direction and implement a procedural map generation system I had been toying with. Instead of having 100% designed levels, levels would be assembled using pre-fab encounter areas, connected together like puzzle pieces. 

In this post, I'll outline in detail how the map generation system works as of Alpha 6.

Step 1 : BSP the Map

I got the idea of using a BSP Tree from this article on rogue-like map generation. You start with a rectangular region and recursively divide it into smaller regions. By varying the division size and adding a probability of early termination, you end up with a set of irregular rectangles that perfectly cover the map.

I had experimented with a similar system a while ago and knew that there were two features of this system I didn't like:

1. A lot of very skinny rooms. 
2. Rooms are connected in a tree graph. At first glance, the maps look like good dungeon maps. But well-designed levels have some method to them-- players come in at one point, are looking for the exit and probably want to visit as much of the map as possible with minimal backtracking. With a BSP tree players will spend a lot of their time backtracking along paths they've already covered.

The first issue is easy to eliminate-- only split rooms along their longest axis.

The second issue is problematic if you use the BSP node connections to define the room connections. So I decided to throw out the tree once the map was divided and fill out the map in a more directional pattern.

Step 2: Choose the Rooms

First, pick a node/region at random and call this the start. This is where players will first spawn when they enter the level.

Now choose a room (I'm using the term room to describe any prefab area that can be placed in a node). The generator uses the following criteria to decide whether or not a room can be placed, and how likely the room is to be chose from the set of possible rooms:

• The room must fit in the node. 
• Some rooms might have minimum or maximum dungeon levels. For example you probably don't want Cthulhu's Lair showing up on level 1.
• If this is not the first room, then the room must have an entrance on the side facing the previous room.
• We may set a minimum and maximum number of exits that the room must have, depending on how complex of a level we want. The first room must have one exit. The room editor allows the designer to specify which sides of the room can be used as an entrance, exit or both. For example if there's a door that can only be opened by stepping on a pressure plate in the room, that door should only be used as an exit, i.e., leading away from the start.
• Each room has a preset "frequency" that allows some designs to show up more often than others. Generally, the more distinctive or special the room, the lower the frequency. A square room with a couple random monsters and a random treasure can appear frequently. A distinctive octagon room with a treasure chest on one wall surrounded by traps should be fairly rare.
• A room's frequency is scaled up relative to the square root of its area. This tends to selector for rooms that are a better fit for their node, without this small rooms would tend to dominate the map because they could be placed in any node, but large rooms can only be placed in large nodes.

Recursively apply Step 2 for each node neighbor that is a valid exit direction.

A room with three Trogdors and a lunchbox.

Above is an example room created in the map editor. It contains three random type 1 monsters, one type 1 treasure and a torch. All four cardinal directions can be used as entrances or exits (this is set when the designer saves the room). 

Step 3: Connect the Dots and Clean-up

(A recent addition to the generator is a "loop" creation step, where there's a small probability that neighboring nodes will be joined together. This allows for random short cuts to appear in the map, creating the possibility of circular loops.)

Once the rooms are placed, the generator connects the rooms together with corridors. Each doorway that connects to another room is extended to the edge of the node. If the entrance/exit corridors don't line up, a "zig" is added to connect them.

The generator infers the size of doorways based on the outermost tiles of a room. In the example shown above, the room can connect in any direction with a corridor 2 tiles wide. After rooms are connected, the generator removes unused doorways, so this room would become a 4x4 square.

Finally, map is "hulled" with walls. Any empty tile that borders a non-wall tile has a wall placed in it to keep entities from escaping into the Nothing, aka NullPointerException land.

Example of a finished map. The generator can output an ASCII "roguelike" depiction for debugging, showing the nodes, some of which were unused in this map. "*" represents player start locations, "%" represents the exit stairs, and "?" represents some other feature.

There are quite a few inefficiencies in my implementation of the above system, but even on a moderately powered machine a large map can be generated in 10-30 milliseconds. Given the infrequency of map generation, I've decided to leave off any optimizations for now.

Entity Selection

Rooms and maps are defined by a set of entity prototypes. Entity prototypes are like entities in a component entity system. Each prototype has a collection of components and a numeric id. Unless otherwise specified by the map, all entities of the same prototype are identical except for position and rotation. This allows game data to be stored compactly and sent to clients quickly. Some entities require extra customization data, for example a list of targets to respond to triggers, but this is a rare exception and most entities can be sent over the wire in 16 bytes.

For increased dungeon variety, there's an EntitySelector component. An EntitySelector component is sort of like a treasure type or wandering monster table from Dungeons & Dragons-- when the game first starts, it randomly creates an entity of a new prototype and then disappears. Entity selector tables consist of lists of entities for each level and their assorted frequency. For example the Level 1 monster table contains "None" with a frequency 500, "Goblin" with a frequency of 400 and "Javelineer" with a frequency of 100. So 50% of the time, the selector disappears and spawns nothing, 40% of the time it spawns a goblin, and 10% of the time is spawns a Javelineer.

Since this all happens at the start of the map, if a room contains several entitty selectors of various types, it may look like a randomly generated room with creatures and treasure appropriate to the level, even though the actual room data doesn't change.

Random, but not too Random

The generation of the map involves a lot of "randomness" to ensure that each map is unique. But it would nice if we could replicate a map after the fact to debug issues with a particular configuration. So whenever I say "random" I really mean "pseudo-random." The generator uses a Mersenne Twister implementation of Random, which is a pretty fast pseudo-random number generator. Given a particular seed number, it will always produce the same random-looking sequence of numbers.

Addendum: Wait, that's too Random

After implementing the generator, I discovered a pernicious bug: it wouldn't always generate the same map from the same seed. It usually would, but if I ran the algorithm 3 or 4 times from the same seed, it would sometimes produce a different map.

This kind of "heisenbug" is the worst kind to track down, complicated by the fact that the generator is supposed to produce random looking maps--  a slight variation at any step may produce drastically different results.

Because computers are pretty deterministic, non-deterministic behavior is the exception rather than the norm. Since the generator is single threaded, a race condition seemed unlikely. And since Mersenne Twister is well tested, I also ruled out a bug in the random number generation.

Eventually I tracked down the problem. After partitioning the map into nodes using BSP, I calculated each node's neighbors so I could later choose connections. I stored neighbors in a set, specifically Java's HashSet. HashSet does not guarantee order for iterating over its members, so the neighbors were coming back in different orders depending on how HashSet indexed them.