Organic Voronoi

Voronoi diagrams are an oft-used method in procedural generation to fill out a space with non-square tiles. This is a voronoi diagram:

Each black circle denotes an "origin" with an x-coordinate, y-coordinate and a colour. No more information is needed to create the Voronoi cells. Each origin has a Voronoi cell, here illustrated with its colour, which consists of all points that are closer to this origin than any other origin.

The great thing about Voronoi is that it is an easy way to fill out a space with arbitrary shapes. In the picture above, you will be able to find rectangles, pentagons, hexagons, heptagons, etc. Theoretically speaking, you can also have triangular cells.

There are some other reasons that Voronoi diagrams are nice, such as them constituting a complete graph of nodes distributed over a space - you could, for instance, use the origins as cities, and then easily find out which cities would have roads leading to each-other.

However, more often, the Voronoi cells themselves (that is, the coloured areas) are used. For instance, one could imagine the cells to denote different biomes in some sort of terrain generation. However, this leaves straight, ugly borders. So what can we do to make the borders less straight?

The above illustration is the same Voronoi diagram as the one above, only now, Perlin noise has been used to distort which points belong to which cell. This creates some more interesting borders between between cells.

This is kind of easy to accomplish as long as you use a pixel-by-pixel (or tile-by-tile) assignment to the closest Voronoi origin, since you can quite simply offset the actual coordinates of the pixel by Perlin noise - quite closely related to distorted Perlin noise. However, if you use the geometric definition of the Voronoi diagram, of points and borders, it's a bit more complex. Not terribly so. I'll make a post about this at some point, I'm sure.

The method I am titling this post about, however, is the one seen above. It might seem a bit like a higher-frequency Perlin noise, but in actuality, it is nothing of the sort. Let me show you via animation:

The reason I call this organic Voronoi is because the Voronoi cells are grown, randomly, starting from each origin. Several thousand times each step, random pixels are checked - if they are coloured, they will colour all neighbouring non-coloured pixels. Repeat until you achieve this nice organic Voronoi pattern.

Of course, this might seem quite computationally expensive, but really, this depends on how many tiles are to be generated. In the Cozy Kingdoms, which I posted a preview of a couple days ago, this method is used with nice results and few problems.