How does All Gas no Mass generate its levels?

Introduction

I want to take some time to explain how All Gas no Mass uses procedurally generated levels, how its game-design revolves wholly on the random levels, and explain how the game uses the Marching Squares algorithm as well as other approaches published by Lawrence Johnson, Georgios Yannakakis, and Julian Togelius to polish its levels.
But first, let's figure out if you're not wasting your time reading this!

Considering Procedural Generation

Procedural Content Generation (PCG) is a double-edged sword. If done right, it makes every playthrough unique and gives your game great replayability while keeping the player on their toes throughout the whole run! If done poorly however, it can make your levels seem dull, copy-pasted, crudely patched-together, uninspired, or downright unplayable. Writing the correct algorithm for level generation can be very complicated and time-consuming, so it  is very important to consider whether or not PCG is the right way to go for you. Here are some questions to consider:

1. How important is replayability for my game?
2. How intricate do I want my levels to be?
3. Are there any other games in my niche that use PCG for their levels I can learn from?
4. Do I want to use my to tell a story, explain mechanics, or encourage behaviour?
5. How detailed do I want my levels to be?
6. How long is my game?
7. How much time/money do I want to invest in the PCG development?

The answers to these should help you figure out whether PCG is right for you, and give you a general idea of how complicated and random your levels should really be. If you did conclude that you should use procedural levels, this post will help figure out how to approach the development and generation of your levels, what you should watch out for when it comes to control-flow, and which technique to based your generation on.

The case for All Gas no Mass

All Gas no Mass was created with two purposes in mind:

1. I worked a lot with AI this summer, so I wanted to re-introduce myself to Unity
2. I wanted to explore procedural level generation

Thus, the main game-loop was kept very simple: collect enough coins to move on to the next level as fast as possible while crashing as little as possible. The player gets a final grade after completing all levels, and can do another run to try to improve.
This way my game revolves around the player always having to adapt to the world around them and swerving around the environment, and also capitalises on the replayability part by giving them a final grade to beat.

Considering all of this before even starting with creating the level-generation algorithm allowed to have a very linear and clear development-cycle during which I always knew what had to be improved upon and how exactly it should function.

Choosing a Technique

Since I wanted the game to be in space where the player can traverse the level as fast as possible while drifting around, I wanted the levels to be very round. The player has a goal tracker that they are supposed to follow, so I didn't want the level to have a "clear" path. Because of this, the level generated by my algorithm look completely differently than what the levels of a game such as Dead Cells look like, which includes rooms and different sections between them. However, I did want the walls to like asteroids/planet sufraces, so I smoothened it out using the Marching Squares algorithm.
It is very important to figure out how exactly a level should look before you start creating an algorithm for it. Try sketching it out on paper, that way I usually get an idea of how it will look in code as well. With all of this in mind, I chose to base my algorithm on a cave-generation algorithm developed by Johnson et al.

Starting Abstract

DISCLAIMER: This is the point where I start talking about my game's code. You can find it on the game's GitHub repository.

This part starts out simple enough. All of its code can be found inside the MapGenerator.cs script.
I started out by declaring a 2D integer array and randomly filling out with either 0s or 1s. 0s represent free space that the player can traverse through, and 1s represent "walls" or obstacles that the player has to move around, with all of the "edges" always being 1s. This gives the player a guaranteed border they can't cross, which would result in the player going out of bounds. I define the "fill percent" value of the grid by using an integer variable, creating a random number between 0 and 100 for each cell, and checking if that random number is less than the fill percent value. The fill percent value changes based on the level. This is what is looks like in code:

map[x, y] = (prng.Next(0, 100) < randomFillPercent) ? 1 : 0;

After that, I apply the smoothing approach presented in the algorithm's publication. The amount of times I smooth out the grid is also dynamic and might change based on the level. The approach is pretty simple: 

1. Count the amount of neighbouring walls a cell has (8 max)
2. If the cell has more than 4 neighbouring walls, turn it into a wall
3. If the cell has less than 4 neighbouring walls, turn it into a free cell
4. If the cell has exactly 4 neighbouring walls, don't change anything

Now I added an extra neighbour to the count if the cell was at the edge because I wanted to encourage walls being there. That way the bounds look more natural.

Getting Real but Staying Low

This is the fun part. Here we are going to transform this 2D integer array into an actual level and polish it! Firstly, we will be talking about the code inside the LowLevel folder.

Since I had a grid and needed a way to represent it in the game's world, I started with a Node class. A node simply has a vector3 position, an index for its vertices, and a constructor that takes in a vector3 position. The index of the vertices will be useful for creating the final mesh of the grid.

I then created the ControlNode class. This node has an "active" flag, as well as a reference to the node above it and to the right. Its constructor takes in a position, a boolean value for the "active" flag, as well as a squareSize float value because it also initializes the nodes above it and to the right. This comes in handy later and is again a great example of why design should come before development.

Now since I want to use the Marching Squares algorithm I need squares to work with, so I created the Square class.
A Square has a control node for the top left, top right, bottom left, and bottom right part, as well as a normal node for the center left, center top, center right, and center bottom of itself. It also has an integer member called "configuration" which is used by the Marching Squares algorithm. The constructor takes in all of the control nodes it needs correspondingly and assigns it to its members. It then gets the "center" nodes from those control node members. For example, the "left center" node is the "bottom left" control node's "above" node member. It then calculates the configuration for itself based on the table below.

This is what it looks like in code:

public Square(ControlNode topLeftNode, ControlNode topRightNode, ControlNode bottomRightNode, ControlNode bottomLeftNode) {
        topLeft = topLeftNode; topRight = topRightNode;
        bottomRight = bottomRightNode; bottomLeft = bottomLeftNode;
     
        leftCenter = bottomLeft.AboveNode; topCenter = topLeft.RightNode;
        rightCenter = bottomRight.AboveNode; bottomCenter = bottomLeft.RightNode;
        
        if (topLeft.Active) configuration += 8;
        if (topRight.Active) configuration += 4;
        if (bottomRight.Active) configuration += 2;
        if (bottomLeft.Active) configuration += 1;
    }

The class also has other helper methods that can come in handly later in development, such as getting an inactive control node inside the square or public getters for all of its nodes.
This class is an example for why you should plan out what exactly you want to use and how exactly you want to generate your levels before you start coding them. If I didn't think about using the Marching Squares algorithm, I would have needed to start refacturing and redesigning my code all the way down at this level.

Now we have everything we need to represent the grid, but we still need an actual grid. So I created the SquareGrid class. This class' constructor takes in the integer grid we created before as well as the size of each square. It created a control node for each cell of the grid, and sets its active flag to true if the cell is supposed to be a wall, which is true if the integer array's value at that point is equal to 1. All of this is put inside a 2D array of control nodes. Afterwards it creates a 2D array of squares based on the control nodes array we just initialized.

Oh boy, we finally did it! This is the whole low-level implementation of my procedural level generation approach. Looking at it from a distant perspective, it is easy to see why smoothing it out with the Marching Squares algorithm is so easy: we are breaking down our grid into squares which are broken down into smaller nodes.

Now I also created a simple Triangle class here which will be needed for the actual creation of the mesh, and since its low-level I will cover it here. It has an array of vertices and a public readonly int member for the index of each of its vertices. It includes another helper method to check if the triangle includes a certain vertex index. You can also get each vertex by just using it like an array, this is what it would look like in code:

triangle[3]; // returns the third vertex of the triangle

Going High

This is the part where the low-level implementations are actually used to create something! The code I will talk about here can be found inside the MeshGenerator.cs script.

Now this is a very long and boring script, so I will try to trim away any unnecessary details. Here is what this script has to do:

1. Initialize and populate the actual square grid
2. Turn that grid into a mesh
3. Create colliders around the edges of the mesh

So firstly - because we will have to destroy and create levels again and again - we have a clear function that nullifies the current grid, all saved verticies, all triangles, outlines, etc.

Then we have the GenerateMesh() function. This code creates a square grid from the integer 2D array and then creates a triangle for each square inside the grid. The reason for this is that our squares are rarely actually squares. Through the Marching Squares algorithm they "smoothen out" and morph into meshes that have to be triangulated. I will spare you out the details of how these triangles are triangulated because it is very linear and dry. A new mesh is then created, to which the newly calculated vertices and triangles are given. We then let Unity recaulcate the normals of the mesh for us.

Finally, we generate the colliders. Every part of the mesh that is separate from the rest of the mesh - think a single asteroid floating about - will need its own collider, so we create an array of 2D Edge Colliders and delete all that existed already, because those belong to the old mesh.
Now we need to calculate all the outlines. For this, we go through all vertices. This can become quite tasking,  which means we don't want to check a vertex twice, so we store those in a hash set and check if they are already there.
To check if it is an outline vertex we get all triangles with that vertex, go through all three vertices of all triangles, and check if any triangles contain any of the new, unchecked vertices. If so, this isn't an outline vertex. Otherwise we simply get the whole outline recursively by just continuing the process for all vertices.
Then a new 2D Edge Collider is created for each outline, with each vertex being added as a point in the collider.

And boom! We just created our new level! Great job on coming so far! I hope I was able to make everything clear to you and didn't miss out anything important. Feel free to also ask me any questions down below. But... we aren't quite done yet. There are still some things we should talk about.

Considering Control-Flow

Normally, Unity loads the scene for us and we don't have to worry about any scripts initializing before the scene loads since we put our initialization code inside the Awake() or Start() functions. But now we are creating our own level, so if we want to access it - e.g. to drop a few coins here and there - then we have to be careful that we don't try to do that before the actual level is initiated.
In my opinion, Unity's execution of the Game Loop Design Pattern is nothing but astonishing, and it is by design that we have no control over which object's Awake() or Start() functions are called first. The way I get over this is by either just putting simple code inside the Awake() function since that is guaranteed to run before any Start() functions, or by using the Observer Design Pattern. Basically, I created a C# event that is called after the initialization of the level. This way I can just subscribe my initialization scripts to that C# event and be sure that it runs after the initialization of the level.

Considering Optimisation

When it comes to creating levels, it can take a bit of time. My game is simple but I really hate having loading screens or using solutions that just take a long time. It can really break the pacing and make the player jump out of their focused state right into an annoyed state. The good thing about the Marching Squares algorithm is that it is embarassingly parallel (this is an actual term in Computer Science). This is because you can just make the algorithm compute each cell in parallel to all other cells. I would say that the most unoptimised part here would be finding all of the outlines. Even though I implement a hash set and dictionaries which are quite fast, since we need to check if a vertex has already been checked, it is not embarassingly parallel. What would be possible is to detect all structures that are not connected to each other and seperate them, and then run all of them at parallel. Or maybe use a flood fill algorithm on one vertex, then just calculate all of the new vertice.

Considering Technique

The actual map generation here is pretty simple. If you want more direction in your levels you might want to simply use a Hilbert's Curve, or you might want to "patch" rooms together, kind of like how Spelunky does it. Check out the "See More" section to learn more about these topics!

All in all there are many different ways to create your levels, and you shouldn't just copy other games. Every game does it differently and it is a whole artform. Have fun with it and experiment!

I hope this was helpful to you.

See Also

• Pav's Article on Procedural Generation of 2D Maps in Unity - this is a great read and introduces you to many interestind concepts
• Wikipedia's Page on the Marching Squares Algorithm - a great explanation of the algorithm with nice illustrations to go along with it
• The Article for the Cave Generation Algorithm used - an interesting and read of the algorithm from the perspective of cellular automata