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:
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:
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:
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.
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:
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.
It just so happens that I found a VERY easy solution to this problem. I use a Flood-Fill technique as follows. First I create a number of random seed locations on the map. Then I use Flood-Fill to "grow" the seeds, randomly. The results very much mirror what was asked for. The code for this is not particularly long. Perhaps one question is, "So, how many seeds should I use?" This will depend on how small/large you would like each region to be. One easy solution is to use a number of partitions as a percentage of the number of hexes/squares in your land mass. For instance: say your land mass is 400 hexes in size and you would like your land mass divided into 10 regions, then simply divide the total size of the land mass (400) by 10 and, thus, create 40 seeds. This is also further easily modified to have a random # of regions (or a random # of regions within a given range, etc...). The following Java code should get you close. Obviously, you will have to fill in some code, but hopefully you get the idea:
private void Assign_Hexes_to_Regions (
final Random RNG,
List <Integer> frontier_hex_IDs,
List <Integer> accompanying_frontier_region_IDs,
final Function <Coords, List <Coords>>
function_all_adjacent_coords
) {
//
// use a Flood-Fill technique to assign EACH Hex to EXACTLY ONE Region
//
while ( frontier_hex_IDs.size() > 0 ) {
//
// Randomly select one of the UNASSIGNED Hexes
//
int random_index = RNG.nextInt( frontier_hex_IDs.size() );
int random_vertex_ID = frontier_hex_IDs.remove( random_index );
int random_region_ID = accompanying_frontier_region_IDs.remove( random_index );
Integer existing_region_ID = this.hex_ID_to_partition_ID.get( random_hex_ID );
if ( existing_region_ID == null ) {
//
// NO Region assigned (yet) to this (Random) Hex
//
this.Assign_Hex_ID_to_Region( random_hex_ID, random_region_ID, frontier_hex_IDs, accompanying_frontier_region_IDs, function_all_adjacent_coords );
} else if ( existing_region_ID != random_region_ID ) {
//
// This Hex was PREVIOUSLY assigned to a DIFFERENT Region. Thus,
// this Hex is at a Region Boundary
//
this.Get_Region( existing_region_ID ).Add_Boundary_Hex_ID( random_hex_ID );
}
}
private void Assign_Hex_ID_to_Region (
final int hex_ID,
final int region_ID,
List <Integer> frontier_hex_IDs,
List <Integer> accompanying_frontier_region_IDs,
final Function <Coords, List <Coords>>
function_all_adjacent_coords
) {
//
// Assigns the Hex to the specified Region
//
this.Set_Region_ID_for_Hex_ID( hex_ID, region_ID );
//
// Add Adjacent Hexes to the Flood-Fill possibilities
//
// note: the Get_All_Adjacent_Coords() function determines if the Coordinates Wrap-Around or not
//
for ( Coords adjacent_vertex_coords : function_all_adjacent_coords.apply( this.space_subset.Get_Space().Get_Coords_from_Vertex_ID( vertex_ID ) ) ) {
if ( this.space_subset.Get_Space().Has_Coords( adjacent_vertex_coords ) ) {
Integer adjacent_hex_ID = this.space_subset.Get_Space().Get_Hex_ID_from_Coords( adjacent_hex_coords );
if ( this.space_subset.Is_in_Subset( adjacent_hex_ID ) ) {
frontier_hex_IDs.add( adjacent_hex_ID );
accompanying_frontier_region_IDs.add( region_ID );
}
//
// do NOT Add the Adjacent Hex if it is OFF on the Land Mass
//
}
//
// do NOT Add the Adjacent Hex if it is NOT on the Map (incl. Wrap-Around)
//
}
}
Here are 2 screenshots of a land mass with 2 different randomly-created regions using the Flood-Fill algorithm.
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.
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.
