During my work on Audiozoe I've been digging deeper into the inner workings of Random and Procedural Content Generation(RPCG) and have found that there are many tactics being utilized by developers to achieve the desired results. I will discuss these methods below.
Pure Pseudo-Random Generated
A game that utilizes purely Pseudo-Randomly generated content will associate specific values to specific objects, or environmental components and then lay them out to create an environment. I first experimented with this method using Unity's built in Random.range which uses Marsaglia's Xorshift 128 algorithm. This produces fairly uniform results, which I've found rather pleasant. Though for Audiozoe, I found that the Mersenne Twister's distribution was a tad more to my liking. The major disadvantage here is that it is prone to odd clumping.
The most advantageous solution to this problem is the use of the modulus operator. Rather than assigning a value to each object, you can simply generate objects if you meet a condition that utilizes the modulus. This guarantees no overlap if done correctly. I think this method can be valuable in some cases, just be sure to seed your random number generator if you are trying to create reproducible levels.
Rule based generation
Using only a handful of randomly placed, random number generated tiles can lead to interesting results if used with very selective rules. Building the level up can be a result of following rules such as:
If there is a dirt block in each of 3 surrounding spaces on a 2d grid, the 4th space should be anything but a dirt tile, unless there is the case that there is nothing it can be.
This method is rather beautiful, and can lead to things such as the terrain and biomes many are familiar with from Minecraft.
Make a little Noise
The Pseudo-Random and modulus method worked fairly well for me, however It still didn't make levels that I was confident felt like levels. As a result I needed to seek out better results. This is when I had a run in with some blue noise. Noise is a concept from digital signal processing and graphics, and actually can be generated for the use in creating random levels. Given a set of inputs in a set of dimensions noise can be generated following one of a set of patterns. Wikipedia has some good examples of the colors of noise, suffice it to say there are blue, red, white, violet noise and grey noise. There are also some specialized forms of noise such Perlin noise which was originally invented with the intended purpose of making computer graphics look less machine-like. Ken Perlin then created a better algorithm known as Simplex Noise which performs better and can scale into dimensions higher than 3 without issue. One of the main things of note is how one might modify the octave and frequency of this noise, it also important to point out that noise generation algorithms produce deterministic results, so after acquiring results, it would still be required to map that to some sort of random generation algorithm and probably to add in a seed to ensure that this yields a result that is not identical on many playthroughs.
Simplex Noise gave me far better results, creating levels that look rather beautiful. and natural.
But how do we get over there?
The most important part of the journey is the ability to reach the conclusion and despite the value of these algorithms, they lack one thing - a guarantee of a level being able to be completed. There are many interesting solutions I've seen on this front. The most common of which is to set a start point and end point, and have these be the first points laid down on the map. After this, run a graph traversal algorithm such as A* at or Jump-Point Search, to determine if the map is achievable. These are better than Dijkstra's because we already know our start and endpoints, Dijkstra's is rather slow in comparison at . AAdonaac, seems to take advantage of some really interesting techniques and algorithms to achieve a procedural level as well.
I'm going to end up using A* to find a path across the levels I currently have generated using Simplex noise. After doing that I will have to ensure that if there is no complete path that I place blocks to ensure there is a cross-able gap.