Thursday, January 31, 2019

The global map - fractals

One of the most common methods of terrain generation is Perlin Noise, which is a method of generating random-looking variation over a constant scale. Amit Patel (again) does this and it combines really well with a Voronoi map, because you simply use the noise map to decide which Voronoi cells count as land and which count as sea. Alternatively you can use Perlin Noise by itself. Minecraft uses a 3D version of this to generate its terrains.

As I may have mentioned, I'm not a mathematician, and I don't really understand how Perlin Noise (or its various relatives) actually works. But I do know how an older method of generating noise works, namely the diamond-square fractal algorithm. The method is pretty simple: you start with a square grid, and put random values in the four corners. Then you follow a number of steps whereby you fill in the rest of the grid using the average of the existing values, with random perturbations. I haven't explained that very well (there are lots of better explanations online!), but the interesting thing is that it produces surprisingly convincing-looking landscapes very quickly, using a method that's not hard to understand. It's been used for this purpose since the mid-80s and it still popular now. Hunter Loftis made a widely-shared application of the idea which demonstrates its power and speed - you can play with it online here.

Can we use this to make our global map? One problem is that the diamond-square algorithm only works on square grids (and they have to have sides that are a power of two plus one, to boot). But we can get around that by sticking several squares together to make a rectangle. The squares have to share their sides, and everything gets a little bit complicated, but we can use this method to make a rectangle of whatever proportions we like. We can also vary the size of the squares to control the scale of the features that emerge. Lastly, of course, we need to adapt the algorithm so that it wraps around the east-west borders but not the north-south ones.

A lot of trial-and-error coding later, this is the result:

Dark areas are low in height, light areas are high. We can specify a particular height to be sea level, and render it so that any areas below that level are blue; we can also change the way we display the land, to give it more of a 3D-texture:

(I'll stick with the greyscale display method for the time being, though, as it's easier to see what's going on with the heights.)

So that isn't totally terrible to start with. We can fiddle with the size of the squares within the rectangle to change the scale of the features that emerge. Here it is with larger squares:

And with smaller squares:

Now immediately we can see some issues with this. The ratio of sea to land isn't really right, but that's easy to fix simply by raising the sea level:

That's better, but not much better. For one thing, the land and the sea are both mingled more or less evenly across the whole map. Compare that to a map of the real world:

In reality, the land clumps together in continents, separated by oceans (actually one big ocean). The diamond-square fractal can't do that. Moreover, the diamond-square terrain undulates fairly evenly over the whole surface. But on the real world map, most land is mostly flat, except for where it rises up into relatively narrow, well defined mountain ranges. The diamond-square fractal can't do that, either.

The diamond-square, and similar fractals and methods of noise generation, are great for making terrain at the small scale - a single island, or valley, or mountainside. Hunter Loftis's function, linked to above, demonstrates that very well. But it's terrible at making terrain at the large scale - a continent or a whole world - because it cannot generate large-scale coherent structures such as oceans and mountain ranges. You can get away with using this technique for larger areas if you're not too bothered about making something that looks like a real world map. For example, Dwarf Fortress uses fractals of this kind, or something very similar. It produces "world" maps that are really continental maps, and those really resemble smaller islands scaled up. That's fine for DF, which isn't really about the landscape, but I'd like something that can create genuinely world-scaled maps that look more believable. Fractals of the kind we've been looking at here will play a role in that, but they can't provide the basic approach to generating the terrain.

No comments:

Post a Comment