Процедурная генерация случайного мира из 100 на 100 клеток?

Question

[Даниил]

Изучал алгоритм Воронова, как только понял, понял, что он не подойдет под мою задачу(так как сама карта(из-за маленького размера) уже частное решение с квадратными полигонами).
Задача, сгенерировать материк на 100 на 100 клетках, и распределить его территорию на N стран с случайными размерами. То есть не понимаю как сгруппировать в области соседние клетки без разных анклавов.
Не могу не чего подходящего найти.
Вот пример, то есть есть разбиение, а как группировать вообще не могу понять. И найти, все статьи заканчиваются на построение диаграммы воroнова, а что дальше делать, не догоняю.

Answer 1

[alexalexes]

Интуитивно можно действовать так:
1. Капнуть разными красками в N начальных точках, выбранных случайно.
2. Выбрать цвет для покраски следующей точки (случайно или последовательно).
3. Найти точку выбранного цвета, с которой еще не работали (нужно выходить из цикла если отработали все точки).
3.1. Если непокрашенных соседей нет, то запоминаем, что работали с этой точкой, идем опять на шаг 3 (или на шаг 2, можно случайно выбирать).
4. Выбрать у этой точки непокрашенного соседа (случайным образом).
5. Покрасить соседа выбранным цветом.
6. Запомнить, что работали с точкой, выбранной на шаге 3. Перейти к шагу 2.
7. Кончились точки с которыми не работали - скорее всего пора выводить результат.

Answer 2

[Andrey Dugin]

Вот упрощённый вариант "на пальцах":

import cv2
import numpy as np
from PIL import Image
from itertools import product

N = 42
W = 200
H = 200

def distance(p1, p2):
    y1, x1 = p1
    y2, x2 = p2
    return ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5

canvas = np.zeros((H, W, 3), dtype=np.uint8)
centers = np.unravel_index(np.random.randint(0, W * H, N), canvas.shape[:2])
canvas[centers] = np.random.randint(0, 256, (N, 3))
centers = list(zip(*centers))

for x in range(0, W):
    for y in range(0, H):
        cy, cx = min(centers, key=lambda center: distance(center, (y, x)))
        canvas[y, x] = canvas[cy, cx]

Результат:

Для получения невыпуклых многоугольников можете случайным образом пообъединять смежные области. Например, берёте случайный центр, ищете ближайший к нему (или один из ближайших), закрашиваете области одним цветом, в списке центров вместо двух вставляете один. И так далее.