Voronoi Diagrams in Procedural City Generation

Procedural city generation relies on mathematical abstractions to simulate the organic complexity of real-world urban environments. By using Voronoi diagrams, game developers can dynamically divide two-dimensional space into logical spatial regions based on a set of generated seed points. This article explores how developers harness these geometric structures to lay down coherent road networks, establish distinct zoning districts, and build scalable urban hierarchies that balance realistic aesthetics with functional gameplay performance.

The Foundation: Voronoi Tessellation in Urban Space

A Voronoi diagram divides a plane into convex polygons, or "cells," relative to a predefined set of seed points (sites). Every point within a specific cell is closer to that cell's seed point than to any other site on the map.

In urban game development, these cells represent the foundational building blocks of a city: neighborhoods, urban blocks, or broader administrative districts. The boundaries where two cells meet naturally form borders, and the intersections where three or more cell boundaries converge form natural junctions or nodes.

Generating Coherent Road Networks

Developers transform the raw geometry of a Voronoi diagram into a navigable road layout by extracting its edges and vertices:

  1. Arterial Highways and Main Roads: The shared borders between Voronoi cells serve as the primary road network. Because Voronoi edges organically trace the median distance between population centers (the seed points), they produce branching, naturally curving avenues that mimic historical, organically grown cities.
  2. Intersection Nodes: The vertices where multiple Voronoi edges intersect are mapped directly as traffic intersections, roundabouts, or town squares.
  3. Dual Delaunay Triangulation for Expressways: The mathematical dual of a Voronoi diagram is the Delaunay triangulation, which connects the seed points directly. Developers often use Delaunay edges to establish high-speed expressways, bridges, or subway lines that link neighborhood cores directly through the center of each cell.
  4. Grid Subdivisions for Local Streets: Once the perimeter of a Voronoi cell is bound by primary roads, the interior of the cell is subdivided using secondary algorithms—such as recursive binary space partitioning (BSP), L-systems, or oriented bounding boxes—to generate regular, high-density residential grids or suburban cul-de-sacs within the organic exterior frame.

Controlling Realism with Lloyd's Relaxation and Distance Metrics

A purely random distribution of seed points yields chaotic, jagged cells that do not reflect functional urban planning. Developers apply specific adjustments to control the structure:

  • Lloyd’s Relaxation: This iterative algorithm repeatedly calculates the centroid of each Voronoi cell and moves the seed point to that centroid before recalculating the diagram. Applying Lloyd's relaxation two to four times evens out cell sizes, smooths harsh angles, and creates hexagonal, honeycomb-like layouts typical of planned suburban layouts or balanced metropolitan districts.
  • Manhattan vs. Euclidean Metrics: While standard Euclidean distance creates smooth, radial networks, switching to Manhattan (Taxicab) distance metrics forces the cell edges into 90-degree and 45-degree angles, generating procedural street grids suitable for modern American-style cities.
  • Biased Point Distributions: Placing seed points along natural features (such as coastlines or river paths) or using Perlin noise masks to cluster points near a defined "downtown" ensures that road density scales realistically with simulated population density.

Procedural Zoning and District Allocation

Once the spatial framework and roads are established, the Voronoi cells are classified into distinct zoning districts (commercial, industrial, residential, and civic):

  • Distance Field Zoning: Developers calculate the distance of each Voronoi cell from the central seed point (the urban core). Cells closest to the center receive high-density commercial zoning; mid-range cells become medium-density residential; outer cells are assigned low-density residential or agricultural tags.
  • Noise-Based Clustering: Coherent districts require adjacent cells to share zones rather than alternating randomly. Developers sample 2D coherent noise (such as Simplex noise) at the seed point coordinates to group contiguous Voronoi cells into unified industrial sectors, historic districts, or waterfront commercial zones.
  • Graph Traversal and Clustering: Because Voronoi cells can be represented as an adjacency graph, developers use clustering algorithms to propagate zone types across neighbors, ensuring that incompatible zones—such as heavy industry and low-density housing—are separated by commercial or parkland buffer cells.

Hierarchical Nesting for Scalable Detail

For expansive open-world games, developers frequently use multi-tier Voronoi diagrams. A macro-scale Voronoi diagram first divides the entire game map into major regions (e.g., agricultural, metropolitan, logistics). Inside each metropolitan region, a secondary Voronoi pass generates specific neighborhoods and main avenues. Finally, within those neighborhood cells, a micro-scale pass defines individual property boundaries and pedestrian alleys. This nested architecture keeps computational generation fast, simplifies pathfinding graph construction, and ensures urban coherence at every level of scale.