Imagine you have a 120×120 grid of tiles. A tile can either be empty or solid. You want to procedurally arrange the grid such that the empty tiles form an interesting complex of caverns. You also want to be able to generate a near-infinite amount of different styles and variations of caverns, because variety is nice.
First, the basic concepts need to be set up. Every tile in the grid needs to know about the tiles that surround it. What is the X and Y position of the tile? How many tiles around it are solid? How many are empty? Is the tile to the left of this one solid or empty? Is this tile on the edge of the grid? All of these questions need to be answerable by an individual tile.
You also need to come up with a solution for how you’re going to tweak all of these tiles to get your result. This is where the concept of a filter (for lack of a better name) comes in. Every time the entire grid is modified, a filter will be handling the logic. By chaining several filters, you get your end result. A filter can be very simple. You could make a filter that finds every tile on the edge of the grid and makes it solid, or a filter that swaps all empty tiles to solid and vice-versa. You can also incorporate several commonly used tools in procedural generation into your filters, such as cellular automata. And so-on.
First, you start by randomizing the tiles. This gives you a rough starting point for shaping your caverns. Next, you apply some simple cellular automata rules to transform the noise into something more manageable. The cellular automata rule is simple: if a tile has 4+ solid tiles directly neighboring it (including diagonals), then it becomes solid. The same logic applies for empty tiles with 4+ empty surrounding tiles. In all other cases, the tile remains as it is.
In the animation you can see that step 1 is the random collection of tiles, while in the following steps a cellular automata rule is applied. The effect of the filter diminishes after the second or third step, so for practical purposes you just need to run that filter 3 times to smooth things out.
One obvious issue is that there are caverns that get generated with no way to move from one to another. What if the solid tiles are unbreakable?
Starting with a nicely smoothed out set of caverns, you could then add a filter which reduces the number of caverns to something more manageable. You could keep the 8 largest caverns and take all remaining caverns and make them solid. To maintain the same number of empty tiles, you could convert random solid tiles from the larger caverns to empty tiles based on how many empty tiles the now-removed caverns had. Now you have a guaranteed collection of 8 or less disconnected caverns and your grid has the same ratio of solid tiles to empty tiles. How can you make sure the caverns are all connected? One solution is to connect every cavern to the largest cavern by digging a trail to the large cavern. Now you can be certain that every empty tile on the grid can be reached by the player.
What if you aren’t satisfied with the distribution of caverns? What if you want to guarantee that the majority of the map has caverns of a specific width (more or less)? You could make a filter which finds every solid tile that has 5+ solid tiles in every cardinal direction, and make it empty. The same logic would conversely apply to empty tiles.
Step 3 on this image illustrates the outcome of applying this new filter. Solid masses of tiles suddenly have hollow interiors and large empty spaces suddenly have solid chunks of tiles filling them up. This filter seems to make a mess of the grid, however, so you would need to re-apply some other filters to clean it up. Reducing the number of caverns to something manageable then connecting all the caverns with another filter would give you desirable results.
Maybe you want the caverns to be more rectangular and less blob-shaped. You could add a filter that fills in small gaps and removes bumps.
Your options are limitless when you have control over the set of filters applied, and the ordering of these filters. The filters can even be fed different parameters to give much different results. Maybe you want to reduce the number of caverns in the grid to 5 instead of 8. This would use the same cavern reduction filter used previously, just with different criteria.
Having more filters at your disposal means you have more control over the end result, and also more interesting combinations to try.
What this conceptual grid of solid and empty tiles will be used for will be the topic of a future post.