Wednesday, February 20, 2019

Tinkering with coastlines

I'm pretty pleased with how the coastlines have turned out, for the most part. But we need more variety.

I've already integrated one way of adding variety, which is to have a global "roughness" map. This is just yet another world-sized fractal. It influences the roughness of the diamond-square algorithm used to create the regional terrain. The higher the roughness at that tile, the more the algorithm will offset the values it assigns to points. That means that, among other things, the coasts will look a little wilder in "rougher" areas.

Also, landfills aren't used anywhere that sea ice is present, to make those coastlines look a bit rougher. The landfills tend to make for a slightly smoother appearance.

We need more though. One feature we currently lack is barrier islands. UW is quite capable of generating islands at both the global and regional levels, but barrier islands are distinctive in that they are very thin, lie close to the coasts, and mirror the coast.

The thing with barrier islands is that although they are quite common, they tend to cluster along particular coastlines. They are much more common along coasts that have low tidal range, that is, where there is little height difference between low and high tide. Tidal range, in turn, is affected by how exposed the coast is to the wider sea. More sheltered coasts - e.g. along Mediterranean-style inland seas - have smaller tidal range than coasts that face the open ocean.

Calculating tidal range properly would be pretty nightmarish, but fortunately it's not too hard to get a rough approximation that is good enough to make a vaguely plausible distinction between areas that are likely to have lots of barrier islands and those that aren't. On the global map, we take each coastal cell in turn. We then "cast" in all eight directions away from that cell - that is, we look along imaginary lines in all of these directions. For each one, we keep going until we hit land, and remember how long the line got. Then we add all eight of those numbers together. The higher the total, the more exposed the coast is and the higher its tidal range.

Barrier islands are too small to show on the global map, of course, so they only appear on the regional map. Drawing them is pernickety but fairly straightforward. It's a matter of finding the coastline on the tile, then copying it a couple of cells out to sea, with occasional breaks in the copy and occasional links to the land. The tricky bit is ensuring that we don't accidentally create sections of sea that are entirely enclosed by land, so we have to keep track of whether the lagoon (the area of sea between the island and the mainland) at each point is open to the sea or not.

This results in tiles that look like this:



And in regional maps that look like this:

They're hard to see as they're only one pixel across, but they're there.

Another feature we can add for more variety is glaciation effects. Wherever there are (or have been) glaciers, you tend to get very jagged coastlines with lots of fjords and little islands. Think Norway, of course, or Chile, or the west coast of Scotland. A fairly easy way to get a vaguely reasonable imitation of this, that looks nice though doubtless wouldn't be remotely convincing to a glaciologist, is simply to extend the mountains into the sea. So at the global level, we go over the coastlines. If we find any that are below a certain temperature, and that have mountains along them (of whatever height - remember that "mountains" might be fairly low hills), we add extra ridges sticking out into neighbouring sea cells, without adding any land below them. These don't show on the global map, and these cells are still considered sea rather than land. At the regional level, these mountains are drawn, and they give the effect of jagged coasts with lots of islands:

It's not perfect, but I still like to think Slartibartfast would approve.

Saturday, February 16, 2019

Carving the rivers

We've got basic terrain, coastlines, and mountains - the bones of the world. But rivers make it feel alive.

Thanks to our work at the global scale, we know the amount and direction of water flowing through every tile of the map. Our task at the regional level is to work out precisely what route it takes through each tile, and to find a way to make that affect the terrain via erosion. We'll store flow volume and direction on an array for the regional map just like the global map. But where almost every cell in the global map (apart from oceans and deserts) has at least some flow on it, this will not be the case for the regional map. So this will look much more like a river map as opposed to a water drainage map.

We can start by repurposing the code from the mountains. The method we used for tracing mountain ridges - from the corners or edges of the tile, via splines, to a central junction point - will work equally well for rivers. For any given tile, there may be water entering the tile from several directions, but it exits in only one direction. All of that information comes from the source cell in the global map, of course. So UW sorts through the flows entering the tile and finds the largest. That is the "main" river of the tile. UW then draws that river, first to the central junction, and then from the central junction to the exit point. It uses splines exactly as it did for the mountains, not worrying about calculating things like meanders, which would rarely be visible at this scale (remember, each cell on the regional map is 2 km across).

There's some additional jiggery-pokery needed though, because the spline function never yields diagonals - it always draws lines that go up then across (or vice versa). We don't want that all the time for the rivers. So I add a function that goes over the drawn river and cuts some of the corners, to produce a more realistic effect.

This gives us tiles that look like this:

Like the global river map, the regional river map stores direction of flow, and flow volume in both January and July. The volume for each cell within that tile is just copied from the flow volume of the source cell on the global map.

This gives us river maps that look like this (darker blue indicates more flow):

Obviously we want the tributaries to meet up with the main rivers. This is harder than it was for mountains, though. There, it didn't matter if the ridges entering a tile all met at the same point - that wouldn't look odd (and in any case there were almost never more than three or four ridges entering the same time). Here there could easily be six or seven flows entering the same tile, and it would look very weird for them all to meet at the same point. Rivers don't do that.

So for each lesser flow that's entering the tile, we have to find a unique point for it to join up with the main flow. So we trace down the length of the already-drawn main flow for a random number of points and make that the target for the new flow. Moreover, if a flow hits another flow before reaching that point, it will end, so it's possible for one tributary to flow into another one before either reaches the main river.

That gives us this:

The flow volumes for the tributaries are taken from the source cells for the tiles that the tributaries are coming from. When a tributary hits an existing river - whether it be another tributary or the main river for this tile - it ends, and its flow is added to the existing river all the way downstream until the exit point of the tile is reached.

Now the map looks like this:

This isn't bad. Also, it's at this point that I had to go back to the global river generation and add lots and lots and lots of tweaks to the depression-filling algorithm and the flow direction calculations to try to get the rivers looking like they go in believable directions. Although I'm writing this account as though I did all the global stuff first and only then did the regional stuff, in fact they go somewhat in tandem because it's only when you can see things at the regional level, sometimes, that you can see what needs changing at the global level.

If there is precipitation in the tile a river is flowing through, it gets additional flow volume from that precipitation. At the moment, this isn't modelled very well - each river just abruptly increases in volume as it passes from one tile to another. (You can see that at some points on the map above where rivers get darker blue at sudden points.) In reality this extra volume would be delivered into the river from other tributaries which arise within the tile. So let's add those!

For each tile, the program now starts off the main river with the total flow of the previous tile that it just came from. It then calculates how much additional flow it should be receiving in the current tile, minus the amount that comes from other rivers entering the tile. This is the amount that should come from small rivers that arise within the current tile (call these springs). It creates several such springs, dividing the additional flow between them, and makes them flow until they hit an existing river. When they do, their flow is added to that river all the way downstream to the exit point of the tile, just as with other tributaries.

Now we get tiles like this:

The main river here flows from the east and leaves the tile to the west. A tributary comes in from the northeast, and other rivers can be seen passing in the northeastern and southeastern corners (remember that tiles share their corners with neighbouring tiles, so these are really rivers in those other tiles). Several springs rise in the tile and flow into the main river. This image doesn't show the relative flow sizes, which makes the map look somewhat confused, but if you examine the flow directions and sizes for each cell it makes sense.

So, skipping over the months of bug-hunting and attempts at optimising this stuff, we have a river network on the regional map that looks quite decent. The rivers wiggle pleasantly across their tiles and meet up more or less convincingly, and the flows are correctly calculated. But what about erosion? We ignored that at the global scale, but we can't at the regional scale, where the effects of fluvial erosion ought to be much more apparent. Rivers ought to erode away the land over which they pass, if they're moving swiftly. If they move slowly, they deposit material. Both of these are notoriously complicated to model.

Here's my solution. You'll notice that, in designing the river courses over each tile, UW has completely ignored the actual terrain in that tile. In general, of course, the rivers will follow the terrain downhill from tile to tile, because that's how they're calculated at the global level, but this ignores whatever local lumps and bumps have been generated within the tile at the regional level with our ever-useful diamond-square method. This is because UW actually does the rivers before it does the local terrain.

The idea is to work out the heights of just the regional cells that the rivers pass over, during the river creation phase. Within each tile, each river starts at the height of the global source cell for the tile it just came from (minus a constant, because rivers should be generally lower than the rest of the terrain in their tiles). When it leaves the tile, it is at the height of the global source cell for the current tile, minus that same constant. The program makes it drop by the appropriate amount as it passes through the tile.

This is more complicated than it might sound, because of tributaries. It may be that a tributary enters the current tile from a tile that is lower than the height of the main river at the point that it hits it. In that case, the height of the rest of the main river has to be recalculated to accommodate it, to ensure that the tributary doesn't leap uphill to join the main river. This may result in a sudden drop in level from the higher part of the main river to the lower, but that's fine - it could be a waterfall.

Anyway, once all these complications are worked out, we have a river system with each river cell assigned a height on the height map, such that the rivers flow constantly downhill. (In fact a lot of the time they flow over completely level ground, but we can live with that.) Only then do we move to the terrain creation phase, using the methods already described. Now the diamond-square algorithm is set so that it doesn't attempt to assign heights to points that already have them; and it will react to existing heights by taking them into account when assigning heights to other points. Because we subtracted a constant from the global source cell height when assigning heights to the rivers, they are lower than most of the rest of the land within the cell. Also, we set the algorithm to mostly nudge heights up when creating the terrain. The upshot of all this is that the land tends to bulge upwards around the rivers, which looks pretty much like the rivers have carved valleys through the land.

The effect can be fairly subtle on the elevation map, but you can now see rivers running through valleys, with hills rising around them:



It's also visible on the relief map, which shows only rivers above a certain flow level. You can clearly see some of the valleys created by smaller, otherwise unseen rivers:

This also has an effect on coastlines. If the river height level is lower than sea level, we get an inlet. So for example:

I think this looks pleasingly natural. In fact when I set this up originally it happened much more often. Something I've done since then (who knows what?) has raised land levels near the coasts and caused this to happen a lot less often. I'm trying to get it to be more frequent again, but that's yet another work in progress. You'd think I could just make the rivers lower, but that seems to break them in incomprehensible ways, so I'm going to have to think about it.

That aside, we're almost there. One more thing to do is to tinker with the visible width of the rivers and their associated valleys. As it stands, every river is one cell wide (i.e. 2 km). Really big rivers should be wider than this. And even more modest-sized rivers might be expected to have wider valleys.

So I add a function that goes over the tiles and increases the visible width of the rivers. Rather than monkeying about with the river array, this uses another array, so that we retain the "real", central portion of the rivers on the proper river array and use the other one simply for the extra bits that are added to make them wider. (This is much easier to do than to explain.) This is simply done by working out how wide the river should be at each point, and if it's more than 2 km, drawing a circular blob of extra river over that point. Wider valleys are equally straightforward, with the program drawing a circular blob of the appropriate height on the height map around the river cell in question.

Here are some images showing the effects. Here is a medium-sized river with an extended river valley around it, which on this visualisation is marked in green:

These green areas are forced to have the same height as the river at that point, so the effect is of a wider, flat valley floor.

A larger river has a much larger valley:

And a larger river still actually takes up more cells itself. They are marked in lavender-grey:

The centre of the river is marked in blue, showing that this is the "real" course of the river, but on the regional relief map it will appear to be three pixels wide - with, of course, an even wider valley around it. (On the river map, we still show all rivers as just one pixel wide, but with higher flows shown in darker blue, as I think that is more useful for seeing their precise courses.)

The relief map of the region we've been looking at now looks like this:

And if you look at the height map, you can see the large valleys around the major rivers:

Was that worth the many months of failures, incomprehensible errors, rivers flowing uphill, coastlines going berserk, all relived in feverish dreams night after night? Probably not, but I'm sure I'm a better person for going through it. Anyway, the next job is to get the rivers to interact properly with lakes, which is where it gets a bit tricky.

Regional climates

Now we have the terrain sorted for the regional map, it's fairly straightforward to do its climate too.

We already have precipitation calculated for the global map. So we can just adapt the diamond-square algorithm that we used for regional terrain to precipitation. Here's a random area of terrain:

And here's the precipitation map:

You can see how it looks roughly right, with the mountains casting a clear rain shadow to the east. (I think that patch of rain in the south is something to do with the mountains being rather lower there, but if not, it's undoubtedly some complex set of local conditions and definitely not an awful glitch in my climate algorithms.)

Temperature is tougher, for two reasons. First, the range of possible temperatures is much smaller than the range of possible precipitation amounts. That makes it hard to use the diamond-square method to get smooth gradients. The solution: multiply the temperatures by a constant, to make them all much higher (or lower, if below 0). Then run the diamond-square method. Then divide them all back again. This sounds clumsy but it does work.

The second reason it's tougher is that temperature is affected by altitude, and we want it to reflect the terrain on the regional map properly. That means we can't just blur a global-level temperature map, which is what the diamond-square method is effectively doing. The solution: remove the elevation element of the temperatures. Then run the diamond-square method. Then go over the whole regional map and add the elevation element back in. The result:

You can see that the temperatures are properly lowered precisely where the mountain ridges and peaks are, but not in the valleys, rather than being generally lower over the whole mountain area.

Now we have temperatures and precipitation for the regional map, we can easily produce a climate map using that information:

And we can also produce a relief map, using exactly the same methods as for the global map, which hopefully looks a bit more pleasing to the eye:

Finally, sea ice. This is sorted in much the same way as temperature. There are only three possible values for sea ice (none, seasonal, and permanent), so a fair bit of clever tinkering is needed to make this work with the diamond-square method, but it does. Here's the transition between permanent and seasonal ice near the North Pole:

There are a few annoying little artefacts there, which I haven't got round to dealing with yet, but generally this works fairly decently.

Wednesday, February 13, 2019

Making mountains

Consider the following regional height map:

This is supposed to be a mountain range. I've included the grid to help with scale. Each of those squares is a tile, and each one corresponds to a single cell or pixel in the global map. So each one represents an area 32 km across.

Which means that that mountain range is like nothing you'd see on Earth. It's at least a hundred kilometres across for much of its length, and it has only a single (very vague) central ridge. So if you were to walk across it from one side to the other, you'd just have a very long, gradual, undulating slope upwards, and then another one downwards.

Compare a real mountain range, such as the Alps:

It has lots and lots of ridges on a much smaller scale, with valleys in between them. That's the effect we need to replicate if our mountains are to be at all convincing.

It was when I realised this, while doing the regional map, that I went back to the global map and rethought the mountains completely. Originally they were just long blobs, which looked nice at the global level but were hopeless at the regional level. As I posted earlier, I changed the design of the mountains so that they are stored in two arrays: one stores the height of the mountains in each cell, and one stores the direction of the ridges. Here, again, is what that looks like in diagrammatic form:

The greyscale shows the height of peaks in each cell, and the yellow lines are the direction of the ridges. These ridges can meet and divide - any given cell can have ridges going off in any or all of the eight directions. (That means that the ridge information for each cell can be stored as a single eight-bit byte, which I think is nifty.)

As we saw before, on the global map only the heights are used - the ridges aren't needed at that scale. And UW maintains two global maps: one with the mountains, and one without, because that allows it to fill depressions on the no-mountains map, to work out the rivers, without creating absurdly high plateaux. So what we'll do now is to change the regional map so it is calculated only from the no-mountains global map, not the one with mountains. And then we'll add the mountains onto that using a different technique.

First, then, we make UW calculate the regional height map from the no-mountains global map:

There's still a noticeable rise in the land where the mountain range was. That's because, when UW makes the no-mountains map, it raises the terrain under the mountains a certain amount. It does this so that rivers (which are calculated on this map, not the mountains map) still run away from mountains, as they should. So we get this gradual rise in the land on the regional map too. But that's good - the ground does typically rise gradually towards mountains, before crinkling up into the ridges and troughs of the actual ranges.

Now we draw the mountains over the terrain. It's fairly straightforward really. As with the basic terrain, we go over it tile by tile. For each tile, we first establish the directions in which ridges are coming into the tile from its neighbours. This is easily done, by reading it off the ridge array. Now the ridges that are coming in from the NW, NE, SW, and SE must do so from the corners of the tile, because those are the only points where it touches its neighbours. What about those that come in from the N, S, E, and W? We could make it so that they come in at the middle of the tile's sides. That would be consistent and easy to calculate, but it would make the mountain range look far too gridlike - it would be obvious how it was made. Instead, we need to make them come in from random points on the tile's sides. But they have to join up with the corresponding ridges in the neighbouring tiles.

The solution is something we've already seen when creating the basic terrain: random number seeds for each side of the tile. The northern and western sides of the tile are assigned the same RNG seed as the tile itself. The eastern side gets the RNG seed of the tile to the east, and the southern side gets the RNG seed of the tile to the south. Now we go through each side in turn, resetting the RNG seed and then choosing a point at random on that side to be the ridge entry point. This ensures that when ridges pass from tile to tile they always meet up.

(A complication: if we do this then the northern and western ridges will always look similar, because they're randomised from the same seed number. So the northern seed gets another value added to it to make it different. That means we have to do the same to the southern seed, of course, because that's just the northern seed of the tile to the south.)

We'll be drawing the ridges from these entry points to a central junction point, where they all meet. Of course we don't want that to be right in the centre of the tile because that would create a grid effect, so we offset it by a random amount.

Now we can draw the ridges. For this, we use splines again. Each ridge is simply a spline that goes from the entry point on the side to the central junction point, via a middle point which is also offset by a random amount.

The result is a series of lines showing where the middles of the ridges will be:

You can see that the ridges don't seem to be perfectly aligned with the higher ground, but that's OK - it just means that the land will be sloping more gradually up to the mountains on one side than on the other, and that adds realism too. It's caused partly by the fact that the ridges are drawn through the middle of the tiles while the terrain heights are calculated from the corners, and partly by randomness governing which tiles UW raises the height in, and by how much, when making the global map.

To make these into more reasonable-looking ridges, we need to do two things. First, we need to make the heights of the ridges change more gradually - you can see sharp changes in the heights in the image above, where the ridges pass from one tile to the next. We should also add randomness to this height variation, so the ridges rise and fall naturally. Second, we need to make the ridges wider and slopier. This is straightforward too: instead of just raising the terrain of a single point, we paste a peak template over the ridge points. In fact, to add ruggedness to the ridges, we'll only draw peaks over some of the points of the ridges.

Adding these changes yields this:

This is starting to look something like a mountain range!

But the valleys in between the ridges are too wide. In fact, real mountain ranges have buttresses, or sub-ridges, running off the main ridges in a more complex system than we've got here. I spent some time trying to make buttresses that ran off perpendicular to the direction of the main ridges, and couldn't get it to work. In the end I just made buttresses go off in random directions. The effect is pretty similar:

And really that's it. I suspect that this method will need further tinkering should I develop UW to include a still closer level of zoom. The peaks may need to be narrower, the buttresses may need to be longer and taller, and they may even need to have buttresses of their own, if it's to look convincing closer up. But all of these things can be added easily if they prove to be needed. As it is, the system produces what seem to my inexpert eye to be pretty believable mountain ranges at this scale:

Where the ranges are lower, we get smaller mountains and, effectively, hills:

Monday, February 11, 2019


How much time, toil, and failure the word "coasts" evokes for me! Writing this account of the work I've done to date on Undiscovered Worlds is an odd experience, because I'm missing out so many failed attempts and false starts, and complete impasses. The coasts are a case in point. I despaired of ever getting these to look right, and at one point decided trying to do it fractally was simply impossible, and started designing coastal tile sets.

Even stripping back UW as it currently is to try to show more primitive versions of its outputs misses out a lot. Take the point we reached in the last post:

In fact, the first version of the regional map with diamond-square was far worse than this - it was a mess that barely reflected the shape of the land, with enormous numbers of inland "seas" and fragmented islands covering the ocean. So what you see here already reflects a lot of tinkering with the settings of the diamond-square algorithm, but it's probably a good thing that we've skipped over all of those.

The main moves I took to make the coasts look better were:

(1) Adjusting the distortion value of the diamond-square algorithm, i.e. the amount that it displaces values by. Higher values lead to bumpier terrain, lower to smoother. I lowered it overall, but particularly on coastal tiles, to avoid having too-jagged coasts all the time. For this to work, I also adjusted the global map-making functions to make the sea at coasts somewhat shallower and the land somewhat lower too, to create something like the right amount of smoothness. If the sea is too deep and the land too high, the coasts are all straight edges as the diamond-square algorithm has no wherewithall to displace the values by. If the sea is too shallow and the land too low, it gets far too crinkly, with lots of islands (OK) and isolated bits of inland sea (not OK).

(2) Adapting my flood fill function to remove all remaining bits of inland sea. This represents something of a failure on my part. I wanted to ensure that every tile, as far as possible, is self-sufficient. That should mean that if any sea is present in the tile, the program is able to work out - without having to look at other tiles - whether that bit of sea connects up with the main ocean (in which case it's OK) or doesn't (in which case it must be filled in). I spent a lot of time trying to develop algorithms for UW to be able to work this out, but most didn't work and those that did made the coasts look very unnatural. So in the end I gave up and applied the flood fill routine to the whole regional map, after the tiles had all been done. Any area of sea that is fully contained within a single tile, or only two tiles, is considered an isolated pool and removed. Others are allowed to remain. This isn't an elegant solution to the problem, but it does work.

(3) Creating a new method of doing coastlines, which I call landfills. Basically, the methods described above resulted in quite jagged coastlines. The coast tended to form bays in each tile, with the arms of the bay at the tile edges. While fine in isolation, this looked a bit odd overall. So I added a function which fills these bays in. Imagine a tile that has land in the northern half (roughly) and sea in the southern half. The function locates the points on the eastern and western edges where the land and sea meet. It then draws a line between them, and uses midpoint displacement to make it wobbly. Any points to the north of that line that aren't already land are raised above sea level.

The idea of making coastlines by directly drawing them with fractals - rather than by allowing them to emerge from an overall fractal terrain - isn't new. But it has difficulties, such as how to stop the coastline from refracting back over itself. My method works quite well because the fractal coastline is drawn only at the level of the tile, that is, a 16 x 16 block of pixels. Within that, it can't really get out of hand. The overall shape of the coastline is still determined by the original global map. Moreover, my landfills don't create the coastline within each tile by themselves - they combine with the coastlines created by the diamond-square fractal within each tile. That also lends some control, since the shape of that fractal is determined to some extent not merely by the relative location of sea and land cells on the global map but by their height.

These work quite well at smoothing the coastlines without creating too many straight lines. (I turn them off wherever there is seasonal or permanent sea ice, since those areas ought to look more rugged.)

(4) Finally, UW goes over the map and cleans and tidies: it removes odd little stick-shaped islands that have a tendency to form, and it also checks for coastlines that have too-long straight lines. If it finds any, it pastes a random blobby template right over them (either creating new land or eating it away).

With all of these techniques added, we have:

And I think that's starting to look fairly reasonable. But those big, vague-looking, lumpy bits along the northern coast don't look very realistic given the scale this is supposed to be. (This image is about the size of France, remember.) They're meant to be mountains, but that's not what mountains look like at this scale. So that's the next problem to tackle.

Thursday, February 7, 2019

Creating detail on the regional map

Let's start putting the terrain together.

So the regional map is divided into 30 x 30 tiles. Each of these tiles corresponds to a single cell or pixel on the global map (call that the source cell). Somehow we have to translate the single height value of that one cell on the global map into a 16 x 16 square of pixels for our tile.

Well, suppose we take that single height value and put it in the top left-hand corner of our tile:

That's a representation of a 16 x 16 tile, taken from the local visualisation that Undiscovered Worlds creates as part of its regional map screen. The square with the highlighted white border just marks the point that the user is currently looking at. The grey square in the top left is the only cell that has a value, because that's the one we've just put in.

What you can't see here is that the tiles all around this one also have a value in their top left-hand corners, too. That means that if we think of this tile not as a 16 x 16 square, but as a 17 x 17 square which shares its edges with its neighbours, we have a tile with all four corners filled in. Those four corners take their value from four neighbouring cells of the global map. If we expand our visualisation to show that whole 17 x 17 square, with all four filled-in corners, it looks like this:

And that tile has sides whose lengths are a power of two, plus one. Does that sound familiar?

Yes, we're going to diamond-square this thing! Usually with a diamond-square fractal you seed the corners with random values. But there's no reason why we can't seed it with known values, as we're doing here. Note also, this approach doesn't violate our tile-autonomy principle (that is, that each tile should, as far as possible, be created without reference to its neighbours). We're taking information not from the neighbouring tiles on the regional map but from the cells in the global map that border our source cell. And we can get their values just straight from the global map, without having to look at other tiles on the regional map. Indeed this will work even for a tile on the edge of the regional map, whose neighbouring tiles aren't been created at all. (It won't work for a tile whose source cell is right on the southern edge of the global map, because it has no southern neighbour, but that's OK - we just won't allow regional maps to go right to the southern edge of the global map.)

But we won't just do the whole tile in a single diamond-square function. This tile is sharing all four of its sides with its neighbouring tiles. That means we have to be sure that they will match - e.g. the northern edge of this tile has to be created in a way that makes it identical to the southern edge of the tile to the north, because they're the same line of cells.

This isn't too hard. It's simply a matter of (a) assigning a seed value to each edge, which can be replicated by neighbouring tiles, and (b) creating the whole edge by midpoint displacement based on that seed.

(a) is straightforward. The tile as a whole has a seed number, which is determined by a formula that includes the coordinates of its source cell in the global map and the precipitation in that source cell. This yields a unique number for each tile, based wholly on its source cell, which means it will always have that same seed number no matter where on the regional map it is drawn. The northern and western edges of the tile belong properly to this tile, so each of those edges will be assigned that seed number. The southern edge really belongs to the tile to the south, so we'll give that edge the seed value of that tile (which we can easily calculate from its source cell). And the eastern edge really belongs to the tile to the east, so we'll give that edge the seed value of that tile.

This ensures that every edge will be given the same seed value no matter which tile it's being currently used by.

Now for (b). This is a one-dimensional fractal, which is basically a simplified version of diamond-square. Imagine we're filling in the northern edge. We take the northeastern and northwestern corners, which have values; we find the mean of of those values; we increase or decrease it by a small random amount; then we put that value in the point at the middle of the northern edge. Then we do the same thing again twice, once for the line between the northwestern corner and the middle point, and once for the line between the middle point and the northeastern corner. And so on, until the whole line is filled. Do that for each edge (first setting the RNG seed to the seed number for that edge), and our tile has its edges - and what's more, they are guaranteed to match the edges that it shares with its neighbours:

It may look like all the border squares are the same colour, but they are actually different - it's just hard to see as they differ only slightly, as they should.

Now all we have to do is use the diamond-square algorithm to fill in the rest. The algorithm is set not to attempt to assign values to points that already have values, so it won't be put off by the fact that the edges are already filled up (which you wouldn't normally do with diamond-square). That gives us something like this:

If we do this to every tile on the regional map, we get a complete regional map. The island that we looked at in the last post now goes from this:

to this:

That is obviously not ideal. But it's a big step forward. You will notice that not only do we now have much more detail, but the jagged straight lines are greatly reduced. E.g. look at the middle of the eastern coast of the island in the original picture: it goes to the north and east in a series of steps. In the fractalised version, those steps are obscured. This is because the height values of the tiles around that coast in the global map aren't constant - they reflect the fact that they're forming an oblique line. This is preserved in the corner values of the tiles and in the fractals they form within the tiles. It's certainly not perfect - you can still see some blockiness along the coast, and in fact new linear artefacts have been created between some of the tiles inland. But it's a start.

This use of the diamond-square algorithm to create new detail within tiles (rather than across the whole map in one fell swoop) is what allows us to expand on the large-scale structures created in the global map, such as mountain ranges and coastlines, while still keeping those structures intact. I think that this interplay between the large scale and the small scale, when it works well, is what gives these regional maps their interest and makes them much more realistic (at least superficially!) than maps created by fractals (or other forms of noise) alone. So this is a technique that we'll be using a lot.

But there's a long way to go yet. That coastline is a mess, so that's what we'll be tackling next.

Wednesday, February 6, 2019

Zooming in: the promise and problems of regional scale

We've reached a stage where Undiscovered Worlds can create worlds at the global scale, but that's not really the heart of the program. I always planned for the zoomed-in, regional level of detail to be the main point of interest.

My thinking was in part inspired by No Man's Sky, which procedurally generates planetary terrain during play. You can fly over immense landscapes that just keep on coming, with the details created as they're rendered - but in such a way that if you go back again you'll see the same things as before. But a problem with No Man's Sky is that it lacks large-scale realistic features such as mountain ranges and rivers. It made me think: what if you made a fairly basic world map first, with large-scale features of that kind, and then based the terrain on that, expanding it as you go? That would keep the idea of procedural generation on the fly, allowing for a huge explorable terrain, but it give some structure to that terrain.

So that's the idea behind the regional scale of Undiscovered Worlds. And in fact it's become another example of the principle that combining different terrain generation methods produces more interesting results than using just one. The terrain that appears at the regional level of UW is the result of a combination of the large-scale terrain of the global map with different terrain generation methods at the regional level. The global scale provides the broad shape of everything, but new details are added using other techniques.

So it works like this. UW creates a new global map (or loads one in). The user can click on different points of the map and get basic information about that point: elevation, rainfall, climate, etc. If they like, they can press a key and UW will generate a regional map based on an area of 34x34 pixels of the global map, centred on that point. Regional maps are not discrete tiles of the global map - if the user had clicked a point just a couple of pixels away, the map would have been centred on that point. But each pixel of the global map is always expanded in the same way in the regional map. You could in theory scroll over the global map, from pixel to pixel, generating a smoothly scrolling regional map, although it would be horribly slow.

Each of those pixels in the 34x34 grid of the global map is turned into an area of 16x16 pixels in the regional map. The regional map is effectively divided into 34x34 tiles of 16x16 pixels each. (The tiles share their sides with each other though to ensure smoothness.) And the regional map is created by going through each of those tiles in turn and generating its terrain - and then going through them all in turn and generating their temperature, or precipitation, or whatever.

There are several challenges to this. The most important one is:

How to make sure that each tile is always exactly the same, no matter where it may be?

Consider the following zoomed-in section of the world map we had UW make in the previous few posts:

This is 34x34 pixels, so each of these little blocks will become a tile of 16x16 pixels on the regional map. Consider any one of these - say the dark green one in the middle of the south coast of that island. It's surrounded by eight other blocks. In the regional map, these will all have to become 16x16 tiles that make sense next to each other - e.g. if one of them has a coastline in it, that coastline must meet up with the coastline in the neighbouring tiles. And of course the same goes for rivers, mountain ranges, and everything. So it looks like, in generating one tile, the program must take into account the tiles next to it. But now suppose the user leaves and goes back to the global map, and then zooms in on a slightly different area:

That block is now on the edge of this area. So it's missing three of the neighbours it had before. So how can the program know, when generating the tile based on this tile, what's in the neighbouring tiles? It won't have as much information available to generate it. Yet it must generate it so it's identical to how it appears in the other map. That's essential if we're to maintain the illusion of a huge, persistent world - that will be ruined if features appear different every time the user zooms in on the map.

So that yields a basic principle of the regional map: each 16x16 tile must, as far as possible, be autonomous. It must be able to be generated in isolation from all others, so that it always appears the same no matter what other tiles appear around it.

In practice, this hasn't been possible. Some features in tiles inevitably spill over into neighbouring tiles. For example, mountain peaks must sometimes straddle tile boundaries, otherwise there would be long straight valleys going through the ranges at those boundaries. So I've had to bend that basic principle on occasion. I've got around that by doing two things. First, such incursions from neighbouring tiles can only affect directly neighbouring tiles - they can't affect anything two tiles along or more. Second, I make it so that although an area of 34x34 tiles is generated, the tiles along the edges of that area are never displayed. They will be lacking any elements that would have spilled over into them from the next tiles along, that haven't been generated. So they might have the wrong appearance - so even though they are generated (in case they affect the ones we can see), they are not shown and we'll just pretend they're not there. In fact, I also had difficulties generating terrain in tiles on the left- and right-hand sides of the regional map, which I solved in a similar way. So in the event, the displayed regional map is actually 30x30 tiles.

All of this leads to the second challenge, which is this:

How to avoid making the map look like it's made of tiles?

I want the maps to look natural, like they are of real places, as far as possible. But the fact that the maps are actually based on expanded blocks means they have an inherent tendency to look blocky, with lots of straight lines and right angles, and that spoils the illusion.

To illustrate, this is what the heightmap of the island in that zoomed-in section above looks like in the regional map, if we simply take all of the heights in each tile directly from the corresponding points in the global map:

That's the starting point for the regional map. Somehow we have to make it so that blocky coastline becomes a smooth, convincing line which obscures the original blocks from which it's actually constructed. The straight edges have to vanish - for example, consider the line of three blocks in a row on the southern coast, or the line of four in a row on the opposite coast, or the vertical line of eight on the far west. We have to find ways of drawing coastlines that follow this rough shape without revealing those straight lines, and what's more we have to do in such a way that respects (as far as possible) the basic principle of making each tile self-sufficient. And of course what goes for coastlines goes for everything else: the gradients of the terrain inland, the shapes of the mountains and rivers, the temperature map, and so on.

Not an easy task! And it's a constant work in progress. But for reference, here is how UW, in its current form, handles that island:

It's not perfect, but we're getting there. So in the next few posts I'll try to explain how it's done.