ВНИМАНИЕ!!! Здесь у меня представлен прототип, который мне кажется интересным сам по себе. По-хорошему, его следует ещё долго доводить до ума. Может, когда-нибудь, я вернусь к нему с новыми силами.

Карту я решил делать максимально логичной и физичной. То есть, реки должны течь строго сверху вниз, а дороги между городами - петлять между холмов и огибать пустыни, а не идти напрямик. План у меня в итоге получился примерно таким:

Карта высот
Расставляем родники и льём воду
Определяем типы местности и биомы
Расставляем поселения
Соединяем поселения дорогами
"Эпоха войн"

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

Карта высот

Здесь я решил взять двумерный шум Перлина. Немного поэкспериментировав, я пришёл к такому вот варианту функции:

 def perlin_noise_v3_simple(seed: int, map_size: tuple[int, int], frequencies: tuple):
    # Проверка корректности ввода
    for i in frequencies:
        if map_size[0] % i != 0:
            print('incorrect input')
            return
    for i in frequencies:
        if map_size[1] % i != 0:
            print('incorrect input')
            return

    # Создаём итоговую матрицу и заполняем её нулями
    map_heights = [[0.0 for _ in range(map_size[1] + 1)] for _ in range(map_size[0] + 1)]

    random.seed(seed)
    for frequency in frequencies:
        print(f'frequency: {frequency}')
        # Создаём матрицы (сетку, значения и вектора)
        # Карта нарезается на прямоугольники по main_points
        # В каждой вершине имеем свой вектор. Нам важен его коэффициент наклона k (z = k*x + b) по x и y
        x_main_points_num = map_size[0] // frequency + 1
        y_main_points_num = map_size[1] // frequency + 1

        vectors = [[[random.random() - 0.5, random.random() - 0.5] for _ in range(y_main_points_num)] for _ in
                   range(x_main_points_num)]

        # Заполняем матрицу значений
        for x_point in range(x_main_points_num - 1):
            for y_point in range(y_main_points_num - 1):
                for place_x in range(frequency):
                    for place_y in range(frequency):
                        z_result = 0
                        # Каждую точку нашего прямоугольника высчитываем исходя из 4-х угловых точек прямоугольника
                        # Первое слагаемое - вклад коэффициента по х, второе - по y
                        zx_0_0 = vectors[x_point][y_point][0] * place_x / frequency
                        zy_0_0 = vectors[x_point][y_point][1] * place_y / frequency
                        zx_0_1 = vectors[x_point][y_point + 1][0] * place_x / frequency
                        zy_0_1 = (-1) * vectors[x_point][y_point + 1][1] * (frequency - place_y) / frequency
                        zx_1_0 = (-1) * vectors[x_point + 1][y_point][0] * (frequency - place_x) / frequency
                        zy_1_0 = vectors[x_point + 1][y_point][1] * place_y / frequency
                        zx_1_1 = (-1) * vectors[x_point + 1][y_point + 1][0] * (frequency - place_x) / frequency
                        zy_1_1 = (-1) * vectors[x_point + 1][y_point + 1][1] * (frequency - place_y) / frequency

                        z_0_0 = zx_0_0 + zy_0_0
                        z_0_1 = zx_0_1 + zy_0_1
                        z_1_0 = zx_1_0 + zy_1_0
                        z_1_1 = zx_1_1 + zy_1_1

                        z_result += z_0_0 * (frequency - place_x) * (frequency - place_y) / frequency ** 2
                        z_result += z_0_1 * (frequency - place_x) * place_y / frequency ** 2
                        z_result += z_1_0 * place_x * (frequency - place_y) / frequency ** 2
                        z_result += z_1_1 * place_x * place_y / frequency ** 2

                        map_heights[x_point * frequency + place_x][y_point * frequency + place_y] += z_result

    return map_heights

Небольшое отступление

Сейчас на карте высот полный хаос от больших минусов до больших плюсов. Поэтому надо её "сжать", то есть, пропорционально привести все значения к диапазону от 0 до 1. В этой функции ничего интересного, но, если кто-то захочет на неё посмотреть, то normalize_map.

Но мне показалось нехорошим, что континент резко начинается и так же резко заканчивается, поэтому я наложил на шум простенький фильтр, который придаёт континенту форму эллипса, сглаживая высоты от центра к берегам, а не обрезая их

 def make_filter_ellipsis_v2(map_heights):
    arr_shape = (len(map_heights), len(map_heights[0]))
    center = (arr_shape[0] / 2, arr_shape[1] / 2)

    x_rad = arr_shape[0] / 2.05
    y_rad = arr_shape[1] / 2.05

    map_ellipsis_filter = [[0.0 for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            ellips_value = ((x_chor - center[0]) / x_rad) ** 2 + ((y_chor - center[1]) / y_rad) ** 2
            if ellips_value <= 1:
                map_ellipsis_filter[x_chor][y_chor] = 1 - ellips_value
            else:
                map_ellipsis_filter[x_chor][y_chor] = 0

    return map_ellipsis_filter

Здесь мы получили только сам эллипс. Карту с 0 по краям и чиселками в центре. Теперь нам надо перемножить две карты: карту высот (от 0 до 1) и только что полученный эллипс. Умножать будем, разумеется, не по правилам матричного умножения, а просто значение на значение. Это функция make_sea_around, и её я тоже приводить не буду в силу её крайней простоты.

В итоге, после первого этапа карта мира выглядела так:

Так выглядит континент. Размер карты 2000*1500

Льём воду

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

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

Здесь я для оптимизации вёл "реестр воды", удаляя из него те частички, которые никуда не передвинулись. Так как, если вода один раз никуда не подвинулась, то она не подвинется вообще, а значит, бессмысленно тратить время на её обсчёт, гораздо лучше запомнить, что она "где-то там лежит"

def put_springs(seed, map_heights, spring_prob):
    random.seed(seed)
    arr_shape = (len(map_heights), len(map_heights[0]))

    springs_list = []
    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_heights[x_chor][y_chor] != 0:
                if random.random() < spring_prob:
                    springs_list.append((x_chor, y_chor, map_heights[x_chor][y_chor]))

    return springs_list


def make_all_water_v2(map_heights, map_filter, springs_list, point_size=1 / 2000, turns=1000):
    water_list = []
    new_grid = map_heights.copy()
    for turn in range(turns):
        print(f'water_turn: {turn + 1}')
        new_water = []
        for point in water_list:
            if point[3]:
                new_water.append(point)
                continue
            arr = [
                (point[0] + 1, point[1]),
                (point[0] + 1, point[1] + 1),
                (point[0], point[1] + 1),
                (point[0] - 1, point[1] + 1),
                (point[0] - 1, point[1]),
                (point[0] - 1, point[1] - 1),
                (point[0], point[1] - 1),
                (point[0] + 1, point[1] - 1), ]
            min_height = point[2]
            new_index = -1
            for i in range(8):
                height = new_grid[arr[i][0]][arr[i][1]]
                if height < min_height:
                    min_height = height
                    new_index = i
            if map_filter[arr[new_index][0]][arr[new_index][1]] > 0:
                if new_index >= 0:
                    new_grid[point[0]][point[1]] -= point_size
                    new_water.append((arr[new_index][0], arr[new_index][1], min_height,False))
                    new_grid[arr[new_index][0]][arr[new_index][1]] += point_size
                else:
                    new_water.append((point[0], point[1], min_height, True))

        for point in springs_list:
            arr = [(point[0] + 1, point[1]),
                   (point[0] + 1, point[1] + 1),
                   (point[0], point[1] + 1),
                   (point[0] - 1, point[1] + 1),
                   (point[0] - 1, point[1]),
                   (point[0] - 1, point[1] - 1),
                   (point[0], point[1] - 1),
                   (point[0] + 1, point[1] - 1),
                   ]
            min_height = point[2]
            new_index = -1
            for i in range(8):
                height = new_grid[arr[i][0]][arr[i][1]]
                if height < min_height:
                    min_height = height
                    new_index = i
            if new_index >= 0 and map_filter[arr[new_index][0]][arr[new_index][1]] > 0:
                new_water.append((arr[new_index][0], arr[new_index][1], min_height, False))
                new_grid[arr[new_index][0]][arr[new_index][1]] = min_height + point_size

        water_list = new_water.copy()

    return water_list


# Принимает "рабочую версию" water_list с лишними данными и преобразует её в выходную
def clean_water(water_list):
    result_water = set()
    for point in water_list:
        result_water.add((point[0], point[1]))
    return list(result_water)


# Дополняет "чистую" версию water_list, добавляя в неё воду вокруг континента
def add_sea(water_list, map_filter):
    arr_shape = (len(map_filter), len(map_filter[1]))
    map_water = [[False for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_filter[x_chor][y_chor] == 0:
                map_water[x_chor][y_chor] = True
            else:
                map_water[x_chor][y_chor] = False
    for point in water_list:
        map_water[point[0]][point[1]] = True
    return map_water

Каждая частичка воды на старте имеет три параметра, три координаты. Потом мы добавляем к ней четвёртую - сдвинулась ли она куда-нибудь. Если не сдвинулась, то мы временно делаем её частью карты высот и "забываем" про неё. В функции clean_water мы избавлялись от лишних данных, а потом добавляли мировой океан.

Во время тестирования я пробовал две стратегии:

Лить воду сразу из всех родников
Лить воду сначала из одного родника, потом из другого, потом из третьего

Как нетрудно догадаться, результаты не отличались, поэтому я выбрал тот, который показал себя более эффективным по времени. Причём, если брать классическую оценку через О-большое, то эффективность у них одинаковая, а разница во времени происходила из-за мелких операций (как быстрая сортировка выигрывает у сортировки слиянием, хотя они обе n*log(n)). Однако основная оптимизация (с "забыванием" частичек воды) была описана выше.

В итоге, карта выглядит так:

Да, на картинке виден контур эллипса, но он пропадёт во время сглаживания на следующих этапах создания карты.

В целом, из всех оптимизаций я стремился к оптимизации именно по времени, хотя, возможно, где-то что-то не заметил

Типы местности и биомы

Сначала надо посмотреть, что у нас вообще с типами местности. Это "равнины", "холмы", "горы" и "вода". Собственно, там всё просто. Если клетка с водой, то пишем "вода". Если в небольшом радиусе от клетки нет большой разницы между минимальным и максимальным значением высот, то это "равнины", если разница средняя, то "холмы", а иначе - "горы"

# По перепаду высот в радиусе определяем тип местности (горы, холмы, равнины) + вода
def set_ground_type(map_heights, map_water, height_radius=3, heights_differences=(0.02, 0.05)):
    arr_shape = (len(map_heights), len(map_heights[0]))
    map_ground = [['' for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_water[x_chor][y_chor]:
                map_ground[x_chor][y_chor] = 'WATER'
            else:
                min_val = 1
                max_val = 0
                for x_shift in range(height_radius * 2 + 1):
                    for y_shift in range(height_radius * 2 + 1):
                        x = x_chor - height_radius + x_shift
                        y = y_chor - height_radius + y_shift
                        if (0 <= x < arr_shape[0]) and (0 <= y < arr_shape[1]):
                            act_val = map_heights[x][y]
                            if act_val < min_val:
                                min_val = act_val
                            if act_val > max_val:
                                max_val = act_val
                diff = max_val - min_val
                if diff < heights_differences[0]:
                    map_ground[x_chor][y_chor] = 'FLAT'
                elif diff < heights_differences[1]:
                    map_ground[x_chor][y_chor] = 'HILLS'
                else:
                    map_ground[x_chor][y_chor] = 'MOUNTAINS'
    return map_ground

После мы отдельно задаём растительность. Там тоже всё просто: смотрим на количество воды вокруг клетки и на основе этого определяем тип.

# Создаём флору по количеству воды вокруг
def set_flora_type(map_water, radius=20, need_water=(1, 60)):
    arr_shape = (len(map_water), len(map_water[0]))
    map_flora = [['' for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    # Блок влияния
    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_water[x_chor][y_chor]:
                map_flora[x_chor][y_chor] = 'WATER'
            else:
                water_num = 0

                for x_shift in range(radius * 2 + 1):
                    for y_shift in range(radius * 2 + 1):
                        x = x_chor - radius + x_shift
                        y = y_chor - radius + y_shift
                        if (0 <= x < arr_shape[0]) and (0 <= y < arr_shape[1]):
                            if map_water[x][y]:
                                water_num += 1

                if water_num < need_water[0]:
                    map_flora[x_chor][y_chor] = 'DESERT'
                elif water_num < need_water[1]:
                    map_flora[x_chor][y_chor] = 'GRASS'
                else:
                    map_flora[x_chor][y_chor] = 'FOREST'

    return map_flora

Далее мы соединяем высоты и флору в один сложный тип. Саму функцию приводить не буду, покажу лишь словарь, как определялись итоговые типы:

ground_flora_types = {
    ('WATER', 'WATER'): 'WATER',
    ('WATER', 'FOREST'): 'SWAMP',
    ('WATER', 'GRASS'): 'SWAMP',
    ('WATER', 'DESERT'): 'ERROR',
    ('FLAT', 'WATER'): 'SWAMP',
    ('FLAT', 'FOREST'): 'FLAT-FOREST',
    ('FLAT', 'GRASS'): 'FLAT-GRASS',
    ('FLAT', 'DESERT'): 'SANDS',
    ('HILLS', 'WATER'): 'SWAMP',
    ('HILLS', 'FOREST'): 'HILLS-FOREST',
    ('HILLS', 'GRASS'): 'HILLS-GRASS',
    ('HILLS', 'DESERT'): 'STONES',
    ('MOUNTAINS', 'WATER'): 'SWAMP',
    ('MOUNTAINS', 'FOREST'): 'MOUNTAINS-FOREST',
    ('MOUNTAINS', 'GRASS'): 'MOUNTAINS-GRASS',
    ('MOUNTAINS', 'DESERT'): 'STONES',
}

Теперь происходит сглаживание. Немного странно, когда у нас посреди поля вдруг торчит одинокая гора. Тут всё сделано по принципу "влияния". Смотрим на местность в определённом радиусе от клетки и вписываем в клетку тот тип местности, которого вокруг больше.

def clean_global_type(map_global_type_base, influence=4):
    arr_shape = (len(map_global_type_base), len(map_global_type_base[0]))
    map_global_type_clean = [['' for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            types_nums = {
                'WATER': 0,
                'SWAMP': 0,
                'SANDS': 0,
                'STONES': 0,
                'FLAT-FOREST': 0,
                'FLAT-GRASS': 0,
                'HILLS-FOREST': 0,
                'HILLS-GRASS': 0,
                'MOUNTAINS-FOREST': 0,
                'MOUNTAINS-GRASS': 0,
            }

            for x_shift in range(influence * 2 + 1):
                for y_shift in range(influence * 2 + 1):
                    x = x_chor - influence + x_shift
                    y = y_chor - influence + y_shift
                    if (0 <= x < arr_shape[0]) and (0 <= y < arr_shape[1]):
                        types_nums[map_global_type_base[x][y]] += 1
            new_type = max(types_nums, key=types_nums.get)
            map_global_type_clean[x_chor][y_chor] = new_type

    return map_global_type_clean

Пока что у нас есть только типы местности. Надо объединить их в биомы. При этом важно, что две пустыни, разделённые чем-либо уже, скорее всего, будут разными. Поэтому надо объединять именно клетки, имеющие общую сторону.

Здесь я разбил карту на небольшие кусочки, в каждом из них определил биомы, а потом соединил кусочки и объединил биомы соседнего типа. Делить карту мне пришлось, так как любой обход такого огромного графа посылал меня куда подальше, не стесняясь в выражениях. А по чуть-чуть всё отрабатывало довольно бодренько

Собственно, здесь я приведу всего три функции из общего набора. Это обход в ширину, которым я делил кусочки на биомы, сама функция разделения кусочков и функция объединения двух биомов в один:

# Берём клетку и поиском в ширину ищем ей подобные
def width_bypass(mini_map_global_clean, start_cell):
    arr_shape = (len(mini_map_global_clean), len(mini_map_global_clean[0]))
    biom_cells = [start_cell]
    cell_type = mini_map_global_clean[start_cell[0]][start_cell[1]]

    cell_num = 0
    while True:
        cell = biom_cells[cell_num]
        if cell[0] != 0:
            if mini_map_global_clean[cell[0] - 1][cell[1]] == cell_type:
                if (cell[0] - 1, cell[1]) not in biom_cells:
                    biom_cells.append((cell[0] - 1, cell[1]))
        if cell[1] != 0:
            if mini_map_global_clean[cell[0]][cell[1] - 1] == cell_type:
                if (cell[0], cell[1] - 1) not in biom_cells:
                    biom_cells.append((cell[0], cell[1] - 1))
        if cell[0] != arr_shape[0] - 1:
            if mini_map_global_clean[cell[0] + 1][cell[1]] == cell_type:
                if (cell[0] + 1, cell[1]) not in biom_cells:
                    biom_cells.append((cell[0] + 1, cell[1]))
        if cell[1] != arr_shape[1] - 1:
            if mini_map_global_clean[cell[0]][cell[1] + 1] == cell_type:
                if (cell[0], cell[1] + 1) not in biom_cells:
                    biom_cells.append((cell[0], cell[1] + 1))
        cell_num += 1
        if cell_num % 1000 == 999:
            print(cell_num + 1)
        if cell_num == len(biom_cells):
            print(cell_num)
            break

    return biom_cells

# Выделяем биомы на карте
def divide_map_to_bioms(mini_map_global_clean, start_reg_num):
    arr_shape = (len(mini_map_global_clean), len(mini_map_global_clean[0]))
    map_bioms = [[0 for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    used_cells = []
    bioms = {}
    reg_num = start_reg_num

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if (x_chor, y_chor) not in used_cells:
                print(f'reg_num: {reg_num}')
                biom = width_bypass(mini_map_global_clean, (x_chor, y_chor))
                used_cells += biom
                bioms[reg_num] = biom
                reg_num += 1

    for key in bioms.keys():
        for cell in bioms[key]:
            map_bioms[cell[0]][cell[1]] = key

    return map_bioms, len(bioms)

# Сливаем биомы (из-за разделения карты могли возникнуть два разных биома одного типа рядом)
def merge_bioms(map_global_bioms, map_global_type_clean):
    arr_shape = (len(map_global_type_clean), len(map_global_type_clean[0]))

    for x_chor in range(arr_shape[0] - 1):
        for y_chor in range(arr_shape[1] - 1):
            if map_global_type_clean[x_chor][y_chor] == map_global_type_clean[x_chor + 1][y_chor] and \
                    map_global_bioms[x_chor][y_chor] != map_global_bioms[x_chor + 1][y_chor]:
                start_num = map_global_bioms[x_chor][y_chor]
                finish_num = map_global_bioms[x_chor + 1][y_chor]
                print(f'{finish_num} to {start_num}')
                map_global_bioms = change_biom_num(map_global_bioms, start_num, finish_num)
                print('changed')
            if map_global_type_clean[x_chor][y_chor] == map_global_type_clean[x_chor][y_chor + 1] and \
                    map_global_bioms[x_chor][y_chor] != map_global_bioms[x_chor][y_chor + 1]:
                start_num = map_global_bioms[x_chor][y_chor]
                finish_num = map_global_bioms[x_chor][y_chor + 1]
                print(f'{finish_num} to {start_num}')
                map_global_bioms = change_biom_num(map_global_bioms, start_num, finish_num)
                print('changed')

    return map_global_bioms

В итоге имеем такую вот прелесть:

Прелесть тут

Поселения

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

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

# Вариант 2 - По всей карте поселения, между ними дороги, по графу дорог смотрим и формируем дистрикты
def find_alive_cells_v2(map_global_type_clean, dead_bioms):
    arr_shape = (len(map_global_type_clean), len(map_global_type_clean[0]))
    map_settlements = [['' for _ in range(arr_shape[1])] for _ in range(arr_shape[0])]

    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_global_type_clean[x_chor][y_chor] not in dead_bioms:
                map_settlements[x_chor][y_chor] = 'no'
            else:
                map_settlements[x_chor][y_chor] = 'dead'
    print('alive_found')

    return map_settlements


# Радиус измеряется в расстоянии, а не в клетках
def find_area(start_cell, map_settlements, radius):
    area = [start_cell]
    distances = {}
    distances[start_cell] = 0
    parent_cells = {}

    cell_num = 0
    while True:
        cell = area[cell_num]
        if distances[cell] >= radius:
            break

        right_steps = [(cell[0] + 1, cell[1]), (cell[0], cell[1]+1), (cell[0]-1, cell[1]), (cell[0], cell[1]-1)]
        diag_steps = [(cell[0] + 1, cell[1] + 1), (cell[0] - 1, cell[1] + 1), (cell[0] - 1, cell[1] - 1),
                      (cell[0] + 1, cell[1] - 1)]

        for new_cell in right_steps:
            # print(new_cell)
            if map_settlements[new_cell[0]][new_cell[1]] != 'dead' and new_cell not in area:
                new_distance = distances[cell] + 10
                distances[new_cell] = new_distance
                parent_cells[new_cell] = cell

                cell_putted = False
                for sorted_cell_num in range(len(area)):
                    sorted_cell = area[sorted_cell_num]
                    if new_distance < distances[sorted_cell]:
                        area.insert(sorted_cell_num, new_cell)
                        cell_putted = True
                        break
                if not cell_putted:
                    area.append(new_cell)

        for new_cell in diag_steps:
            # print(new_cell)
            if map_settlements[new_cell[0]][new_cell[1]] != 'dead' and new_cell not in area:
                new_distance = distances[cell] + 14
                distances[new_cell] = new_distance
                parent_cells[new_cell] = cell

                cell_putted = False
                for sorted_cell_num in range(len(area)):
                    sorted_cell = area[sorted_cell_num]
                    if new_distance < distances[sorted_cell]:
                        area.insert(sorted_cell_num, new_cell)
                        cell_putted = True
                        break
                if not cell_putted:
                    area.append(new_cell)

        cell_num += 1
        if cell_num == len(area):
            break

    return area


# Забиваем на воду (роем колодцы) и просто расселяемся по всей карте
def set_settlements_v2(seed, map_settlements, min_settl_area):
    random.seed(seed)

    alive_cells = []
    arr_shape = (len(map_settlements), len(map_settlements[0]))
    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_settlements[x_chor][y_chor] != 'dead':
                alive_cells.append((x_chor, y_chor))
    save_district('TEST_ALIVE.txt', alive_cells)
    print('alive_configured')

    settlements_num = 0
    while len(alive_cells) > 0:
        settlements_num += 1
        settl_cell = random.choice(alive_cells)
        print(settl_cell)
        area = find_area(settl_cell, map_settlements, min_settl_area)
        print(area)
        print('area found')
        for cell in area:
            map_settlements[cell[0]][cell[1]] = 'area'
            alive_cells.pop(alive_cells.index(cell))
        map_settlements[settl_cell[0]][settl_cell[1]] = 'true'
        print(f'settlements: {settlements_num}/{len(alive_cells)}')
        print('------------------------------')

    return map_settlements

Расстояние здесь измерялось не в клетках, а непосредственно в "единицах расстояния". Во-первых, потому что так логичнее, а во-вторых, потому что могу себе это позволить

Дороги

Когда все поселения расставлены, надо проложить между ними дороги. При этом, есть определённая максимальная длина дороги между поселениями. Своего рода, дневной переход. А далее запускаем взвешенный обход в ширину. Ой, его сначала надо написать. Собственно, вот:

# Обход в ширину с разной длиной шага (радиус в расстоянии, а не в клетках)
def put_roads_from_settlement(map_settlements, start_cell, finish_cells, radius):
    # Часть 1, заполняем карту региона по удаленности от стартовой клетки
    distances = {}
    distances[start_cell] = 0
    parent_cells = {}
    queue = [start_cell]

    cell_num = 0
    while True:
        # print(distances)
        cell = queue[cell_num]
        # print(cell)
        if distances[cell] >= radius:
            break

        right_steps = [(cell[0] + 1, cell[1]), (cell[0], cell[1] + 1), (cell[0] - 1, cell[1]), (cell[0], cell[1] - 1)]
        diag_steps = [(cell[0] + 1, cell[1] + 1), (cell[0] - 1, cell[1] + 1), (cell[0] - 1, cell[1] - 1),
                      (cell[0] + 1, cell[1] - 1)]

        for new_cell in right_steps:
            # print(new_cell)
            if map_settlements[new_cell[0]][new_cell[1]] != 'dead' and new_cell not in queue:
                new_distance = distances[cell] + 10
                distances[new_cell] = new_distance
                parent_cells[new_cell] = cell

                cell_putted = False
                for sorted_cell_num in range(len(queue)):
                    sorted_cell = queue[sorted_cell_num]
                    if new_distance < distances[sorted_cell]:
                        queue.insert(sorted_cell_num, new_cell)
                        cell_putted = True
                        break
                if not cell_putted:
                    queue.append(new_cell)

        for new_cell in diag_steps:
            # print(new_cell)
            if map_settlements[new_cell[0]][new_cell[1]] != 'dead' and new_cell not in queue:
                new_distance = distances[cell] + 14
                distances[new_cell] = new_distance
                parent_cells[new_cell] = cell

                cell_putted = False
                for sorted_cell_num in range(len(queue)):
                    sorted_cell = queue[sorted_cell_num]
                    if new_distance < distances[sorted_cell]:
                        queue.insert(sorted_cell_num, new_cell)
                        cell_putted = True
                        break
                if not cell_putted:
                    queue.append(new_cell)

        cell_num += 1
        if cell_num == len(queue):
            break

    # Часть 2, возвращаемся от финишной клетки к стартовой, составляем дорогу
    roads = []
    # print(queue)
    # print(distances)
    for finish_cell in finish_cells:
        if finish_cell in queue:
            road = []
            cell = finish_cell
            while cell != start_cell:
                road.append(cell)
                try:
                    cell = parent_cells[cell]
                except:
                    print(f'KeyError!!! {cell}\n{parent_cells}')
                    break
            road.append(start_cell)
            roads.append(road)
            # print(road)

    return roads


# От каждого поселения к каждому прокладываем дороги
def put_roads(map_settlements, max_road_length):
    arr_shape = (len(map_settlements), len(map_settlements[0]))

    settlements = []
    for x_chor in range(arr_shape[0]):
        for y_chor in range(arr_shape[1]):
            if map_settlements[x_chor][y_chor] == 'true':
                settlements.append((x_chor, y_chor))

    all_roads = []
    for settl1_num in range(len(settlements) - 1):
        set1 = settlements[settl1_num]
        neighbours = []
        for settl2_num in range(settl1_num + 1, len(settlements)):
            set2 = settlements[settl2_num]
            if (set1[0] - set2[0]) ** 2 + (set1[1] - set2[1]) ** 2 <= (max_road_length // 8) ** 2:
                if set1 != set2:
                    neighbours.append(set2)
        roads = put_roads_from_settlement(map_settlements, set1, neighbours, max_road_length)
        all_roads += roads
    return all_roads

Мне кажется, это что-то среднее между обходом в ширину и алгоритмом Дейкстры.

В итоге имеем такую вот карту поселений и дорог:

Всё прошло успешно, дороги огибают воду, пустыни и горы. А что случилось с мелкими речушками? Так ручей не особо сложно перейти. А на крайний случай можно построить мост.

"Эпоха войн"

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

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

def kingdoms_wars(seed, roads_lengths: dict, neighbours_nums, max_kingdoms=100, max_turns=10000):
    random.seed(seed)

    kingdoms = {}
    settlements = list(roads_lengths.keys())
    settl_status = {}

    # Создаём первичные королевства
    for key_num in range(len(settlements)):
        kingdoms[key_num] = {
            'power': neighbours_nums[settlements[key_num]] ** 2,
            'settlements': [key_num],
            'neighbour_settlements': [],
        }
        settl_status[key_num] = {
            'chors': settlements[key_num],
            'owner': key_num,
            'neighbour_kingdoms': [],
            'neighbour_settlements': [],
            'incoming_influence': {},
        }

    # Заполняем соседей
    for key in kingdoms.keys():
        capital = kingdoms[key]['settlements'][0]
        neighs = list(roads_lengths[settlements[capital]].keys())
        for neighbour in neighs:
            kingdoms[key]['neighbour_settlements'].append(settlements.index(neighbour))
            settl_status[key]['neighbour_kingdoms'].append(settlements.index(neighbour))
            settl_status[key]['neighbour_settlements'].append(settlements.index(neighbour))

    for turn in range(max_turns):
        # Заполняем входящее влияние
        for settl_num in range(len(settlements)):
            incoming = {}
            for neigh_num in settl_status[settl_num]['neighbour_kingdoms']:
                incoming[neigh_num] = kingdoms[neigh_num]['power']
            settl_status[settl_num]['incoming_influence'] = incoming

        # Завоёвываем соседей
        for kingdom_num in kingdoms.keys():
            power = kingdoms[kingdom_num]['power']
            if len(kingdoms[kingdom_num]['settlements']) > 0:
                capture_chance = 10 / len(kingdoms[kingdom_num]['settlements'])
                for neigh_num in kingdoms[kingdom_num]['neighbour_settlements']:
                    enemy_owner = settl_status[neigh_num]['owner']
                    other_influence = kingdoms[enemy_owner]['power']

                    for inf in settl_status[neigh_num]['incoming_influence'].values():
                        other_influence += inf
                    other_influence -= power
                    if power > other_influence and random.random() < capture_chance:
                        settl_status[neigh_num]['owner'] = kingdom_num

        # Пересчитываем поселения в королевстве
        for kingdom_num in kingdoms.keys():
            kingdoms[kingdom_num]['settlements'] = []
        for settl_num in range(len(settlements)):
            owner = settl_status[settl_num]['owner']
            kingdoms[owner]['settlements'].append(settl_num)

        # Пересчитываем соседние поселения
        for kingdom_num in kingdoms.keys():
            neighs = []
            for settl_num in kingdoms[kingdom_num]['settlements']:
                for neigh in settl_status[settl_num]['neighbour_settlements']:
                    if neigh not in kingdoms[kingdom_num]['settlements']:
                        neighs.append(neigh)
            kingdoms[kingdom_num]['neighbour_settlements'] = list(set(neighs))

        # Пересчитываем силу королевств и определяем количество живых
        alive = 0
        for kingdom_num in kingdoms.keys():
            power = 0
            for settl_num in kingdoms[kingdom_num]['settlements']:
                power += len(settl_status[settl_num]['neighbour_settlements']) ** 2
            kingdoms[kingdom_num]['power'] = power
            if power > 0:
                alive += 1
        print(f'turn: {turn}, alive: {alive}')

        # Прерываем цикл по достижению требуемого количества королевств
        if alive <= max_kingdoms:
            break

    kingdoms = drop_dead_kingdoms(kingdoms)

    return kingdoms, settl_status

Потом ещё немного раскрашиваем всё, и в итоге имеем вот такое вот "лоскутное одеяло":

Если дать генерации больше шагов, то количество хаоса уменьшится. Как и количество независимых королевств. А ещё, ярко выделятся несколько крупных империй, захвативших огромные куски континента.

Сам проект, хоть и не был доведён до конца, получился довольно интересным. Если кто-то хочет взглянуть на его полную версию, то https://github.com/Konstantin-Lis/fantasy_maps_generator

Я знаю

Я не веду гитхаб. Да, это так. Надо завести привычку пользоваться контролем версий
Много странных прибавок к названиям функций и файлов (v2, v3). Да, это тоже так. Код дважды переписывался на основе предыдущих наработок. Функции часто тоже имели несколько версий в зависимости от своей сложности. По-хорошему, надо прибраться
Основной цикл загадит рабочую директорию. Это тоже так. Надо прибраться

Надеюсь, вам было интересно :-)

Как Питолис мир создавал