Voronoi Diagram
voronoi-preview.jpg

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
FVfwBdt.png
  • Assign an 'id' to each point, in this case, we'll assign colours to visually distinguish our points
j856qZ9.png
  • For each cell begin to fill it with the colour of the nearest point - first cell shown below
I0QRbpo.png
  • Continue to fill the cells one by one - first line shown below
eS9U6J4.png
  • Keep going until your grid is full :)
X4c7oFh.png
  • 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:

{"module":"wiki\/image\/FlickrGalleryModule","params":{"tags":"voronoi","tagMode":"any"}}

External Links

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License