Search code examples
algorithmlanguage-agnosticdictionarygeneratortopology

Simplified province generation

I need some clever and rather simple solution to my problem - province shape generation. Suppose that map is matrix NxM. Each cell is represented by natural number. 0 means that tile does not belong to any province. numbers 1 means that it belongs to province nr 1, nr 2 means that cell belongs to province nr 2... etc.

Consider this map, which is 4x4:

0000
0000
0000
0000

This map represents 16 tiles that do not belong to any province.

This is map containing 1 province:

0010
0111
0100
0000

this is province of size 5, and id = 1. It has no neighbours.

Consider 3 provinces:

1133
2100
2200
2000

So province 1 is neighbour of 2 and 3. Province 3 is only neighbour of 1 and province 2 is only neighbour of 1. There are also 7 not associated tiles.

My problem is: I want to generate k provinces on map NxN. There are also few simple rules:

  • there is max size of province and min size of province (for example min = 2, max = 10)
  • all tiles of province should be connected (by vertical or horizontal, but not corners)

Example of invalid province (it's not connected):

1100
0000
0011
0000
  • there should not be enclaves (province inside province)
  • shapes should be random

I was trying to implement it by flood fill modification but it has some disadvantages. I'll be glad to hear some ideas or any help. Map's can be 300x300 with 200 provinces or more so it should be also some clever algorithm.

Solution

  • Using Voronoi Diagrams

    I think this one will not generate all the possible maps, but will do with most "reasonable" ones.

    Voronoi Diagrams consist of partitioning the plane according to proximity to selected points. You can see examples in the Wikipedia link on the title.

    Algorithm:

    1) Select a set of random points greater or equal to your desired number of provinces. If you generate more than needed, you'll guarantee empty spaces.

    alt text

    2) Run the Voronoi algorithm (could describe it if you are interested, but easy to find in the web)

    alt text

    3) Calculate the areas of the resulting polygons

    4) Check that you have enough areas with surface > (minimum desired area). If not, go to 1

    5) If you generated more random points than those needed, select randomly the set of polygons that will compose each province from those with area > (min area)

    6) Check if your polygons have area < (max area). If not, you have to reduce them.

    7) To reduce the area of each polygon

    • While area > (max area)
      • Find Polygon boundary
      • Delete a random point from the polygon boundary

    BTW, I wrote this program in Mathematica to get the graphs above:

     Clear["Global`*"];
 Needs["ComputationalGeometry`"];
 data2D = Table[{RandomReal[16], RandomReal[16]}, {10}]
 convexhull = ConvexHull[data2D]
 (delval = DelaunayTriangulation[data2D]) // Shallow[#, {5, 6}] &
 b1 = {{0, 0}, {16, 0}, {16, 16}, {0, 16}};
 {diagvert1, diagval1} = BoundedDiagram[b1, data2D, delval, convexhull];
 Show[{Graphics[Join[{PointSize[Large]}, {Point@data2D}], Frame -> True]}]
 Show[{Graphics@Point[data2D],   DiagramPlot[data2D, diagvert1, diagval1]}]

    I include the code just to show that the algorithm is easy to implement with the right tools.

    Note: The algorithm description does not mention that your areas are composed of squares ...

    HTH