• Methods
  • Graph-based Generation
  • Cellular Automata
  • Rooms and Mazes
• Best suited method

For ProcGene I wanted to create a tool which could create procedurally generated areas.

The requirements I set for this tool were;

• The generated area should be big enough so it can take several minutes before the player has finished it.
• The generated area should use all three axis (xyz).
• The player should always be able to progress to the next area. It shouldn’t be possible to hit a dead end.

Methods

Now that the requirements were set up, I took a look at what different kind of methods were available for procedural area generation.

I came up with a few methods. I wasn’t sure if some of the methods I found could actually be used for dungeon generation, so I discussed with other students to see if they could figure out a way that these methods could be used. After examining the methods, I came up with the following;

Graph-based Generation

The steps in Graph-based generation are like this;

1. Create rooms in random points.
2. Select the bigger rooms and connect every room with every other room.
3. Remove all connections, save for the absolutely necessary connections.
4. Replace all connections with L-shaped pathways.
5. Incorporate smaller rooms into the pathways and create remaining pathways so all rooms are still connected.

The gif below shows the entire process.

This method was explained by the developer of TinyKeep on reddit. Some of the links aren’t working anymore, but thankfully this article does a pretty good job of explaining all the steps.

Using this method in 3D doesn’t seem like it’d change that much. The only thing that might need to be tweaked is turning smaller rooms into pathways, seeing as the Y axis might differ heavily from the main rooms' Y axis.

Thanks to the spanning tree, we can be sure that all rooms are connected at least once.

Cellular Automata

Cellular Automata is a model used in computer science, and many other sciences.

A cellular automaton is made up of several cells in a grid. Each cell has a state which, for example can be on or off. Cells also have a set of cells near it, called its neighborhood. A cell is assigned a new state when a new generation is created, according to some fixed rule. The new state is dependent on the cells neighborhood. The changes are defined in the rule.

A good example for cellular automata would be the Game of Life;

This can be applied to area generation as is very well explained in this Tuts+ article. I also took a look at the following sites; A C# algorithm to build interesting cave systems and Mapgen: Cellular Automata, which expanded on the other site.

These sites go beyond just using Cellular Automata, but also include some graph-based generation to connect separated caves with each others with tunnels and rooms.

So far, all the examples I’ve seen are in 2D. I did look at 3D examples but couldn’t find a whole lot of code examples but I think it wouldn’t be that much of a challenge to add the Y axis to the X and Z axis.

Using the pathways and rooms method above, you can be sure that the player won’t hit a dead end and should always be able to proceed to the next area.

Rooms and Mazes

Rooms and Mazes is a method which feels a lot like the graph based method, in which rooms are placed in random points in a grid and then adds mazes between those rooms. It then checks for entrances from the mazes to the rooms.

This method is described very well on this site; Rooms and Mazes

Making this 3D would look like quite the challenge, since it would need to create a whole lot more mazes than in a 2D grid.

The player should never hit a dead end, because all the rooms are connected to a maze

Best suited method

From the previously detailed methods I have decided to start a prototype of the Graph-based generation method. I chose this method because it went in-depth about the stuff I wanted to learn. It Showed visuals which clearly showed what a certain step would do.
Creating this method in 3D also seemed like the easiest option.