Tinkering with tools

Now that the actual terrain generation is mostly done (barring a few bugs, of course), I've been messing about with the UI, and I've added two new features that I've wanted to add for a while.

The first is the ability to change the colours and other settings used to generate the relief maps:

As you can see, you can change all the colours (thanks to the stylish colour wheel that comes with Nanogui), and also change the strength (and direction) of the shading, as well as the marbling effect and how many rivers will be shown. This allows the user to customise the look of their maps to quite a high degree from within the app. The settings stay with the world if you save it and load it later, and you can also save the settings themselves to apply to another world if you want to.

The second new feature is the ability to generate, and export, maps drawn to regional scale but of larger areas. The user can simply mark out an area on the global map that they'd like detailed maps of, and UW will draw the maps and save them to the hard drive. (You can't view them within UW, but you can of course open them in whatever other program you like.) So you can have maps like these:

That last image is pretty huge (3441x2017 pixels)! (It has the shading on land cranked up to maximum too.) As you can see, it's now possible to create detailed maps of entire continents if you so choose, as long as you don't mind waiting for them (the last one took a couple of minutes). It might in theory be possible to create a detailed map of the entire world, but I haven't tried...

The only feature left to add is the ability to import your own heightmap and have UW turn it into a complete world, including working out all the climates and rivers and so on. Some people have requested this, and I'd like to add it, but it would be a little complicated because I need to work out how to do mountains. (Remember, Undiscovered Worlds' mountains are not simply areas of high elevation on the heightmap - UW also stores ridge directions and connections, which are additional data. So I need to think of a way to create that data from raw heightmaps.) I want to avoid feature creep, so I may leave this to add at a later date, after I've released the first version. If I do that, then once I've squashed the more prominent of the remaining bugs and worked out how to actually create a standalone app, I'll be in a position to release it and let other people play with it.

Finishing the sea floor

Mid-oceanic rifts, with their associated ridges, are a really prominent feature of underwater terrain. The most famous one is the Mid-Atlantic Ridge:

But it's not really a single, discrete feature - rather, it's part of a network of rifts of this kind that wrap around the whole world, where oceanic plates are pulling apart from each other.

If we think of these rifts as basically arising at the mid-points between continental shelves, it's not too difficult to trace their paths. I can adapt the method I used to find the midpoints between mountain ridges. First, we place seed points along the edges of the continental shelves. Then we identify all the points next to those points. Then all the points next to those points - and so on until there are no points left. On each turn, we simply note down, for each point visited, which turn it was that we met it on. The result is an approximate map of how far each point of the ocean is from the nearest continental shelf, which we can represent like this (the lighter they are, the further):

Something weird happened in the western ocean there. It's something to do with the point at which the western boundary of the map meets the eastern (remember, after all this, the map gets adjusted east/west so that the boundary falls in the middle of the ocean, so the artefact there reflects where that boundary was before the adjustment). I can't work out quite why this happens, but it doesn't really matter, as we shall see.

Now the mid-oceanic points are those where two neighbouring points are closest to two different shelf points that are sufficiently far apart from each other. We can pick these out like this:

Obviously these are much too regular-looking. But we can do something about this by adapting the methods I used to make interesting continental shapes. First, we make an imaginary grid with squares a few pixels wide. Then we go through each intersection on that grid. If it's close enough to one of the points identified on the map above, we mark it. That gives us a set of points on a grid. Each one gets assigned a unique number, and we also identify its neighbours on the grid. If we draw lines between neighbouring points, we get an effect pretty similar to the previous one (now I'm drawing these lines on the elevation map itself):

However, because these lines are based on a list of points with known neighbours, and are not simply being read off a 2D array, it's now easy to move those points about and get wigglier lines. As with the continental outlines, I apply two transformations to them. One is based on a fractal, which determines how far north/south and east/west each point is moved. That means that each point is moved a similar (though not identical) distance to its neighbours. Second, each point gets a random nudge all of its own. Together, these two transformations give us a much more realistic map of oceanic rifts:

That looks a lot better. The rifts come and go, depending on the distance to the nearest continental shelf, but this should be fine as we can easily make the ridges' height depend on that distance, so they will fade in and out. If we do that, and also make the ridges wider, we get this:

I think that looks pretty good at the global level. At last, we can see where the tectonic plates of the world must be, even though my method doesn't actually simulate them at all!

At the regional level, though, it's not quite as impressive:

The ridge is completely undetectable! It is there - it's just that because it covers such a large area, the slope is gradual enough that you can't really see it. Clicking on different parts of the regional map reveals the different depths, but the changes are just not dramatic enough to be noticeable on the relief map, or indeed on the elevation map either.

Well, we can help things by adding undersea mountains. Oceanic rifts have parallel lines of increasingly more minor ridges running alongside them. As we raise the land on the global map, we can note down the distance each cell is from the central rift. Cells that are the same distance from that central rift can have underwater mountain ranges connecting them. With a bit of tinkering to improve the directions of the lines, and the addition of extra mountain peaks scattered about to stop them looking too linear (and also to reflect the chaotic nature of this kind of terrain in real life), we get something like this (the central rift is just off to the left of this map):

It's also a straightforward matter to add the central rift itself, with a high density of additional peaks around it:

I noticed something curious in one area though:

Where have these lines come from that are crossing the ridges?? By a process of elimination, I work out that it's something to do with the routines that draw the ridges themselves (nothing to do with the central rift or the peaks around it, or the random peaks that are scattered among the ridges). My best guess is that it's something to do with the pseudo-random number generator, which is set to a different seed for each tile before making the ridges there. Each tile's seed is, in part, generated by its coordinates on the global map, as well as by other distinctive properties such as its rainfall or temperature. It must be that in this region, the seed numbers in each column are similar enough that they are producing similar random numbers for the peak heights, leading to the illusion of these lines. They are not perfectly vertical because the locations of all of the ridge peaks are warped slightly by a global-scale fractal, which pushes them by a varying amount across the map to reduce the appearance of a grid. 

I can't make this happen in the same way elsewhere - for one thing, it would only create lines running north-south or east-west. But I'd like to reproduce the effect, or something like it, as I think that, by chance, it looks fantastic.

To do this, we need to store some new information at the point of world generation. Each central ridge point needs to know the angle of the line that is roughly perpendicular to the ridge at that point. Now, lines of this kind do not, in fact, normally pass through the central ridge at exactly right angles:

So this is my solution. We make (yet another) global-level fractal. On the basis of this fractal, we assign an angle - between 0 and 360 degrees - to every point on the map, so we have a global map of gradually changing angles. (Note: this means that making this fractal is a little more complicated than usual, because the values have to be able to wrap - e.g. if we're trying to find the midpoint between 30 and 350, the answer is 10, not 190.)

At the ridge points, we take the average of (1) this fractal-based angle and (2) the angle of the line that would actually be perpendicular to the ridge at that point. We will then use this average as the angle of the lines that we will draw on the regional map at this point.

This method ensures that we keep the realistic effect of mostly roughly parallel lines that don't cross the ridge at exactly right angles, without allowing anything too crazy such as lines that cross the ridge at a very acute angle.

Now, at the regional level, we go through each tile that contains central ridge in turn. (We do this for a considerably larger area than is actually shown in the regional map, because there might be lines entering the regional map from ridges that are off-screen.) Then we just draw straight lines from those tiles in the appropriate directions. Some of these are raised ridges, while others remove any ridges they encounter. The length and exact direction get a random offset too.

It takes a fair bit of experimenting (as well as a lot more maths than I'm at all comfortable with) to get it looking reasonable, but I end up with maps like these:

And I think these look pretty nice. Sometimes these radiating spikes make more of a confused jumble, but that's OK - confused jumbles are what mid-oceanic ridges are all about, really.

Now comes the tricky bit. Oceanic rifts are also crossed by more substantial fault lines that actually break up and stagger the line of the rift itself:

These lines are transform faults in the sea bed, breaking up the ridge systems:

How do we implement these?

Well, on the global map, we choose some points on the rift network. For each point, we shuffle along the rift a little way in each direction, to identify a short length of rift. Now we can use the work we've already done in the last bit, when we identified the angle of those lines crossing the rift at every point. We use the angle of the line at the point mid-way along our section of rift, and basically just shift that whole section of rift, and all its associated ridges and other information, a random amount along the line indicated by that angle. And we do that repeatedly all over the map.

That gets us this:

I found that the lines slashing across the ridges looked rather ugly on the global map, so I have toned down the pseudo-3D shadows around them, which helps. On the regional map, the lines of the faults themselves aren't actually visible. Instead, these areas look like this:

It's probably not tremendously realistic, but it adds some pleasing chaos to parts of the rift system, so I'll leave it at that.

One more feature I want to add to the oceans, at least for now, is deep-sea trenches. These tend to appear on the edges of some oceanic plates, where they meet continental plates:

To simulate these, I'll just run along the edges of some of the continental shelves drawing blobs. Where the blobs cover ocean that isn't continental shelf, I'll drastically increase the ocean depth.

And that gives us this:

On the regional map, these areas look like this:

And I think that looks suitably profound and mysterious.

With that, I'll leave the sea floors for now. They're not tremendously detailed or accurate, but I'm aware that most people probably won't care too much about what's going on down there, so hopefully what we've got now should suffice to add a little bit of believability.

Next, some refinements to the UI, including the ability to customise colours and other elements of the appearance from within the program.

Installing the shelving

The sea bed hasn't had much love from Undiscovered Worlds to date. I've basically just applied a bit of randomness from a fractal at the global level and left it at that - and completely ignored it at the regional level. But of course the real sea bed is far more complicated! We need to try to emulate the look of hydrographical maps if ours are to be at all convincing.

First, we need to sort out continental shelves. The sea bed doesn't just slope gradually down from the edge of the land - it remains relatively shallow for quite a way and then drops off fairly suddenly. This is where the continental tectonic plate ends and the oceanic tectonic plate begins.

A fairly basic approach to this isn't too hard to do. First, we go over the map and at every coastal point we draw a circle. The radius of the circles varies according to a fractal map. This means we get a gradual variation in size throughout the map:

That's a start. Now we also offset the circles by an amount that is also determined by a fractal map. That shifts the edges of the shelves in a slightly more interesting way:

Finally, we run the whole thing over a fine-grained Voronoi map to make the edges a little more interesting (and also to help fill in some of the gaps that appear from offsetting the edges in that previous step):

Note that this is done before we apply a fractal to the whole map in order to remove some land. That means that where land is removed in that stage, continental shelf is left behind. The map above doesn't have many areas like that, but you can see for example at the southern edge of that large continent in the middle, where there is a peninsula and an island. Those are the remains of a larger area of land that's been removed (compare the previous maps above, where this hadn't happened yet). The continental shelf still extends across this whole area, which I think looks pretty good.

After this we add just a few little tweaks. We choose some random points within the shelves to be the centres of circles which we flatten to the level of the shelf, to disrupt the edges a little. Then, we re-use the flood-fill routine to ensure there are no areas of oceanic depth within the shelves.

All of that gives us the basic shapes of the continental shelves. Now we can add some variation to their depth, as well as to the depth of the oceans themselves. As always, this can be done with another fractal. In addition, yet another fractal is used to vary the extent of the smoothing of the sea floor, making some transitions between continental shelf and ocean more abrupt than others. That (together with some tweaks to the colours and shading, and the addition of climates on the land) gives us this:

And that seems to me to be looking pretty reasonable. Note here that the additional processes involved in making the continental shelves have meant that more (pseudo-)random numbers have been used, which means that the random numbers used when subtracting some areas of land later in the map generation process are different. In this case this has led to some more substantial areas of sea within the continental plates, rather like the Baltic Sea.

Now how does this look at the regional level? It took some time to get this working at all, because I simply hadn't bothered with generating sea beds before, except as part of the coastal generation process. I found the best way was to create a whole sea bed terrain, distinct from the normal terrain, and then paste it onto the regional map wherever there was sea. That way, tinkering with the sea bed generation wouldn't mess up the very carefully balanced (i.e. tinkered-with-to-death) coastal generation.

Once that was done, I had this:

As you can see, that's unacceptably blocky. There isn't enough variation in the fractals in each tile to disrupt the tiles. I tried increasing the variation:

That is actually a pretty cool effect, but it's totally at odds with what I'm trying to do! It's caused by the edges of the tiles not matching, which is annoying as they're supposed to match.

Well, a day of tinkering sorts that out and I manage to get everything matched up and suitably bumpy:

The tiles are still very evident at the intersection of the continental shelf and the deeper ocean, though, no matter how much I crank up the noise. So I need to do something else to disguise this.

I came up with a variation on an idea I've used a number of times, which is to apply an irregularly-shaped template to a border area in order to disrupt that border. In this case I used some smudge templates with fuzzy edges, to make the disruptions blend into the rest of the terrain. I think it makes a decent-looking effect:

I don't know quite how realistic this slightly terraced look is, but I like it. (As with large lakes, though, I now have to create the seabed on a map much larger than the displayed regional map, and then trim away all the unseen bits. This is because the templates I'm using to create this effect are quite large, so they can alter the terrain several tiles away from where they are actually placed. This means that we need to calculate terrain for quite a wide area around the displayed area, to ensure that each tile will always look the same no matter where on the map it may appear. This is a hassle, and of course it increases the generation time, but I think it's worth it to get the better appearance.)

Now, real continental shelves often have much more complicated features at the transition to oceanic plate. For example, there are sometimes systems of trenches and canyons that look strikingly like river valleys, as with these off the coast of California:

These are caused by water currents and sediment flowing from the shallower areas to the deeper ones, and they carve out these canyon-like features.

The easiest way to mimic these is to think of them like rivers, and that means we can re-use the basic methods for calculating rivers. At least, you'd think so. After typing the above I spent two days first trying to rewrite those methods to apply them to this situation, and then trying to write new routines from scratch, before giving up. In a perfect world I'd have these canyons at the edges of continental shelves, and perhaps at some point I'll find a way to add them in, but for now I'm going to stick with what I've got (which does match the edges of most continental shelves anyway).

Next is the tricky part of sea beds: mid-oceanic ridges!

Mountains, Gandalf!

About a million years ago I designed a system for generating mountains that would allow for the creation of vaguely convincing ridges and valleys at the regional level. Now this was much better than just using diamond-square to add detail to the global heightmap, and in fact I was so impressed with my mountains that it spurred me on to try to make all the other elements in Undiscovered Worlds as good as they were. But the system does really leave a fair bit to be desired, compared to reality.

For example, here's the regional map I put at the end of my last post:

Those mountain ridges look superficially OK. But they're far too wide, really, given that one pixel is one kilometre, and they don't have any proper sub-ridges coming from them. When I initially made this system, I had difficulty doing that, and so I just added random lines of ridges sticking out in random directions from the main ridges, which makes them look a bit fuzzy but doesn't really make much sense.

Compare the Himalayas:

and the Pyrenees:

These are far busier than my mountain ranges, with all those little sub-ridges and valleys in between them.

So it's time to try to improve the mountains a bit. First, we make our main ridges thinner, and get rid of additional fuzziness. This is straightforward:

Now how do we go about adding buttresses to these ridges that make sense? I decided that the best way would be to mark key points along the ridges while drawing them, and then go through the map tile by tile. For each cell in each tile, we work out which of the key points is closest and how far away it is. It's then straightforward to identify all the ones that are a key maximum distance from the nearest key points. These form an outline some distance from the ridges. Also, any cells that are closer to their nearest key points than that, but which do not have any neighbour which (a) has the same closest key point and (b) is further from it, are cells that form the boundary between two watersheds, as it were.

The map probably explains it better. The ridges are in turquoise, cells that are the maximum allowed distance from their key points are dark pink, and the cells that are equidistant between two ridges are lighter pink:

Now all we have to do is to go over all of those marked cells and choose some of them to be the end points of buttresses. Buttresses are drawn from the key points on the original ridges out to the end points, with perhaps a bit of swerving along the way, and a gradual decrease in height.

Then we do all of that again, to create smaller, secondary buttresses that emerge from the first set of buttresses.

The result isn't as elegant as the real mountain ranges shown above, but it doesn't look totally unreasonable:

The relief map of this area looks like this:

I think that looks pleasingly rugged. Here's how the region I showed at the start of this post looks now:

There are a few other differences here, because I've been fiddling about with the grid-concealing elements that I talked about in my last post. But the main thing is that the mountains are looking a little more believable, I think.

Another range from the same world, showing how complex the ridges can sometimes get:

And finally, of course, where there are low mountain ranges, we have hills. These are now looking like this:

As I always say, it's not perfect, but it's an improvement. There will probably be endless tinkering to be done with this approach, and I wish I were able to get it more realistic in detail, but I'm quite pleased with the general effect for now.