2Bit Studios' Andrew Joy told us about the development of the voxel space survival Planetation using the procedural world generation system Frontier and explained how biomes are calculated with Voronoi diagrams.
Hello! I’m Andrew Joy and I’ve been working with Unreal Engine for nearly a decade. Most recently I’ve been developing Planetation, a frontier space survival game where you grow metals on your farm from the comfort of your retrofitted dual-purpose farming/battle mech – your Tractormech.
I’m here to post-mortem a recent redesign of our procedural world generation system Frontier. We had the rare opportunity to rebuild a core game system from the ground up, and this allowed us to incorporate years of procgen experience informed by the crushing weight of hindsight. These new techniques are what I’ll be sharing with you today and, whether you’ve got your own procedural game or you’re just here because procgen is so cool, we hope they blow your mind. Some programming knowledge is expected but experience with procedural generation is not – we will explain key terms as we go, so let’s get started!
Setting the Scene: Voxels
Planetation is fully procedural all the way down to its voxel environment. If you aren’t familiar with voxels, Minecraft cubes are a simple form of voxel! Voxels are just a regular 3D grid of values, usually environmental information like the colour or density of the ground. Voxels allow us to create the world with math at runtime, rather than hand-make everything during development. Minecraft cubes are just basic binary voxels with a spacing of 100cm, i.e. there is a fully filled or entirely empty voxel for every meter in every direction.
More advanced voxel games use smaller spacing sizes and more complex algorithms, such as marching cubes, to transform voxel data into visible geometry. This does away with the cube look, allowing for partially filled and partially empty voxels to appear as smooth slopes or shear cliffs. “More advanced” in this case also means more expensive to run, however, so voxels are a constant juggling act between fidelity and performance.
For the voxels in Planetation, we use the Voxel Plugin in Unreal Engine. It’s a powerful tool that handles raw rendering, collision, and foliage for us, but to create rich authentic worlds we have to extend it further. How does it know where the sky ends and the ground begins? Or what part of the ground is dirt, sand, or grass? For this, we have to create our own logic that can efficiently describe the entire world in low resolution, yet be rapidly transformed on demand into relevant chunks of high-resolution voxel data.
This is the purpose of Frontier, to abstract our humble voxels behind flexible logic that can power the world of Planetation. It’s our low-resolution layer and it’s very tightly coupled with the Voxel Plugin, so much so that when we chose to upgrade from legacy Voxel Plugin 1.2 to the shiny new 2.0 rewrite, we had to rewrite much of Frontier alongside it. Two key areas that received a complete redesign were our biome and landmark systems, so let’s break them down!
Like many procedural survival games before it, Planetation divides its world into a patchwork of distinct areas called biomes – you might be familiar with the forests, deserts, and mountains of Minecraft. Planetation, however, differs from the common temperature-based realistic biome model and instead generates increasingly more dangerous variants of the Outback, Mesa, Swamp, and eventually Salt Flats the further you venture from your crash site.
With Frontier, borders between biomes are defined by a single Voronoi diagram that spans the entire world. Voronoi diagrams allow you to calculate cell area, edges, and neighbours from a simple collection of points in space, allowing a very small amount of data to be transformed into a plethora of information when it’s needed.
Each cell is linked to a specific biome, and blending is performed between neighbouring biomes along shared edges. By slightly perturbing the locations that we sample we can break up the predictable straight edges into something that looks much more natural.
Two particularly important properties of Vonoroi diagrams that synergise well with voxels are determinism and parallelism. Determinism means that if we sample the same location twice we will always get the same result, allowing us to reliably tear down and recreate voxel chunks only when they become relevant to the player. Parallelism means we can safely sample the diagram at multiple locations independent of each other at the same time, spreading this huge amount of work easily across multiple threads.
Our legacy implementation of Voronoi biomes calculated most of its data at sample time. Edges, neighbours, and the relation between cell and biome were all runtime processes. Because each voxel often requires multiple samples before it can be fully generated (for properties like colour, density, and foliage), this leads to significant and unavoidable redundant calculations. In addition to this, our original implementation could also only manage a 2D map of biomes, and as such underground or sky biomes were completely off of the table.
The solution to this problem is rather obvious, yet far from trivial - simply pre-calculate all edges, neighbours, and relations at load time, then sample directly from this baked data at runtime. Our original implementation was built on top of a minimal Voronoi noise generator and we were already stretching it well beyond its limit, but, thankfully, Unreal Engine wraps a much more powerful open-source Voronoi library called Voro++.
In our new implementation, we construct our cell locations at load time, run them through whatever distortions we please, relate them back to each biome, and then finally bake it all out with Voro++ into a persistent Voronoi diagram. We store all the shape data we need for blending, such as edges and neighbours, which has the added benefit of being readily available for non-voxel tasks like drawing a minimap.
A further advantage of fully pre-calculating our diagram is that we can post-process it in ways that are only possible when we can see the “whole picture” at once. We can ensure that two incompatible biomes never appear next to each other, we can populate metadata such as randomly generated region names, and we can cache every minor detail that might speed up later sampling. And yes, Voro++ supports 3D diagrams!
By baking our biome diagram out at load time, our minimal generation benchmark (voxels only, no landmarks, no foliage) went down from ~73sec to ~32sec. In fact, we took so many calculations out of each sampling that the bottleneck quickly became the Voronoi cell lookup itself (where Voro++ determines which cell contains the sample location). There was no further way to speed this up, so we returned to the root of the redesign in the first place – Voxel Plugin.
The new-and-improved Voxel Plugin 2.0 samples each chunk of the world as a group. Because we know the boundaries of these chunks, we can pre-fetch every cell that a group of pending samples overlaps and then shortcut their cell lookups to only the pre-fetched list. This one additional optimisation saw our benchmark drop from ~32sec to an astounding ~6sec. We were, needless to say, ecstatic.
As previously stated, voxels are a constant juggling act between fidelity and performance. These improvements didn’t just help Planetation run faster, they were significant enough to unlock greater fidelity than ever before.
The Wonderful World of Landmarks
Voxels are great for solid, procedural surfaces like the ground below your feet, but you have to put stuff in your world to give it life. That’s where landmarks come in – standalone objects designed with a purpose, whether visual or interactive, such as trees, boulders, and explosive mushrooms. They aren’t themselves procedural (not composed of voxels at least), but they are placed procedurally in the world at runtime.
Generating landmarks is a complicated process, and is fraught with compromise. Everyone does landmarks differently and the Voxel Plugin doesn’t hold your hand here because there is no one-size-fits-all solution. This usually involves a two-step “gather and spawn” process; first gather as many landmark spawn locations as possible, usually by tracing the ground with rays for collision points, then spawn from a pool of possible landmarks at each location.
The “gather” step is a deceptively expensive process. Tracing thousands of rays against the ground is only the tip of the iceberg of problems. If you want to generate landmarks in the distance you first have to generate temporary collision geometry from the voxels, and if your landmark distance is far enough away then you run into Schrödinger’s procgen problem: you can’t tell if there is a surface in that chunk until after you sample all the voxels. Additionally, if you want landmarks on the walls or ceiling of a cave for example, you’d better be casting those thousands of rays again from multiple directions.
The “spawn” step is unfortunately non-trivial as well. Each possible spawn location is iterated for each possible landmark, so every filter you add (minimum spacing, random spacing, maximum elevation, required angle, surface, or subterranean) slows the process significantly. You also have to be able to query existing landmarks so that you can ensure things like the minimum spacing is respected, and you have to prioritise difficult-to-spawn landmarks over easy ones, otherwise, every location will become a twig or pile of stones. It’s a first-come first-served, a flood fill algorithm that can lead to clumps of one of every rare landmark bunched together around where they raced for the first free spawn locations – such as where the player starts from or where they teleport to.
These are all issues that our original landmark generator suffered from and that we solved in our redesign. We drew inspiration from Voronoi diagrams and general procgen theory, specifically the importance of determinism and parallelism. Furthermore, our solution only became possible due to the highly efficient world sampling explained in the previous section.
We begin by sorting all possible landmarks in a chunk by their maximum spacing and then for each landmark type, we generate possible spawn locations in empty 3D space. We perform a short-range search of the surrounding space thanks to our fast sampling, resulting in each location either being snapped to a surface in the world or discarded entirely. This process leaves us with a thin web of spawn locations draped across the voxel surface. Importantly, wall and ceiling locations are treated as first-class citizens alongside ground locations with no need for additional searches.
This process is very intensive despite the fast sampling, but it saves more work than it creates. First, we no longer require collision checks so we don’t have to generate far voxels or trace rays against them. Second, we don’t have to query existing nearby landmarks to enforce minimum same-type spacing, because our web of locations is already appropriately spaced for each landmark. Last but not least, we can gather the bare minimum of locations needed because we don’t have to worry about having enough spare locations left over once high-priority landmarks have gobbled them all up.
Furthermore, this process is fully deterministic so there are no concerns of clumping, and it can be run in parallel on worker threads. An additional benefit is that landmarks can be separately generated based on the visible size in the distance, i.e., trees can be created from afar but twigs and stones in their greater numbers and smaller size can be generated only when nearby. We’ve also extended this approach to foliage, greatly improving the quality of wall and ceiling foliage.
This new approach to generating landmarks has enabled us to create much richer environments, especially underground – such as adding a fully procedural geode event in our v0.9 release.
Despite these big advances, there is still plenty of room to improve on Frontier. We have a wishlist a mile long, but that’ll have to wait until the next time we get an excuse to go back to the drawing board. Good luck in your own adventures, and we hope this has been helpful!