System Overview

Voronoi diagrams partition space into regions based on distance to seed points. Each region contains all points closer to its seed than any other. Delaunay triangulation is the dual graph of Voronoi, connecting points whose regions share boundaries.

Lloyd relaxation iteratively moves seed points to their Voronoi cell centroids, creating more uniform, evenly-spaced partitions. This is essential for biome generation, territory mapping, and procedural world division.

Why Games Use This

• Biome Generation: Divide world into distinct regions with natural boundaries
• Territory Systems: Define player or AI-controlled areas
• Procedural Maps: Create varied, organic-looking regions
• Pathfinding: Use Voronoi cells as navigation nodes
• Resource Distribution: Ensure even spacing of important features

Key Parameters

• Number of Points: More points = more regions, but slower computation
• Lloyd Relaxation: Iteratively improves spacing uniformity
• Relaxation Steps: More steps = more uniform, but may lose interesting variation
• Seed: Determines initial point placement

Failure Modes

• Too many points: O(n²) complexity makes computation slow
• Over-relaxation: Too many Lloyd steps create boring, uniform grids
• Edge cases: Points near boundaries create infinite Voronoi cells
• Degenerate triangles: Collinear points break Delaunay triangulation
• Memory issues: Storing full Voronoi mesh for large point sets is expensive

Scaling Behavior

Naive Voronoi computation is O(n²) per cell. Efficient algorithms (Fortune's sweep) achieve O(n log n), but for real-time applications, limit to 50-100 points. Lloyd relaxation multiplies cost by iteration count.

For large worlds, use hierarchical approaches: generate Voronoi at multiple scales, or use spatial hashing to only compute nearby regions.

Related Algorithms

• Fortune's Algorithm: O(n log n) Voronoi construction
• Bowyer-Watson: Incremental Delaunay triangulation
• Centroidal Voronoi: Lloyd relaxation variant with better convergence
• Poisson Disk Sampling: Generate well-spaced points for Voronoi seeds
• Voronoi Noise: Use Voronoi distances as noise function

Free Tools & Libraries

• d3-voronoi: JavaScript Voronoi implementation
• delaunator: Fast Delaunay triangulation
• CGAL: C++ computational geometry library
• scipy.spatial: Python Voronoi and Delaunay

System-Thinking Prompts

• What happens with 1000 points? How does performance degrade?
• Where do Voronoi cells break? Edge cases, degenerate inputs?
• How could players exploit deterministic partitioning? Predictable territories?
• Which parameter dominates? Point count, relaxation, or seed?
• What's the optimal relaxation count? When does it stop improving?
• How do boundary conditions affect generation? Infinite vs bounded cells?
• Can we guarantee minimum cell size? Maximum variation?