Simplified province generation

Question

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.

Answer 1

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.

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

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

Answer 2

I have few time but a nice idea is: adding province first left to right then right to left. Like

 1111222
 3333322
 3344555        
 0000665

I've written random numbers.. is it correct?

void insert(Matrix matrix){
    lastProvince=0;
    missingProvince=MIN;
    if(matrix.dimensio<MIN*K) throw new RuntimeException("Matrix too small");
    for(y=0;y<matrix.height;y++){
        if(y%2==0){
            for(x=0;x<matrix.width;x++){
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
        }else{
            for(x=matrix.width;x>=0;x--){// is -- not ++
                matrix[x][y]=lastProvince;
                missingProvince--;
                if(missingProvince==0) {
                    lastProvince++;
                    missingProvince=MIN;
                }
                if(lastProvince==k) return;
            }
         }
   }
}

Not tested but that's the idea..

Answer 3

Just off the top of my head:

1. Generate a "seed" for each province you need. You have a NxM map and L provinces, just generate L unique random numbers in the range [0-(N*M-1)]. the X,Y coordinates of your seed with number P are P/M and P%M.

2. Until all your provinces are larger than min size and smaller than max size:

   a. Select a random province that can still be grown (size smaller than max, not completely surrounded by other provinces)

   b. Add a random neighbor cell that is not part of any province to that province.

There is a small chance of enclaves with this technique, but it is very low. You could enhance step b to check for them and not grow if growing will create one.

There is also a chance that provinces will remain too small if they become completely surrounded with other provinces before they themselves can grow large enough. You could check and adjust for that after step 2 completes.