I know it's been forever since I've posted. Maybe I'll write another post about why I'm coming back now sometime. Regardless, I plan to try and make shorter, more regular posts.
Procedural Generation of infinite game worlds is hard. It's hard because it presents challenging technical problems. It's hard because an infinite world can make things seem very same-y. It can cause challenges in structuring player progression. Finally, it's hard because a lot of the really cool techniques and algorithms people use for procedural generation are hard to adapt to infinite worlds.
It's this last point I want to explore in this series. How can we apply procedural generation techniques typically used in smaller examples to an infinite world? Which work well? Which can be reliably composed together?
I believe I have a compelling framework to do this. I've seen some early success adapting some pretty interesting techniques, and I want to share my progress as I go along.
In this post, I want to take some time to discuss how existing systems, particularly Minecraft and Factorio, approach this problem. I picked these examples because they're successful games with procedural worlds at their core, and both are fairly well documented, with active modding communities that deeply understand the world generation systems.
I'm going to stay high level in this post, just giving some context. In future posts, we'll take a closer look at some of the implementation details.
Chunks
First, these systems break the infinite world up into "Chunks" -- finite tiles that can be independently loaded and processed. Both of these games use a 2D Chunk system, but there's nothing inherently special about that. It would be just as sensible to for Minecraft to use 3D chunks, and it would be reasonable for a side scrolling game (e.g. something like Terraria) to use 1D chunks.
Really the relevant thing to think about here is how many dimensions of the world are infinite -- in Minecraft, for instance, the world extends infinitely in all horizontal directions, but there's a finite amount of vertical space. You can't mine infinitely deep, or climb infinitely high into the sky.
In Minecraft, these chunks are fairly small relative to the player -- just 16x16 blocks. Factorio isn't much different -- only 32x32 tiles. For most applications, it makes sense to keep the Chunks small. As we'll see, Chunk size doesn't have a lot of effect on what algorithms you can use during generation; it's mostly a practical choice for in game performance.
You want to be able to load and save chunks to the disk quickly, so the relevant tradeoff is more about keep chunks small enough to make loading fast, but large enough that you're not going to be doing potentially expensive disk seek operations too often. Both of these games have picked a chunk size such that the player can traverse across a chunk in about 3.5 seconds of real time.
Both of these games have also selected axis-aligned square chunks, which are easy to index and translate into screen / game coordinates. As we'll probably discuss in a future post, I don't think this choice is always the best during the generation process, but it makes a lot of sense for performance and simplicity when actually serving up an infinite world in game.
Chunk Generation Order Shouldn't Affect the Result
We should be able to generate chunks individually and in any order.
In theory, we could envision other systems. A sweepline / sweepcircle algorithm starting at the origin would enforce the order in which chunks are generated. Alternatively, we could imagine a system when each new chunk is based directly its already generated neighbors, so that two players, starting with the same seed, would see different worlds based on the order in which they explored.
But these systems have undesirable behavior -- in the first, world generation becomes more and more expensive as the player moves away from the origin. In the second, we risk creating boundary conditions that are unsatisfiable or absurd -- Imagine two players approaching the same chunk from opposite directions. Player A is on top of a huge mountain, Player B is sailing on a massive ocean. The world generation system would be forced to construct a massive cliff within a 16-tile region in order to bridge the gap.
It's better to add the constraint that, in some sense, the world is fixed by the seed, and we can just peek at only the parts we need at any given moment. This means that we need to ensure that
- Generating any chunk, regardless of its position, is approximately as expensive as generating any other.
- The order in which we generate chunks should not matter.
Bounded Reach Effects
In order to compute the contents of a chunk, you should only have to look at a small neighborhood around that chunk. As an example, let's think about how Minecraft's caves used to work. Newer updates have made caves into a much fancier system, but the old system is easier to understand, so I'm going to start there.
Classic Minecraft caves are basically Perlin Worms. Let's not get bogged down in the specifics yet; each cave is a long, wiggly line, which starts from some point, and extends up to some maximum distance. Let's assume that we can find all the places a cave should start within a chunk (I'll call this a cave seed), and that we've got some way to actually generate the cave itself -- given a cave seed, we can determine which blocks we should carve out.
The core observation here is that because a cave has a maximum length, when we're generating a chunk, we only have to look in a fairly small radius around that chunk for the cave seeds. If each individual cave can extend at most 256 blocks, then we only need to look at the Cave seeds less than 16 chunks away. That set of cave seeds will tell us which blocks in our chunk we need to remove.
Because of the way caves can intersect each other, we will end up with systems of caves that intersect each other, and extend further than 256 blocks -- potentially infinitely -- but each individual chunk only needs to look at its immediate neighborhood during generation.
Many algorithms only care about the immediate neighbors of a chunk. Others, like cave generation, need to look at a larger, but still constant, set of neighbors. I'll talk about how I've come to abstract these sorts of relationships in a future post.
Perlin Noise and other Infinite Functions
Perlin Noise, Simplex Noise, and other similar coherent noise functions are a mainstay of procedural generation. part of the reason is that they naturally obey a lot of the properties we've been talking about above.
Imagining we have some mathematical function f(x,y,z) with closed form, we can evaluate that function at any point, in any order, and get consistent results. Methods like Perlin noise operate by summing up small, local wavelets. That means that, to compute the noise value at a specific point, it's possible to examine a small, finite amount of wavelets -- just like the cave seeds. It's a natural fit -- and that's even ignoring the fact that many applications work by summing noise at multiple octaves, which may mean it's possible to create infinite, apparently non-periodic noise just by sampling a small number of finite textures.
Regardless, there are a bunch of clever ways to use noise functions to create features of infinite worlds. You can threshold the value to create ore patches. You can multiply or sum noise with simple or even linear functions to create terrain surfaces, or enforce difficulty curves (e.g. Factorio ore patches get richer as you move further out -- but so do the density and intensity of biter nests). You can use the same noise channels for different things, leading to correlations among the generated features (e.g. richer ore under mountains). You can create coherent biomes by using noise to generate temperature, rainfall, and "geology", and then apply simple functions on top of those values.
In fact, it's tempting to think you can do everything this way! In a general sense, perhaps you can, but in my opinion, this approach comes with pitfalls. In particular, it's hard to enforce structure on a world generated this way. It defies simple mid-generation modifications, and it can be hard to interpret and reason about behavior.
It also pushes things towards an interpretation where the underlying world is being sampled from a continuous function. That's a good fit for some applications, but it breaks down around things that are supposed to look designed or sensible. It's easier to make an organic, natural environment that works this way than a city, or highway system.
Pre-generated Structures and Sub-Generators
One way to augment noise based generation is to take inspiration from our Cave seeds from earlier -- what if we used the noise to place structure seeds? Then we could stamp down pre-created structures on these seeds, or even invoke smaller, finite, procedural generation sub-routines to create complex structures for each of these seeds. As long as we know in advance what the maximum size of a generated structure is, we can use the same approach as caves to stamp them down.
Minecraft works exactly like this. Desert Temples, Villages, Mineshafts, Ruined Portals and more are effectively small, self contained generators that operate after the basics of the world are laid down. They give a lot of control and structure to the world.
In my opinion, they're also one of the weakest aspects of Minecraft's world generation. Procedural generation of "designed" structures is hard, but Minecraft's villages tend to feel incredibly same-y. There's only one type of Desert temple, and once you've encounter it, you know them all. Structures never interact with each other, or tell a broader story. You might come across a village and a mineshaft just blocks away from each other, but they won't influence each other -- there won't be more mining-related jobs in the village, and you won't find a mineshaft that even attempts to look like it's in active use.
People are still great at coloring in the blanks and telling a story, but it helps a lot if the world makes some attempt to help or hint at depth. Minecraft doesn't do that, and one of the big reasons is this seed system -- every structure seed needs to be generated independently, and in a specific order. They don't get an opportunity to "talk" to each other in a meaningful way.
In a future post, I hope to talk about alternatives that approach the same problem a bit more cohesively. I think embracing the idea of small, structured "stories" like "this village uses the nearby mine to create goods for export" is essential to getting a good result.
Wrap up and Conclusion
I think this is a good place to call it for today. I've mostly discussed how Minecraft's world generation system works at a 1000ft view -- use noise to generate a bunch of big continuous natural world functions, add discrete seeds various places, then use sub-generators to make structures within that world of small finite size.
As long as you follow some simple, and not too restrictive rules, you'll be able to generate the world, chunk-by-chunk, in any order you want. And once you have those chunks, you'll be able to serve and modify them without worrying about world generation at all. The pitfall is that sometimes these restrictions keep you from creating easy wins, and they make certain types of cross-chunk structure hard to create.
There are a lot of important details involved in implementing this system. My next post will probably be about how to think about creating the abstractions needed to implement, and extend on this system, because I think the seeds of greatness are tied up in the details here. I'll then start to talk about how to make some (imo) interesting "toy" infinite generation systems that challenge what's possible.
