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.
No comments:
Post a Comment