Simple Map Generator Part 3 ( Elevation )

Hey again!

If you read the previous part ( Part 2.5 ) you probably already know I decided to just convert Amit’s code from now on and keep my personal additions at minimum. Hopefully I’ll also be able to post more frequently , just because of this too.

But again let me remind you this , since we’re working on a totally different framework and somewhat different structure , it won’t be exact same as Amit’s original code. There are still some differences  like order of calculations or WPF related extra code here and there but the algorithms and stuff will be almost same.

Also if you remember Part 2.5 was totally optional , even not recommended so we’ll keep working on Part 2 now.

 

This is what we had at the end of Part 2 and now , in this post, we’ll talk about and implement elevation calculation.

 

It seems like Amit decided to do this in two little parts , first calculating the corner elevations then redistributing the elevation and scaling all numbers down to 0 – 1.0 range.

 

To do this , we’ll first find the corners at the edge of the map and set their elevation to zero and every other corners elevation to a very high value ( double.MaxValue ). this will create a huge , long block and then we’ll carve our island from it.

 var queue = new Queue<Corner>();

 foreach (var q in App.AppMap.Corners.Values)
{
   if (q.Border)
  {
    q.Elevation = 0.0;
    queue.Enqueue(q);
  }
   else
  {
    q.Elevation = double.MaxValue;
  }
}

 

This part is pretty self explanatory I guess. If it’s a border , we set elevation to 0 and Enqueue that corner to use later. If not , just set elevation to double.MaxValue.

You may have noticed that since we’re using Queue , we’ll calculate elevations as if we’re flood filling a space. Now that we have some corners to start with , we’ll take one , process it , add it’s adjacent to queue , and dequeue the current one.

I guess it’ll be easier to explain with code ,

 while (queue.Count > 0)
{
     var corner = queue.Dequeue();

     foreach (var adj in corner.Adjacents)
    {
         double newElevation = 0.01 + corner.Elevation;
         
         if (!corner.Water && !adj.Water)
        {
            newElevation += 1;
        }
         
         if (newElevation < adj.Elevation)
        {
            adj.Elevation = newElevation;
            queue.Enqueue(adj);
        }
    }
 }

So we take corners one by one , find it’s adjacent , if that adjacent is not water , we increase the current corners elevation by a tiny bit and set it as the adjacent corner’s elevation.

This , like a flood fill , go find every corner on the map and set it’s elevation based on the lowest corner around it. Oh and if we change the elevation of a corner , we add that corner to queue again because it’ll also effect it’s adjacent and we must repeat this process for them too.

 

This method should get you something like this now ,

WindowClipping (4)

Notice the elevation at the left side bar , it’s above 10.96. But we want elevation numbers between 0 and 1.0 , also a little bit more control over the general elevation distribution on our island. So we’ll use this numbers as a base value and redistribute elevations from scratch.

double scaleFactor = 1.1;
var locations = App.AppMap.Corners.Values.Where(x => !x.Ocean).OrderBy(x => x.Elevation).ToArray();

for (int i = 0; i < locations.Count(); i++)
{
    double y = (double)i / (locations.Count() - 1);

    var x = 1.05 - Math.Sqrt(scaleFactor * (1 - y));
    if (x > 1.0)
        x = 1.0
    locations[i].Elevation = x;
}

 

OK this part is a little bit more complex so I’ll go slowly.

First of all let me explain the Amit’s plan here a bit. It seems he wanted to distribute elevations in a way that elevation frequency will be directly related to the elevation itself. In example , only the 0.1 of the corners will have 0.9 elevation and 0.2 of them will have 0.8 elevation and so on. Admittedly I’m not a fan of this , but here we go,

We’ll start off by setting a scaleFactor. Scale Factor is pretty much maximum elevation on the island. We’ll use it for calculations but later clamp the elevation between 0 – 1.0 anyway.  This will create a bit more mountain tops at max elevation on our map , so it won’t look like just one sharp spearhead.

Then we select the corners we want to recalculate. Obviously oceans will have 0 elevation but since lakes at the top of mountains should be calculated properly , we’ll select them too. So we’ll get every non-ocean corner and order them by their elevations.

To explain the distribution calculation , I’ll just quote Amit’s own comment from the code ,

Let y(x) be the total area that we want at elevation <= x. We want the higher elevations to occur less than lower  ones, and set the area to be y(x) = 1 - (1-x)^2.


y = I / ( locations.length – 1 );

Now we have to solve for x, given the known y.


y = 1 - (1-x)^2
y = 1 - (1 - 2x + x^2)
y = 2x - x^2
x^2 - 2x + y = 0

From this we can use the quadratic equation to get:

x = Math.sqrt(SCALE_FACTOR) - Math.sqrt(SCALE_FACTOR*(1-y));

 

I guess this is better than trying to explain it with my broken math/english eh?

The 1.05 you can see in the code is just the square root of 1.1 , I doubt we need it but anyway. Rest should be pretty much same as he explained. I honestly not sure if it worths the trouble tho , because square root is a costly calculation and simply dividing all corner elevations to the biggest one pretty much gets you a similar map anyway.

 

And after this 2nd method , you’ll end up with something like this ;

WindowClipping (5)

 

The gray part in the middle are areas with elevation above 0.8 and pinkish areas you can see right about beaches are areas with elevation below 0.3 I believe. All style files are in that solution anyway so you can already play with numbers to color them as you please.

 

You can find the sample solution file below , please don’t hesitate to ask anything you like. Next post , I believe , will be about calculation the moisture!

 

Visual Studio 2010 Solution

Pingbacks and trackbacks (1)+