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
Brute force approach implemented in JavaScript
//specify an empty points array
var points = [];
//get a random number in range min, max - 1
function randRange(min, max) {
return Math.floor(Math.random() * ((max) - min) + min);
}
function definePoints(numPoints, mapSize) {
//we want to take a group of points that will fit on our map at random
for(var i = 0; i < numPoints; i++) {
//here's the random points
var x = randRange(0, mapSize);
var y = randRange(0, mapSize);
//type: decides which point it is
//x, y: location
//citizens: the cells in our grid that belong to this point
points.push({type: i, x: x, y: y, citizens: []});
}
//brute force-y but it works
//for each cell in the grid
for(var x = 0; x < mapSize; x++) {
for(var y = 0; y < mapSize; y++) {
//find the nearest point
var lowestDelta = {pointId: 0, delta: mapSize * mapSize};
for(var p = 0; p < points.length; p++) {
//for each point get the difference in distance between our point and the current cell
var delta = Math.abs(points[p].x - x) + Math.abs(points[p].y - y);
//store the point as nearest if it's closer than the last one
if(delta < lowestDelta.delta) {
lowestDelta = {pointId: p, delta: delta};
}
}
//push the cell to the nearest point
var activePoint = points[lowestDelta.pointId];
var dx = x - activePoint.x;
var dy = y - activePoint.y;
//log delta in cell for drawing
activePoint.citizens.push({
dx: dx,
dy: dy
});
}
}
}
definePoints(20, 40);
for(var point of points) {
for(var citizen of point.citizens) {
//set color of cell based on point
//draw cell at (point.x + citizen.dx) * cellSize, (point.y + citizen.dy) * cellSize
}
}
The Brute Force Approach - Manhattan Distance sampling
- Randomly select points on your grid
- Assign an 'id' to each point, in this case, we'll assign colours to visually distinguish our points
- For each cell begin to fill it with the colour of the nearest point - first cell shown below
- Continue to fill the cells one by one - first line shown below
- Keep going until your grid is full :)
- You're done. This is the basic idea behind the algorithm, there are places to improve like finding a smarter way to find the nearest point and deciding on cells that are the same distance from two or more points, you could just give one precedence, or, alternatively, let RNG decide. The opportunities are endless.
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.
- 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