Procedural Level 101

Today I attempted some very basic procedural level generation. I wanted to experiment a little after my thought on Building New Worlds. Given a NxN lattice I wanted to generate random paths that would go from left to right. A walkable path is defined with "_" while a background or neutral tile is defined with "O". For example:

 O O O O O O O O O O
 O _ _ O O O O _ _ _
 _ O O _ _ _ _ O O O
 O _ O O O O O O _ _
 O O _ O O _ _ _ O O
 _ _ O _ _ O O O O _
 O O O O O O O O _ O
 _ _ _ _ O O O O O O
 O O O O _ _ _ _ O _

The first thing I did was define a base level (not necessarily valid) and a print function. I wanted to be able to quickly debug my levels. Before you even write a line of code you have to define the rules or degrees of freedom. A few simple ones included:

• A "_" tile has to have a "O" tile above to be considered walkable
• Only walkable "_" tiles are allowed
• A valid path takes me from column 0 to column N-1 by going from "_" to "_"
• A valid step from "_" to "_" must move to the next column (you can't go up or down, only up-right, right, down-right)
• The first row can only be "O" (this is pretty much a corollary of previous rules)

Now that the rules are defined, how do I add randomness? But most importantly, how do I add meaningful tile generation? I got started by using a random value between O to 1OO. If the value is above 5O we have a "_" tile. But how do I promote viable path generation? Naively I add a probability bonus based on what precedes the current tile. For example if I have a "_" on the same row but previous column I increase the chances to generate "_" by 1O%, and so on. Pretty quickly most of my generated levels were valid ones but I know that it is still a possibility for invalid levels to be created.

An idea that I did not implement was a level checker, a function that would navigate the level to make sure at least a viable path existed based on the currently generated level. Kind of a way to "fix" the level so that it is playable. But before I even got that far I wanted to create a level validator. A simple function that given a level, it would tell me if a viable path existed. Turns out that is the most challenging part for this basic case!

The good news is that I don't need to enumerate all possible paths but as long as there is one viable path I'm good to go. Intuitively it's pretty easy to tell, you start from the left and find a viable tile on the next column and see if you can continue doing that until the end. But what if you reach a tile with multiple viable options? (In this specific world either you can go right, or you can go up-right or down-right). You have to pick one, continue looking for viable paths and if you get to the end you validated the level. If you can't, you have to try the alternative path (so you walk back) and see if you can proceed until the end. Keep this up until you reach a valid end or you are out of options.

Surprise, surprise! This is backtracking! And just like that I found myself doing a leet code challenge. But that's ok, backtracking is a pretty common algorithm and nothing too wild. There are many optimizations one can make but some are unnecessary in this case, some can be helpful but overkill if your level can only grow so much (so for N really large). For example when you try an alternative path, there is a chance you might end up on a path you already explored. If that's the case you can exit early as you know that if you touch any tile twice it means there was no way out and you can continue with the next row or next option available.

Thoughts

This was a pretty light exercise to feed my curiosity. I wonder how in procedurally generated levels we can guarantee to respect the rules of the world while providing enough randomness to reduce repeated levels to a minimum. I'll investigate a bit further and report back. Fun times!

Additionally, does this really qualify as procedurally generated? I'll confirm how we define procedural generation and make sure I'm on the right...path!