Level generation system for a topdown 2D game

By Floris Kuiper

Table of contents
Introduction
The aim
The process
– Algorithms?
– UI
– Representing values
– Layer system
– Exporting/importing JSON files
– The results
Reflection
Future improvements

Introduction
Any avid player of rogue like games can likely name quite a few games that generate aspects of their levels, weapons, enemies, etc. in a pseudo random, procedural manner, as opposed to crafting them all by hand.

Inspired by games like Nuclear Throne, Enter the Gungeon and Dead Cells I wanted to try my hand in creating a PCG system like one seen in those games.

Nuclear Throne, (c) Vlambeer
Enter the Gungeon, (c) Dodge Roll
Dead Cells, (c) Motion Twin

PCG, procedural content generation, is an umbrella term for the kinds of systems that, according to a set of predefined rules and guidelines, generate this kind of content. For this R&D assignment I explored the various ways this can be done.

The Goal

That said, I wanted to go a little further than just generating some tile maps and being done with it.
My goal for this assignment was to create a modular system for procedurally generating levels in a top-down, 2D game that, based on the given parameters, generates distinctive looking levels that satisfy certain criteria by combining the outputs of a set of different algorithms.

I envisioned a system that’s easily directed by tweaking parameters in a GUI (graphical user interface) which generates levels that are visually distinct, such that even without any graphics, you can identify what level “type” has been generated.

For this I aim to make some kind of UI system that allows for easy composition of instruction sets for this system. It’ll let you add “layers” and assign a certain algorithm to it with the required parameters. Ideally, these sets could then be exported to a file format like JSON or XML that allows them to be used later.

With that out of the way, I got started researching possibilities/prototyping ideas. First on the list…

Algorithms?
At the heart of every PCG system lie the algorithms that evaluate any input and produce a certain output. There are many to choose from, all with their own strengths and weaknesses. To get an idea of what the possibilities were I spent some time looking into a couple of options and a handful of those I prototyped within Unity.

Cellular Automata
Functioning much like Conway’s well-known “Game of Life”, this algorithm iteratively generates very organic looking shapes by looping over every tile, checking every one of its 8 neighbours and depending on how many of them are filled (alive) or empty (dead) the tile flips or remains the same. If 4 neighbours are alive nothing happens. If there’s less than 4 alive that tile becomes empty. If there’s more than 4 alive that tile is also filled.

A map generated with my own implementation of the algorithm. The map is initialized with 50% of its tiles filled, then after two iterations of cellular it comes out looking like this.

After a single iteration the map still looks quite jagged. If you keep iterating those jagged edges will slowly be rounded off, resulting in very organic contours.

Random Walk
Also known as “drunken walk”, this algorithm works by deploying a “walker” on a random tile and letting it step around in random directions, carving out a path in the map as it goes, leading to very chaotic, jagged looking paths and rooms.

In concept quite a simple algorithm. It guarantees that whatever is generated by one walker is continuous without having to run checks. It also turned out to be an algorithm that can produce quite wildly differing results just by giving it some directions.

Like for instance, by giving it a chance to walk in a straight line for a certain amount of steps. This “multistep” function creates long/straight corridors in between all of the organic clusters of rooms. This algorithm turned out to be the most diverse/powerful one out of the lot and would go on to become a cornerstone of the map generation system. Incidentally, I learned later that this is the same algorithm that Nuclear Throne relies on heavily for its map generation.

Diamond Square
Originally designed for creating height maps, this algorithm works by assigning random starting values to all corners of a grid, creating the “square” part, then averaging their values together creating the points for the “diamond” step in between the square’s corners. The map is then split into four square chunks, and the points created by the previous diamond step become the corners in the next square step. This is then repeated until every spot on the grid has a unique value. This results in a grid with gradient values that increase/decrease in value very gradually as you traverse the map.

Pictured above, a heightmap generated with the diamond square map. Implementation courtesy of Klayton Kowalski @ https://github.com/klaytonkowalski/example-diamond-square

While looking quite interesting, this algorithm’s output didn’t fit very well into what I was trying to accomplish. Heightmaps are better for generating something in a continuous manner, as opposed to the one off areas I’m looking to generate.

Lazy Flood Fill
Similar in function to the paint bucket tool in MSPaint, this algorithm starts in a given position and “fills” every square around it until it hits an edge and terminates. Instead of going until it hits a wall, this algorithm keeps track of a chance variable that decays ever so slightly with every iteration. If this chance is succeeded the algorithm repeats itself on these neighbours. If this chance doesn’t succeed it terminates. This results in an effect similar to a viscous liquid dropped onto a flat surface, creating organic looking “blobs” of tiles.

Pictured above, my own implementation of the algorithm. Black dots denote the origin of a “blob”, each given a certain likelihood to “conquer” another blob’s tiles. Some organic colours were added giving the illusion of a continent with different biomes a la Minecraft. On the right the same system with some added coloration logic for fun.

I immediately took a liking to this algorithm and decided I wanted to incorporate it into my system. Its simplicity combined with the interesting/unpredictable shapes it generated would lend it well to generating open areas.

Wave Function Collapse
Apparently borrowing its name from a concept in quantum mechanics, this algorithm works by taking an input and using it as an instruction for generating new content that behaves in a similar way. Take for example, a grid of tiles representing a grassy field. In this field there is a road that can go straight or turn at a 90 degree angle. Away from the road there’s a forest. This forest thins out at the edges.

Wave function collapse then takes these rules and, starting with an empty grassy field, adds some tiles randomly, loops over every square in the grid, examines its neighbours, then determines what tiles could potentially appear there given the rules defined above. For instance, a straight, horizontal bit of road can only have other road tiles on either side of it, another straight piece or a corner. A dense forest tile can only exist with normal forest on all sides, etc. These steps are then repeated until every square on the grid is assigned a tile.

Image courtesy of Robert Heaton (c)

Pictured above, some examples of the things this algorithm can do given relatively simple inputs. It lends itself well to anything from texture creation to level geometry generation, etc.

I would’ve liked to utilize this algorithm to populate the levels the system generates, but that turned out to not fit within the time allotted, so I decided to leave it at that. I didn’t want my scope to balloon too much.

Binary Space Partitioning
This algorithm works quite simply by taking any rectangular grid and splitting it in half. This is done iteratively a certain amount of times until you end up with a grid that’s split into smaller, rectangular pieces that, with a lot of imagination, could vaguely resemble rooms.

Image courtesy of Romain Beaudon (c)

I initially planned on adding this algorithm to the system’s options, but on reflection I thought its output was generally underwhelming and kind of uninteresting. On top of this, it requires a rectangular bit of map to really do its thing, which would be incompatible with the more organic shapes I’m looking to generate.

Hilbert’s Curve
This fractal space-filling algorithm is a way of iteratively filling a grid of any dimension with a path. The more iterations, the more space gets taken up. You could use it to generate, for instance, long, stretched out caverns.

Image courtesy of Pav Creations https://pavcreations.com/procedural-generation-of-2d-maps-in-unity/6/

Quite quickly I decided to ignore this algorithm because of how predictable its results tended to be. It also runs into the same problem BSP does where it requires a rectangular bit of map, meaning it doesn’t lend itself well to expanding upon a given input, basically taking over the entire grid by itself.

Physics Based Room Expansion
This algorithm’s name is quite a mouthful, which is mostly because of the lack of an agreed upon name. Different implementations of it can be found floating around the web, none of which really call it by name, thus I figured I’d coin this name myself.
Despite being a mouthful, it neatly summarizes how this algorithm functions. Multiple rectangular “room” objects are spawned, all with physics colliders, within a unit circle without accounting for any overlap before letting the physics calculation push them all apart until none are colliding/overlapping.

Pictured above, the “room” objects after letting the physics engine do its thing, with the result translated to a tilemap on the right. (Screenshots are not of the same simulation, I lost the screenshots, woopsie.)

While the results are impressive, the way they’re generated didn’t really fit into what I had in mind for this system. I want the algorithms to function as “layers” that can be stacked upon each other, combining their results. This approach can only really overwrite the current state of the map.

With all of that research out of the way, I decided to stick with random walk, lazy flood and cellular. Those three fit the bill quite well for what I’m trying to create. After prototyping them in separate scripts I got to thinking about how I wanted to implement them in a more contained, concise manner, so that I wouldn’t have to keep track of >4 monobehaviours that all needed instantiation, updating, etc. But before that, I had a look into how to represent/store the eventual results.

Tile maps and grids
To represent the maps for this system I opted to use Unity’s powerful tile map system. Tile maps make it easy to create, store and manipulate large grids of tiles in a performance conscious manner.

Pictured above, my custom PCGTile class that forms the backbone of the map generation.

You’ll note that the PCGTile’s state is an int, this represents a value corresponding to a field in the TileType enum, which dictates what state the tile is in. This is then used to determine whether or not a tile can be mutated and what tile should be put on its coordinates when the tilemap is being constructed.

Implementing algorithms
As mentioned, I wasn’t a very big fan of the idea of having multiple MonoBehaviours to look after, so I came up with the idea of creating a static class I could house the algorithms in as separate functions. This would mean having access to them anywhere in the project without having to create and maintain multiple objects that weren’t making use of MonoBehaviour functionalities anyway.

The class being static would mean it couldn’t contain its own variables/objects, meaning it’d have to be written in such a way that it takes an input, performs its actions and then outputs everything all at once.

With this in mind I decided to make the all the algorithms both take in and return a two dimensional array of my custom BasePCGTile class, essentially taking the current state of the map, adding its own stuff on top of that, then returning the whole thing. This map could then be taken and turned into a tilemap.

Pictured above, my own implementation of cellular that takes a 2D array of tiles and returns it after performing the given number of iterations. The rest of the class containing the other algorithms, as well as some helper functions can be viewed here.

GUI
To start off I created a simple UI system for adding individual layers of a certain type to big grid of squares. It allowed you to resize the map, add a layer of Cellular or add a random walker/blob of lazy fill.

Pictured above, a map generated by letting loose a few random walkers.
To further expand on this I created some menus that allow users to edit the various algorithms’ parameters before letting them run wild.

I expanded upon this system by allowing for more control over the algorithm’s parameters.

Expanding the UI
To allow for more control over the algorithms’ various parameters I created some UI panels to group together relevant elements. Things like how many iterations, the length of a random walk and what kind of tiles an algorithm should be generating can all be changed and edited.

Layer System
Then the time came to take the systems detailed in the previous section and turn them into something that allows a user to create “presets” for the eventual map generator. I envisioned a list of “steps” that briefly summarize which algorithm would be run and with what relevant parameters, as well as a window that would allow a user to edit those values, allowing them to simply click an element in the list of steps, and have its parameters be editable in the editor window.

Pictured above, the step editor (left) and the step list (right) windows.

Step list window
This window lets you add or remove steps to perform. Every step shows what algorithm it’s using, what tile type it will produce and what parameters it will use for its generation. Clicking on any of these elements will allow you to edit these parameters in the…

Step editor window

Here you can change the step’s values or even change what type of operation it’s supposed to perform. Doing so will enable any relevant controls and disable any fields that aren’t relevant, to avoid any confusion. Any changes made are immediately reflected in the step list window.

Live preview

The next obvious step forward for this system was to give a live preview of the changes made. Every time a layer is added or a parameters is tweaked the tilemap should update to reflect the changes made.

Immediately, this presented an interesting problem. How do you make sure that the mostly random output stays consistent? It’s hard to get an understanding of what a particular change in the list of steps is doing to do to the map that’s being generated if the whole thing is regenerated randomly each time a change is made, which segues nicely into…

Seeding and determinism
A way of ensuring that you can generate the same output multiple times is by giving a pseudo-random system like Unity’s Random class a “seed”. Usually a string of numbers and letters that in some way informs the generation process. Adding this functionality to my own system turned out to be quite easy.
Unity’s random system can be initialised with a seed value by calling its InitState function and passing in a value. This allows you to essentially “restart” the Random system in a given state, ensuring that the same results can be achieved over and over again. This made it easy to ensure that the live preview wouldn’t just be completely scrambled every time a change is made.

Exporting to/importing from JSON
One of my main requirements for this project was to have a way of creating presets, storing them for use later. To be able to use presets later they can be exported into JSON files.
Using Unity’s JsonUtility, it’s quite easy to do exactly that.

The code used to turn an instance of a custom, serializable GeneratorPreset object into JSON.

The generator system
To turn the resulting JSON files, as well as the presets created within the editor into actual maps, a bit more code was needed. It turned out to be quite simple, amounting to a switch statement on the current step’s StepType that calls the corresponding methods of the PCGAlgorithms class. Once all of the steps have been handled the resulting two dimensional array of PCGTiles is taken and turned into a tilemap.

Results
I figured it would be fun to show off some examples of map types I’ve generated with it so far, with some custom tilemap graphics I drew myself to make it look a little less lifeless.

Preset name: “TestPreset”
32 x 32 map
3 random walkers, 300-400 steps, 0 multi chance, empty
1 iteration of cellular
5 random walkers, 150-200 steps, 0.1 multi chance 5 steps, empty
Preset name: “Desert”
64 x 64 map
12 random walkers 150-200 steps, 0 multi chance, empty
1 iteration of cellular
6 random walkers, 50-200 steps, 0.05 multi chance 5 steps, emptylocked
Preset name “UndergroundBunker”
Random fill of 55%
2 iterations of cellular
7 random walkers, 200-250 steps, 0.05 multi chance, empty
Preset name: “UndergroundFortress”
14 lazy flood fill, filled, 0.99-0.995 chance variable.
2 cellular iterations
10 random walkers, 150-200 steps, 0% random, empty

Future Improvements
Aaaand, that’s it, for now anyway! While I’m very happy with the resulting system, there are obvious avenues for what to add next. Generating a level’s basic geometry is one thing, but does not a game make! If I’d had more time, a system to validate any output would be my first goal. Currently the system can generate maps with unreachable areas and generally doesn’t do any kind of checking whether or not the output “makes sense” or “looks good”, because telling a computer how to analyse something for vague, human qualifiers like that is not as easy as it sounds.

Besides that, stuff like enemies, pickups and decorations placed around the map in a sensible way would be next on the list. Currently the maps look barren and empty, some minor decorative elements would go a long way into making it feel like an actual game.

I’ll definitely continue expanding on this system when I find the time, because I think there’s a fun game in here somewhere, it just needs more. For now, thanks for reading. I hope this was both a fun and informative read.

Sources:
https://www.gamedeveloper.com/programming/procedural-dungeon-generation-algorithm
https://docs.unity3d.com/ScriptReference/JsonUtility.html
https://github.com/mxgmn/WaveFunctionCollapse
https://www.researchgate.net/publication/235974389_Compositional_procedural_content_generation
https://publications.lib.chalmers.se/records/fulltext/256132/256132.pdf
https://github.com/klaytonkowalski/example-diamond-square
https://www.youtube.com/watch?v=-QOCX6SVFsk
https://www.youtube.com/watch?v=CaI6edoGbFY&list=UU4i6i-HBjQzBC_pC7l8GB1A
https://pavcreations.com/procedural-generation-of-2d-maps-in-unity/6/
https://www.youtube.com/watch?v=jV-DZqdKlnE
https://docs.unity3d.com/ScriptReference/Random.InitState.html
https://www.youtube.com/watch?v=I74I_MhZIK8