In this post I aim to describe in relative detail one of the fundamental systems of my new game that currently goes under the working title ”miniTD”. The procedural level generation.

 

Features

There are 6 main components of the procedural level generation in miniTD:

Generate terrain

Generate grid

Generate paths and buildable locales

Find path solution

Create level

Merge layers

 

The terrain generation is a straight-forward process of generating black and white noise into a 16×16 color array. This array is stored away until the paths and buildable locales have been generated.

So next up, a grid pattern is created by placing 3 to 6 lines across the X and Y axis respectively. This is not an actual grid written to a texture, but rather a logic grid saved into a List<int>. The only rule that applies to placement here is that two vertical/horizontal lines may not run next to each other and they may not be placed so that they run along the edges of the map. As already mentioned, this grid only exists as a list of sorted integers and are not drawn on a texture. Instead, the two lists of integers (for x and y axes) are used to calculate possible intersections (where the lines across X and Y cross paths). These intersections, in turn, are used as a basis for the path solver.

The image is an illustration of the grid where red signifies excluded areas, blue is a placed line and green is a calculated intersection.

Onto the next step – the path solver decides a starting location on either the left or right side of the map (along X), and an ending point at the lower or upper part of the map (along Y). After this, the sorted list of intersections (List<Vector2>) is loaded into the solver and an iterative process of decisions on whether to move along X or Y is performed. For each move, an intersection is moved out of the list of loaded intersections, into a list of selected intersections. The primary rules for moving is that only nearby intersections are viable and thus an intersection may not be crossed. If there are no viable nearby intersections, the current index of the list of selected intersections gets removed, essentially moving the path solver backwards one step. This means that the solver has “lost” a move and needs to re-evaluate the previous step. This process will be ongoing up until the point where there are enough viable moves to get to the end of the level. The basic thinking behind this process is that the solver needs to be able to avoid “locking itself in” when it cannot make any moves that gets it closer to the end of the level. A slowed down solving process can be seen here:

https://youtu.be/gdmI3OXsR-U

The video illustrated the solver making a wrong decision, then backtracking to find a viable way towards the end of the level.

Once the solver has completed its work, the list of selected intersections gets returned and the path can now be finished. The path, just like the terrain, is just an array of colors (green in this case). This array is used to determine where to place buildable locales. The buildable locales can only be placed directly next to a path or diagonally from a path, because the turrets have only 1 unit of range (at least until the level up). The locales are randomly placed in conjunction with the path. Locales are marked with red on the same map along with the path in green.

After this, the terrain array is merged with the path and locales, essentially just if red or green color is detected, then terrain map gets marked with red/green. The final map is pushed through a blurring process to allow the terrain to “sink in” around the paths, to avoid extreme cliffs.

The image shows what a map would look like made into a texture.

Up until this point, no objects have been created, so the greyscales of the map are used as an indicator of what is referred to as “stack height”, the number of tiles to stack for height. This value ranges from 0 to 20, where black means no tiles are placed, and white means 20 tiles are placed. This is done for each pixel of the map, except for pixels where the colors red or green are detected. Instead, these are given fixed height values, ensuring that the enemy path and locales are always on same height, so that they can be easily recognized by the player going into a new level.

To make the levels more interesting and allow for further random variation, the stacking of tiles based on the greyscale parts of the map always end with a random chance of “gibberish” placement. Gibberish is the in-code term for non-gameplay vital objects such as trees, rocks, bushes or whatever the selected game world theme the player has selected come with. All the actual object creation is done off screen, so as to avoid visible lag from spawning multitudes of objects.

Lastly, as a method optimize the scene and avoid excessive shadow casters, while also making it easier to manage all the terrain layers when displaying the level construction to the player, all terrain layers are merged into one new mesh object before the level is displayed to the player. The same merging process occurs to the trees and rocks placed into the level, once they have fallen into place, and before the level’s spawn point is activated. Merging the rocks and trees is also a way to cut down on the number of shadow casters in the scene.

Video showing several random levels being made.

 

I hope this write-up has been enjoyable, comments and questions are always welcome. 🙂