Procedurally generate regions on island

Question

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.

How did you get that island image in the first place? Did you generate it, and if so, how did you achieve it? — Vaillancourt♦, Jun 23 '19 at 2:30
Sorry for the delay in updating my answer - took longer to get home than originally planned. I added some illustrations & links. — Pikalek, Jun 24 '19 at 15:37
If you got this from an online generator, you should look at Azgaar's Fantasy Map Generator. It has regions and names, with customizeable parameters, and WB.SE says hello. It's a github, so you may be able to check their code. — Anoplexian, Jun 25 '19 at 15:40

Bram · Accepted Answer · 2019-06-22 22:53:33Z

39

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.

answered Jun 22 '19 at 22:53

Bram

3,51014 silver badges20 bronze badges

3

\$\begingroup\$ Note that in real world, political or administrative divisions also sometimes have arbitrary divisions, usually straight lines (e.g. along latitud/longitud lines, lines between mountain peaks, etc.). \$\endgroup\$ – Pablo H Jun 24 '19 at 12:02
2

\$\begingroup\$ @PabloH Good point, although straight borders seem to be post-mediaval colonial era phenomenon. But since we don't know the setting of OPs problem, it might be relevant \$\endgroup\$ – Sentry Jun 24 '19 at 14:31

add a comment |

Community · Accepted Answer · 2020-06-16 10:15:23Z

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.

For procedural floor plans this is what I do, do a Voronoi diagram from points inside the region (the island), construct a grid (it doesn't have to be rectangular, for your case a deformed grid) that encloses the same region, then compute the boolean intersections of the grid and the Voronoi, calculate the areas and assign to a data tree (list of list, jagged array, etc... whatever data structure you prefer) according to the 0.6 percentage of the smallest grid cell, you'll get some missing cells, but you can compare your culled grid with the original to find and reassign to your tree. — Felipe Gutierrez, Jun 24 '19 at 3:37
You added images! This is exactly what I am doing for a different purpose — Felipe Gutierrez, Jun 26 '19 at 3:39

Guntram Blohm · Accepted Answer · 2019-06-24 13:11:44Z

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.

Tom · Accepted Answer · 2019-06-25 11:27:50Z

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

split your landmass into smaller areas, e.g. through delauny triangulation or voronoi cells.
determine (randomly or otherwise) "starting" locations for your cultures, realms, religions or whatever else you want to simulate.
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.
Now iterate over your realms (etc) and, depending on growth factor, make them spread into surrounding, empty tiles until the entire map is filled.
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.

Wouter Lievens · Accepted Answer · 2019-06-23 21:34:21Z

3

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.

answered Jun 23 '19 at 21:34

Wouter Lievens

2661 silver badge3 bronze badges

add a comment |

NikoNyrh · Accepted Answer · 2019-06-26 18:56:10Z

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.

Stack Exchange Network

current community

your communities

more stack exchange communities

Procedurally generate regions on island