Now, when we got a Voronoi graph (see the previous post), we can create something resembling a map, like this “Europe…khe-khe” one above created in a two minutes.

It is a pure heightmap as all the colors just represent the height of the particular polygon. It looks like a map even without coastline and rivers being drawn. So let’s explore how to create a heightmap in a few steps.

It sounds a bit ridiculous but the easier heightmap generation algorithm I use the better result I get. Frankly speaking I didn’t try to use the most obvious variant — noise function. I’m going to try some noise in the future, but it’s not a priority. So the easiest algorithm I can imagine is:

- Select a random polygon
- Assign a value from 0 to 1 as the polygon height
- Set height of the neighbor polygons with a small decrement
- Repeat for the new (unused) neighbors while height is significant

As a result you will get a cute blob (‘island’).

To implement the algorithm above we need to create a queue and poke the next and next neighbor polygons to the function that will calculate the height. Calculation formula is *parentHeight * decrement*.

*ParentHeight* (height) is a currently used height* *value derived from the initial (start) polygon height. *Decrement *(radius) is a less-than-1 number which make the island to be sloped and to nullified in a several polygons from the start point. It is a constant for every blob and actually controls the blob radius.

Sounds confusedly, so let’s algorithmize it:

- Define initial (peak) height value
- Select start polygon and mark it as used
- Assign initial height to start polygon
- Decrease height by multiplying on
*Decrement* - For each unused neighbor
- Assign current height to this polygon
- Add polygon to the queue
- Mark polygon as used

- Repeat steps 4-5 for all elements in queue while current height > 0.01 (it won’t be zero as we use multiplication)

*ParentHeight *(height) and* decrement *(radius)* *are user defined, so we will add inputs to vary that values. You may play with code and inputs in JSFiddle.

function addIsland() { // locate start polygon as closest to mouse point var point = d3.mouse(this), start = diagram.find(point[0], point[1]).index, // get options from inputs height= heightInput.valueAsNumber, radius = radiusInput.valueAsNumber, queue = []; polygons[start].height = height; polygons[start].used = 1; queue.push(start); for (i = 0; i < queue.length && height > 0.01; i++) { height *= radius; polygons[queue[i]].neighbors.forEach(function(e) { if (!polygons[e].used) { polygons[e].height += height; // max height is 1 if (polygons[e].height > 1) {polygons[e].height = 1;} polygons[e].used = 1; queue.push(e); } }); } // re-color the polygons based on new heights polygons.map(function(i) { $("#" + i.index).attr("fill", color(1 - i.height)); i.used = undefined; // remove used attribute }); }

As you may notice the blobs are smooth and there is no way to make them sharp and irregular. But in the real-word big islands usually look different. Just take a look on the shape of Ireland and Iceland: both isles have sharp coast with a lot of long, narrow inlets from one side while another coasts are smooth, straightened. Even I’m not a specialist in coastal geomorphology, I realize that it is not the only possible island form. But this shape is interesting with all of its inlets, peninsulas and harbors.

To resolve this issue let’s change the code a bit to add some randomness. Each time before the height is assigned to polygon we will multiply the height by random modifier. Modifier is calculated based on *sharpness* variable and should be slightly less or greater than 1. In the case it is less than 1 height will decrease faster, greater – height *can *increase. This minor chance of increasing provides a lot of form irregularity and allows small accompanying isles generation.

The *sharpness *is not enough by itself. We the need change the code to support the irregularity. The height calculation should be based not on the current height, but on the height of the parent polygon – this will allow ridges and valleys sprawling from the blob center. Compare two blobs below. Left blob is generated without a modifier (actually modifier is 1), so it is smooth. Right blob is created with modifier varying from 0.9 to 1.1 and it’s sharp.

Take a look on the code below (FSFiddle):

function addIsland() { // locate start polygon as closest to mouse point var point = d3.mouse(this), start = diagram.find(point[0], point[1]).index, // get options from inputs height = heightInput.valueAsNumber, radius = radiusInput.valueAsNumber, sharpness = sharpnessInput.valueAsNumber, queue = []; polygons[start].height = height; polygons[start].used = 1; queue.push(start); for (i = 0; i < queue.length && height > 0.01; i++) { height = polygons[queue[i]].height * radius; polygons[queue[i]].neighbors.forEach(function(e) { if (!polygons[e].used) { // calculate the modifier var mod = Math.random() * sharpness + 1.1 - sharpness; // if sharpness is 0 modifier should be ignored (=1) if (sharpness == 0) {mod = 1;} polygons[e].height += height * mod; // max height is 1 if (polygons[e].height > 1) {polygons[e].height = 1;} polygons[e].used = 1; queue.push(e); } }); } }

There is a problem in this approach. In case of using more that one blob there is a big chance that blobs will overlap each other. And, as polygon height is derived from parent’s polygon, in case of overlapping summary height will be off-scaled. So we need to change the line 21 to re-define the height in case of overlapping. This will not resolve the problem as new blobs won’t cover each other and won’t provide a more complex shape.

It’s a good idea to create big high blob using the 2^{nd} code variant and then add a couple of smaller and lower ones using the 1^{st} code variant. The smaller blobs will ‘cover’ the initial sharp blob in some places and this will change the landform in the desired direction. For my generator I create one big blob as a first step and then add 10 small blobs. Compare the shapes below:

Use this JSFiddle playground for the experiments (1^{st} blob will be a big ‘island’).

You need to realize one more thing. The calculations and map look depend on the graph size. For my maps I use 8000 polygons, just because this amount still runs smoothly in my browser with the already added details. As an experiment I’ve tried 100k polygons with rather interesting look (JSFiddle), but it needs to be tested more.

## 6 thoughts on “Heightmap”