World Creator 2 - Building the World Map.
Tags: javascript, algorithms
Published: 2021-12-27 21:59:48

# Introduction
How is a world created? (Worldbuilding)

In Worldbuilding there is two methods of creation, the first is called "top-down", where you create the world's cultures, its inhabitants, civilizations and then the geographic features, it's the option that i will try to avoid, since i want to create the world historically, so from year 0 to year i-dont-know. The other method is the first but inverted, so it's called "bottom-up", where you create the geographic features, such as continents, tectonic plates, biomes and then the cultures, civilizations and more. I will try to use the "bottom-up" method, it's just what i want. 

## Ok, so where to start?
I want to create a world organically, so as i'm going to use the "bottom-up" method, i will create the world terrain first and then adapt the cultures on it. So, this is the thing: i will start by creating the world terrain.

---

# PART 1 - The Terrain Generation Process

So, i've read about map generaton, a lot, and there's a very famous process called Voronoi, which uses a polygonal map structure to draw solid terrain and water, it's extremelly cool and looks good. I'll mess with that process and maybe improve that to something more polished. 
![World procedurally generated](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3blacm1cnfognhtudx0w.png)
This is how i want it to look like.

Oh and i didn't said, but i will not code Voronoi by myself, it's a huge waste of time since there's libraries that does that and this is not a university research.
So this is going to be a kind of side-project, a map generator for the biggest project, a fantasy world generator. Looks good for me.

---

## Generating the map
So, we did started the project, that's good. Ok, how is the map going to be generated? For instance, we are just starting to think about that, but the beginning of this adventure starts at seeds. Yes, seeds, remember Minecraft? It has seeds too, and it generates the maps.

This is our code:
 
``` Javascript
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())});
    }
}
```

What is it doing?

Basically, it's generating grids at the canvas and then we add **jitter**, because we cannot use the same points for the Voronoi process, this is where jitter enters, it breaks the regular grid lines.
Yeah, cool, but it doesn't really shows anything. So let's draw it!

``` Javascript
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();
}
```

Awesome! We have points at where the map is going to be drawn, it's where our Voronoi will be drawn too.

![Voronoi points](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h2xjjv7tz6z41zlv8076.png)

### Where the Voronoi really comes up
Now we are getting closer to the exciting part of this code! We have just generated some functional randomly disposed points where we are going to deploy our Voronoi elements. How we do this?

First of all we are going to run the Delaunay triangulation algorithm, which will create the Voronoi cells for us (the spaces between the lines, where our points will be at the center)

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

Ok, we did the triangulation, now we need to calculate the centimeters of the triangles, we will use something called "centroids" which are part of the Voronoi process.

``` Javascript
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;
}
```

Then, we store the information:

``` Javascript
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 finally, we draw the Voronoi cells:

``` Javascript
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();
}
```

![Voronoi points with cells](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kdarq1onvww2d07r2hns.png)
Exciting! Looks like a Voronoi-based draw for me.

## Island shape
Until now we've created the algorithm for the points, that generates our cells, now we are going to put it in action, that means we are going to draw the terrain. Yeah!

If we want it to look like an island, we need to create a height map, so we aren't going to see any floating random terrain at the ocean. Here it goes:

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

These are the regions, we have it at the application's memory, now we need to draw it:

``` Javascript
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%)"
);
```

We have the islands!

![Islands!](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vts92lkg8wf7vf62dwsp.png)
 
## Biomes
Every respectfull world has diversified biomes, that's what we need.

For that, we need to generate a second noise map, so we can see where the biomes are on our hemispheres.

``` Javascript
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 just put some colors on it:
``` Javascript
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)
);
```
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dlup6edbfba69ic038he.png) 
Beautiful!

---

# Conclusion

We have created a simple but not so simple map generator, it looks extremely good and i'm honestly very happy with the result, but it wouldn't be possible without the help of these awesome articles about world generation:

[Polygonal Map Generation for Games - by amitp from Red Blob Games](http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/#source)
[Voronoi Maps Tutorial - by amitp from Red Blob Games](https://www.redblobgames.com/x/2022-voronoi-maps-tutorial/)
[MapBox's Delaunator Algorithm](https://github.com/mapbox/delaunator)
[Jwagner's Simplex-Noise Algorithm](https://github.com/jwagner/simplex-noise.js)

Follow me on my social medias, so you won't miss anything:

[My Twitter](https://twitter/matjs_)
[My Github](https://github.com/matjsilva)
My Discord: @matjs#1006