Game Dev Mechanics: Voronoi Diagrams — How It Works

Imagine dropping colored dye onto a flat surface and watching each drop expand outward at the same rate, observing where the advancing fronts collide to form crisp boundaries. The mosaic of irregular polygonal regions that emerges is a Voronoi diagram — formalized by Russian mathematician Georgy Voronoi in 1908, and now a versatile tool in computational geometry and game development.

The Core Concept

A Voronoi diagram partitions a plane into regions based on proximity to a set of seed points (also called sites). Each region — a Voronoi cell — contains every point in the plane that is closer to its associated seed than to any other seed. Formally, given $n$ seed points $P = \{p_1, p_2, \ldots, p_n\}$, the Voronoi cell $V(p_i)$ is:

$$V(p_i) = \{ x \in \mathbb{R}^2 \mid d(x, p_i) \leq d(x, p_j) \text{ for all } j \neq i \}$$

where $d(x, p_i)$ is the distance between point $x$ and seed $p_i$. The Voronoi edges — boundaries between adjacent cells — lie exactly on the perpendicular bisectors between neighboring seed pairs. Points where three or more edges meet are Voronoi vertices.

This structure is useful because it has a dual relationship with the Delaunay triangulation, emerges naturally from many physical processes, and can be parameterized simply by changing the distance metric.

Computing Voronoi Diagrams

The Brute-Force Approach

The most intuitive algorithm: for every pixel in your space, measure the distance to every seed and color the pixel according to the nearest one. This runs in $O(n \cdot W \cdot H)$ time per frame (where $n$ is the seed count, $W$ and $H$ are the grid dimensions), and is surprisingly practical for small seed counts — especially on the GPU, where every pixel runs in parallel.

function drawVoronoi(canvas, seeds) {
  const ctx = canvas.getContext('2d');
  const imageData = ctx.createImageData(canvas.width, canvas.height);
  const data = imageData.data;

  for (let y = 0; y < canvas.height; y++) {
    for (let x = 0; x < canvas.width; x++) {
      let minDist = Infinity;
      let nearest = 0;

      for (let i = 0; i < seeds.length; i++) {
        const dx = x - seeds[i].x;
        const dy = y - seeds[i].y;
        // Skip sqrt: relative ordering is preserved by squared distance
        const dist = dx * dx + dy * dy;
        if (dist < minDist) { minDist = dist; nearest = i; }
      }

      const idx = (y * canvas.width + x) * 4;
      data[idx]     = seeds[nearest].r;
      data[idx + 1] = seeds[nearest].g;
      data[idx + 2] = seeds[nearest].b;
      data[idx + 3] = 255;
    }
  }
  ctx.putImageData(imageData, 0, 0);
}

The key optimization: comparing $dx^2 + dy^2$ instead of $\sqrt{dx^2 + dy^2}$, since $\sqrt{a} < \sqrt{b} \iff a < b$. This avoids expensive square-root calls when you only need relative ordering. For small seed counts (under ~50), this brute-force CPU approach works well.

Fortune's Sweepline Algorithm

For large seed counts, Fortune's algorithm (1987) constructs the complete Voronoi diagram in $O(n \log n)$ time. It sweeps a horizontal line downward across the plane while maintaining two key data structures:

• The beachline: a sequence of parabolic arcs. Each arc is the set of points equidistant between a processed seed and the sweepline. For seed $p_i$ and sweepline at $y = y_s$, the parabola satisfies $d(x, p_i) = y - y_s$. The intersections between adjacent arcs trace out Voronoi edges as the line sweeps.
• The event queue: two event types drive the algorithm — site events (sweepline reaches a new seed, inserting a new parabolic arc) and circle events (three arcs converge, producing a Voronoi vertex and removing the middle arc).

def fortunes_algorithm(sites):
    events = PriorityQueue()
    for site in sites:
        events.push(SiteEvent(site), priority=-site.y)

    beachline = Beachline()
    voronoi_edges = []

    while not events.empty():
        event = events.pop()
        if isinstance(event, SiteEvent):
            # New parabola splits an existing arc
            handle_site_event(event, beachline, events, voronoi_edges)
        else:  # CircleEvent
            # Arc disappears, Voronoi vertex recorded
            handle_circle_event(event, beachline, events, voronoi_edges)

    return finalize_unbounded_edges(voronoi_edges)

Fortune's algorithm operates in $O(n \log n)$ time — dominated by priority queue operations — and $O(n)$ space. For map generation with thousands of regions, this is preferable to brute force.

The Delaunay Dual

Voronoi diagrams have a mathematical dual: the Delaunay triangulation. Connect the seeds of every pair of adjacent Voronoi cells, and you get a triangulation with one key property — no seed point lies inside the circumcircle of any triangle. This maximizes the minimum angle across all triangles, avoiding thin, degenerate slivers.

The duality means you get both structures for the price of one computation. The Delaunay triangulation is essential in game development for:

• Navigation mesh generation: Constrained Delaunay triangulation (CDT) is the backbone of most NavMesh systems — Unity's built-in NavMesh, Recast/Detour, and others all use it internally.
• Terrain mesh generation: Scatter height-sampled points irregularly across a heightmap, triangulate via Delaunay, and you get a quality triangle mesh with no slivers, adapting resolution to terrain complexity.
• Natural neighbor interpolation: Uses the ratio of overlapping Voronoi cell areas to smoothly interpolate scattered data — cleaner than inverse distance weighting for terrain and biome blending.

Distance Metric Variations

The visual character of a Voronoi diagram depends entirely on the distance function. Swapping metrics transforms the diagram's geometry completely:

• Euclidean: $d = \sqrt{dx^2 + dy^2}$ — The standard. Produces smooth, rounded cells with circular symmetry. Default for most applications.
• Manhattan: $d = |dx| + |dy|$ — Produces diamond-shaped cells. Perfect for grid-based or urban-layout maps where movement is axis-aligned.
• Chebyshev: $d = \max(|dx|, |dy|)$ — Produces square cells. Ideal for tile-based games where diagonal movement costs the same as cardinal movement.
• Minkowski: $d = (|dx|^p + |dy|^p)^{1/p}$ — Generalizes all three. At $p=1$: Manhattan, $p=2$: Euclidean, $p \to \infty$: Chebyshev.
• Weighted Voronoi: $d(x, p_i) / w_i$ — Larger weights produce larger cells. Ideal for territory control where factions have unequal strength.

Switching between metrics in a GPU shader is trivial — a single function swap:

float getDist(vec2 a, vec2 b, int metric) {
    vec2 d = abs(a - b);
    if (metric == 1) return d.x + d.y;          // Manhattan
    if (metric == 2) return max(d.x, d.y);       // Chebyshev
    return sqrt(d.x * d.x + d.y * d.y);         // Euclidean
}

Voronoi in Game Development

Procedural Map Generation

Voronoi diagrams are fundamental to polygon-based map generators. Amit Patel's widely-referenced polygon map generator uses Voronoi cells as geographic regions — each cell receives a biome type (ocean, grassland, desert, tundra) based on elevation and moisture values. The irregular shapes of Voronoi cells look more natural than rectangular grids, and the dual Delaunay graph provides cell adjacency for free, enabling flood-fill ocean spreading and river routing along Voronoi edges.

A typical pipeline:

1. Scatter $n$ random seed points across the map bounds
2. Apply Lloyd's relaxation (5–10 iterations) for more uniform cell sizes
3. Compute the Voronoi diagram to define cell shapes
4. Assign elevation and moisture values per cell (via noise or simulation)
5. Classify biomes from the (elevation, moisture) pair
6. Use the Delaunay adjacency graph to route rivers, spread ocean cells, build road networks

Lloyd's Relaxation

Random seed placement produces uneven cell sizes. Lloyd's relaxation iteratively moves each seed to the centroid of its Voronoi cell, then recomputes. After 5–10 iterations the distribution becomes more uniform — an effect used in procedural texture generation, point distribution, and stippling algorithms. The continuous centroid of a cell is:

$$p_i^{\text{new}} = \frac{1}{|V(p_i)|} \int_{V(p_i)} x \, dA$$

In a pixel-grid approximation:

function lloydRelax(seeds, width, height, iters = 5) {
  for (let iter = 0; iter < iters; iter++) {
    const sums = seeds.map(() => ({ x: 0, y: 0, n: 0 }));

    for (let y = 0; y < height; y++) {
      for (let x = 0; x < width; x++) {
        let minD = Infinity, nearest = 0;
        seeds.forEach((s, i) => {
          const d = (x - s.x) ** 2 + (y - s.y) ** 2;
          if (d < minD) { minD = d; nearest = i; }
        });
        sums[nearest].x += x;
        sums[nearest].y += y;
        sums[nearest].n++;
      }
    }

    seeds = seeds.map((s, i) =>
      sums[i].n > 0
        ? { ...s, x: sums[i].x / sums[i].n, y: sums[i].y / sums[i].n }
        : s
    );
  }
  return seeds;
}

Worley Noise (Cellular Noise)

Worley noise, introduced by Steven Worley in 1996, converts Voronoi distances into a procedural noise function. For each point, compute $F_1$ (distance to nearest seed) and $F_2$ (distance to second-nearest seed). Different combinations create different textures:

• $F_1$: Smooth gradient within each cell, brightest at seed centers. Used for water caustics, cellular blobs, pore structures.
• $F_2 - F_1$: Highlights cell boundaries with a bright ridge. Produces cracked stone, leather, dried mud, skin pores.
• $1 - F_1$: Inverted — bright centers fading to dark edges. Soap bubbles, scales, cells under a microscope.

vec2 worley(vec2 uv) {
    float f1 = 1e6, f2 = 1e6;
    for (int i = 0; i < NUM_SEEDS; i++) {
        float d = distance(uv, uSeeds[i]);
        if (d < f1)      { f2 = f1; f1 = d; }
        else if (d < f2) { f2 = d; }
    }
    return vec2(f1, f2); // .x = F1, .y = F2
}

// In main():
vec2 w = worley(vUv);
float crackPattern = w.y - w.x;  // Bright at cell edges
float cellFill     = 1.0 - w.x;  // Bright at cell centers

Fracture and Destruction Physics

When a surface shatters in a game, Voronoi diagrams define the fracture pattern. Scatter seed points at and around the impact location, compute the Voronoi cells, and each cell becomes a physics fragment — extruded into a 3D shard and given a rigid body. The technique appears in Red Faction: Guerrilla, various Houdini-powered FX pipelines (via the Voronoi Fracture SOP), and physics middleware like NVIDIA Blast.

void FractureObject(Vector3 impactPoint, int numFragments) {
    var seeds = new List<Vector3> { impactPoint };
    for (int i = 1; i < numFragments; i++)
        seeds.Add(impactPoint + Random.insideUnitSphere * fractureRadius);

    // Voronoi-partition the mesh into cells
    var cells = VoronoiMesher.Partition(targetMesh, seeds);
    foreach (var cell in cells) {
        var fragment = CreateFragment(cell);
        var rb = fragment.AddComponent<Rigidbody>();
        rb.AddExplosionForce(impulse, impactPoint, fractureRadius);
    }
}

Territory and Influence Systems

In strategy games, Voronoi diagrams naturally model territorial control: each faction's territory is the Voronoi cell of its capital or stronghold. The weighted Voronoi (power diagram) extends this — the effective distance to seed $p_i$ becomes $d(x, p_i) - w_i$, so factions with larger weights $w_i$ control proportionally larger regions. Updating the diagram in real time as cities are captured and strengths change gives natural-looking borders without expensive polygon clipping.

GPU Rendering and Jump Flooding

For real-time applications with many seeds — dynamic territory maps, live noise textures, signed distance field generation — the GPU is the right tool. Since every fragment independently computes its nearest seed, the brute-force approach becomes embarrassingly parallel: $O(n)$ work per fragment, but all fragments run simultaneously.

For very large seed counts, the Jump Flooding Algorithm (JFA) computes approximate Voronoi diagrams in $O(\log n)$ passes on the GPU. Each pass propagates seed information with a step size halved each iteration: $n/2,\, n/4,\, \ldots,\, 2,\, 1$. In each pass, every pixel checks 8 neighbors at the current step distance and updates its nearest-seed record if a neighbor's seed is closer. After $\lceil \log_2 n \rceil$ passes, every pixel holds its approximate nearest seed. JFA is used in Unreal Engine for distance field generation and in many real-time SDF shadow techniques.

Summary

Voronoi diagrams are a fundamental computational geometry structure with wide applications in game development. Procedural world generation, realistic fracture systems, GPU noise textures, and dynamic territory control all rely on Voronoi partitioning. The mathematics are elegant, the GPU implementation is efficient thanks to parallelism, and the visual results are compelling. The interactive demo at the top of this article lets you explore the core behavior directly: drag seed points to reshape cells in real time, switch between Euclidean, Manhattan, and Chebyshev distance metrics to see each metric's distinct geometry, and toggle Worley $F_2 - F_1$ mode to see the noise application. These parameters are just the starting point.