Infinite Procedural Generation: 2 -- Chunk Indexing

In my last post, I discussed how chunk-based generation of Minecraft's infinite world works (on a very basic level). In this post I want to talk about implementing such a system in practice.

In fact, I want to try and lay out a very general way of thinking about chunk-based infinite generation. One that works on 2d and 3d grids of any type, irregular partitioning of the plane, and much more.

Chunk Indexes

Indexing chunks seems trivial, but I promise there's somewhere interesting to go here.

We need to pin down a system for identifying chunks. There are two reasons for this:

1. Chunk indexes are generally used as keys when storing chunks
2. Chunk indexes implicitly provide a system for transitioning between world coordinates and their associated chunk.

The simplest chunking system is axis aligned squares, as discussed last post. Here, the chunk index is a tuple of integers, and can easily be found via integer division.

index(x,y) := (x//16, y//16)

We can also reason about which points belong to each chunk (cx, cy).

16cx <= x < 16(cx+1), 16cy <= y< 16(cy+1)

There are other conceivable systems though. For instance, we could use a hexagonal grid to make chunks. Natural indexes for hexagons are also tuples, but the mapping is a bit more complicated.

There's also the potential for more irregular chunking systems. It's conceivable that some aperiodic tiling or other irregular partitioning could produce good results. Tiles could be Voronoi regions of some arbitrary infinite graph, or correspond to simulated geopolitical boundaries. In these systems, there might be some arbitrary function to create chunk indexes from world points.

Chunks could also parameterize non-euclidean spaces! For instance, we might be looking at the surface of a large sphere. Technically this system is finite, but it could be prohibitive to generate and serve the entire world at once, so applying infinite generation techniques is desirable. We can also imagine some game taking place in a hyperbolic space that truly is infinite. In these systems, the world coordinates are more complex than just normal tuples.

We can even think about more exotic world coordinates. Perhaps the world coordinates are discrete, and each world coordinate corresponds to a node in an infinite graph. Chunks are small collections of "nearby" nodes. We could handle this case by embedding the graph in some other world coordinate system and using chunks in that system, but we don't technically have to, as long as we have some system for partitioning the world coordinates.

Some definitions

In general, let's create the following conventions for our abstraction.

We have some space of world coordinates, W. A specific member of this set is denoted by w∈W. We also have a set of (discrete) chunk indexes, C, with  c∈C. We'll also define a "boundary" type, b∈B. This boundary denotes a contiguous set of world coordinates. 

We'll also define two related functions to map between these domains.

index: W↦C

boundary: C↦W

These functions must obey that ∀w, ∀p∈boundary(index(w)), index(w) == index(p).

In plain English, index / boundary should partition the world coordinates into discrete, predictable chunks.

Chunks and Layers

Something I kind of glossed over in my last post is that world generation, typically, doesn't happen all at once. There are intermediate steps.

When I discussed cave generation, I mentioned that during each chunk's generation process, it would need to look at cave seeds in surrounding chunks, but these chunks may not be generated yet! How can we find the cave seeds without generating them (which in turn would generate all their neighbors, ad infinitum)?

There are a few different answers here, but in my view the most extensible one is to think of world generation happening in layers.

In this case, we can generate cave seeds in a separate layer, that depends on nothing else. It's just random points, say 2-5 selected per chunk index. This "cave seed layer" doesn't need to look at any other chunks during generation. It just is. When the "world with caves" layer is generated, we can look only at this "cave seed layer" -- we don't need to know, and therefore don't need to generate, the full content of the neighbor chunks.

These world generation layers need to form a pre-determined directed acyclic graph, with higher order layers depending on only layers below them. Some layers don't have any external dependencies and can be generated completely independently. Others will require exploring other layers and neighboring chunks.

Note that both the nodes and edges in this graph have interesting interpretations.

In one sense, nodes contain data -- there's a mapping between the index of the chunk and the contents of that chunk. In another, it's helpful to think of the node as simply being a function which takes in the contents of its dependencies and outputs this data.

Edges don't just note that we need to look at the contents of a layer, they also contain a rule about which relative chunk indexes to look at. I call these mappings "chunk index transfer functions".

Chunk Index Transfer Functions

Given a chunk index in one layer, the transfer function maps us onto  

chunk_transfer: C↦𝒫(C)

Note that while the above definition, we're implicitly assuming that all layers use the same chunk index system. That isn't required. We could use different indexes for each layer, in which case, the slightly more general statement for the edge between layer a and layer b is:

chunk_transfer: C_a ↦𝒫(C_b)

Example

For instance, we can imagine a chunk transfer function for Minecraft caves. Given a chunk index, we need to select all chunks within the maximum cave length. We can express this distance in terms of the size of a chunk, a quantity I'll denote L.

within(L)((i,j)) := {(i+di, j+dj) ∀ di∈[-L,L], dj∈[-L,L] }

Note that we could tighten this substantially -- we're finding all chunks within Manhattan distance L, where we probably in fact want chunks within Euclidean distance L.

Memoizing Chunk Contents

To make this work, we'll probably want to memorize the contents of most, if not all chunk contents on each layer. For right now, let's assume that the contents of each chunk are some arbitrary data.

Each layer can be memoized separately, ore we could put them all into a single dictionary. For right now, let's keep them separate.

A world can be therefore memorized in a Dict[Layer, Dict[ChunkIndex, ArbitraryWorldData]], or any equivalent data structure. There are definitely interesting choices to be made here, since there are clear patterns in how chunk contents get read. For now, I won't explore this further.

World Generation

Putting this altogether suggests a simple approach to world generation.

For a given  desired world coordinate, lookup the associated chunk. Optionally, extend to all nearby chunks.

Now, follow the transfer function edges to determine which chunks need to be generated for each dependent layer. Where possible, pull from the memoized cache. Each chunk that doesn't exist is generated and cached.

It's also possible to batch generations for each layer, if there are efficiency gains to be had.

In the next post, I'll discuss one of the simplest non-trivial applications of this work, generating Poisson Discs, and hopefully share some actual code.

Infinite Procedural Generation: 1 -- Introduction and Problem Statement

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

1. Generating any chunk, regardless of its position, is approximately as expensive as generating any other.
2. 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.