So in theory I should be working on the update to my game, WebUrbEx Lost Media, but instead I kinda got invested in going back to procedural generation of terrain. Almost entirely because I wanted to make a cross country walking simulator style game but very quickly decided I wanted to add the curvature of the surface of a planet to the environment so it looked better.
An introduction to Procgen
So Procedural generation for game environments is a bit of a whole ass field of gamedev, and it was the focus of my University final year project Before/After/Unbroken/Whatever I Was Calling It At That Point Dawn. I don’t expect everyone to be familiar with it, especially if you’re looking through the blog for stuff related to WebUrbEx.
In the past I’ve worked on procedural generation systems based on heightmaps, noise, and mathematical function “brushes”, projected on to a canvas of a Quadtree Cube Sphere. Lots of concepts there many of which lack Wikipedia articles. In this article I go over each in turn and give some examples, so we’re on the same level, and I will continue on in Part 2 with what I’m currently working on.
Heightmaps are easy, but have limits
This one’s fairly simple, hopefully. A heightmap is fundamentally the same thing as a texture, except used differently. On a heightmap, each pixel of the image corresponds to the height of a point on the terrain.
To make an explorable environment out of a heightmap, begin with a mesh, and then for each point on the mesh sample, find the corresponding location on the height map and raise the point to that level. This is called Displacement Mapping, as it displaces the positions of points on the mesh.
A big advantage of heightmaps is that all they are is an image, so if you wanna draw up your game’s level in paint and then use that as a heightmap… that’s quick. Similarly you can use IRL survey data to quickly recreate real places, see earth opposite.
There’s several downsides to heightmaps:
- They are 2 dimensional, so you can’t derive any overhangs or straight vertical rises from them.
- The mesh is only offset in height, so anywhere where height changes rapidly can lead to very stretched faces.
- This one’s the killer for me: Resolution. Heightmap terrain is only as sharp as the image you have for it, and the bigger and/or more detailed you want an environment to be, the bigger that texture has to be.
For that reason I’ve generally turned away from using them in favour of something that can be calculated on the fly, but that does give up the big advantage of just being able to draw levels into existence.
Side Note: Voxels
If a heightmap is a 2d texture showing a mesh how much to displace a flat mesh, a voxel map is a 3d texture showing a mesh how to construct itself in a 3d space. this solves the first two problems, though if you’re familiar with minecraft, you’ll probably be aware that the size of a save file can grow quite rapidly with the size of the world.
Noise: That thing everything uses
Coherent Noise, be it perlin noise, simplex noise, worley noise, or some other shit, is everywhere. It’s just a good method of making a random thing that still looks coherent. In VFX and games it’s used to make normal maps that make things look flawed and rough, but it can also be used to generate heightmaps or voxel maps: you probably know this kind of use from minecraft.
Generally speaking several different noise functions are layered over each other, which can create more complex rules. For example in minecraft biomes are selected based on several noise textures for heat, wetness, weirdness, and some other ones, then based on that biome the 3d noise for that region is filtered, scaled, etc to match the rules for that biome.
Side note: I don’t like GenAI asset generation, but this feels like a good opportunity to demystify the tech: Diffusion model image generators actually use noise, They start with a noise texture and then mark which bits don’t look like the image they’re trying to create, change those, check again, repeat until image ticks enough boxes to be handed to the prompter. Not magic, just image recognition tech used backwards.
I kinda hate how some of the tech around AI is genuinely interesting but because of the economic consequences of it, it just sucks at the moment.
Noise is generated using a pseudo-random number generator, which is deterministic, so feeding it the same “seed” starting number gives the same result. Handy. You can also just grab something unpredictable as the seed for truly random feeling results.
Also, one big advantage noise has is because it’s maths, you kinda don’t need to turn it into a texture. Hence minecraft generating new chunks as it goes rather than the whole world in one go.
What about the downsides? Well… it’s not always performant to calculate it on the fly and a lot of the time noise is baked into heightmaps specifically to avoid performance hitches from running a bunch of maths.
The big kicker is that “coherent” noise lacks intentionality, recurring patterns show up not for a reason, but because the patterns in the noise align again, and to me I’ve always found this makes noise based terrain, at least visually vapid.
I have for a long time been a proponent of trying to design procgen systems that de-emphasise the role of noise-based procgen. It’s still good at adding variation, but personally I find it better as freckles on skin on the flesh on the skeleton of more intentionally designed super-systems. Speaking of.
I call these brushes but that’s probably not their name
Remember how noise is just maths that you can sample at a given point? well there’s other things we can define mathematically, and this is the name I tend to group them under.
Say you want to make a crater on the surface of a planet. Well, what is a crater? a circular depression around a point of impact, surrounded by raised walls where the force of the impact blasted stuff away.
Say you want to make a river? What is a river? A source (or series of sources), in the mountains that flow down to a mouth at the ocean or sea, rivers always flow downhill so if a river has a set start and end point it flows downhill towards the ocean unless it hits a local minimum where it will either carve through, or form a lake which raises it above the obstacle required to continue.
I rather like the idea of playing around with “brushes”, creating terrain features with a set structure, placing them intelligently and then implementing them onto the terrain when resolving it. Obviously, performance remains a big limit here.
What is Cube Sphere?
A cube sphere is a cube where every point is normalised, which is to say made a distance of 1 from the centre of the cube. On a regular cube with a quad on each face, this… produces a cube with a side length of the square root of 2.
However if you subdivide the faces of the cube to have multiple quads, normalising each point starts to look like a sphere.
The point of this all is quad spheres are easy to work with. they have kinda even distribution of points (though not so much around the corners of the cube), and each face is a grid.
In short: sphere, but also grid. which is useful for:
Quadtrees
This is where we get into how this all works on a planetary scale.
A quadtree is a data structure where a face of a grid can be replaced by 4 smaller grids filling that space, and so on and so forth… essentially the point is it’s good for making LODs where details get more sparse the further away from the player they get.
Having a cube sphere subdivided to the point where terrain has fidelity at… let’s say 1 quad is 1 meter, on a tiny representation of a planet 2 km in radius… you need a lot of subdivisions and very quickly that starts eating up memory.
The alternative to having a whole planet in memory is to just subdivide the tree around the player, and then stitch the edges to the less sub-divided neighbouring grids. easier said than done.
Putting this all together… I made something that kinda sucks
OK so remember this image?
Yeah so putting this all together, aside from my pretty janky implementation, even when it was functioning I ended up with planets with this horrible aliased/stair-step effect. just inherent to the grid, the resolution of the heightmap, etc. I was a student at the time so… yeah no it still sucked.
I did attempt to refine this during covid, adding a second “glacier” sphere that allowed me to have two heightmaps over the world (one which could have holes in it) but aside from being a glitchy mess it kinda shows off the aliasing effect even more, as does the vertex colours that show up around craters in this more advanced terrain model.
Ultimately, while I think a lot of the problems with how I did this all previously would have been solvable somehow, especially with better optimisation (this started from a student uni project and there was some code in there I just didn’t want to refactor because when I tried rewriting it it stopped working and… I was not about playing that game when I had a functional system), I kinda dropped the idea of procgen around the time AI started making headway in the creative industries and I started focusing on more hand-crafted projects that… mostly didn’t get finished, and then eventually WebUrbEx being a very handcrafted project.
Coming back to 3D game stuff though I wanted to take another swing at it, again for having a “realistic” recedinghorizon for a small project’s terrain, in a very different approach to make something that (even if it probably would have its own limitations) would at least not have the same awkward aliasing and heightmap resolution related problems that my earlier attempts. it’s been interesting and actually a lot of fun to revisit… And you’ll have to wait to read Part 2 if you want to find out how the design has been going.
Remember who you are,
-Matt