Mostly Harmless


A blog about science, art, coding, life,... mostly harmless stuff.


PCG Terrain III: Adding Props

This post is mostly about adding some details to the terrain in the form of props (rocks and trees). We are not gonna spent any time actually designing or generating nicely looking rocks and trees. We are just gonna put some dumb cylinders and spheres with a bit of color. Instead, we are going to concentrate on making the generation of the props efficient. In a later post we’ll deal with actually generating nicer looking rocks and trees. Here is a picture of whats coming:

Dumb terrain details

But before that, I want to give a second chance to the terrain subdivision, to make a few points clearer.

Last post was about making an adaptive mesh generator that could provide both high performance and high quality. We kind of got away with it but using a region quadtree to represent the terrain, making successive subdivisions where more resolution was needed. I couldn’t post a detailed enough snippet, simply because there is no such a snippet. All the code necessary to make that kind of technique work is rather complex, even if not exactly rocket science.

In any case, although a complete implementation would be way to large to fit in a 1000 words post, I do want to point out some implementation details, in the hope of saving a few headaches that I myself got when trying to come up with a clean implementation.

Subdividing the terrain, revisited

The first thing I want to point out, is about how to expand such a quadtree. Remember, each node represents a patch of terrain, located in some fixed world coordinates, and with an specific width.

At runtime, we check the entire quadtree generated so far, and decide which nodes to destroy and which nodes to open. This decision can be based on an approximate screen size for the given patch, calculated by dividing the distance between two extremal points of the terrain patch plane and the distance to the camera, and then multiplying by the screen diagonal (in pixels). This gives a view dependent approximate screen size in pixels for each patch, which, if not accurate, is good enough for deciding which patches to close or open.

Those nodes whose patches have an approximate screen size bigger or lower than a given threshold are respectively opened or closed. Opening a node means creating four new children nodes (and patches) with half the dimensions, that together cover the same region of the parent patch. This effectively quadruples the resolution of the patch (remember also to hide/disable the parent’s mesh). Closing a node means destroying its children, and enabling its own mesh.

The second point is about how to explore the quadtree in an efficient manner that doesn’t kill your framerates. There are two tricky problems here. First, if the tree is very big, and/or you have to open too many nodes, chances are you’ll not be able to do that in a single frame, or even in a few milliseconds. So you have to split the opening and closing routine across many frames. This can be easily accomplished in Unity 3D by using a coroutine: basically wrap all your code in an enumerator, and drop a few yield return now and then to let the engine catch up with the framerates. But then, once you’ve done that, if you are moving fairly fast, chances are that when your coroutine actually opens a node that you decided was worth opening a few frames ago, the camera has already passed over it, and you’ll be waisting resources constantly opening nodes which are actually behind the camera. Believe me, it happens, a lot.

After playing around with BFS and DFS, trying to devise a clever way to sort the quadtree nodes based on the camera position and direction, I stumbled across a better, and simpler solution: iterative deepening. IDS is a tree search algorithm that works exactly like DFS, except it only goes down to a specific level, instead of all the way to the leaves. An outer loop increases this maximum depth by a given factor each iteration. Its taken out of the AI field, but with a few modifications, it can be made to work like this: each time the terrain generation coroutine ends, you restart it again from the root of the quadtree, recursing into already opened children. Once it finds a leaf node, it decides whether the node needs to be opened, breaking the recursion at that level. That way, in every full iteration of the coroutine, only one new level can be added to the quadtree.

This might seem like a waste of resources, starting all over from the root, but it is far faster to recurse into the portion of the quadtree that is already opened, than opening new nodes (which implies creating meshes and textures), so must of the work is actually spent at opening the leaf nodes. And the quick pruning of recursion makes it far less likely for a patch to get subdivided int a lot of high resolution pieces, just to be quickly closed. As a result, if you fly very fast over a patch, chances are it will get opened at most once, even if more resolution was needed; but hey, you left it behind in a couple of frames anyway, so what the hell. And when the camera sits still in a given patch, the generator will have enough time to divide it further and further until necessary. Now onto the main dish!

Adding rocks

We’ll be adding two kinds of props to make our terrain a somewhat nicer place to look at: rocks and trees. Lets begin with rocks. Our basic rocks will be plain spheres, painted with some noisy material that looks somewhat like stone (but it isn’t, just don’t tell anybody). Here is a closeup of a rather big one:

A nicely rounded rock

Putting loads of these round not-so-rocks around isn’t a big issue. You just need to decide at which patch size you want to start seeing rocks, and the next piece of code (inside your patch generation code) gets the job done:

int rocks = RandomInteger(MinRocks, MaxRocks);

for (int i = 0; i < rocks; i++) {
    // Our nicely rounded rock
    var rock = GameObject.CreatePrimity(PrimitiveType.Sphere)
    // Put it in random position inside this patch
    rock.transform.localPosition = Vector3.left * RandomUniform(-1, 1) * Width / 2 +
                                   Vector3.forward * RandomUniform(-1, 1) * Width / 2;
    // Set the scale
    rock.transform.localScale = Vector3.one * RandomUniform(1f, 10f);
    // Set the material
    rock.renderer.material = Resources.Load<Material>("Materials/Rock");
    // Attach to this object
    rock.transform.parent = this.transform;
}

Of course, I’m assuming you have the utility methods for random generation, and the correct materials in place. The attachment part serves two purposes. First, it correctly set the rocks world coordinates with respect to the patch. Second, it ensures that the rocks generated for this patch will be destroyed once the patch gets closed. Otherwise you’ll end up with a bunch of disconnected rocks lying around.

However, the tricky part here has nothing to do with actually generating the rocks, but with placing them in random locations. Since we are choosing random locations for the rocks, every time a node gets closed and reopened in the future, it will place its rocks in a whole different configuration! Actually, the same happens every time we run the program with our whole island landscape. Even though Perlin is a completely deterministic function, our Gaussian mountains are generated with random centers, so the whole island landscape is different from run to run. But there is a very easy way to turn any (pseudo)random algorithm into a deterministic one: by controlling the random number generator seed.

Controlling the randomness

See, the thing with random generators is, most of them are not really random. They are called pseudo-random generators, because they generate a sequence that looks random (for a given set of statistical tests), but is actually completely determined by the internal state of the generator, which often consists of a single number, called (in a low and grave voice) the seed. The theoretical reasons for this are way out of scope right now, but nevertheless it serves well. We just need to seed the random generator with a fixed number (like 0), and we’ll have a completely deterministic sequence of random numbers.

However, it is not enough to have a seeded random generator to guarantee that our procedural algorithms are deterministic. This is due to the fact that although every decision in our algorithms depends solely on the state of the random generator, their order depends on the user. That is, we choose to open or close some node by looking at the camera’s position. This means that in every two different runs of our program the camera will, in general, take a whole different path (users are nasty people, I know), so we will be opening and closing nodes in a different order, so we will be using the same sequence of random numbers all the time, but we will taking asking different questions every time, so the overall result will be just as random as before.

The solution for this is to have a different random number generator at each node in the quadtree. Every time we open a node, creating four children, we give each of this children a new seed for their own use. These seeds are generated themselves using the random generator of the parent, which is seeded with the parent’s seed. All props created at any level in the quadtree are based on a second random generator in the parent, also seed by its own seed. This way we are effectively creating a hierarchy of random number generators, each one completely determined by its parent seed, so the whole system is essentially encoded in a single number: the seed of the root. Our whole world, with all his mountains, bumps, rocks, and trees can be stored, shared, and completely recreated by means a single number!

Just a final tip: I’m using .NET’s native Random class instead of Unity’s own, because in Unity the Random class is static.

If you want to give it a try, just download the demo (~10 MB), and try to find the pond in the following picture. You’ll find out is just exactly like that:

An oasis of clean water

Layering rocks

To add a final touch to our rock generation algorithm, we’ll introduce one more change. Instead of generating the rocks on a single level of the quadtree, we can generate them in every subsequent level of the quadtree. If we calculate the scale of the rocks based on the size of the patch, we can effectively have a multi-resolution rock map. Since we are already generating patches efficiently, we won’t be adding too many rocks, because only close enough patches will have very small sizes, and hences, loads of small to medium to large rocks. Far away patches will only have very large rocks. This way we have a high density of tiny rocks near the user, and a few bigger and bigger boulders in the distance.

Adding trees

Trees are just as easy as rocks: pick a single level of the quadtree where you want them, and drop a few of them just like you did with rocks. For this time, we’ll be using very dumb trees, more like a wooden stick with a green puff on the top, or a big and strange grass lollipop:

A nicely looking round tree

Horrible, I know, but we’ll have to deal with that next time.