Использование диаграмм Вороного

Я думаю, что этот не будет генерировать все возможные карты, но сделает с наиболее "разумными".

Диаграммы Вороного состоят из разделения плоскости в соответствии с близостью к выбранным точкам. Вы можете увидеть примеры в ссылке Википедии на заголовке.

Алгоритм:

1) Выберите набор случайных точек, превышающий или равный желаемому количеству провинций. Если вы сгенерируете больше, чем нужно, вы гарантированно получите пустые места.

2) Запускаем алгоритм Вороного (можно описать, если интересно, но легко найти в сети)

3) Вычислить площади полученных многоугольников

4) Убедитесь, что у вас достаточно площадей с поверхностью > (минимальная желаемая площадь). Если нет, перейдите к 1

5) Если вы сгенерировали больше случайных точек, чем нужно, выберите случайным образом набор полигонов, которые будут составлять каждую провинцию, из полигонов с площадью > (мин. площадь)

6) Проверьте, имеют ли ваши полигоны площадь ‹ (максимальная площадь). Если нет, то вы должны уменьшить их.

7) Уменьшить площадь каждого полигона

• While area > (max area)
  • Find Polygon boundary
  • Удалить случайную точку с границы полигона

Кстати, я написал эту программу на Mathematica, чтобы получить графики выше:

 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]}]

Я включил код только для того, чтобы показать, что алгоритм легко реализовать с помощью правильных инструментов.

Примечание: В описании алгоритма не упоминается, что ваши области состоят из квадратов...

ХТН

У меня мало времени, но есть хорошая идея: добавить провинцию сначала слева направо, а затем справа налево. Нравиться

 1111222
 3333322
 3344555        
 0000665

Я написал случайные числа.. это правильно?

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;
            }
         }
   }
}

Не проверено, но это идея ..

Просто у меня в голове:

1. Создайте «начальное число» для каждой нужной вам провинции. У вас есть NxM карта и L провинций, просто сгенерируйте L уникальных случайных чисел в диапазоне [0-(N*M-1)]. координаты X,Y вашего семени с номером P равны P/M и P%M.

2. Пока все ваши провинции не будут больше минимального размера и меньше максимального размера:

   а. Выберите случайную провинцию, которую еще можно вырастить (размер меньше максимального, не полностью окруженная другими провинциями)

   б. Добавьте в эту провинцию случайную соседнюю ячейку, которая не является частью какой-либо провинции.

Есть небольшой шанс анклавов с этой техникой, но он очень низок. Вы можете улучшить шаг b, чтобы проверить их и не увеличивать, если рост создаст их.

Также существует вероятность того, что провинции останутся слишком маленькими, если они будут полностью окружены другими провинциями, прежде чем сами смогут стать достаточно большими. Вы можете проверить и настроить это после завершения шага 2.