Галактиката от семе в Python

Проблем

Нова галактика всеки път

В тази поредица правим втора игра, много различна от Арканум: Epic Cosmos, космическа стратегия по ходове, пак цяла и пак в конзолата. Не се върти един герой по карта. Управляваш империя: имаш една система с една столица, малко ресурси и първи флот. Колонизираш планети, проучваш технологии, строиш флот и се редиш с още два или три съперника, които се управляват сами. Победата е завладяване на галактиката, проучване на Звездната врата или икономика, а ако никой не успее, след 150 хода печели най-силният.

Игра като тази има смисъл само ако всяка партия е в нова галактика: системите са другаде, пътищата минават другаде, планетите са богати на друго. Но има и обратното искане. Грешка, която играчът съобщи, трябва да се повтаря точно. Записът не бива да тежи цяла галактика. А проверката на сайта пуска играта на четири езика и сравнява изходите байт по байт.

Двете искания се събират в едно число: семето. Галактиката не се пази, а се прави пак от семето, всеки път същата. Този урок е за това как се прави. Започва с играта, а после строи нейната първа част.

Ход 1/150  Земна империя (A)                            точки 20
M70+8 G60+4 C20+3 U5+1  наука +3
Нищо не се проучава (r номер). Натрупана наука: 0
Земна империя започва от системата Elara: столица,
корабостроителница, лаборатория и първият ти флот.
Колонизирай планети, проучвай технологии, строй флот. В битка
I бие B, B бие F, F бие I.
Победа: завладей всички, проучи Звездната врата или произведи
9800. След 150 хода печели най-силният. Напиши help.

Enter или map: към картата   help: команди

Пробвай

Играй

Това е истинската игра: JavaScript версията, пусната в браузъра. Тук няма клавиши. Пишеш команда на реда под екрана и натискаш Enter. Започни с help, после map, после sys 1: ще видиш картата, системата, в която си, и планетите ѝ.

Epic Cosmos: империята

Една система, първи флот и цяла галактика. Съперниците вече мислят.

Пиши командите на реда отдолу и натисни Enter (help показва всички; празен ред е map). Записите остават в този браузър.

Най-важните команди (help показва всичките, празен ред е map):

map показва картата на галактиката: [ 1 ] са системите, точките са пътищата, буквите са империите.
sys N показва система N: планетите, какво добиват и кои флоти са там.
emp показва империите, tech дървото на технологиите, fleets флотите.
col P колонизира планета P, b mine P строи мина на нея, r X проучва технология.
ship T N P строи N кораба от вид T, go A B праща флота от система A към B по пътищата.
end завършва хода, wait N пропуска до N хода, save 1 и load 1 са за запис.

Победата е една от три: завладяване (всички империи освен твоята падат), наука (проучваш Звездната врата, последната технология) или икономика (произвеждаш общо 9800). Играта е най-много 150 хода.

По-точно, за любопитните

Играта в браузъра е същият файл, който ще видиш в уроците и ще пуснеш на компютъра. Само блокът, който в Node чете аргументите и пише записите във файлове, е заменен: тук входът идва от полето под екрана, а записите са в паметта на браузъра (localStorage). Всяка нова игра на страницата е със семе от часовника, затова галактиката ѝ е различна от тази в картите по-долу (те са със семе 2026, както е по подразбиране в терминала). Записът пази семето.

Идеята

Какво има в нея

Галактика от 12 до 20 системи и 3 или 4 империи. Всяка система има една до три планети. Ресурсите са четири: метал (M), газ (G), кристал (C) и уран (U).
Планети и сгради. Колонизираш планета, строиш мина (повече ресурси), лаборатория (наука), корабостроителница (кораби) и крепост (защита).
Дърво на технологиите: тринайсет технологии с предпоставки, от „Дълбок добив“ до „Звездна врата“. Не можеш да проучиш нещо, преди да си проучил това, от което зависи.
Флотите. Четири вида кораби: прехващач, бомбардировач, фрегата и дредноут. В бой прехващачът бие бомбардировача, бомбардировачът бие фрегатата, а фрегатата бие прехващача (камък, ножица, хартия). Флотите се движат по пътищата.
Битка, в която ходовете се решават едновременно. Всички заповеди на хода се изпълняват наведнъж, не една след друга.
Съперници с изкуствен интелект и характер. Воин (напада), Строител (разширява се и строи) и Учен (търси науката). Всеки оценява какво му носи най-много полза този ход.
Дипломация: мир и война, с минимално време на мир. Случайни събития: метеорит, пирати, бунт, откритие и още.
Победа по три начина, запис в три слота и симулация на хиляди игри само на изкуствен интелект, с която се настройва балансът.

Цялото минаване, с което се проверява играта, е 192 команди и 5175 реда изход: от първия ход до края.

Идеята

Картата на кода

Играта е един файл от около 3900 реда на всеки език. Вътре е разделена на части (региони), а всяка част е в един от шест слоя:

Слой	Части	Редове
Данни и текстове	`io-text` `text` `data` `data-load`	1023
Вход, изход, рисуване	`random` `buffer` `terminal` `map-draw`	230
Екраните и командите	`screen` `screen-stack` `screens` `commands`	584
Светът: галактиката и технологиите	`world` `graph` `galaxy-gen` `tech-tree` `topo` `event-bus`	474
Империите: флоти, икономика, съперници	`fleets` `battle` `economy` `diplomacy` `events` `ai-rivals` `turn` `victory`	1194
Запис, симулация, пускане	`save` `load` `simulate` `main` `node`	395

Числата са от JavaScript версията и се смятат при строенето на сайта. Част от тях вече знаеш от Арканум: генераторът random, буферът и екраните, стекът от екрани и шината от събития са същите идеи. Новото е в слоевете „Светът“ и „Империите“. Този урок е за random, world, graph и galaxy-gen.

Идеята

Един код, четири езика, един изход

Играта е написана четири пъти: на Java, C#, Python и JavaScript, част по част и със същите имена. Проверката на сайта я пуска на четирите езика със записаните 192 команди (на български, английски, немски и испански) и изисква байт по байт един и същ изход. Пуска и симулацията на баланса. Ако една версия хвърли зара другояче, галактиката е друга и проверката пада.

Ето картата от първия ход (команда map) на галактиката със семе 2026. Системите са [ 1 ] … [16], точките между тях са пътищата, а Aa, Bb, Cc и Dd са столиците на четирите империи.

Ход 1/150  Земна империя (A)                            точки 20
M70+8 G60+4 C20+3 U5+1  наука +3
Нищо не се проучава (r номер). Натрупана наука: 0
    [ 1]..........[ 2]..
    Aa            .   ...[ 3]........[ 4]..........[ 5]
                         .. ..     ..Bb .          . .
                           ....  ..      ..         .
                             [ 6]          .     .[ 8]
                             . .          [ 7]... .  .
                               .          ..         .
                               .         .            .
              ...[10]........[11].....[12]            .
      [ 9]....   . . ...     . .     ..   ...        [13]
      Dd   ....    .    ....   .   ..        ...     Cc
               .... .       ... ...             ...  .
                  [14]........[15]                [16]
                  .           .                   .

A:Земна империя C:Съюз Лира     D:Академия Вега B:Хегемония Ори

help: команди   end: край на хода   sys N: система

И системата, в която започваш (sys 1): две планети (едната е твоя, с мина, лаборатория, корабостроителница и крепост) и първият флот.

Ход 1/150  Земна империя (A)                            точки 20
M70+8 G60+4 C20+3 U5+1  наука +3
Нищо не се проучава (r номер). Натрупана наука: 0
Система 1 Elara, жълта звезда. Пътища към: 2
Планета 1 Elara I, океанска (Земна империя)
  богатство M3 G3 C2 U1
  мини 1  лаб да  двор да  крепост 1
Планета 2 Elara II, газов гигант (свободна)
  богатство M1 G4 C1 U0
Флот на Земна империя: 3I 2B 2F

Enter или map: към картата   help: команди

Как се получава един и същ изход, когато всеки език има свой Random? Играта не ползва вградения генератор. Тя има свой, малък и еднакъв навсякъде, само с цели числа. Той е първата тема на урока.

Идеята

Пусни я на компютъра

Целият файл е тук: [Cosmos.java](/games/cosmos/Cosmos.java), [Cosmos.cs](/games/cosmos/Cosmos.cs), [cosmos.py](/games/cosmos/cosmos.py), [cosmos.js](/games/cosmos/cosmos.js). Сложи го в празна папка и го пусни:

python cosmos.py

В терминала играта чисти екрана и оцветява. С --plain печата кадрите като обикновен текст. С --seed=2026 галактиката е винаги една и съща (това е и семето по подразбиране), а с --lang=en играта е на английски (има и de и es). С --simulate=200 пуска 200 игри само на изкуствен интелект и печата баланса. Записите са в папка saves до играта.

Трябва Python 3.12 или по-нов.

Идеята

Как ще я строим

Модулът е шест урока. Всеки взима една част от играта, обяснява защо е такава и я строи с по-малки програми, които можеш да пуснеш, после показва същата част в истинския файл.

Галактиката от семе (този урок): генератор със семе, звезди и планети, пътищата като граф, свързаност.
Дървото на технологиите: ориентиран граф без цикли, предпоставки, топологичен ред, какво може да се проучи сега.
Флотите и космическата битка: едновременно решаване на ходовете, роли на корабите, симулация на битка.
Съперниците: империи с изкуствен интелект, оценка на полезността, характер на империята.
Ходът на галактиката: фази на хода, случайни събития, дипломация, шина от събития.
Цялата стратегия: победа, запис, баланс със симулация.

Идеята

Семето

Генераторът е в региона random на играта. Ето го, както е в канона:

# mulberry32: малък генератор със семе. Само 32-битови цели числа (маска & 0xFFFFFFFF и ръчно
# imul), затова дава една и съща поредица на всеки език.
MASK32 = 0xFFFFFFFF


# Math.imul от JavaScript: произведението, от което остават само долните 32 бита.
def imul(a, b):
    return (a * b) & MASK32


# „x >>> 0“ от JavaScript: число към 32 бита без знак (нечисло и безкрайност стават 0).
def to_uint32(value):
    if value != value or value == float('inf') or value == float('-inf'):
        return 0
    return int(value) & MASK32


class Random:
    def __init__(self, seed):
        self.state = to_uint32(seed)

    def next32(self):
        self.state = (self.state + 0x6D2B79F5) & MASK32
        z = self.state
        z = imul(z ^ (z >> 15), z | 1)
        z = (z ^ (z + imul(z ^ (z >> 7), z | 61))) & MASK32
        return (z ^ (z >> 14)) & MASK32

    # От 0 до n-1, без дробни числа.
    def next_int(self, n):
        return self.next32() % n

    # От min до max, двете включени.
    def range(self, low, high):
        return low + self.next_int(high - low + 1)

    def chance(self, percent):
        return self.next_int(100) < percent

    # Разбърква списъка на място (Фишер-Йейтс отзад напред).
    def shuffle(self, items):
        i = len(items) - 1
        while i > 0:
            j = self.next_int(i + 1)
            keep = items[i]
            items[i] = items[j]
            items[j] = keep
            i -= 1

Само три реда са същината: next32 променя едно число (state) и от него извежда друго, nextInt(n) взима остатъка му при деление на n, а range, chance и shuffle са построени върху nextInt. Нищо друго не се променя между две извиквания. Затова две копия на генератора с едно и също начално число (семе) дават една и съща поредица, а с различно число дават различна.

Програмата показва това: три генератора, два със семе 2026 и един с 2027, дават по шест числа от 0 до 99. После един списък от осем клетки се разбърква с shuffle, както играта разбърква клетките на решетката:

for seed in [2026, 2026, 2027]:
    rng = Random(seed)
    rolls = [rng.next_int(100) for _ in range(6)]
    print(f"семе {seed}: {' '.join(str(v) for v in rolls)}")

cells = list(range(8))
Random(2026).shuffle(cells)
print(f"разбъркани клетки: {' '.join(str(v) for v in cells)}")

семе 2026: 75 58 22 36 57 62
семе 2026: 75 58 22 36 57 62
семе 2027: 50 47 63 23 32 32
разбъркани клетки: 3 2 6 4 1 0 5 7

Първите два реда са еднакви до число, третият няма нищо общо с тях. Разбъркването е същото на четирите езика, защото shuffle само вика nextInt в строго определен ред: от края към началото, на всяка стъпка избира с кого да се разменя. Това е Фишер-Йейтс.

В Python целите числа нямат граница, затова imul отрязва произведението до 32 бита с маска. Без това числата щяха да растат и да се различават от другите езици.

Идеята

Галактиката е граф

Галактиката са две неща: системи (звезди с планети) и пътища между тях, по които се движат флотите. Такава структура се казва граф: системите са върховете, пътищата са ребрата. Един път е между две системи и работи в двете посоки.

Най-простият начин да го пазиш е всяка система да знае съседите си. Системата е клас с номер, място на картата и списък links:

class StarSystem:
    def __init__(self, system_id, x, y):
        self.id = system_id
        self.x = x
        self.y = y
        self.links = []

В играта същият клас е в региона world: има още име, цвят на звездата (червена, жълта или синя) и списък с планетите ѝ.

class StarSystem:
    def __init__(self, system_id, name, x, y):
        self.id = system_id
        self.name = name
        self.x = x
        self.y = y
        # Класът на звездата: 0 червена, 1 жълта, 2 синя.
        self.cls = 1
        self.links = []
        self.planets = []

Път между A и B значи, че B е в списъка на A и A е в списъка на B. Затова пътят се добавя с една функция, която пише на две места. Списъците се държат подредени по номер: insertSorted вмъква на правилното място, а не в края.

def insert_sorted(items, value):
    at = len(items)
    while at > 0 and items[at - 1] > value:
        at -= 1
    items.insert(at, value)


def has_lane(systems, a, b):
    return b in systems[a].links


def add_lane(systems, a, b):
    insert_sorted(systems[a].links, b)
    insert_sorted(systems[b].links, a)

Подредбата е важна за едно: когато играта обхожда съседите, ги вижда винаги в един и същ ред, на всички езици. Ако бяха в реда, в който са добавени, различните версии биха стигали до едно и също по различен път и изходите щяха да се различават.

Програмата слага шест системи, добавя пътищата в разбъркан ред и печата съседите на всяка. Номерата на системите на екрана са от 1, а в паметта от 0: numbers прибавя 1, преди да ги покаже.

systems = [StarSystem(i, i * 10, 0) for i in range(6)]
lanes = [(4, 0), (0, 2), (0, 1), (2, 3), (3, 5), (1, 4)]
for a, b in lanes:
    add_lane(systems, a, b)

for system in systems:
    print(f"система {system.id + 1}: {numbers(system.links)}")
print("път 1-3: " + ("да" if has_lane(systems, 0, 2) else "не"))
print("път 1-4: " + ("да" if has_lane(systems, 0, 3) else "не"))

система 1: 2 3 5
система 2: 1 5
система 3: 1 4
система 4: 3 6
система 5: 1 2
система 6: 4
път 1-3: да
път 1-4: не

Виж система 1: пътищата към системи 5 (добавен първи), 3 и 2 се печатат като „2 3 5“, във възходящ ред, не в реда на добавяне. Системите 1 и 3 имат път, 1 и 4 нямат.

Идеята

Свързана ли е галактиката?

Играта има смисъл само ако от всяка система може да се стигне до всяка друга. Иначе флотите няма как да минат, а империя на остров не може да бъде нападната. Искаме свързан граф: от всеки връх има път до всеки друг.

Проверката е обхождане в ширина (BFS). Започваш от една система и пускаш вълна: първо самата тя е на разстояние 0, след това съседите ѝ на 1, техните съседи на 2, и така нататък. Опашката пази системите, които чакат ред. Системите, до които вълната не стига, остават с −1.

def bfs(systems, start):
    dist = [-1] * len(systems)
    queue = [start]
    dist[start] = 0
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        for nxt in systems[current].links:
            if dist[nxt] < 0:
                dist[nxt] = dist[current] + 1
                queue.append(nxt)
    return dist

Графът е свързан точно когато вълната от система 1 стигне до всички: няма −1.

def is_connected(systems):
    for d in bfs(systems, 0):
        if d < 0:
            return False
    return True

Програмата прави два „острова“ (системи 1 до 4 и 5 до 7), печата разстоянията от система 1 и дали е свързана. После добавя един път между тях:

systems = [StarSystem(i, i * 10, 0) for i in range(7)]
lanes = [(0, 1), (1, 2), (2, 3), (4, 5), (5, 6)]
for a, b in lanes:
    add_lane(systems, a, b)
print("разстояния от система 1: " + " ".join(str(d) for d in bfs(systems, 0)))
print("свързана: " + ("да" if is_connected(systems) else "не"))

add_lane(systems, 3, 4)
print("разстояния от система 1: " + " ".join(str(d) for d in bfs(systems, 0)))
print("свързана: " + ("да" if is_connected(systems) else "не"))

разстояния от система 1: 0 1 2 3 -1 -1 -1
свързана: не
разстояния от система 1: 0 1 2 3 4 5 6
свързана: да

Преди пътя системите 5, 6 и 7 са −1: вълната не е минала. След пътя между 4 и 5 вълната стига до тях с разстояния 4, 5 и 6.

def is_connected(systems):
    for d in bfs(systems, 0):
        if d < :
            return False
    return True

В играта същата функция стои в региона graph, но обхождането пази и родителя на всяка система: от коя е открита. По родителите, вървейки назад, се получава най-краткият път:

# Обхождане в ширина от една система: разстояние в пътища (-1 е недостижима) и родител по пътя.
def bfs(systems, start):
    dist = [-1] * len(systems)
    parent = [-1] * len(systems)
    queue = [start]
    dist[start] = 0
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        for nxt in systems[current].links:
            if dist[nxt] < 0:
                dist[nxt] = dist[current] + 1
                parent[nxt] = current
                queue.append(nxt)
    return SimpleNamespace(dist=dist, parent=parent)

# Най-късият път като списък от системи, включително двата края; празен, ако няма път.
def shortest_path(systems, start, to):
    result = bfs(systems, start)
    if result.dist[to] < 0:
        return []
    path = [to]
    current = to
    while current != start:
        current = result.parent[current]
        path.append(current)
    path.reverse()
    return path

Играта ползва този път, когато флотата върви към далечна цел: go 1 9 не казва по кои системи минава, а на всеки ход флотата прави следващата стъпка от най-краткия път (nextStep). Същото ползва и изкуственият интелект на съперниците.

Една подробност, която е честно да се каже: isConnected е в канона, но самата игра не я вика. Свързаността е гарантирана от дървото, а функцията е за проверка, като тази в програмата по-горе и в упражнението по-долу.

Идеята

Звезди на решетка

Сега да направим самата галактика. Системите не се хвърлят в произволни точки на картата: някои биха се струпали една върху друга, а други биха останали сами в празно място. Играта ползва решетка: картата е 5 колони на 4 реда, 20 клетки. От тях се избират 12 до 20, а във всяка избрана клетка звездата е на случайно място.

COLS = 5
ROWS = 4
CELL_W = 12
CELL_H = 4


def place_stars(rng, count):
    cells = list(range(COLS * ROWS))
    rng.shuffle(cells)
    chosen = cells[:count]
    chosen.sort()
    systems = []
    for i in range(count):
        col = chosen[i] % COLS
        row = chosen[i] // COLS
        x = col * CELL_W + rng.next_int(6)
        y = row * CELL_H + rng.next_int(2)
        systems.append(StarSystem(i, x, y))
    return systems

Три стъпки: shuffle разбърква номерата на клетките, първите count се вземат и се сортират (за да са системите номерирани отляво надясно и отгоре надолу), и във всяка клетка звездата получава малко случайно изместване. Клетките пазят разстояние между звездите, а случайността ги прави различни от партия на партия.

В играта броят системи не е даден. Първото хвърляне на генератора го определя: 12 + nextInt(9) е число от 12 до 20.

Идеята

Пътища: първо дървото, после допълнителните

Остава да се реши кои звезди да са свързани. Ако слагаш пътища на случайни двойки, не можеш да си сигурен, че нищо няма да остане на остров. Ако слагаш всички пътища, картата става паяжина. Играта ползва двустъпково решение.

Първо дърво. Започва се от система 1. На всяка стъпка се търси най-късият път от система в дървото до система извън него и се добавя. Новата система влиза в дървото. Така се повтаря, докато влязат всички. Този алгоритъм се казва най-късо обхващащо дърво (Prim). Пътищата в него са точно брой системи − 1 и е ясно защо графът е свързан: всяка нова система влиза с един път към вече свързаните.

После допълнителни. Дърво няма цикли: между две системи има един-единствен маршрут и този маршрут може да е дълъг. Затова всяка система получава и път до най-близката система, с която още няма път, но само ако тя е достатъчно близка, няма вече 4 пътя и хвърлянето на зара е под 55%. Получават се кръгови маршрути и избор.

Разстоянието е квадратът на разстоянието, без корен (сравнява се само кое е по-малко): dy е умножено по 3, защото знаците в конзолата са по-високи, отколкото са широки.

def squared_distance(a, b):
    dx = a.x - b.x
    dy = (a.y - b.y) * 3
    return dx * dx + dy * dy

def connect(systems, rng):
    count = len(systems)
    in_tree = [False] * count
    in_tree[0] = True
    for step in range(1, count):
        best_a = -1
        best_b = -1
        best_d = 0
        for a in range(count):
            if not in_tree[a]:
                continue
            for b in range(count):
                if in_tree[b]:
                    continue
                d = squared_distance(systems[a], systems[b])
                if best_a < 0 or d < best_d:
                    best_a = a
                    best_b = b
                    best_d = d
        add_lane(systems, best_a, best_b)
        in_tree[best_b] = True
    for a in range(count):
        best = -1
        best_d = 0
        for b in range(count):
            if b == a or has_lane(systems, a, b):
                continue
            d = squared_distance(systems[a], systems[b])
            if best < 0 or d < best_d:
                best = b
                best_d = d
        if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55):
            add_lane(systems, a, best)

Две подробности правят изхода еднакъв. При равни разстояния печели първото намерено (d < bestD, не <=), т.е. по-малкият номер. А шансът (rng.chance(55)) е последен в условието с &&: зарът се хвърля само за път, който иначе би се добавил. Ако се хвърляше по-рано, и двата варианта щяха да са разумни, но всяко хвърляне взима число от генератора и всичко след него щеше да е друго: щяха да се получат други галактики от същите семена.

Виж го

Галактиката в движение

Дванайсетте системи на галактика със семе 18. Следи броячите горе: островите падат от 12 до 1, докато растат пътищата на дървото; после идват допълнителните пътища в друг цвят и накрая вълната от обхождането.

def connect(systems, rng):
    count = len(systems)
    in_tree = [False] * count
    in_tree[0] = True
    for step in range(1, count):
        best_a = -1
        best_b = -1
        best_d = 0
        for a in range(count):
            if not in_tree[a]:
                continue
            for b in range(count):
                if in_tree[b]:
                    continue
                d = squared_distance(systems[a], systems[b])
                if best_a < 0 or d < best_d:
                    best_a = a
                    best_b = b
                    best_d = d
        add_lane(systems, best_a, best_b)
        in_tree[best_b] = True
    for a in range(count):
        best = -1
        best_d = 0
        for b in range(count):
            if b == a or has_lane(systems, a, b):
                continue
            d = squared_distance(systems[a], systems[b])
            if best < 0 or d < best_d:
                best = b
                best_d = d
        if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55):
            add_lane(systems, a, best)

def connect(systems, rng):
    count = len(systems)
    in_tree = [False] * count
    in_tree[0] = True
    for step in range(1, count):
        best_a = -1
        best_b = -1
        best_d = 0
        for a in range(count):
            if not in_tree[a]:
                continue
            for b in range(count):
                if in_tree[b]:
                    continue
                d = squared_distance(systems[a], systems[b])
                if best_a < 0 or d < best_d:
                    best_a = a
                    best_b = b
                    best_d = d
        add_lane(systems, best_a, best_b)
        in_tree[best_b] = True
    for a in range(count):
        best = -1
        best_d = 0
        for b in range(count):
            if b == a or has_lane(systems, a, b):
                continue
            d = squared_distance(systems[a], systems[b])
            if best < 0 or d < best_d:
                best = b
                best_d = d
        if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55):
            add_lane(systems, a, best)

def bfs(systems, start):
    dist = [-1] * len(systems)
    queue = [start]
    dist[start] = 0
    head = 0
    while head < len(queue):
        current = queue[head]
        head += 1
        for nxt in systems[current].links:
            if dist[nxt] < 0:
                dist[nxt] = dist[current] + 1
                queue.append(nxt)
    return dist


def is_connected(systems):
    for d in bfs(systems, 0):
        if d < 0:
            return False
    return True

Стъпка по стъпка, с думи

12 звезди върху решетка 5 на 4 (20 клетки): избраните клетки светват. Още няма нито един път, значи всяка система е остров: 12 острова.
Първо най-късото обхващащо дърво (Prim). То започва от система 1. На всяка стъпка се търси най-късият път от система в дървото до система извън него.
Намереният път се добавя и новата система влиза в дървото. След 5 пътя остават 7 острова: всеки път свързва два острова в един.
11 пътя и един остров. Всяка нова система влиза с точно един път, затова никоя не остава сама: галактиката е свързана още преди допълнителните пътища.
После допълнителни пътища (в друг цвят): до най-близката несвързана система, ако е близо, има по-малко от 4 пътя и хвърлянето е под 55%. Получават се 3 обиколни пътя.
Проверка: обхождане в ширина от система 1. Вълната върви слой по слой и записва на всяка система разстоянието ѝ в пътища (0, 1, 2…).
Няма нито едно −1: вълната е стигнала до всички 12 системи, значи галактиката е свързана. Със същото семе тази картина е всеки път същата.

Идеята

Цялата галактика от едно семе

Остава да се сглоби: семе, брой системи, звезди, пътища. Функцията galaxy(seed) е целият генератор. Втората функция, describe, превръща галактиката в текст: така две галактики се сравняват с един ==.

def galaxy(seed):
    rng = Random(seed)
    count = 12 + rng.next_int(9)
    systems = place_stars(rng, count)
    connect(systems, rng)
    return systems


def describe(systems):
    text = ""
    for system in systems:
        text += f"{system.id + 1} ({system.x},{system.y}): {numbers(system.links)}\n"
    return text

Програмата прави галактиката със семе 18 (12 системи, 14 пътя: 11 от дървото и 3 допълнителни), после я прави още веднъж със същото семе и с по-следващото, и накрая проверява 200 различни семена:

systems = galaxy(18)
print(describe(systems), end="")
lanes = sum(len(system.links) for system in systems) // 2
print(f"пътища: {lanes} ({lanes - len(systems) + 1} допълнителни)")
print("свързана: " + ("да" if is_connected(systems) else "не"))

first = describe(systems)
print("същото семе пак, същата галактика: " + ("да" if describe(galaxy(18)) == first else "не"))
print("друго семе, друга галактика: " + ("да" if describe(galaxy(19)) != first else "не"))

ok = 0
for seed in range(1, 201):
    if is_connected(galaxy(seed)):
        ok += 1
print("семена 1-200: свързани " + str(ok) + " от 200")

1 (5,5): 2
2 (12,4): 1 5 6
3 (36,5): 4 6 7
4 (50,5): 3
5 (17,9): 2 6 9
6 (24,8): 2 3 5 7
7 (37,8): 3 6 11 12
8 (3,12): 9
9 (17,12): 5 8 10
10 (27,12): 9
11 (40,12): 7 12
12 (53,12): 7 11
пътища: 14 (3 допълнителни)
свързана: да
същото семе пак, същата галактика: да
друго семе, друга галактика: да
семена 1-200: свързани 200 от 200

Три неща са важни тук. Първо, същото семе е същата галактика до последната координата. Второ, съседното семе е съвсем друга галактика. Трето, всички 200 са свързани: това не е късмет, а следствие от дървото. Тази проверка е малък тест на свойство: не питаме „как изглежда тази галактика“, а „вярно ли е за всяка галактика, че е свързана“.

Така изглежда истинската функция в играта. Тя прави същото, но и дава име на всяка звезда (имената се разбъркват с още един shuffle) и цвят (червена, жълта или синя), а работи върху общия свят world:

def generate_systems(world, count):
    rng = world.rng
    cells = []
    for i in range(MAP_COLS * MAP_ROWS):
        cells.append(i)
    rng.shuffle(cells)
    chosen = cells[:count]
    chosen.sort()
    names = []
    for i in range(len(STAR_NAMES)):
        names.append(i)
    rng.shuffle(names)
    for i in range(count):
        col = chosen[i] % MAP_COLS
        row = chosen[i] // MAP_COLS
        x = col * CELL_W + rng.next_int(6)
        y = row * CELL_H + rng.next_int(2)
        system = StarSystem(i, STAR_NAMES[names[i]], x, y)
        system.cls = rng.next_int(3)
        world.systems.append(system)
    # Най-късото обхващащо дърво (Prim): при равни разстояния печели по-малкият номер.
    in_tree = [False] * count
    in_tree[0] = True
    for step in range(1, count):
        best_a = -1
        best_b = -1
        best_d = 0
        for a in range(count):
            if not in_tree[a]:
                continue
            for b in range(count):
                if in_tree[b]:
                    continue
                d = squared_distance(world.systems[a], world.systems[b])
                if best_a < 0 or d < best_d:
                    best_a = a
                    best_b = b
                    best_d = d
        add_lane(world.systems, best_a, best_b)
        in_tree[best_b] = True
    # Допълнителни пътища: до най-близкия още несвързан съсед, ако не е твърде далеч.
    for a in range(count):
        best = -1
        best_d = 0
        for b in range(count):
            if b == a or has_lane(world.systems, a, b):
                continue
            d = squared_distance(world.systems[a], world.systems[b])
            if best < 0 or d < best_d:
                best = b
                best_d = d
        if best >= 0 and best_d <= 420 and len(world.systems[a].links) < 4 and len(world.systems[best].links) < 4 and rng.chance(55):
            add_lane(world.systems, a, best)

Всичко, което играта знае, живее в класа World: семето, генераторът, системите, планетите, империите и флотите. Затова записът е на едно място и newWorld(seed) е единственото, което прави галактика:

class World:
    def __init__(self, seed):
        self.seed = seed
        self.rng = Random(seed)
        self.turn = 1
        self.systems = []
        self.planets = []
        self.empires = []
        self.fleets = []
        self.queue = []
        self.offers = []
        self.news = []
        self.turn_lines = []
        self.bus = EventBus()
        self.victory = None
        self.fort_left = {}
        self.stats = SimpleNamespace(battles=0, lost=0, colonies=0, techs=0, events=0)
        self.last = SimpleNamespace(battle=[])
        self.quiet = False
        self.alert = 0
        self.pace = 100

    def living_count(self):
        n = 0
        for e in self.empires:
            if e.alive:
                n += 1
        return n

И как newWorld я ползва. Семето става света: броят системи, пътищата, после столиците на империите и планетите, и накрая всяка империя получава родна планета:

# Целият свят от едно семе. human е играчът (в симулацията няма), personalities е по избор
# списък с характери, по един на империя.
def new_world(seed, human, personalities, quiet):
    load_data()
    world = World(seed)
    world.quiet = quiet
    world.pace = RIVAL_PACE if human else 100
    install_subscribers(world, quiet)
    rng = world.rng
    count = 12 + rng.next_int(9)
    generate_systems(world, count)
    rivals = 2 + rng.next_int(2) if count >= 15 else 2
    defs = [0]
    pool = [1, 2, 3]
    rng.shuffle(pool)
    for i in range(rivals):
        defs.append(pool[i])
    capitals = pick_capitals(world, len(defs))
    generate_planets(world, capitals)
    for i in range(len(defs)):
        empire = Empire(i, EMPIRE_DEFS[defs[i]], len(defs))
        if personalities is not None:
            empire.personality = PERSONALITIES[personalities[i]]
        empire.human = human and i == 0
        world.empires.append(empire)
        place_homeworld(world, empire, capitals[i])
    return world

Столиците са избрани с обхождане в ширина: първата е най-лявата система, а всяка следваща е най-далечната (по пътища) от вече избраните. Така империите започват възможно най-далеч една от друга:

# Столиците: първата е най-лявата система; всяка следваща е най-далеч (по пътища) от вече избраните.
def pick_capitals(world, count):
    chosen = []
    first = 0
    for system in world.systems:
        if system.x < world.systems[first].x:
            first = system.id
    chosen.append(first)
    nearest = list(bfs(world.systems, first).dist)
    while len(chosen) < count:
        best = -1
        for system in world.systems:
            if system.id in chosen:
                continue
            if best < 0 or nearest[system.id] > nearest[best]:
                best = system.id
        chosen.append(best)
        d = bfs(world.systems, best).dist
        for i in range(len(nearest)):
            if d[i] < nearest[i]:
                nearest[i] = d[i]
    return chosen

Идеята

Планети с тегла

Всяка система има една до три планети, и не всички са еднакво вероятни: една планета е с 30% шанс, две с 45%, три с 25%. Видът на планетата също е с тегла (скална, газов гигант, ледена, океанска, вулканична). Нужна е функция, която избира елемент по тегло.

Идеята: хвърляш число от 0 до сбора на теглата и вървиш по списъка, като изваждаш теглото на всеки елемент, докато хвърленото не е по-малко от текущото тегло.

def pick_weighted(rng, weights):
    total = 0
    for w in weights:
        total += w
    roll = rng.next_int(total)
    for i in range(len(weights)):
        if roll < weights[i]:
            return i
        roll -= weights[i]
    return len(weights) - 1

С тегла 30, 45 и 25 сборът е 100. Хвърляне от 0 до 29 е индекс 0, от 30 до 74 индекс 1, от 75 до 99 индекс 2. Програмата хвърля 1000 пъти (планетите са индекс + 1) и после отделно взима броя планети на първите осем системи:

weights = [30, 45, 25]
rng = Random(2026)
counts = [0, 0, 0]
for _ in range(1000):
    counts[pick_weighted(rng, weights)] += 1
print(f"планети в 1000 системи: 1={counts[0]} 2={counts[1]} 3={counts[2]}")

few = Random(7)
planets = [pick_weighted(few, weights) for _ in range(8)]
print(f"първите 8 системи: {numbers(planets)}")

планети в 1000 системи: 1=299 2=467 3=234
първите 8 системи: 2 3 2 2 3 3 1 1

От 1000 системи около 30%, 45% и 25% имат съответно 1, 2 и 3 планети. Не е точно: теглата са вероятности, не квоти. Но със същото семе числата са винаги едни и същи.

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

class Planet:
    def __init__(self, planet_id, system_id, index, type_index, rich):
        self.id = planet_id
        self.system_id = system_id
        self.index = index
        self.type_index = type_index
        self.rich = rich
        self.owner = -1
        self.mines = 0
        self.lab = 0
        self.yard = 0
        self.fort = 0
        self.siege = 0

Истинският generatePlanets ползва същата функция два пъти: за броя и за вида на всяка планета. После хвърля още едно число за всеки ресурс (богатство от 0 до 4), а цветът на звездата добавя един към ресурса: червената към газа, жълтата към метала, синята към кристала.

def generate_planets(world, capitals):
    rng = world.rng
    type_weights = []
    for ptype in PLANET_TYPES:
        type_weights.append(ptype.weight)
    for system in world.systems:
        is_capital = system.id in capitals
        roll = pick_weighted(rng, [30, 45, 25]) + 1
        count = 2 if is_capital and roll < 2 else roll
        for index in range(count):
            type_index = pick_weighted(rng, type_weights)
            ptype = PLANET_TYPES[type_index]
            rich = []
            for r in range(RES_COUNT):
                value = clamp(ptype.base[r] + rng.next_int(3) - 1, 0, 4)
                rich.append(value)
            # Звездата тегли: червената дава газ, жълтата метал, синята кристал.
            if system.cls == 0:
                rich[1] = min_of(5, rich[1] + 1)
            elif system.cls == 1:
                rich[0] = min_of(5, rich[0] + 1)
            else:
                rich[2] = min_of(5, rich[2] + 1)
            planet = Planet(len(world.planets), system.id, index, type_index, rich)
            world.planets.append(planet)
            system.planets.append(planet.id)

Пробвай

Предвиди изхода

Шест системи, номерирани от 0. Пътищата са 0-1, 1-2, 2-3, 0-4, 4-3 и 3-5: пръстен от пет системи и още една, закачена за него. Какво печата програмата?

systems = [StarSystem(i, i * 10, 0) for i in range(6)]
lanes = [(0, 1), (1, 2), (2, 3), (0, 4), (4, 3), (3, 5)]
for a, b in lanes:
    add_lane(systems, a, b)
print(" ".join(str(d) for d in bfs(systems, 0)))

Отговор

0 1 2 3 1 4

1 2 3 3 2 4

0 1 2 2 1 3

Пробвай

Намери грешката

Колега подмени един ред в цикъла на дървото. Програмата прави галактики от 200 семена и брои свързаните. Преди бяха всички 200, сега са:

def connect(systems, rng):
    count = len(systems)
    in_tree = [False] * count
    in_tree[0] = True
    for step in range(1, count - 1):
        best_a = -1
        best_b = -1
        best_d = 0
        for a in range(count):
            if not in_tree[a]:
                continue
            for b in range(count):
                if in_tree[b]:
                    continue
                d = squared_distance(systems[a], systems[b])
                if best_a < 0 or d < best_d:
                    best_a = a
                    best_b = b
                    best_d = d
        add_lane(systems, best_a, best_b)
        in_tree[best_b] = True
    for a in range(count):
        best = -1
        best_d = 0
        for b in range(count):
            if b == a or has_lane(systems, a, b):
                continue
            d = squared_distance(systems[a], systems[b])
            if best < 0 or d < best_d:
                best = b
                best_d = d
        if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55):
            add_lane(systems, a, best)


ok = 0
for seed in range(1, 201):
    if is_connected(galaxy(seed)):
        ok += 1
print("семена 1-200: свързани " + str(ok) + " от 200")

семена 1-200: свързани 150 от 200

Кой ред е виновен?

Избери реда с грешката.

По-точно

Какво не е в тази система

Една галактика от семе има малко правила, но зад тях стоят избори.

Дървото е просто. Алгоритъмът на Prim тук е с три вложени цикъла: за дърво от 20 системи това са няколко хиляди сравнения. В по-голям граф (милиони върхове) се използва приоритетна опашка и Prim върви за O(E log V). Тук простият цикъл е по-кратък, лесен за четене и еднакъв на четирите езика.

Допълнителните пътища не са гарантирани. Затова някои галактики са почти дървета: дълги вериги без обиколни пътища. Това е решение за играта: такива карти са по-тактически (ключов проход, който се пази). Колко допълнителни пътища (55%, най-много 4 на система, близо) се настройва със симулация, както балансът.

Свързаността е избор, не закон. В други игри островите са на място: не всички неща са достижими. Тук е обратното: свързаността е условие на играта. Затова е добре да се проверява, както прави програмата със 200 семена.

Семето не е цялата история. Същото семе дава същата галактика само докато генераторът вика nextInt в един и същ ред. Ако добавиш една нова хвърлена стойност в началото, всички галактики на всички стари семена се променят, а старите записи се зареждат в различен свят. Затова в истинска игра промяна в генерацията трябва да е промяна на версията: записът на играта има версия на формата именно за такива случаи.

Пътищата са в двете посоки. Графът тук е ненасочен. Дървото на технологиите (следващият урок) е различно: „А трябва преди Б“ е еднопосочно. Там графът е насочен.

Упражнение

Острови

Реши задачата в редактора си.

Острови. Програмата чете от входа на първия ред броя системи n и броя пътища m, а после m реда с по два номера (от 1). Тя печата колко острова има галактиката (острови са групи системи, свързани помежду си), колко системи има най-големият остров и дали галактиката е свързана.

С вход 8 5 | 1 2 | 2 3 | 4 5 | 6 7 | 7 8 (по един на ред) изходът е:

острови: 3
най-голям остров: 3
свързана: не

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

Още задачи

Най-краткият път. Допълни програмата да чете още два номера и да печата най-краткия път между тях по системите, а ако няма, „няма път“. Родителят на всяка система е ключът.
Колко пътя да добавя? Колко най-малко пътя трябва да се добавят, за да стане свързана галактика с k острова? Опитай с няколко примера и виж правилото.
Колко семена не са свързани без дървото? Махни цикъла на дървото и пусни проверката на 200 семена. Колко галактики са свързани само от допълнителните пътища?

Тест

Провери се

1. Защо със същото семе галактиката е всеки път същата?Защото генераторът е формула: следващото число зависи само от предишното, а кодът вика генератора в един и същ редЗащото Random на всеки език дава една и съща поредицаЗащото галактиката се записва на диска и се чете оттам

2. Галактика с 12 системи има най-късо обхващащо дърво. Колко пътя има в него?126611

3. След обхождане в ширина от система 1 разстоянията са „0 1 2 3 -1 -1 -1“. Какво значи −1?Системата не е достигната: няма път до нея, значи галактиката не е свързанаСистемата вече е била обходенаСистемата е на разстояние минус едно, т.е. зад началото

4. Тегла 30, 45 и 25, а хвърлянето е 55. Колко планети получава системата?321

5. Записът на Epic Cosmos съдържа реда seed=… Защо не пази и системите, и пътищата?Защото пътищата се измислят наново и може да са другиЗащото галактиката се прави пак от семето и излиза същата; в записа остава само това, което играта променяЗащото ги пази другаде

6. Какво би станало, ако допълнителните пътища се добавят без дървото?Галактиката би била винаги несвързанаНищо: пътищата пак биха свързвали всичкоНякои галактики биха били несвързани: допълнителните пътища са случайни и нищо не гарантира, че свързват всичко

Галактиката от семе

Бисквитки