Voronoi maps tutorial

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:

Simplex Noise: jwagner/simplex-noise^[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 < delaunay.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(delaunay, start) {
    const result = [];
    let incoming = start;
    do {
        result.push(incoming);
        const outgoing = nextHalfedge(incoming);
        incoming = delaunay.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(delaunay, 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();
        }
    }
}

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);

Then we can use both the elevation and moisture map to decide on a biome color:

function biomeColor(map, r) {
    let e = (map.elevation[r] - 0.5) * 2,
        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); e = e**4; // tweaks
        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)
);

biomes

Hey, this looks reasonable!

5 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:

organize the code to fit into your own project
improve point spacing by using better jitter, poisson disk, lloyd relaxation, or precomputed blue noise
remove the weird shapes at the edges of the map, or maybe clip them ; I don’t know the best way but I have written up notes about the boundary points
change the island shaping to use a better formula; I don’t know the best way but I have some notes about island functions
use more octaves for the elevation and moisture noise; see my guide to noise for maps
construct rivers using the delaunay triangulation (forming a Triangulated Irregular Network^[8])

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

All the code on the page also generates the diagrams on this page: 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.

1 Seed points#

2 Voronoi cells#

3 Island shape#

4 Biomes#

5 Next steps#

Links