A big part of making a procedural environment is coming up with the shape of the world. There are lots of ways of doing this, from using Perlin noise to make a mountain range to simulating plate tectonics for continents and island chains. This article is about the step that comes after that.

Say you use a fairly well-trodden algorithm to generate a cave system – there are lots of articles around for using Perlin noise as a basis for this – and now you have a cool area to explore. If you’re making a game about exploring a completely inorganic and empty cave system, that’s all you need. But, what if you want there to be a bit more life in these caves? What if you want there to be creatures building homes in them, or big spacious areas with monsters in them guarding treasure?

We could approach this from two directions – we could build the cave for the event, or we could build the event for the cave. Because we want to adapt to both procedural and player-created environments, we have chosen the latter approach. In other words, we’re creating the environment, then looking for places where a monster might want to build a home.

Of Tiles and Flood Fills

A theme that will recur a bit here is that of flood filling. This is usually thought of as a tool in a paint program – you get out the paint can tool and click somewhere, and that area gets filled with the selected colour. Specifically, ‘area’ here is defined as “everywhere you can reach from the originally clicked pixel, without stepping outside the originally clicked pixel’s colour”. I won’t spend much time talking about how this works – I assume most people are familiar.

So, suppose we have a world of tiles, every tile either blocked (with dirt or stone or whatever) or open (empty). We might want to find, for instance, areas that are completely unreachable to each other – ‘rooms’ of connected open tiles, that have no path between them and other such rooms. Hopefully, you can imagine that this is doable with a flood fill – if I gave you a bitmap that looks liked this:

With not too much time faffing about in a paint program, you could classify different rooms like this:

Now that we have that classification, what can we do with it? Well as it stands, not a great deal – it’s nice to know that the orange room and the green room can’t touch each other, I suppose. But there’s nothing here to tell us that that big orange room is actually kind of a couple of distinct areas – meanwhile the light blue and the orange room, if you could just dig a little hole there, could be joined.

Of Distance Fields and Dijkstra’s

A good thing to know about if you’re a game developer is Dijsktra’s algorithm. It’s conceptually related to the idea of flood fills, and in some cases it’s just a slower version of A* search, but it let’s you do something kind of cool. Instead of finding a path from a point to a point, it lets you find the optimal path from every point to a point. This can be handy if you have, say, a horde of enemies all chasing a single player. It does this by creating a sort of expanding frontier, starting from a given point, and as it grows outwards it records the shortest path from the starting point to every point it reaches. However, there’s no reason it has to start from a point – you can always start Dijkstra’s from multiple points, to generate (for instance) a map of shortest paths to the nearest health pickup spawn point, or whatever. Seriously, it has a lot of potential uses – if you’re a game developer, I recommend having a good look at the wikipedia page for it if you’re unfamiliar.

In this case, we’re going to use this mutated version of Dijkstra’s to find a map that contains the shortest distance to a blocked tile, for every open tile. It will look something like this:

Now we’re getting somewhere. Since these examples are based on a random noise image, rather than actual screenshots from Sun Shy, it’s a bit less tile-based than the real situation. But, you can see here that the darkest grey areas are open tiles that are close to walls, etc. It turns out that this has a name, so instead of referring to this as a weird mutated Dijkstra’s search, we can call it a Grassfire transform, which sounds cooler anyway. As an aside, this is kind of related to the field of algorithms called Skeletonisation algorithms, and while that’s not exactly what we’re doing here, makes for interesting reading relating to procedural generation in general.

Room size and open spaces

Let’s have another look at that coloured diagram from above:

If we were looking for a a place to spawn an epic boss battle, what is the right place? We’re going to need a lot of space. A reasonable first thought would be to classify the rooms by area – simply counting up the pixels. Unfortunately, this method kind of sucks. I haven’t actually counted the pixels, but if we look at the above image, it looks to me like the orange room is the biggest one, and maybe it’s a good place for a boss fight but it isn’t enormously spacious at any point. The bluey-purple room in the top left has quite a few pixels, but is very skinny and has no high ceilings. The pink room is not huge, but it’s round and you could fit a larger thing in there. In general, the point here is that a long skinny area can have a lot of tiles in it, but it doesn’t really have a lot of room. A big monster can’t stand up in there, there’s not space to fly around, etc.

Now, let’s take another look at the grassfired version of the caves:

Now, we have a simple method of finding big open spaces – look for specks of white. Long skinny rooms end up mostly dark grey, because they’re not appropriate for boss fights (or whatever). The bigger our space requirements, the more iterations of our algorithm we can go through to ‘grow’ out from the walls.

Door ways and digging sites

Often, games need to be able to classify areas as discrete rooms. For instance, management games like Rimworld sometimes have to divide areas into rooms for things like whether a rotting corpse in the corridor should contribute to someone’s bad mood amount their bedroom decorations. Happily, these things are doable using the simple flood fill approach described above – simply count doors as walls for purposes of blocking the flood, and you’re good to go. However, when it comes to classifying places where creatures might like to build things, this doesn’t help us. We need to decide where to put the doors, rather than reacting to where the player puts them. So, what we’re going to do is the same old flood fill classification approach, but we’re only going to flood areas that are above a certain level of whiteness – that is, our flood fill won’t just be stopped by blocked tiles, it will also be blocked by tiles that are open but very dark. We get something like this:

We can see that most of the rooms are still considered a single room according to this approach, but the spindly formerly-purple room in the top left has been split into three small rooms, and the huge orange room is now considered two. Naturally, we could tweak the threshold of wall proximity (effectively, changing the grey darkness threshold for the flood fill to be blocked by) if we wanted to count bigger or smaller openings as doors.

Finally, we can re-flood from these colours, now getting all the open spaces. So long as we do all these flood fills in parallel, the distinct rooms’ colours will butt up against each other, showing us the place where a door should go:

Finally, we can continue this flood fill a bit further, beyond the open tiles, and into the blocked tiles. If any differently coloured rooms touch during this stage, instead of finding a door, we’ve found a place where we can tunnel between the two rooms. The more steps we go through expanding in this way, the longer the tunnel is that we’ll have to dig. For instance, above, the cyan and bright green rooms are coming very close – if we expand outwards a little bit, this is what we find:

Note that we’re not really expanding these caves, this is all exploratory. What we’re actually going to end up with when this is all done is something like this:

Coming up next…

This is all well and good, but we’ve ignored a little thing called gravity. In other words, this all makes a lot of sense for a top-down 2D game, but we’re overlooking the fact that these rooms don’t necessarily work for a platformer, since the doors are in the ceiling and there’s no space to actually walk around. I’ll talk about how to do those things a bit in the next blog post.