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.
PCG Wiki References
The following images on Flickr have been generated using Voronoi diagrams:
- Voronoi Diagram - Wikipedia article on Voronoi diagrams.
- Polygonal Map Generation - Uses Voronoi Diagrams as the initial step.
- Voroni Diagrams tutorial, source for image.
- Over-engineering Dungeon Generation by RogerN, which uses a delaunay triangulation to determine points between which to construct tunnels.
- Fortune's Algorithm Explanation Walk through of the best method for creating Voronoi diagrams