Ttdfjt

I currently have islands that look like this:

And I want to procedurally subdivide it into regions, like this:

What algorithm does what I'm looking for? Do you have suggestions on how to create coherent regions like in the bottom picture. Your help is appreciated.

In the real world, those provincial borders will often be following geological features like rivers.

So maybe a good approach would be to model the geology of the island and have the borders fall out of this?

Red Blob Games has some good articles on this subject, with nice looking results.

His approach seems to involve using Voronoi tessellation, and define the rivers as the boundaries between the cells.

Check out the other articles on his site, he has done a lot of writing on the subject of map generation.

I would solve this problem with two passes of Voronoi diagrams:

First Pass: Region Partitioning

The first pass would use a somewhat sparse distribution of points (i.e. the distance between the points should be relatively large) in order to roughly divide the island into regions (see the note below regarding point generation). Next generate a Voronoi diagram based on these points. This will divide the island into polygonal regions around each point as shown below:

Second Pass: Border Randomization

Now that the island has been divided into regions, then next step is to 'rough up' the boundaries between them. To do so, generate a new layer of points using a more compact distribution of points (i.e. the distance between points should be small) and again use these points to create another Voronoi diagram. Next for each smaller region, assign it to a larger region by checking its 'seed' point. This will result in a more jagged boundaries between the larger subdivisions. Here's a close up of what it looks like with both Voronoi diagrams in place:

And here's that same area showing only the final boundaries:

Comments on Point Generation

Regarding point generation, I like using a Poisson disc distribution in order to get a relatively nice & even distribution of points. The other common option is to get a similarly even distribution is to use Lloyd's algorithm on a set of 'regular' random points. LLoyd's is easier to code, but can take some trial & error to determine how many passes are required to give the desired result.

One potential problem with this approach is that the first pass partitioning may generate some very small regions. If you don't want them in your final result, I would simply merge them with a random adjacent region.

Final Notes

The illustrations I provided happen to be raster images, but this technique also works with polygonal / vector representations as well.

MineCraft does this nicely, and its world generation algorithm has been analyzed and documented thoroughly.

There are various descriptions of the algorithm, one of them here: https://github.com/UnknownShadow200/ClassiCube/wiki/Minecraft-Classic-map-generation-algorithm

The core of the algorithm is a Perlin noise generator. This controls elevation directly (more or less, as the subsequent step to carve out caves can change the surface as well), as well as biome generation. Something like the biome generator is probably what you want to use to create your areas.

(An old version of it) is documented, basically it works by using two different Perlin Noise generators, one for "temperature", one for "precipitation", then choosing the biome from those two. The variables themselves (temperature and precipitation) aren't really used in the game later; for example, deserts have no rain, but the game determines this from the "desert" property, not from the original precipitation value.

There are various online tools to generate a biome map from a random seed, one of them is mineatlas.com. I guess that, internally, they use a java server which uses the internal classes of MineCraft itself; I don't know if any of their source code is available directly.

A typical algorithm used, for example, by Azgaar (source code). Is roughly like this:

1. split your landmass into smaller areas, e.g. through delauny triangulation or voronoi cells.


2. determine (randomly or otherwise) "starting" locations for your cultures, realms, religions or whatever else you want to simulate.


3. determine (randomly or otherwise) a "growth factor" for each of them. The more difference in growth factors you have, the less uniform your final map.


4. Now iterate over your realms (etc) and, depending on growth factor, make them spread into surrounding, empty tiles until the entire map is filled.


5. You probably want to end with straightening out borders a bit, by switching cells that have only one neighbour in their own colour and are otherwise surrounded by a different one to that colour.

If you are interested in doing this in vectorial format rather than raster-based approaches, I have written a blog post a while ago about pretty much exactly this.

http://blog.particracy.com/worlds-and-their-geography/

The idea is you start with a mesh (Voronoi based usually) and grow the regions concentrically from randomly seeded points that are sufficiently spaced apart.

What a fun question :) This approach is kinda based on Vornoi cells but the distance metric isn't quite Euclidian (I used the power of 1.5 instead of 2.0) and has some randomness built into it. It may jump over the water which isn't ideal.

Nearby regions can be merged together to get more interesting shapes, here I kind of used the N nearest neighbors to determine this.

If you are interested I can go into more details and share the Python code.