JavaScript version of my Polygon Map Generator.

• The algorithms mostly follow my article about polygon map generation..
• The data structures are rather different from the original ActionScript 3 code.
  • The mesh connectivity (voronoi, triangles, edges, points) is stored in the Mesh structure.
  • The generated map (elevation, rivers, biomes, etc.) is stored in the WorldMap structure.
  • The original project uses an “array of struct” approach; this one uses a “struct of arrays” approach.
• The naming convention for the data is x_property_y where x and y are r, s, or t indicating the type of the output (x) and input (y). For example, s_downslope_t would be an array indexed by a t (triangle) id, and returning an s (side) id.
• The maps are created with coordinates 0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000.

This repository contains the map generation algorithms and also the code for UI and rendering.

Example

There are several steps to generate a map:

1. Choose points, either a jittered grid or blue noise (poisson disc) or some other pattern.
2. Add boundary points around the edges of the map
3. Turn the points into triangles and voronoi cells using Delaunator.
4. Use my dual-mesh library to complete and wrap the mesh structure with “ghost” elements.
5. Use the WorldMap generator to assign elevation, rivers, and biomes.

import SimplexNoise  from 'simplex-noise';
import Delaunator    from 'delaunator';
import Poisson       from 'poisson-disk-sampling';
import {makeRandInt} from '@redblobgames/prng';

import {TriangleMesh} from "./dual-mesh/dist/index.js";
import {generateInteriorBoundaryPoints} from "./dual-mesh/dist/create.js";
import {WorldMap} from './map.js';

const bounds = {left: 0, top: 0, width: 1000, height: 1000};
const spacing = 100;
let points = generateInteriorBoundaryPoints(bounds, spacing);
let numBoundaryPoints = points.length;
let generator = new Poisson({
  shape: [bounds.width, bounds.height],
  minDistance: spacing / Math.sqrt(2),
});
for (let p of points) { generator.addPoint(p); }
points = generator.fill();
let init = {points, delaunator: Delaunator.from(points), numBoundaryPoints};
init = TriangleMesh.addGhostStructure(init);
let mesh = new TriangleMesh(init);

let map = new WorldMap(mesh,
                  {
                      amplitude: 0.2,
                      length: 4,
                      seed: 12345
                  },
                  makeRandInt,
                 );

map.calculate({
    noise: new SimplexNoise(),
    shape: {round: 0.5, inflate: 0.4, amplitudes: [1/2, 1/4, 1/8, 1/16]},
    numRivers: 30,
    drainageSeed: 0,
    riverSeed: 0,
    noisyEdge: {length: 10, amplitude: 0.2, seed: 0},
    biomeBias: {north_temperature: 0, south_temperature: 0, moisture: 0},
});

The previous version of this library wrapped up all these steps in a convenient function. However, I used that in real projects and found it was limiting. The current version makes the caller run all the steps so that they can all be swapped out (boundary points are optional, Poisson disc is optional, ghost elements are optional, noise function can be changed, random number sequence can be changed).

The library supports seeded random numbers with my makeRandInt / makeRandFloat functions. If you don’t care about seeds, you can use the built-in random number function instead:

function makeRandInt (_ignoreSeed) {
    return N => Math.round(Math.random() * N);
}

You can pass in your own noise function instead of using the SimplexNoise library:

noise: {noise2D(nx, ny) { return … }}

However, the code as written doesn’t have a way to pass in your own height map or a water/land assignment function. You can modify the assign_r_water function if you want to use your own water/land shape.

Output

If your project needs polygon data:

let polygons = [];
for (let r = 0; r < map.mesh.numSolidRegions; r++) {
    polygons.push({
       biome: map.r[r_biome],
       vertices: map.mesh.r_around_t(r)
                         .map((t) => map.pos_of_t(t))
    });
}

If you want the noisy edges instead, see map.lines_s[s] for the line segments that should be used instead of side s.

If your project needs the polygons split into triangles:

let triangles = [];
for (let s = 0; s < map.mesh.numSolidSides; s++) {
    let r = map.mesh.r_begin_s(s),
        t1 = map.mesh.t_inner_s(s),
        t2 = map.mesh.t_outer_s(s);
    triangles.push({
       biome: map.biome_r[r],
       indices: [
          map.pos_of_r(r),
          map.pos_of_t(t1),
          map.pos_of_t(t2),
       ]
    });
}

If your game needs the polygons split into tiles, use a polygon rasterization library like points-in-polygon to get a list of tiles for each polygon. I have not tried this yet. The default coordinate space is 0 ≤ x ≤ 1000, 0 ≤ y ≤ 1000. Scale this up or down to your desired tile map size before rasterizing.