29
\$\begingroup\$

I currently have islands that look like this:

island

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

island with regions

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.

\$\endgroup\$
4
  • \$\begingroup\$ How did you get that island image in the first place? Did you generate it, and if so, how did you achieve it? \$\endgroup\$
    – Vaillancourt
    Jun 23, 2019 at 2:30
  • \$\begingroup\$ I got it from a online map generator. \$\endgroup\$
    – domisum
    Jun 23, 2019 at 6:23
  • \$\begingroup\$ Sorry for the delay in updating my answer - took longer to get home than originally planned. I added some illustrations & links. \$\endgroup\$
    – Pikalek
    Jun 24, 2019 at 15:37
  • \$\begingroup\$ 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. \$\endgroup\$
    – Anoplexian
    Jun 25, 2019 at 15:40

7 Answers 7

39
\$\begingroup\$

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.

island

\$\endgroup\$
2
  • 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, 2019 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, 2019 at 14:31
27
\$\begingroup\$

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:

enter image description here

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:

enter image description here

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

enter image description here

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.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ Jun 24, 2019 at 3:37
  • \$\begingroup\$ You added images! This is exactly what I am doing for a different purpose \$\endgroup\$ Jun 26, 2019 at 3:39
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
2
\$\begingroup\$

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.

map 1 map 2

\$\endgroup\$
0
\$\begingroup\$

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)
        //
    }
}
New contributor
Tarzan is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
\$\endgroup\$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .