When we decided to continue working on Fireside after Stay Safe Jam, we wanted to keep the scope small and the game simple. After all, we're still studying while developing this game and our #1 priority is to actually finish the project.

Now you've read the headline and maybe think like: “Uh oh. Paul, this does not seem like something that belongs in a small scoped project.” And indeed, making a procedural level generation system which still gives some creative agency to the level designer and stays consistent enough not to produce any broken edge cases still seems like a hard task. It may be the wrong decision but we still want to do it.

However, making a risky decision for the project's scope doesn't mean we can't at least have a reasonable approach to this problem. This means, we need to keep an overview of the state of the feature and should be able to make an informed decision whether to cut it at any time.

This post is about the first step in that process. We needed to answer the question: Can we implement an algorithm that generates some distribution of assets with reasonable overlap and paths winding in between the assets.

So the task was set. Time for...

The approach

The way I decided to handle this was to make a quick prototype in Processing 3 without having to worry about any architecture. Using a different engine would

1. Allow me to use a better set of tools (than Unity) for this particular task
2. Make it easier to throw the result away if it didn’t work (don’t underestimate this!)

You can find the processing implementation here. You can even play around with the parameters!

I also decided that I should try my own solution first and run with that if it showed any promise. This also means, that I won't follow a tutorial for now. Following tutorials can be a valuable way of doing things, but it often also leads to not understanding an algorithm 100% and that can bring problems down the stretch. It’s also way more fun this way. What about you? Would you try to follow some tutorials first or try to implement your own solution?

The nitty gritty

So what’s the algorithm? I chose to us a perlin noise filtering approach to generate a set of related points that wouldn’t overlap.

The algorithm I came up with generates points on a 2D texture which can later be converted into world space. It follows 5 steps:

1. Generate a base perlin noise texture of a set width and height.
2. Round the perlin noise values according to a band width
3. Select a band from this perlin noise
4. Sample buckets from the perlin noise band
5. Merge the buckets to get the final points

Step 1: Create a texture with perlin noise

First, we calculate the value of the perlin noise at each pixel of the texture. This is as simple as iterating over each pixel and calling the noise(x,y) function in Processing. The function will return a float value between v [0; 1], which we need to keep in mind when converting the noise value to an actual pixel color since processing stores colors with 3 ints [0;255].

Now we round the float value we got. We do this by first multiplying v by a maximum bandwidth (which in my case was set to 255) then dividing the value by the bandwidth we want. The result of this calculation is rounded to the nearest integer and then multiplied by the band width again so we get the final pixel color. Since we chose 255 as our maximum bandwidth we don’t need to worry about converting the noise value into a color value anymore! Just set the r, g and b values of each pixel to the value we just calculated.

Step 3: Select a band

We now set a multiplier for the band width we just defined. In this way we can select the color of one band. We set the pixel color of each pixel inside this band to black. Every other pixel we set to white. I call this the shelf of the perlin noise we selected.

Note: Steps 1, 2 and 3 can technically be done in one iteration of the pixel-set, since the operations don’t depend on groups of pixels. This is more performant! I’ve split it into three steps here, to make the algorithm easier to understand.

Step 4: Sample buckets from the perlin noise band

We now iterate over all pixels again, this time laying a uniform grid over the image. For each grid cell we count the amount of black pixels in that cell and create a bucket which saves it’s coordinates and the number of black pixels in the bucket. 

We then sort the buckets by the amount of pixels they counted and select the first n buckets from the sorted list. This gives us a set of buckets on the thickest parts of our band. This is what it looks like when we draw them!

The smaller we chose our grid cell size the more accurate this will be, but the more buckets we will need to fill out the entire texture and the slower our algorithm will run.

Side Note: Using the grid cells as cells for a tile based dungeon could be pretty cool at this point :).

Step 5: Merge the buckets

As a final step we iterate over all buckets and merge close by buckets to clusters. We compute the average position of all buckets in a cluster and save this as the bucket cluster’s center. When we draw the bucket cluster centers we get this result.

These points (in texture space) will be the points we use to place assets and nodes for paths later on! The nice thing about this approach is, that we can get sets of (mostly) non overlapping points by selecting different bands of the rounded perlin noise. Of course, we will still get some overlap but I am hopeful that this stays manageable and so far the approach has proven to be solid.

Moving Forward

After moving this implementation to Unity, adding some path generation this is the result of generating a map based on three different shelves of noise.

So far, the approach we took for generating maps procedurally has stayed promising and we continue to explore procedural generation as a part of Fireside! If you want to join us live we stream development every Thursday from 10:00 AM to 12:00 AM CET at twitch.tv/emergoentertainment. What do you think about the approach we took and how we implemented the algorithm so far? 

There’s still more than one devlog to be had from procedural level generation but also other areas of development! So follow us here on itch.io and join our Discord server to stay in touch!