DOCSEARCHbyAlgolia
Submit Docs

Mapgen4

repository·main·Indexed 21 days ago

https://github.com/redblobgames/mapgen4

A procedural wilderness map generator designed for real-time regeneration and aesthetic appeal. It utilizes a Delaunay+Voronoi mesh structure to generate terrain, rivers, and biomes. The library provides a TriangleMesh class for managing regions, sides, and triangles, and a MeshBuilder for creating meshes from points or Poisson disk sampling.

Tokens
2.3K
Snippets
6
Records
11
Agent score
75%

What's inside mapgen4

  1. Understand the Mapgen4 codebase structure

    main

    The project is written in TypeScript and uses esbuild for building (note: esbuild does not perform type checking; use an IDE for type safety). The core logic is distributed across the following files:

    • mapgen4.ts: The main entry point.
    • map.ts: Contains the map generation algorithms.
    • dual-mesh/: Contains the main data structures.
    • painting.ts: Handles input painting logic.
    • render.ts: Handles output rendering.
    • worker.ts: Contains calculation logic for workers.
    • geometry.ts: Contains calculations shared between the worker and the renderer.

  2. Optimize array allocations in dual mesh functions

    main

    For performance-critical loops, many functions that return arrays allow you to pass an optional destination array as a parameter. This avoids repeated memory allocations by writing the results into an existing array.

    If no destination array is provided, the function will allocate and return a new array for convenience.

    // Efficient: reuse an existing array
let out_r = [];
mesh.r_around_t(t, out_r);

// Convenient: allocates a new array
let out_r = mesh.r_around_t(t);

  3. How TriangleMesh elements and relationships work

    main

    A TriangleMesh represents a triangle-polygon dual mesh consisting of Regions (r), Sides (s), and Triangles (t).

    Element IDs

    • Regions: 0 <= r < numRegions
    • Sides: 0 <= s < numSides (Sides are directed)
    • Triangles: 0 <= t < numTriangles

    Relationships

    • Sides and Triangles: A side s belongs to a triangle t. Use t_inner_s(s) to get the triangle inside the side and t_outer_s(s) to get the triangle on the other side.
    • Sides and Regions: A side s represents a boundary between two regions. r_begin_s(s) is the starting region and r_end_s(s) is the ending region.
    • Side Pairs: Every side s has an opposite directed side s_opposite_s(s). If the side is on the boundary and has no pair, this returns -1 (unless addGhostStructure() was used).
    • Adjacency:
      • s_next_s(s) and s_prev_s(s) navigate sides around a triangle.
      • s_around_r(r) returns the sides surrounding a region.
      • r_around_t(t) returns the regions surrounding a triangle.

  4. Understand the dual mesh naming convention

    main

    The library uses an output_from_input naming convention for its API. A function named x_name_y takes an input of type y and returns an output of type x.

    Element Types:

    • r: Regions
    • s: Sides
    • t: Triangles

    Example: r_begin_s is a function that takes a side (s) as input and returns a region (r). In code, this is called as mesh.r_begin_s(s).

  5. Create a dual mesh using MeshBuilder

    main

    To generate a mesh, use the MeshBuilder class. You can build a mesh by providing an array of points or by using Poisson disk sampling for evenly spaced points.

    Note that the library is considered unstable and the create.js interface is subject to breaking changes.

    // Basic usage with an array of points
let mesh = new MeshBuilder()
    .addPoints(array_of_points)
    .create();

// Usage with Poisson disk sampling
let Poisson = require('poisson-disk-sampling');
let mesh = new MeshBuilder({boundarySpacing: 75})
    .addPoisson(Poisson, 75)
    .create();

  6. Install and run Mapgen4

    main

    To set up the Mapgen4 development environment, you need to install esbuild globally, install the project dependencies, and run the build script. Once built, you can serve the project using a local HTTP server to view the embedded demo.

    1. Install dependencies and build:
      • Install esbuild globally via npm or pnpm.
      • Install project dependencies.
      • Run ./build.sh.
    2. Run a local server:
      • Use python3 -m http.server 8000.
      • Visit http://localhost:8000/embed.html in your browser.
    npm install -g esbuild
npm install
./build.sh

# Then run the server
python3 -m http.server 8000

  7. Configure map scale via spacing

    main

    The underlying code can support over 1 million Voronoi cells. You can adjust the scale of the map by changing the spacing parameter in config.js.

    Note: While the engine supports very large scales, the rendering and parameters are optimized to look best at approximately 25,000 cells.

    // In config.js
// Change spacing to 0.7 to support 1 million+ Voronoi cells
spacing: 0.7

  8. Complete a mesh using addGhostStructure()

    main

    When creating a mesh from Delaunator, the resulting mesh may have unpaired sides (boundaries). To create a complete graph where every side has an opposite pair, use the static TriangleMesh.addGhostStructure(init) method.

    This method returns a new MeshInitializer object that includes "ghost" sides, triangles, and a ghost region to fill the gaps. You should pass this returned object into the TriangleMesh constructor to ensure a fully connected dual mesh.

    import { TriangleMesh, type MeshInitializer } from '@redblobgames/dual-mesh';

// 1. Prepare your initial Delaunator-based data
const init: MeshInitializer = {
    points: myPoints,
    delaunator: myDelaunatorData,
    numBoundaryPoints: 0
};

// 2. Generate the ghost structure to complete the graph
const completeInit = TriangleMesh.addGhostStructure(init);

// 3. Construct the mesh with the completed data
const mesh = new TriangleMesh(completeInit);

  9. Initialize a TriangleMesh from Delaunator data

    main

    To create a TriangleMesh, provide a MeshInitializer object to the TriangleMesh constructor. This object requires points (an array of Point) and delaunator data (containing triangles and halfedges as Int32Array).

    You can optionally specify numBoundaryPoints to define which points are considered boundary regions, and numSolidSides to define the count of non-ghost sides.

    If you have updated your Delaunator data and want the mesh to reflect these changes, call update(init) with a new MeshInitializer object. Note that update() does not update boundary regions or ghost elements.

    import { TriangleMesh, type MeshInitializer, type Delaunator, type Point } fact {
  const init: MeshInitializer = {
    points: [[0, 0], [1, 0], [0, 1]],
    delaunator: {
      triangles: new Int32Array([0, 1, 2]),
      halfedges: new Int32Array([-1, -1, -1])
    },
    numBoundaryPoints: 0
  };

  const mesh = new TriangleMesh(init);
}

  10. Reference: TriangleMesh Status and Ghost Checks

    main

    Use these properties and methods to distinguish between "solid" (real) elements and "ghost" elements (added to complete the graph).

    Counts

    • numSides, numSolidSides
    • numRegions, numSolidRegions, numBoundaryRegions
    • numTriangles, numSolidTriangles

    Ghost/Boundary Checks

    • is_ghost_s(s): True if side s is a ghost side.
    • is_ghost_r(r): True if region r is the ghost region.
    • is_ghost_t(t): True if triangle t is a ghost triangle.
    • is_boundary_s(s): True if side s is a boundary side.
    • is_boundary_r(r): True if region r is a boundary region.

  11. Reference: TriangleMesh Accessors and Properties

    main

    The TriangleMesh class provides several methods to query the mesh structure and element positions.

    Position Accessors

    • x_of_r(r), y_of_r(r): Coordinates of region r.
    • x_of_t(t), y_of_t(t): Coordinates of triangle t (centroid or ghost center).
    • pos_of_r(r, [out]): Returns [x, y] for region r.
    • pos_of_t(t, [out]): Returns [x, y] for triangle t.

    Structural Accessors

    • r_begin_s(s), r_end_s(s): The regions on either side of directed side s.
    • t_inner_s(s), t_outer_s(s): The triangles on either side of directed side s.
    • s_next_s(s), s_prev_s(s): The next/previous side in a triangle's rotation.
    • s_opposite_s(s): The opposite directed side.

    Iteration/Collection Accessors

    • s_around_t(t, [out]): The three sides forming triangle t.
    • r_around_t(t, [out]): The three regions surrounding triangle t.
    • t_around_t(t, [out]): The triangles adjacent to triangle t.
    • s_around_r(r, [out]): The sides surrounding region r.
    • r_around_r(r, [out]): The regions adjacent to region r.
    • t_around_r(r, [out]): The triangles surrounding region r.