Voronoi Diagram
Description
Voronoi Diagrams is an algorithm where one takes any arbitrary (usually random) set of points on a map (or a table, etc.) Then the algorithm counts the nearest point for every pixel (or unit, etc), and assigns the pixel for that point. Using Voronoi Diagrams often results in a more organic looking division than rectangular or circular systems. The different points (and their areas) can be used to demonstrate different countries, vegetation, sea and land, or almost anything. It's not limited to terrain either, you could use it for AI as a kind of influence map, or texture generation or anything that needs different values in a 2d (or 1d or 3d..) table.
Code Example
PCG Wiki References
Flickr Stream
The following images on Flickr have been generated using Voronoi diagrams:
External Links
- Voronoi Diagram - Wikipedia article on Voronoi diagrams.
- Voronoi maps - A blog entry featuring Voronoi diagrams used as world maps
- Over-engineering Dungeon Generation by RogerN, which uses a delaunay triangulation to determine points between which to construct tunnels.
- Voroni Diagrams tutorial, source for image.
page_revision: 15, last_edited: 1248097816|%e %b %Y, %H:%M %Z (%O ago)
