Генерация карты: связность по построению

Если ты умеешь генерировать связный мир через непересекающиеся множества и знаешь, почему «к ближайшему» не связывает, листай до «Теперь сам».

Как думаешь, будет ли путь

Генератор пещер ставит стены между соседними залами и каждую стену ломает с вероятностью 1/2. Можно ли гарантировать, что из любого зала дойдёшь до любого другого?

Ответь себе до чтения. Нельзя: зал может оказаться окружён четырьмя уцелевшими стенами, и с вероятностью 1/16 так и будет. Можно генерировать заново, пока не повезёт, и проверять обходом, - но это лотерея, и на большой карте выигрышный билет приходит всё реже. Есть путь прямее: ломать не случайные стены, а случайные стены между ещё не связанными залами. Тогда каждый пролом соединяет две разные группы, и к концу группа одна.

На что это похоже

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

Механизм: случайный Крускал

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

Отсюда две гарантии без проверки. Связность: Крускал добавляет рёбра, пока компонент больше одной, а стены есть между всеми соседями, значит, к концу компонента одна. Отсутствие циклов: ребро внутри одной компоненты не берётся. Остов на V вершинах имеет ровно V − 1 ребро - это и есть счётная проверка, которую печатает программа: на 60 залах 59 проломов.

«В одной ли компоненте» отвечают непересекающиеся множества из раздела 9 со сжатием пути - почти за константу. Порядок стен перемешивает тасование Фишера - Йейтса из раздела 20: каждая перестановка равновероятна.

Правило

Если игра обещает связность, строй её устройством генератора, а не проверкой после: случайный или минимальный остов через непересекающиеся множества связен по построению и содержит ровно V − 1 ребро. Жадное «каждый к ближайшему» связности не гарантирует.

Разбор: пещеры случайным Крускалом

Сетка 6 × 10 залов, 104 стены между соседями. Залы нумеруются числом r · C + c, проломы хранятся строками "a-b" - пары в множестве движок не держит.

import random

# Пещеры острова: сетка 6 × 10 залов, между соседними залами стены.
# Ломаем стены в случайном порядке, но только между залами, которые ещё
# не соединены, - тогда все залы связаны и обход нигде не ходит по кругу.
R = 6
C = 10
roditel = []
for v in range(R * C):
    roditel.append(v)

def koren(v):
    while roditel[v] != v:
        roditel[v] = roditel[roditel[v]]    # сжатие пути (раздел 9)
        v = roditel[v]
    return v

steny = []
for r in range(R):
    for c in range(C):
        v = r * C + c
        if c + 1 < C:
            steny.append([v, v + 1])
        if r + 1 < R:
            steny.append([v, v + C])
random.seed(14)
# перемешивание Фишера - Йейтса (раздел 20)
for i in range(len(steny) - 1, 0, -1):
    j = random.randint(0, i)
    steny[i], steny[j] = steny[j], steny[i]
prohody = set()
for s in steny:
    a = koren(s[0])
    b = koren(s[1])
    if a != b:
        roditel[a] = b
        prohody.add(str(s[0]) + "-" + str(s[1]))

# рисуем: "+" угол, "---" и "|" стены, пробелы - проломы
print("+" + "---+" * C)
for r in range(R):
    stroka = "|"
    niz = "+"
    for c in range(C):
        v = r * C + c
        stroka = stroka + "   "
        if c + 1 < C and str(v) + "-" + str(v + 1) in prohody:
            stroka = stroka + " "
        else:
            stroka = stroka + "|"
        if r + 1 < R and str(v) + "-" + str(v + C) in prohody:
            niz = niz + "   +"
        else:
            niz = niz + "---+"
    print(stroka)
    print(niz)
kornej = set()
for v in range(R * C):
    kornej.add(koren(v))
print("залов:", R * C, "| стен:", len(steny), "| сломано:", len(prohody),
      "| компонент:", len(kornej))

+---+---+---+---+---+---+---+---+---+---+
|                   |   |               |
+   +   +   +---+---+   +---+---+   +   +
|   |   |       |           |       |   |
+---+   +   +---+---+   +---+---+   +---+
|   |   |           |       |           |
+   +   +---+---+   +   +   +   +---+---+
|   |   |   |           |           |   |
+   +   +   +   +---+   +---+   +   +   +
|       |       |   |   |       |       |
+   +   +   +---+   +---+---+---+   +---+
|   |   |           |                   |
+---+---+---+---+---+---+---+---+---+---+
залов: 60 | стен: 104 | сломано: 59 | компонент: 1

Из 104 стен сломано 59 - ровно 60 − 1, компонента одна. Любой зал достижим из любого, и путь между двумя залами единственный: циклов нет. Это обещание доказано один раз, для любого семени генератора, и на каждой новой карте его не нужно проверять. Граница правила: лабиринт без циклов - это часто слишком жёстко для игры, в нём один путь и много тупиков. Если дизайнер хочет кольцевых ходов, после остова ломают ещё несколько случайных стен: связность от этого не пропадает, а циклы появляются.

Разбор: мосты между островами

Девять островов, мост строится по клеткам буквой Г - сначала по строке, потом по столбцу, - и его длина - сумма разностей координат. Нужно связать все острова, потратив меньше всего. Сравним три способа.

import random

random.seed(31)
ostrova = []                       # центры островов на карте 128 × 128
for i in range(9):
    ostrova.append([random.randint(0, 127), random.randint(0, 127)])

def dlina(a, b):
    # мост строится по клеткам: длина - сумма разностей координат
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

pary = []
for i in range(len(ostrova)):
    for j in range(i + 1, len(ostrova)):
        pary.append([dlina(ostrova[i], ostrova[j]), i, j])

def koren(roditel, v):
    while roditel[v] != v:
        v = roditel[v]
    return v

def postroit(mosty):
    # мосты по порядку; мост внутри уже связанной группы пропускаем.
    # Возвращает [длина, мостов, групп островов]
    roditel = []
    for v in range(len(ostrova)):
        roditel.append(v)
    summa = 0
    mostov = 0
    for p in mosty:
        a = koren(roditel, p[1])
        b = koren(roditel, p[2])
        if a != b:
            roditel[a] = b
            summa = summa + p[0]
            mostov = mostov + 1
    return [summa, mostov, len(ostrova) - mostov]

def k_blizhajshemu():
    # каждый остров - мост к ближайшему; часто остаются отдельные группы
    mosty = set()
    for i in range(len(ostrova)):
        luchshij = -1
        luchshaya = 0
        for j in range(len(ostrova)):
            d = dlina(ostrova[i], ostrova[j])
            if j != i and (luchshij == -1 or d < luchshaya):
                luchshij = j
                luchshaya = d
        mosty.add(str(min(i, luchshij)) + "-" + str(max(i, luchshij)))
    vybrany = []
    for p in pary:
        if str(p[1]) + "-" + str(p[2]) in mosty:
            vybrany.append(p)
    return postroit(vybrany)

def pervyj(p):
    return p[0]

sluchajno = []
for p in pary:
    sluchajno.append(p)
for i in range(len(sluchajno) - 1, 0, -1):
    j = random.randint(0, i)
    sluchajno[i], sluchajno[j] = sluchajno[j], sluchajno[i]
print("к ближайшему:   ", k_blizhajshemu(), "- [длина, мостов, групп]")
print("случайный остов:", postroit(sluchajno))
print("Крускал:        ", postroit(sorted(pary, key=pervyj)))

к ближайшему:    [232, 7, 2] - [длина, мостов, групп]
случайный остов: [654, 8, 1]
Крускал:         [311, 8, 1]

«Каждый остров к ближайшему» самый дешёвый - 232 клетки, - потому что недоделан: две пары взаимно ближайших островов построили один и тот же мост, мостов вышло 7 вместо 8, и архипелаг распался на две части. Ближайший у острова почти всегда в той же кучке, и две далёкие кучки так и не встречаются. Случайный остов связен, но длинен - 654. Крускал по возрастанию длины даёт минимальный остов, 311: дешевле связать девять островов нельзя, это доказано свойством разреза в разделе 11. Граница правила: минимальный остов связывает, но не даёт коротких путей - из одного конца архипелага в другой ходить по нему далеко. Если важен путь, к остову добавляют короткие мосты между далёкими по остову островами.

Что ломается без этого

Карта без пути. Генератор «ломает стены с вероятностью 1/2» - и то у одного, то у другого игрока шахта, до которой не дойти.

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

Жадность, которая кажется ответом. «Мост к ближайшему» дёшев и выглядит разумно на маленькой карте, а на большой оставляет отрезанные группы островов.

Зачем это в работе

Тот же приём - «строить так, чтобы свойство следовало из устройства» - работает везде, где проверка после дорога или поздно: генерация уровней, прокладка кабелей между офисами, сеть водопровода, топология кластера, где каждый узел должен быть доступен. Минимальный остов прокладывает кабель дешевле всего, а случайный остов генерирует лабиринты и тестовые деревья.

Теперь сам

1. Пещеры 20 × 20 залов. Сколько стен сломает случайный Крускал?
2. После остова дизайнер ломает ещё 10 случайных стен. Сколько независимых циклов появится и может ли карта стать несвязной?
3. У четырёх островов попарные длины мостов: 1-2: 5, 1-3: 9, 2-3: 4, 3-4: 6, 2-4: 8, 1-4: 7. Какой будет минимальный остов и его длина?