Voronoi maps tutorial

 from Red Blob Games
25 May 2020

I’ve written a page about polygon map generation with Voronoi[1] but it doesn’t explain how to code it. On this page I’m going to go through the basics of how to make maps like this with Javascript code examples:

voronoi map

Many people want to code Voronoi and Simplex Noise themselves. I usually use libraries. Here’s what I’ll use:

  1. Simplex Noise: jwagner/simplex-noise[2].
  2. Voronoi: mapbox/delaunator[3].

If you’re not using Javascript, there are noise libraries available for most languages, and Delaunator has been ported to many languages.

The first step is to load the libraries. You might use npm or yarn but for this page I’m going to load them with script tags. Delaunator’s documentation includes instructions for this but the Simplex Noise library does not, so I’m using unpkg[4] to load them:

<script src="https://unpkg.com/simplex-noise@2.4.0/simplex-noise.js"></script>
<script src="https://unpkg.com/delaunator@4.0.1/delaunator.min.js"></script>

I also put my own source into a file and a place for it to draw:

<canvas id="map" width="1000" height="1000"></canvas>
<script src="voronoi-maps-tutorial.js"></script>

 1  Seed points#

With a square tile map we’d loop through to generate a tile for each location:

const GRIDSIZE = 25;
let points = [];
for (let x = 0; x <= GRIDSIZE; x++) {
    for (let y = 0; y <= GRIDSIZE; y++) {
        points.push({x, y});
    }
}

For Voronoi we need to give it locations for its polygons. Although we could use the same points for our Voronoi, one of the main reasons to use Voronoi is to break up the regular grid lines. Let’s add jitter to the locations:

const GRIDSIZE = 25;
const JITTER = 0.5;
let points = [];
for (let x = 0; x <= GRIDSIZE; x++) {
    for (let y = 0; y <= GRIDSIZE; y++) {
        points.push({x: x + JITTER * (Math.random() - Math.random()),
                     y: y + JITTER * (Math.random() - Math.random())});
    }
}

To see if it looks reasonable, let’s draw them:

function drawPoints(canvas, points) {
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.fillStyle = "hsl(0 50% 50%)";
    for (let {x, y} of points) {
        ctx.beginPath();
        ctx.arc(x, y, 0.1, 0, 2*Math.PI);
        ctx.fill();
    }
    ctx.restore();
}

drawPoints(document.getElementById("diagram-points"), points);
jittered points

These points could be better (using either poisson disk or relaxation), but this set seems good enough for now.

 2  Voronoi cells#

Now we can construct the Voronoi cells around each of the seed points. It’s not obvious that Delaunator, a library for Delaunay triangulation, can construct Voronoi cells. For that, I refer you to the Delaunator Guide[5], which shows sample code for constructing Voronoi cells (without clipping).

The first step is to run the Delaunay triangulation algorithm:

let delaunay = Delaunator.from(points, loc => loc.x, loc => loc.y);

The second step is to calculate the circumcenters of the triangles. For various reasons I’m going to use a variant of Voronoi that uses centroids. The code on this page will work whether you use circumcenters or centroids, so experiment with different triangle centers and see which works best for you.

function calculateCentroids(points, delaunay) {
    const numTriangles = delaunay.halfedges.length / 3;
    let centroids = [];
    for (let t = 0; t < numTriangles; t++) {
        let sumOfX = 0, sumOfY = 0;
        for (let i = 0; i < 3; i++) {
            let s = 3*t + i;
            let p = points[delaunay.triangles[s]];
            sumOfX += p.x;
            sumOfY += p.y;
        }
        centroids[t] = {x: sumOfX / 3, y: sumOfY / 3};
    }
    return centroids;
}

Let’s construct an object to store everything:

let map = {
    points,
    numRegions: points.length,
    numTriangles: delaunay.halfedges.length / 3,
    numEdges: delaunay.halfedges.length,
    halfedges: delaunay.halfedges,
    triangles: delaunay.triangles,
    centers: calculateCentroids(points, delaunay)
};

And now we can draw the Voronoi cells. This code is based on the code in the Delaunator Guide[6].

function triangleOfEdge(e)  { return Math.floor(e / 3); }
function nextHalfedge(e) { return (e % 3 === 2) ? e - 2 : e + 1; }

function drawCellBoundaries(canvas, map) {
    let {points, centers, halfedges, triangles, numEdges} = map;
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.lineWidth = 0.02;
    ctx.strokeStyle = "black";
    for (let e = 0; e < numEdges; e++) {
        if (e < halfedges[e]) {
            const p = centers[triangleOfEdge(e)];
            const q = centers[triangleOfEdge(halfedges[e])];
            ctx.beginPath();
            ctx.moveTo(p.x, p.y);
            ctx.lineTo(q.x, q.y);
            ctx.stroke();
        }
    }
    ctx.restore();
}
drawCellBoundaries(document.getElementById("diagram-boundaries"), map);
cell boundaries

Hey, that looks pretty good, except for the edges of the map. Reload the page to see a new map. Let’s ignore the edges for now. We’ll figure out a solution later.

 3  Island shape#

The next step is to assign a height map. I’ll adapt the techniques I use on my terrain-from-noise page. Instead of assigning elevation to every tile, we’ll assign elevation to every Voronoi region. Let’s put them into an array indexed by the region number.

const WAVELENGTH = 0.5;
function assignElevation(map) {
    const noise = new SimplexNoise();
    let {points, numRegions} = map;
    let elevation = [];
    for (let r = 0; r < numRegions; r++) {
        let nx = points[r].x / GRIDSIZE - 1/2,
            ny = points[r].y / GRIDSIZE - 1/2;
        // start with noise:
        elevation[r] = (1 + noise.noise2D(nx / WAVELENGTH, ny / WAVELENGTH)) / 2;
        // modify noise to make islands:
        let d = 2 * Math.max(Math.abs(nx), Math.abs(ny)); // should be 0-1
        elevation[r] = (1 + elevation[r] - d) / 2;
    }
    return elevation;
}

map.elevation = assignElevation(map);

Let’s draw these regions. I’ll again use code based on the Delaunator Guide[7].

function edgesAroundPoint(halfedges, start) {
    const result = [];
    let incoming = start;
    do {
        result.push(incoming);
        const outgoing = nextHalfedge(incoming);
        incoming = halfedges[outgoing];
    } while (incoming !== -1 && incoming !== start);
    return result;
}

function drawCellColors(canvas, map, colorFn) {
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    let seen = new Set();  // of region ids
    let {triangles, numEdges, centers} = map;
    for (let e = 0; e < numEdges; e++) {
        const r = triangles[nextHalfedge(e)];
        if (!seen.has(r)) {
            seen.add(r);
            let vertices = edgesAroundPoint(map.halfedges, e)
                .map(e => centers[triangleOfEdge(e)]);
            ctx.fillStyle = colorFn(r);
            ctx.beginPath();
            ctx.moveTo(vertices[0].x, vertices[0].y);
            for (let i = 1; i < vertices.length; i++) {
                ctx.lineTo(vertices[i].x, vertices[i].y);
            }
            ctx.fill();
        }
    }
    ctx.restore();
}

drawCellColors(
    document.getElementById("diagram-cell-elevations"),
    map,
    r => map.elevation[r] < 0.5? "hsl(240, 30%, 50%)" : "hsl(90, 20%, 50%)"
);
cell elevations

Ok, not great, but it works. It’ll take some tweaking to make the shapes the way you want, but the basics are there.

 4  Biomes#

The next step is to make biomes. Again, I’ll follow the techniques from my terrain-from-noise page. The main idea is to add a second noise map:

function assignMoisture(map) {
    const noise = new SimplexNoise();
    let {points, numRegions} = map;
    let moisture = [];
    for (let r = 0; r < numRegions; r++) {
        let nx = points[r].x / GRIDSIZE - 1/2,
            ny = points[r].y / GRIDSIZE - 1/2;
        moisture[r] = (1 + noise.noise2D(nx / WAVELENGTH, ny / WAVELENGTH)) / 2;
    }
    return moisture;
}

map.moisture = assignMoisture(map);

Biomes depend on both temperature and rainfall. We don’t have a separate temperature value, so we’ll use elevation as a proxy for temperature. Higher elevations have lower temperatures. We also don’t have a rainfall value, so we’ll use moisture/humidity instead. Maximum rainfall is a non-linear function of temperature, but we’ll use a linear relationship here to keep it simple. The exact function here isn’t important; you will probably have to tweak it to fit your needs.

function biomeColor(map, r) {
    let e = (map.elevation[r] - 0.5) * 2, // rescale 0:1 to -1:+1
        m = map.moisture[r];
    if (e < 0.0) {
        r = 48 + 48*e;
        g = 64 + 64*e;
        b = 127 + 127*e;
    } else {
        m = m * (1-e); // see note about humidity vs rainfall
        e = e**4; // tweak for better coloring
        r = 210 - 100 * m;
        g = 185 - 45 * m;
        b = 139 - 45 * m;
        r = 255 * e + r * (1-e),
        g = 255 * e + g * (1-e),
        b = 255 * e + b * (1-e);
    }
    return `rgb(${r|0}, ${g|0}, ${b|0})`;
}

drawCellColors(
    document.getElementById("diagram-cell-biomes"),
    map,
    r => biomeColor(map, r)
);
varying biomes, with a desaturated set of colors

Hey, this looks reasonable!

Another option is to use discrete biome colors, such as yellow for desert, green for grasslands, etc.

biomes, discrete colors

The code assigns a biome to each range of temperature/moisture, using some variant of the Whittaker Diagram. Tweak the ranges to match your needs:

function biomeColorDiscrete(map, r) {
    let e = 2.0 * (map.elevation[r] - 0.5); // convert 0:1 to -1:+1
    let m = map.moisture[r] ** 2; // tweak as needed
    
    if (e < 0.0) return "#44447a"; // ocean
    
    if (e > 0.6) {
        if (m < 0.2) return "#888888"; // barren rock
        if (m < 0.5) return "#bbbbaa"; // tundra
        else         return "#dddde4"; // glacier
    }

    if (e > 0.4) {
        if (m < 0.33) return "#c9d29b"; // temperate desert
        if (m < 0.66) return "#889977"; // shrubland
        else          return "#99aa77"; // taiga
    }

    if (e > 0.2) {
        if (m < 0.16) return "#c9d29b"; // temperate desert
        if (m < 0.50) return "#88aa55"; // grassland
        if (m < 0.83) return "#679459"; // temperate deciduous forest
        else          return "#448855"; // temperate rain forest
    }

    if (m < 0.16) return "#d2b98b"; // subtropical desert
    if (m < 0.33) return "#88aa55"; // grassland
    if (m < 0.66) return "#559944"; // tropical seasonal forest
    else          return "#337755"; // tropical rain forest
}

drawCellColors(
    document.getElementById("diagram-cell-biomes-discrete"),
    map,
    r => biomeColorDiscrete(map, r)
);

 5  Rivers#

Rivers are a bit tricky. I’m working on a guide to rivers.

The simplest approach is to put the rivers in the Voronoi cells. However, in some projects I place rivers in the triangles, and they end up on the edges between Voronoi cells. For this tutorial I’ll use the simpler approach.

We’ll use elevation to decide which direction the rivers flow. We’ll use rainfall to decide how much water goes into each river. We’ll use moisture as a proxy for rainfall.

 5.1 Flow

A river will flow downhill, so we can use a function that calculates which direction “downhill” is. For each Voronoi cell, let’s decide which neighboring cell, if any, water will flow to.

function assignDownslope(map) {
    let {elevation, halfedges, triangles} = map;
    let downslope = Array.from({length: elevation.length}, () => undefined); // undefined if we never calculated, null if it's a local minimum
    for (let incoming1 = 0; incoming1 < triangles.length; incoming1++) {
        let outgoing1 = halfedges[incoming1];
        if (outgoing1 < 0) continue; // on convex hull, ignore
        let r1 = triangles[outgoing1];
        let bestElevation = elevation[r1];
        let bestEdge = null;
        for (let incoming2 of edgesAroundPoint(halfedges, incoming1)) {
            let r2 = triangles[incoming2];
            if (elevation[r2] < bestElevation) {
                bestElevation = elevation[r2];
                bestEdge = incoming2; // this seems backwards, r2->r1, but it's convenient this direction later
            }
        }
        downslope[r1] = bestEdge;
    }
    return downslope;
}

map.downslope = assignDownslope(map);

Let’s make sure it calculated what we wanted. My initial code did not. This code is tricky. I recommend visualizing the intermediate data to make sure it matches expectations. These are lines from each Voronoi cell to the neighbor the water flows towards:

function drawDownslope(canvas, map) {
    let {points, downslope, halfedges, triangles} = map;
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.lineWidth = 0.02;
    ctx.strokeStyle = "blue";
    ctx.fillStyle = "blue";
    for (let r1 = 0; r1 < points.length; r1++) {
        if (downslope[r1] === undefined || downslope[r1] === null) continue; // no outflow
        let r2 = triangles[downslope[r1]];
        let p = points[r1];
        let q = points[r2];
        ctx.fillRect(p.x-0.03, p.y-0.03, 0.06, 0.06);
        ctx.beginPath();
        ctx.moveTo(p.x, p.y);
        ctx.lineTo(0.5 * (p.x + q.x), 0.5 * (p.y + q.y));
        ctx.stroke();
    }
    ctx.restore();
}

drawCellColors(document.getElementById("diagram-downslope"), map, r => `hsl(100 ${map.elevation[r] < 0.5? 0 : 20}% ${map.elevation[r] * 100}%)`);
drawDownslope(document.getElementById("diagram-downslope"), map);
downhill direction from each region

This code is “good enough” but a little bit incomplete: edgesAroundPoint() will not calculate all the edges if we’re on a Voronoi cell on the border of the map. That’s because it “falls off” the edge of the map, and the loop stops prematurely. I also skip processing the edges on the convex hull. The Delaunator Guide[8] discusses this. For this project though, the border of the map is all ocean, and we have no rivers there, so we don’t need to solve that (literal) edge case.

Another tricky implementation detail is that the edgesAroundPoint() needs an incoming edge, not the starting pointr1. So I iterate over all edges, and calculate the starting point r1 from the incoming edge. That way I have both the incoming edge and r1 in the outer loop.

 5.2 Rainfall

Let’s assume rainfall is proportional to moisture. What does it look like?

rainfall values
drawCellColors(
    document.getElementById("diagram-rainfall"), 
    map, 
    r => map.elevation[r] < 0.5? `hsl(0 0% 70%)` : `hsl(220 ${map.moisture[r] * 100}% 50%)`
);

 5.3 Flow

The flow in a river is the rainfall in that area plus the flow from the rivers upstream. To calculate the flow, we need to calculate the upstream flow first. So let’s sort the regions from highest to lowest elevation.

function assignRiverFlow(map) {
    let {elevation, moisture, downslope, triangles} = map;
    let regions = Array.from({length: elevation.length}, (_, r) => r);
    regions.sort((r1, r2) => elevation[r2] - elevation[r1]); // sort higher elevations first

    let flow = Array.from({length: elevation.length}, () => 0);
    for (let r of regions) {
        if (elevation[r] < 0.5) continue; // skip oceans
        flow[r] += moisture[r]; // rainfall

        let incomingEdge = downslope[r];
        if (incomingEdge === null) continue; // this is the final point
        let outgoingRegion = triangles[incomingEdge];
        flow[outgoingRegion] += flow[r];
    }
    return flow;
}

map.flow = assignRiverFlow(map);

Let’s draw the flow per region:

function drawRivers(canvas, map, threshold) {
    let {points, flow, downslope, triangles} = map;
    let ctx = canvas.getContext('2d');
    ctx.save();
    ctx.scale(canvas.width / GRIDSIZE, canvas.height / GRIDSIZE);
    ctx.strokeStyle = "rgb(48, 64, 127)";
    ctx.lineCap = 'round';
    for (let r1 = 0; r1 < points.length; r1++) {
        if (downslope[r1] === undefined || downslope[r1] === null) continue; // no outflow
        if (flow[r1] < threshold) continue; // don't draw small rivers
        let r2 = triangles[downslope[r1]];
        let p = points[r1];
        let q = points[r2];
        ctx.lineWidth = 0.05 * Math.sqrt(flow[r1]);
        ctx.beginPath();
        ctx.moveTo(p.x, p.y);
        ctx.lineTo(q.x, q.y);
        ctx.stroke();
    }
    ctx.restore();
}

drawCellColors(document.getElementById("diagram-rivers"), map, r => biomeColor(map, r));
drawRivers(document.getElementById("diagram-rivers"), map, 0.01);
potential rivers everywhere

The drawing code could be better (curved rivers, clip when it reaches the ocean, meandering, etc.) but we have a basic river generator.

 5.4 Subsetting

Almost every Voronoi cell potentially has a river in it. But that’s probably more rivers than we want. We can set a threshold on how much water is in a river before we draw it.

only draw rivers with threshold = 
function drawRiversWithThreshold() {
    let logOfThreshold = document.getElementById("river-log-threshold").valueAsNumber ?? 0.1;
    let threshold = Math.pow(10, logOfThreshold);
    drawCellColors(document.getElementById("diagram-rivers-threshold"), map, r => biomeColor(map, r));
    drawRivers(document.getElementById("diagram-rivers-threshold"), map, threshold);
}
drawRiversWithThreshold();
document.getElementById("river-log-threshold").addEventListener('input', drawRiversWithThreshold);

The threshold will depend a lot on your generator and the map resolution. The rivers don’t look very interesting at this low resolution; try changing GRIDSIZE to 50 in the sample code to increase the resolution.

 6  Next steps#

I hope this gets you started. There’s plenty more to do.

For example, you may have noticed the map at the top of the page has straight edges but the map we made has ragged edges. Here’s the trick: I added some extra points outside the map so that everything at the edges of the map has another point outside to connect to.

points.push({x: -10, y: GRIDSIZE/2});
points.push({x: GRIDSIZE+10, y: GRIDSIZE/2});
points.push({y: -10, x: GRIDSIZE/2});
points.push({y: GRIDSIZE+10, x: GRIDSIZE/2});
points.push({x: -10, y: -10});
points.push({x: GRIDSIZE+10, y: GRIDSIZE+10});
points.push({y: -10, x: GRIDSIZE+10});
points.push({y: GRIDSIZE+10, x: -10});

Other improvements to consider:

I describe more features and other things to try on my polygon map generator page[9].

All the code on this page is available here: voronoi-maps-tutorial.js. I used emacs org-mode to extract the code from this page into a javascript file, and then I run the javascript file on the page to generate the diagrams. The code shown is the same as the code that runs.

Email me , or comment here:

Links

  1. [1]: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/
  2. [2]: https://github.com/jwagner/simplex-noise.js
  3. [3]: https://github.com/mapbox/delaunator
  4. [4]: https://unpkg.com/
  5. [5]: https://mapbox.github.io/delaunator/
  6. [6]: https://mapbox.github.io/delaunator/
  7. [7]: https://mapbox.github.io/delaunator/
  8. [8]: https://mapbox.github.io/delaunator/#incoming-edge-index
  9. [9]: http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/