Level Generation
The key to level generation for Slappy is to assume that they player is not stranded in a wasteland ala the Fallout series, but the player is stranded in an abandoned part of the world. Around him are forests, open space, and enemies trying to kill him. In my head I imagine it being very similar to the movie/book I Am Legend but with our hero choosing to survive in the woods rather than a major metropolitan area.
Each level will be rectangular in nature (easier to model with a computer) and the focus of this blog post is how I have decided to fill in the rectangular area with empty and filled space. The goal of level generation is to create an environment that feels natural and spacious.
Initial Research
Searching for “procedurally generated levels” on Google yields plenty of resources and tutorials. A large portion of these resources are similar to this one: Create a Procedurally Generated Dungeon Cave System. These tend to generate maps that feel like they were designed on graph paper. Whenever I see these I think back to my time playing Dungeons and Dragons with pen and paper. Lately, a lot of these levels have been associated with the rogue-like sub-genre within RPG/Action games.
The tutorials that caught my eye were ones discussing cave generation and were not focused on rougue-like. I would see images like this one:
Looking at that image I can see the top down view of a level that provides freedom to explore the level as the player sees fit, and more importantly it is a level that I would easily believe could occur naturally.
Many of the “procedural cave generation” articles that I read all referenced Cellular Automata and one algorithm in particular Cellular Automata Method for Generating Random Cave-Like Levels. I am not sure who is the first to discover this particular cellular automata, nor who was the first to apply it to procedural cave generation, but I will try to call out each of the interesting articles that helped me refine my level generator.
Initial Implementation
I have written a simple libGDX application for exploring different procedural generation algorithms that can be found on my GitHub account. Each blog post will have a tag so that you can download the specific version of the code that I’m referring to, since I plan to continually update the code.
The cave generation algorithm is based on a cellular automata
(Wikipedia). The level is
represented as a two-dimensional matrix (boolean[][]
) and each cell can be
in one of two states (EMPTY
or FILLED
). The matrix is initialized
randomly with roughly 40% of the matrix starting out filled. The borders of
the matrix are also initialized as filled just to ensure that the player is
unable to walk off of the map. A sample initialized matrix is visualized
below.
Now that our matrix is initialized we can begin evolving the cave structure
by repeatedly applying some rules for deciding whether or not a cell stays
filled
or becomes empty
. The rules are applied to each cell in the
matrix independently. In the cellular automata literature, these rules can
also be referred to as a birth rule and a survival rule. There are two
inputs to the rules that we define, each one is a count of the number of
neighbors within a specified range that are filled. A visual demonstration
of the neighborhoods is shown below.
It is important to point out that although it looks like the nieghborhoods are
disjoint, d=2
actually contains all of d=1
.
The rules that I used are a combination of those found in these two articles: one and two. After initialization there are two phases to our cellular automate. The first of these phases is responsible for carving out the main cave structure, and the second phase refines the structure and clears out some of the middle to create more open spaces.
We define the following rules:
if count(d_1) >= x
cell = FILLED
else if count(d_2) <= y
cell = FILLED
else
cell = EMPTY
In the first phase x=5
and y=2
. After one iteration we have the following:
And after a few more iterations we can see the cave structure emerging.
In the second phase we set x=5
and y=-1
effectively shutting down the
second conditional since there cannot have a negative number of filled cells
around a cell in the matrix. This begins removing small chunks in the middle
that do not have enough neighbors to stay around and opens up the space on
the interior.
And after a few more iterations.
We have now reached a reasonable looking cave and happened to be lucky enough that all of the chambers are connected. There is a small bit of code included with the cave generation code to ensure that all rooms are connected. The basic idea is to use a “flood fill” algorithm to identify all of the unique rooms in the level (redblobgames.com). Once we have identified the unique rooms we begin a random walk towards the center of the map clearing out filled cells until we hit another room.
Running Demo
I included a demo of the system running (thanks to LibGDX HTML5 output).
Thanks for reading this far, and feel free to send me any feedback.