Tech Talk: The Voronoi Diagram

Tech Talk Banner

Procedural generation is an umbrella term for various ways of using algorithms to create game content that might otherwise be hand-crafted – things like levels, music, and game content.  One tool that can be useful in procedural level and art generation is the Voronoi diagram.  In this post I’d like to tell you a little about the Voronoi diagram, what it can be used for, and how you might go about using Voronoi diagrams in your own code.

A portion of a Voronoi diagram

What is a Voronoi diagram?

Simply put, the Voronoi diagram is a way of dividing a given space into a series of areas centered around seed points, such that every point in an area is closer to that area’s seed than to any other area’s seed.  The diagram is named after Georgy Voronoy, a Ukranian mathematician who studied the concept.

The Voronoi diagram has a very distinctive look, which is a large part of its appeal.  At the top of the post, you can see an example from a small program I wrote recently, with the seed points in black.

The colors are only illustrative; it is the general shape of the diagram, with blobby, irregular areas, that makes it so interesting.  While this particular example has very evenly distributed regions, other configurations are also possible depending on how seed points are distributed.  Other options might include changing point density based on a Perlin noise function, or placing points based on pre-existing data, such as the location of supermarkets in a city (which could be used to visualize food deserts, or coverage of a given city by one company and its competition).  A great way to get a feel for the diagram’s structural potential is this online Voronoi generator.

Uses

The Voronoi diagram has a number of uses, and its potential almost certainly extends far beyond what it has already been used for.  Wikipedia has a nice list of (non-game) applications, but there are a number of game development applications as well.

One of the most obvious uses is in terrain generation, where Voronoi diagrams help the designer break the terrain up into manageable but irregular chunks that can then be used to generate large terrain features.  One of the most impressive instances of this I’ve come across is this implementation by Amit Patel, in which he generates entire landscapes using a Voronoi diagram as a substrate.  I have also done some work in this area myself, with maps like this as the result (the circular curvature on the left is an artifact of my simplistic terrain generation algorithm, and not a fault of the Voronoi diagram’s).

Another application is in art and texture generation.  The Procedural Content Generation Wiki has a long list of images featuring art created using a Voronoi diagram.  Particularly good candidates might include scales, cracked terrain, or stylized ripples on water.

In a particularly creative use, Gaslamp Games are using the underlying concepts behind a Voronoi diagram to assign plant species to different climate types, as well as using it to setup biomes and climate in their upcoming game.

Another unusual, more experimental example is that of Voromoeba, a small game in which the graphics (including text) are entirely composed of a dynamic Voronoi diagram.

Beyond direct usefulness in game development, the Voronoi diagram can also be a powerful visualization tool.  If you are designing an open world game, for instance, you can use a Voronoi diagram to plot the location of specific kinds of places, and the empty space around them, which makes it much easier to see, for example, a large area where there are no points of interest, or which towns and hamlets are closest to which major cities.

A Simple Implementation

There are a number of potential ways to generate Voronoi diagrams, some of which are more difficult to understand and implement in others.  One formula which is especially popular is Fortune’s algorithm, but unless you require real-time Voronoi calculation, implementing a simpler and more straightforward solution is also a perfectly valid approach.  The approach I will describe here is one I use in my own projects, and makes use of some optimizations I’ve developed that help make it much faster than simply brute-forcing the diagram.  Any code I use will be C++, but in practice it shouldn’t be difficult to translate the code into other languages such as C# or Java.

The substrate of the Voronoi diagram I will be calculating is simply a 100×100, 2D grid of integers called Grid.  In practice, these points could be anything, from a simple two-element vector to an entire instance of a class of something like map tiles, planets, or whatever else is most useful to you.  Integers just happen to be extremely simple.

Seed distribution is critical to the overall shape of the Voronoi diagram, but it also depends strongly on what you want to do with it, so I’ll leave that up to you.  If you want very evenly spread areas, such as in the example image below, I highly recommend checking out Poisson disk sampling, which is a simple and effective way to achieve that result.  However, there are other ways to get relatively evenly-spaced points, and many other situations in which the points should not be evenly distributed.

Points distributed using Poisson disk sampling

So what we start with, then, is a 100×100 grid in which all the integers have the value 0.  First we place seed points, which are identified by giving them a unique negative value – the first seed point placed was -1, the second -2, etc.  So for example, in this case, the value of Grid[5][5] is negative (perhaps -1, or -8, or -27).  When using single data points like plain integers, it is important to somehow be able to distinguish seeds from non-seeds.  I chose to make seeds be of the opposite sign as the non-seed points, but you could do things differently, for example by having seed integers be odd and non-seeds be even.

Each non-seed point must be assigned to a seed, as part of that seed’s cell.  To do this, every single point in Grid[][] with a value of 0 must be checked; with a two-dimensional vector, that generally means two loops iterating throughout the vector.  For each case where (Grid[x][y] == 0), we need to find the closest point with a negative value.  The easiest way to do this is to search the nearby area, expanding the search until a point is found.  If we were to color the first-searched points darker and the last-searched points lighter, we could illustrate the search we need to perform like this:

First check the neighboring points that are 1 unit away, then those that are 2 units away, and so on, until the first seed point is encountered.  It is most efficient to check each of these layers one at a time, and only once.  Before optimizing, though, I did this the brute-force way: iterate through a 3×3 (center + radius of 1) square around the point, then again through a 5×5 square, and again through a 7×7 square, ad infinitum.  This is very inefficient, though, since while-looping until something is found and checking all points in range means that by the time the third ring has been checked, the second ring will have been checked twice and the first ring three times.

My solution to this was simple enough.  I now have a single while-loop that searches a single layer at a given distance from the point in question, with that distance increasing each time the loop fails to find a seed.  This is significantly faster; it almost doubled the speed of the algorithm.  The principle is pretty simple; for each iteration of the loop, as long as no seeds have been found, define four numbers, representing the coordinates of the outer edges of the square, like this:

int LeftBound = Point.x – SearchRadius;
int RightBound = Point.x + SearchRadius;
int UpperBound =  Point.x + SearchRadius;
int LowerBound = Point.x – SearchRadius;

I haven’t done so here, for clarity’s sake, but always remember to prevent the search from straying beyond the bounds of the vector; otherwise, it’s quite possible the algorithm will simply crash, for instance if it tries to access the point at Grid[-2][4], or other invalid options.

Once you have these, you’ll want to have two smaller loops iterating along a list of options.  One loop will check the upper and lower edges of the search square, the other will check the left and right edges.

These loops will also figure out the closest point at the same time; it is important not to simply take one of the first points to be found by the search, since points in the corners of the square are actually much further than points in the middle of the sides, and you can end up with points being marked as closest which are actually not.  I had that problem when developing this algorithm, and you can see the consequences below; to the left was the first attempt, where the first points to be found by the square search were the only ones considered; to the right is the “correct” formula (though you may well find that the first way to do things is prettier!).

Of course, you can voluntarily choose to calculate distances inexactly to achieve certain effects; another option is to use Manhattan distance (i.e. the sum of the X and Y differences between two points), which will again create a different visual effect.  For now, though we’ll stick with exact distances.

To find the closest of all found seeds, you will need to keep track of three things:

  • Whether you’ve started finding seeds (here, bool GotSomething, which should start false)
  • How close the closest of those seeds is (here, float ClosestSoFar, which should start absurdly high; I like to set it to the square of Grid’s size)
  • Which seed is the closest so far (here, Vector2i Closest)

This loop, for example, searches for all values between the LeftBound and the RightBound that has a Y value either of the UpperBound or the LowerBound.

for (int xCheck = LeftBound; xCheck <= RightBound; ++xCheck) 

//Check the top 
if (Grid[xCheck][UpperBound] < 0 &&
Distance(Vector2i(xx, yy), Vector2i(xCheck, UpperBound)) < ClosestSoFar) 

ClosestSoFar = Distance(Vector2i(xx, yy), Vector2i(xCheck, UpperBound));
GotSomething = true;
Closest = Vector2i(xCheck, UpperBound);

}
//Check the bottom 
if (Grid[xCheck][LowerBound] < 0 &&
Distance(Vector2i(xx, yy), Vector2i(xCheck, LowerBound)) < ClosestSoFar) 
{

ClosestSoFar = Distance(Vector2i(xx, yy), Vector2i(xCheck, LowerBound));
GotSomething = true;
Closest = Vector2i(xCheck, LowerBound);

}

The loop that checks the left and right edges is similar.  At the end of each iteration of the while loop, SearchRadius is incremented by one until GotSomething is true and SearchRadius is equal to or larger than ClosestDistance, meaning it is impossible to find new points closer than the closest already found.  Doing this for every non-seed point is necessary, and this can be very computationally intensive, especially if you are working with a grid of several hundred units to a side or more.  My example of a map, above, is on a 700-size grid, and it takes around 25 seconds to generate an entire world, a bit more than half of which is the Voronoi diagram itself.

The end result, though, is that every point in the grid will have a non-zero value, most of them positive.  If you create a number of cells equal to the highest value present on the grid, then the index of the cell each point belongs to will be the absolute of that point’s value minus 1 (because if the cells are in some kind of array or vector, they will start at 0, whereas your lowest absolute integer point will be 1).  This makes distributing points to cells trivially easy.

A cell itself can take any shape you like, from a vector of Vector2i objects to instances of a whole class with many other useful functions.  How you set things up depends on what you want to do with them; in my map-making program, a Cell is a class that contains a list of pointers to Chunks (the points being assigned), a number of useful functions for map-making, as well as other attributes such as geography rules, parent regions, flags used during construction, a separate list of edge Chunks, and more.

Conclusion

Ultimately, Voronoi cells are simply a way of spreading the influence of points around the map.  The core usefulness of a Voronoi diagram lies in its rendering a sort of controlled chaos; you, the designer, have control over the size and regularity of cells, which you can use to your advantage to create interesting geometries, for whatever purposes you see fit.

In the case of map-making, Voronoi diagrams have the potential disadvantage of not being able to quickly generate infinite maps, as in Minecraft – it can only generate arbitrarily large maps.  In many cases, this may not be a problem; it may be nice for Minecraft to have an infinite world, but I doubt many players would complain if they only had a world of, say, 100,000 square kilometers.  The advantage over techniques such as Perlin noise, as I see it, is that it allows for a much more modular approach, which in turn gives the designer much more control over the end result.


Guerric Haché is a Game Design student at VFS

Leave Comments