Упрощенное поколение провинций

Question

Мне нужно какое-то умное и довольно простое решение моей проблемы - создание формы провинции. Предположим, что map является матрицей NxM. Каждая ячейка представлена ​​натуральным числом. 0 означает, что тайл не принадлежит ни одной провинции. цифры 1 означают, что она принадлежит провинции № 1, № 2 означает, что ячейка принадлежит провинции № 2 ... и т. д.

Рассмотрим эту карту размером 4х4:

0000
0000
0000
0000

Эта карта представляет 16 тайлов, которые не принадлежат ни одной провинции.

Это карта, содержащая 1 провинцию:

0010
0111
0100
0000

это провинция размером 5 и id = 1. У нее нет соседей.

Рассмотрим 3 провинции:

1133
2100
2200
2000

Таким образом, провинция 1 является соседом 2 и 3. Провинция 3 является только соседом 1, а провинция 2 является только соседом 1. Есть также 7 не связанных плиток.

Моя проблема: я хочу создать k провинций на карте NxN. Есть также несколько простых правил:

• есть максимальный размер провинции и минимальный размер провинции (например, min = 2, max = 10)
• все плитки провинции должны быть соединены (по вертикали или горизонтали, но не по углам)

Пример недопустимой провинции (она не подключена):

1100
0000
0011
0000

• не должно быть анклавов (провинция внутри провинции)
• фигуры должны быть случайными

Я пытался реализовать это путем изменения заливки, но у него есть некоторые недостатки. Я буду рад услышать некоторые идеи или любую помощь. Карты могут быть 300x300 с 200 провинциями или более, поэтому это должен быть также какой-то умный алгоритм.

Answer 1

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

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

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

Алгоритм:

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

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

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

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

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

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

7) Для уменьшения площади каждого многоугольника

• Пока площадь> (максимальная площадь)
  • Найти границу полигона
  • Удалить случайную точку от границы многоугольника

Кстати, я написал эту программу в 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]}]

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

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

* * НТН тысяче сорок-девять

Answer 2

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

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

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

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

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

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

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

Answer 3

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

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

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