Procedural World Generation: Part 1 - Some Basic Terrain

I've been playing around with procedural world generation in Unity3D. It originally started out as a stress test for a Minecraft-esque cube based destructible terrain, but then moved into mesh based landscapes and experimenting with a day / night cycle. You can see the last version I played with at the weekend in the video below (the night time didn't convert too well to video).

So I started by using Unity3D's perlin noise function to generate a heightmap, I just fed in the x/z coordinate divided by a large constant number, and multiplied the result by the maximum height I wanted and rounded it. I used the number it generated to spawn prefabs cubes from 0 up to that height, I also set a global "water level" and if the generated height was lower than that I spawned a prefab cube from the generated height up to the water level. The result was this:

Single Perlin Minecraft

I used a coroutine so I could generate more land as I was walking around (anything bigger than a 20 by 20 grid was freezing the editor), and then made it so that it started at the origin and spiraled outwards, writing that looping logic probably took as long as it did to write the code to generate the heightmap in the first place! :$

This async method took many many minutes to render out to the maximum draw distance, and the framerate dropped very quickly, so straight up Minecraft terrain using prefabs, not going to happen! Pretty much what I expected Minecraft's engine is specifically design to render this type of terrain and I can still see it generating in the distance. Next I did a quick test where I only spawned the uppermost layer of the cubes (and the water), this did result in passable playability but it still took quite a few seconds to spawn significant chunks of terrain.

Given that Unity is capable of rendering terrain (lets not worry about details like tress or buildings yet) all the way to pretty much any max view distance you set, it's reasonable to assume the reason rendering it Minecraft style is not performant is because of the vast number of cubes you spawn as separate gameobjects, the rendering and processing overhead of storing the details for each and running fixedupdate / update for each was too much! The terrain system that's built in uses a single massive mesh, and that works pretty well. So the next thing to try is creating a patchwork of meshes (a patch work so you can generate it frame by frame on the fly, pretty much a requirement for an 'infinite' world), this is also a pretty natural evolution from a single layer of cubes.

I've generated meshes previously in Unity, so I just grabbed the boilerplate code from one of my other projects and change it so it generated a square on the x-z plane with the y coordinate specified by a delegate, into which I passed the same Perlin function as before. Water was slightly more tricky this time, I detected the minimum height of a mesh when generating it and then if it was less than the water level spawned a single square mesh the size of that patch of terrain at the water level. The result was this:

Single Perlin Mesh

This generated out to a very significant distance out within a second, and there was very little framerate drop even when the generated grid was over four times as wide as the view distance. So we can assume that if we only intelligently dynamically generated this terrain (rather than just spiraling out forever) it would have acceptable performance levels. This generated terrain is a nice start, but it's pretty isomorphic, it's all roughly the same height no large scale varition. It's pretty easy to add more variation simply by using another perlin noise function, by using a smaller divisor and either adding or multiplying the existing function by this causes variation over larger distances.

Double Perlin Mesh

You can quite few different 'feels' from your terrain just with a pair of perlin noise functions, by playing with the divisors (scale), post-multiplication factor (total height) and either adding or multiplying the two noise functions. I played with the fact a fair bit before I got the results you can see in the youtube videos. It's worth noting that the Unity3D perlin noise function takes inputs between 0 and 1, so you'll get a point of symmetry around the origin unless you add an offset to the values you pass in for x and z. Using a pair of functions with different scales can very effectively mask this though, especially when using an offset. Whilst the functions will generate a value between 0 and 1, it will be around 0.5 much more often than 0 or 1, see this unity answers thread for more info.

If you look closely at either of the previous two images, especially the first, you can see seams between the different patches of terrain. This is caused by the fact the automatic normal generation for the meshes can't adjust for correctly the next point on the terrain as it's on a different mesh. This is actually surprisingly easy to solve, you calculate the normals yourself, because you know the function which generates the terrain you can work out the correct normal. It's simply the cross product of the difference between adjacent vertex positions in the z and x axes.

All this is good fun, but this is a very bottom up design. The advantage is you can independently determine the height of the terrain at any point, very helpful if you want to create an infinite world Minecraft style, and it's fine if you're okay with a somewhat isomorphic feeling land. There are a number of disadvantages though, having sensibly placed and morphing biomes and generating large believable macro scale features like rivers, mountain ranges, roads and paths is very difficult. I found this extremely informative and refreshingly open article which discusses a more top down approach, where you start with what you want to achieve (believable coast lines, mountain ranges, sensible biomes) and then work backwards to the generation method. I'm impressed by what the techniques achieve so I'm going to work at implementing and hopefully improving some of them next!

As you can see from the videos I also did some additional work on a day / night cycle which should be transferable to any method of world generation (even building one by hand!), this will form part 2!

Read Procedural World Generation: Part 2