## Friday, November 4, 2016

### It's Not My Fault!

In a previous posting, I talked about how to generate mountains in a heightmap by using noise, and also about how to place mountains on a map so that they "make sense".  By that I meant that mountains should (1) only be on part of the map, (2) have a natural shape on the map, and (3) should transition smoothly into the rest of the terrain.  The approach I suggested was to use a mask, based either on noise or the already existing terrain (putting the mountains where the terrain was highest).  That yielded fairly natural-looking terrain:

In this posting, I'm going to talk about another approach for placing mountains that is based on the notion of fault lines.

A fault line is a fracture in the rock of the Earth's surface.  This happens for various reasons, but one cause is when two tectonic plates push past each other.  This can cause the rock of one plate to be thrust upward as the other plate burrows beneath the first plate.  Tectonic action of this sort created mountain ranges such as the Rocky Mountains in North America.  The very reason that we have notions like mountain "ranges" is because this mechanism is so primary in creating natural mountains.  So how can we implement a (simple) fault line model?

To start with, we can model a fault as a straight line cutting across the map from one edge to the other, forming a shallow peak at the line:

Implementing this is fairly straightforward:  Randomly create a line that crosses the map and then add height to the land based upon how far away the land is from the line.  For this, it's useful to know how to calculated the distance from a point to a line.  Here's an implementation in Javascript:

//
//  Distance from a Point to a Line Segment
//
//  This calculates the distance from (x,y) to the line defined by the
//  two points (x0, y0) and (x1, y1).  If segment is true, the line
//  is treated as a line segment.
//
function distanceFromPointToSegment(x, y, x0, y0, x1, y1, segment) {
var d = (x1-x0)*(x1-x0)+(y1-y0)*(y1-y0);
var t = ((x-x0)*(x1-x0)+(y-y0)*(y1-y0))/d;
// If t < 0 || t > 1 we're off the end of the segment, and
// the distance is just the distance to the proper endpoint.
if (segment && t < 0) {
return Math.sqrt((x-x0)*(x-x0)+(y-y0)*(y-y0));
};
if (segment && t > 1) {
return Math.sqrt((x-x1)*(x-x1)+(y-y1)*(y-y1));
};
// Otherwise calculate the perpendicular point and then
// the distance to that point.
var xp = x0 + t*(x1-x0);
var yp = y0 + t*(y1-y0);
return Math.sqrt((x-xp)*(x-xp)+(y-yp)*(y-yp));
}; 

The inverse distance can then be used to add a slope to the map on either side of the fault line, as in this exaggerated example:

The routine above can also treat the line as a line segment.  If we use this to add slope, it creates a rounded end at each end point of the line segment:

(We'll see why this is useful in a later post.)

A map can also have multiple fault lines, as in this example:

This gets busy and "unnatural" looking pretty quickly, although on a larger scale map it would make sense to have more fault lines.

One problem with these fault lines is that they're unnaturally straight and regular, as is evident if we map one:

Even with some noise added to break up the outlines, it's very evident where the fault lies (so to speak).

We can fix this by using noise to perturb the fault line.  Some tweaking is necessary to get appropriate noise parameters, but the result can be a very organic shape:

So we now have a natural looking fault line, created by drawing a perturbed line across the map and adding a gentle slope to either side.  Now we'd like to add a mountain range along the fault line.

We already know how to add mountains to an area by using a mask that fades out at the edges of the area.  What we need is a mask for the area around the fault line.  But that's just a steeper and narrower version of the fault itself.  Here I've overlayed a mask on top of the fault:

Where the mask is high, the mountains will show through fully; where it is low they will fade away.

However, you may have noticed that while the fault is a natural curve, the mountains mask is a straight line.  We correct that by apply the same perturbation we applied to the fault line to the mountains mask:

As you can see, the mountains mask now follows the same curve as the fault.  However, the mask has also become distorted: wider in some places, narrower in others, and with a bulge in the middle.  This is the natural consequence of using noise to perturb the mask.  The amount of noise can be tweaked to get a result that is acceptable -- you just need to make sure you use the same perturbation to both the fault line and the mountains mask.  The final step then is to generate mountains using noise and add the mountains to the map using the mountains mask as a filter:

The result is a pretty realistic-looking mountain "range".   Here's what that looks like in a map view:

There are a lot of tweaks you can apply to get different results, such as peakier mountains:

A more gradual transition into the surrounding terrain:

Multiple fault lines:

And so on.

There are a couple of shortcomings with this approach.  In real fault lines, the slope is steeper on one side and lower on the other.  That could be modeled with a mask that is steeper on one side than the other.  I also haven't talked about how to end a mountain range on the map, rather than running it from edge to edge.  In a later posting I'll talk about that, and how this technique can also be applied to generating island chains.