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

Накратко: Epic Cosmos е цяла космическа стратегия, която се прави урок по урок. Първият урок строи галактиката: генератор със семе, 12 до 20 системи на решетка 5 на 4, пътища като граф (първо най-късо обхващащо дърво, после допълнителни), проверка за свързаност с обхождане в ширина и планети с тегла.

Проблем

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

В тази поредица правим втора игра, много различна от Арканум: 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). Сложи го в празна папка и го пусни:

dotnet new console -n Cosmos
cd Cosmos
# смени Program.cs с Cosmos.cs
dotnet run

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

Програмата е един файл с няколко класа и Main в Cosmos.

Идеята

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

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

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

Идеята

Семето

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

// mulberry32: малък генератор със семе. Само 32-битови цели числа (uint и unchecked), затова
// дава една и съща поредица на всеки език.
class Random
{
    public uint State;

    public Random(uint seed)
    {
        State = seed;
    }

    public uint Next32()
    {
        unchecked
        {
            State = State + 0x6d2b79f5;
            uint z = State;
            z = (z ^ (z >> 15)) * (z | 1);
            z = z ^ (z + (z ^ (z >> 7)) * (z | 61));
            return z ^ (z >> 14);
        }
    }

    // От 0 до n-1, без дробни числа.
    public int NextInt(int n)
    {
        return (int)(Next32() % (uint)n);
    }

    // От min до max, двете включени.
    public int Range(int min, int max)
    {
        return min + NextInt(max - min + 1);
    }

    public bool Chance(int percent)
    {
        return NextInt(100) < percent;
    }

    // Разбърква списъка на място (Фишер-Йейтс отзад напред).
    public void Shuffle(List<int> items)
    {
        for (int i = items.Count - 1; i > 0; i--)
        {
            int j = NextInt(i + 1);
            int keep = items[i];
            items[i] = items[j];
            items[j] = keep;
        }
    }
}

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

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

foreach (int seed in new[] { 2026, 2026, 2027 })
{
    var rng = new Random((uint)seed);
    var rolls = new List<int>();
    for (int i = 0; i < 6; i++) rolls.Add(rng.NextInt(100));
    Console.WriteLine($"семе {seed}: {string.Join(" ", rolls)}");
}

var cells = new List<int>();
for (int i = 0; i < 8; i++) cells.Add(i);
new Random(2026).Shuffle(cells);
Console.WriteLine($"разбъркани клетки: {string.Join(" ", 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 в строго определен ред: от края към началото, на всяка стъпка избира с кого да се разменя. Това е Фишер-Йейтс.

В C# Random тук е собственият клас на играта, не System.Random. Състоянието е uint, а блокът unchecked оставя умноженията да се преливат като в другите езици.

Идеята

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

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

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

class StarSystem
{
    public int Id;
    public int X;
    public int Y;
    public List<int> Links = new List<int>();

    public StarSystem(int id, int x, int y)
    {
        Id = id;
        X = x;
        Y = y;
    }
}

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

class StarSystem
{
    public int Id;
    public string Name;
    public int X;
    public int Y;
    // Класът на звездата: 0 червена, 1 жълта, 2 синя.
    public int Cls;
    public List<int> Links = new List<int>();
    public List<int> Planets = new List<int>();

    public StarSystem(int id, string name, int x, int y)
    {
        Id = id;
        Name = name;
        X = x;
        Y = y;
        Cls = 1;
    }
}

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

static void InsertSorted(List<int> list, int value)
{
    int at = list.Count;
    while (at > 0 && list[at - 1] > value) at--;
    list.Insert(at, value);
}

static bool HasLane(List<StarSystem> systems, int a, int b)
{
    return systems[a].Links.IndexOf(b) >= 0;
}

static void AddLane(List<StarSystem> systems, int a, int b)
{
    InsertSorted(systems[a].Links, b);
    InsertSorted(systems[b].Links, a);
}

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

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

var systems = new List<StarSystem>();
for (int i = 0; i < 6; i++) systems.Add(new StarSystem(i, i * 10, 0));
(int, int)[] lanes = { (4, 0), (0, 2), (0, 1), (2, 3), (3, 5), (1, 4) };
foreach (var (a, b) in lanes) AddLane(systems, a, b);

foreach (StarSystem system in systems)
{
    Console.WriteLine($"система {system.Id + 1}: {Numbers(system.Links)}");
}
Console.WriteLine("път 1-3: " + (HasLane(systems, 0, 2) ? "да" : "не"));
Console.WriteLine("път 1-4: " + (HasLane(systems, 0, 3) ? "да" : "не"));

Изход

система 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.

static int[] Bfs(List<StarSystem> systems, int from)
{
    int[] dist = new int[systems.Count];
    Array.Fill(dist, -1);
    var queue = new List<int> { from };
    dist[from] = 0;
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        foreach (int next in systems[current].Links)
        {
            if (dist[next] < 0)
            {
                dist[next] = dist[current] + 1;
                queue.Add(next);
            }
        }
    }
    return dist;
}

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

static bool IsConnected(List<StarSystem> systems)
{
    foreach (int d in Bfs(systems, 0))
    {
        if (d < 0) return false;
    }
    return true;
}

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

var systems = new List<StarSystem>();
for (int i = 0; i < 7; i++) systems.Add(new StarSystem(i, i * 10, 0));
(int, int)[] lanes = { (0, 1), (1, 2), (2, 3), (4, 5), (5, 6) };
foreach (var (a, b) in lanes) AddLane(systems, a, b);
Console.WriteLine("разстояния от система 1: " + string.Join(" ", Bfs(systems, 0)));
Console.WriteLine("свързана: " + (IsConnected(systems) ? "да" : "не"));

AddLane(systems, 3, 4);
Console.WriteLine("разстояния от система 1: " + string.Join(" ", Bfs(systems, 0)));
Console.WriteLine("свързана: " + (IsConnected(systems) ? "да" : "не"));

Изход

разстояния от система 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.

static bool IsConnected(List<StarSystem> systems)
{
    foreach (int d in Bfs(systems, 0))
    {
        if (d < ) return false;
    }
    return true;
}

Провери

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

// Обхождане в ширина от една система: разстояние в пътища (-1 е недостижима) и родител по пътя.
public static BfsResult Bfs(List<StarSystem> systems, int from)
{
    int[] dist = new int[systems.Count];
    int[] parent = new int[systems.Count];
    Array.Fill(dist, -1);
    Array.Fill(parent, -1);
    List<int> queue = new List<int> { from };
    dist[from] = 0;
    int head = 0;
    while (head < queue.Count)
    {
        int current = queue[head];
        head++;
        foreach (int next in systems[current].Links)
        {
            if (dist[next] < 0)
            {
                dist[next] = dist[current] + 1;
                parent[next] = current;
                queue.Add(next);
            }
        }
    }
    return new BfsResult { Dist = dist, Parent = parent };
}

// Най-късият път като списък от системи, включително двата края; празен, ако няма път.
public static List<int> ShortestPath(List<StarSystem> systems, int from, int to)
{
    BfsResult result = Bfs(systems, from);
    if (result.Dist[to] < 0) return new List<int>();
    List<int> path = new List<int> { to };
    int current = to;
    while (current != from)
    {
        current = result.Parent[current];
        path.Add(current);
    }
    path.Reverse();
    return path;
}

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

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

Идеята

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

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

const int COLS = 5;
const int ROWS = 4;
const int CELL_W = 12;
const int CELL_H = 4;

static List<StarSystem> PlaceStars(Random rng, int count)
{
    var cells = new List<int>();
    for (int i = 0; i < COLS * ROWS; i++) cells.Add(i);
    rng.Shuffle(cells);
    List<int> chosen = cells.GetRange(0, count);
    chosen.Sort();
    var systems = new List<StarSystem>();
    for (int i = 0; i < count; i++)
    {
        int col = chosen[i] % COLS;
        int row = chosen[i] / COLS;
        int x = col * CELL_W + rng.NextInt(6);
        int y = row * CELL_H + rng.NextInt(2);
        systems.Add(new StarSystem(i, x, y));
    }
    return systems;
}

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

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

Идеята

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

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

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

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

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

static int SquaredDistance(StarSystem a, StarSystem b)
{
    int dx = a.X - b.X;
    int dy = (a.Y - b.Y) * 3;
    return dx * dx + dy * dy;
}

static void Connect(List<StarSystem> systems, Random rng)
{
    int count = systems.Count;
    var inTree = new bool[count];
    inTree[0] = true;
    for (int step = 1; step < count; step++)
    {
        int bestA = -1;
        int bestB = -1;
        int bestD = 0;
        for (int a = 0; a < count; a++)
        {
            if (!inTree[a]) continue;
            for (int b = 0; b < count; b++)
            {
                if (inTree[b]) continue;
                int d = SquaredDistance(systems[a], systems[b]);
                if (bestA < 0 || d < bestD)
                {
                    bestA = a;
                    bestB = b;
                    bestD = d;
                }
            }
        }
        AddLane(systems, bestA, bestB);
        inTree[bestB] = true;
    }
    for (int a = 0; a < count; a++)
    {
        int best = -1;
        int bestD = 0;
        for (int b = 0; b < count; b++)
        {
            if (b == a || HasLane(systems, a, b)) continue;
            int d = SquaredDistance(systems[a], systems[b]);
            if (best < 0 || d < bestD)
            {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems[a].Links.Count < 4 && systems[best].Links.Count < 4 && rng.Chance(55))
        {
            AddLane(systems, a, best);
        }
    }
}

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

Виж го

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

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

static void Connect(List<StarSystem> systems, Random rng)
{
    int count = systems.Count;
    var inTree = new bool[count];
    inTree[0] = true;
    for (int step = 1; step < count; step++)
    {
        int bestA = -1;
        int bestB = -1;
        int bestD = 0;
        for (int a = 0; a < count; a++)
        {
            if (!inTree[a]) continue;
            for (int b = 0; b < count; b++)
            {
                if (inTree[b]) continue;
                int d = SquaredDistance(systems[a], systems[b]);
                if (bestA < 0 || d < bestD)
                {
                    bestA = a;
                    bestB = b;
                    bestD = d;
                }
            }
        }
        AddLane(systems, bestA, bestB);
        inTree[bestB] = true;
    }
    for (int a = 0; a < count; a++)
    {
        int best = -1;
        int bestD = 0;
        for (int b = 0; b < count; b++)
        {
            if (b == a || HasLane(systems, a, b)) continue;
            int d = SquaredDistance(systems[a], systems[b]);
            if (best < 0 || d < bestD)
            {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems[a].Links.Count < 4 && systems[best].Links.Count < 4 && rng.Chance(55))
        {
            AddLane(systems, a, best);
        }
    }
}

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

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

Идеята

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

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

static List<StarSystem> Galaxy(int seed)
{
    var rng = new Random((uint)seed);
    int count = 12 + rng.NextInt(9);
    List<StarSystem> systems = PlaceStars(rng, count);
    Connect(systems, rng);
    return systems;
}

static string Describe(List<StarSystem> systems)
{
    string text = "";
    foreach (StarSystem system in systems)
    {
        text += $"{system.Id + 1} ({system.X},{system.Y}): {Numbers(system.Links)}\n";
    }
    return text;
}

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

List<StarSystem> systems = Galaxy(18);
Console.Write(Describe(systems));
int lanes = 0;
foreach (StarSystem system in systems) lanes += system.Links.Count;
lanes /= 2;
Console.WriteLine($"пътища: {lanes} ({lanes - systems.Count + 1} допълнителни)");
Console.WriteLine("свързана: " + (IsConnected(systems) ? "да" : "не"));

string first = Describe(systems);
Console.WriteLine("същото семе пак, същата галактика: " + (Describe(Galaxy(18)) == first ? "да" : "не"));
Console.WriteLine("друго семе, друга галактика: " + (Describe(Galaxy(19)) != first ? "да" : "не"));

int ok = 0;
for (int seed = 1; seed <= 200; seed++)
{
    if (IsConnected(Galaxy(seed))) ok++;
}
Console.WriteLine("семена 1-200: свързани " + 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:

public static void GenerateSystems(World world, int count)
{
    Random rng = world.Rng;
    List<int> cells = new List<int>();
    for (int i = 0; i < MAP_COLS * MAP_ROWS; i++) cells.Add(i);
    rng.Shuffle(cells);
    List<int> chosen = cells.GetRange(0, count);
    chosen.Sort();
    List<int> names = new List<int>();
    for (int i = 0; i < STAR_NAMES.Length; i++) names.Add(i);
    rng.Shuffle(names);
    for (int i = 0; i < count; i++)
    {
        int col = chosen[i] % MAP_COLS;
        int row = chosen[i] / MAP_COLS;
        int x = col * CELL_W + rng.NextInt(6);
        int y = row * CELL_H + rng.NextInt(2);
        StarSystem system = new StarSystem(i, STAR_NAMES[names[i]], x, y);
        system.Cls = rng.NextInt(3);
        world.Systems.Add(system);
    }
    // Най-късото обхващащо дърво (Prim): при равни разстояния печели по-малкият номер.
    bool[] inTree = new bool[count];
    inTree[0] = true;
    for (int step = 1; step < count; step++)
    {
        int bestA = -1;
        int bestB = -1;
        int bestD = 0;
        for (int a = 0; a < count; a++)
        {
            if (!inTree[a]) continue;
            for (int b = 0; b < count; b++)
            {
                if (inTree[b]) continue;
                int d = SquaredDistance(world.Systems[a], world.Systems[b]);
                if (bestA < 0 || d < bestD)
                {
                    bestA = a;
                    bestB = b;
                    bestD = d;
                }
            }
        }
        AddLane(world.Systems, bestA, bestB);
        inTree[bestB] = true;
    }
    // Допълнителни пътища: до най-близкия още несвързан съсед, ако не е твърде далеч.
    for (int a = 0; a < count; a++)
    {
        int best = -1;
        int bestD = 0;
        for (int b = 0; b < count; b++)
        {
            if (b == a || HasLane(world.Systems, a, b)) continue;
            int d = SquaredDistance(world.Systems[a], world.Systems[b]);
            if (best < 0 || d < bestD)
            {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && world.Systems[a].Links.Count < 4 && world.Systems[best].Links.Count < 4 && rng.Chance(55))
        {
            AddLane(world.Systems, a, best);
        }
    }
}

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

class World
{
    public long Seed;
    public Random Rng;
    public int Turn;
    public List<StarSystem> Systems = new List<StarSystem>();
    public List<Planet> Planets = new List<Planet>();
    public List<Empire> Empires = new List<Empire>();
    public List<Fleet> Fleets = new List<Fleet>();
    public List<QueueItem> Queue = new List<QueueItem>();
    public List<Offer> Offers = new List<Offer>();
    public List<string> News = new List<string>();
    public List<string> TurnLines = new List<string>();
    public EventBus Bus = new EventBus();
    public Victory? Victory;
    public Dictionary<int, int> FortLeft = new Dictionary<int, int>();
    public WorldStats Stats = new WorldStats();
    public List<string> LastBattle = new List<string>();
    public bool Quiet;
    public int Alert;
    public int Pace;

    public World(long seed)
    {
        Seed = seed;
        Rng = new Random(unchecked((uint)seed));
        Turn = 1;
        Victory = null;
        Quiet = false;
        Alert = 0;
        Pace = 100;
    }

    public int LivingCount()
    {
        int n = 0;
        foreach (Empire e in Empires)
        {
            if (e.Alive) n++;
        }
        return n;
    }
}

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

// Целият свят от едно семе. human е играчът (в симулацията няма), personalities е по избор
// списък с характери, по един на империя.
public static World NewWorld(long seed, bool human, List<string>? personalities, bool quiet)
{
    LoadData();
    World world = new World(seed);
    world.Quiet = quiet;
    world.Pace = human ? RIVAL_PACE : 100;
    InstallSubscribers(world, quiet);
    Random rng = world.Rng;
    int count = 12 + rng.NextInt(9);
    GenerateSystems(world, count);
    int rivals = count >= 15 ? 2 + rng.NextInt(2) : 2;
    List<int> defs = new List<int> { 0 };
    List<int> pool = new List<int> { 1, 2, 3 };
    rng.Shuffle(pool);
    for (int i = 0; i < rivals; i++) defs.Add(pool[i]);
    List<int> capitals = PickCapitals(world, defs.Count);
    GeneratePlanets(world, capitals);
    for (int i = 0; i < defs.Count; i++)
    {
        Empire empire = new Empire(i, EMPIRE_DEFS[defs[i]], defs.Count);
        if (personalities != null)
        {
            empire.Personality = PERSONALITIES.Get(personalities[i]);
        }
        empire.Human = human && i == 0;
        world.Empires.Add(empire);
        PlaceHomeworld(world, empire, capitals[i]);
    }
    return world;
}

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

// Столиците: първата е най-лявата система; всяка следваща е най-далеч (по пътища) от вече избраните.
public static List<int> PickCapitals(World world, int count)
{
    List<int> chosen = new List<int>();
    int first = 0;
    foreach (StarSystem system in world.Systems)
    {
        if (system.X < world.Systems[first].X) first = system.Id;
    }
    chosen.Add(first);
    int[] nearest = (int[])Bfs(world.Systems, first).Dist.Clone();
    while (chosen.Count < count)
    {
        int best = -1;
        foreach (StarSystem system in world.Systems)
        {
            if (chosen.IndexOf(system.Id) >= 0) continue;
            if (best < 0 || nearest[system.Id] > nearest[best]) best = system.Id;
        }
        chosen.Add(best);
        int[] d = Bfs(world.Systems, best).Dist;
        for (int i = 0; i < nearest.Length; i++)
        {
            if (d[i] < nearest[i]) nearest[i] = d[i];
        }
    }
    return chosen;
}

Идеята

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

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

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

static int PickWeighted(Random rng, int[] weights)
{
    int total = 0;
    foreach (int w in weights) total += w;
    int roll = rng.NextInt(total);
    for (int i = 0; i < weights.Length; i++)
    {
        if (roll < weights[i]) return i;
        roll -= weights[i];
    }
    return weights.Length - 1;
}

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

int[] weights = { 30, 45, 25 };
var rng = new Random(2026);
int[] counts = new int[3];
for (int i = 0; i < 1000; i++) counts[PickWeighted(rng, weights)]++;
Console.WriteLine($"планети в 1000 системи: 1={counts[0]} 2={counts[1]} 3={counts[2]}");

var few = new Random(7);
var planets = new List<int>();
for (int i = 0; i < 8; i++) planets.Add(PickWeighted(few, weights));
Console.WriteLine($"първите 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
{
    public int Id;
    public int SystemId;
    public int Index;
    public int TypeIndex;
    public int[] Rich;
    public int Owner;
    public int Mines;
    public int Lab;
    public int Yard;
    public int Fort;
    public int Siege;

    public Planet(int id, int systemId, int index, int typeIndex, int[] rich)
    {
        Id = id;
        SystemId = systemId;
        Index = index;
        TypeIndex = typeIndex;
        Rich = rich;
        Owner = -1;
        Mines = 0;
        Lab = 0;
        Yard = 0;
        Fort = 0;
        Siege = 0;
    }
}

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

public static void GeneratePlanets(World world, List<int> capitals)
{
    Random rng = world.Rng;
    List<int> typeWeights = new List<int>();
    foreach (PlanetType type in PLANET_TYPES) typeWeights.Add(type.Weight);
    foreach (StarSystem system in world.Systems)
    {
        bool isCapital = capitals.IndexOf(system.Id) >= 0;
        int roll = PickWeighted(rng, new int[] { 30, 45, 25 }) + 1;
        int count = isCapital && roll < 2 ? 2 : roll;
        for (int index = 0; index < count; index++)
        {
            int typeIndex = PickWeighted(rng, typeWeights.ToArray());
            PlanetType type = PLANET_TYPES[typeIndex];
            int[] rich = new int[RES_COUNT];
            for (int r = 0; r < RES_COUNT; r++)
            {
                rich[r] = Clamp(type.Base[r] + rng.NextInt(3) - 1, 0, 4);
            }
            // Звездата тегли: червената дава газ, жълтата метал, синята кристал.
            if (system.Cls == 0) rich[1] = MinOf(5, rich[1] + 1);
            else if (system.Cls == 1) rich[0] = MinOf(5, rich[0] + 1);
            else rich[2] = MinOf(5, rich[2] + 1);
            Planet planet = new Planet(world.Planets.Count, system.Id, index, typeIndex, rich);
            world.Planets.Add(planet);
            system.Planets.Add(planet.Id);
        }
    }
}

Пробвай

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

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

var systems = new List<StarSystem>();
for (int i = 0; i < 6; i++) systems.Add(new StarSystem(i, i * 10, 0));
(int, int)[] lanes = { (0, 1), (1, 2), (2, 3), (0, 4), (4, 3), (3, 5) };
foreach (var (a, b) in lanes) AddLane(systems, a, b);
Console.WriteLine(string.Join(" ", Bfs(systems, 0)));

Отговор

1 2 3 3 2 4

0 1 2 2 1 3

0 1 2 3 1 4

Провери

Пробвай

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

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

static void Connect(List<StarSystem> systems, Random rng)
{
    int count = systems.Count;
    var inTree = new bool[count];
    inTree[0] = true;
    for (int step = 1; step < count - 1; step++)
    {
        int bestA = -1;
        int bestB = -1;
        int bestD = 0;
        for (int a = 0; a < count; a++)
        {
            if (!inTree[a]) continue;
            for (int b = 0; b < count; b++)
            {
                if (inTree[b]) continue;
                int d = SquaredDistance(systems[a], systems[b]);
                if (bestA < 0 || d < bestD)
                {
                    bestA = a;
                    bestB = b;
                    bestD = d;
                }
            }
        }
        AddLane(systems, bestA, bestB);
        inTree[bestB] = true;
    }
    for (int a = 0; a < count; a++)
    {
        int best = -1;
        int bestD = 0;
        for (int b = 0; b < count; b++)
        {
            if (b == a || HasLane(systems, a, b)) continue;
            int d = SquaredDistance(systems[a], systems[b]);
            if (best < 0 || d < bestD)
            {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems[a].Links.Count < 4 && systems[best].Links.Count < 4 && rng.Chance(55))
        {
            AddLane(systems, a, best);
        }
    }
}

int ok = 0;
for (int seed = 1; seed <= 200; seed++)
{
    if (IsConnected(Galaxy(seed))) ok++;
}
Console.WriteLine("семена 1-200: свързани " + ok + " от 200");

Изход

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

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

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

1static void Connect(List<StarSystem> systems, Random rng)2{3 int count = systems.Count;4 var inTree = new bool[count];5 inTree[0] = true;6 for (int step = 1; step < count - 1; step++)7 {8 int bestA = -1;9 int bestB = -1;10 int bestD = 0;11 for (int a = 0; a < count; a++)12 {13 if (!inTree[a]) continue;14 for (int b = 0; b < count; b++)15 {16 if (inTree[b]) continue;17 int d = SquaredDistance(systems[a], systems[b]);18 if (bestA < 0 || d < bestD)19 {20 bestA = a;21 bestB = b;22 bestD = d;23 }24 }25 }26 AddLane(systems, bestA, bestB);27 inTree[bestB] = true;28 }29 for (int a = 0; a < count; a++)30 {31 int best = -1;32 int bestD = 0;33 for (int b = 0; b < count; b++)34 {35 if (b == a || HasLane(systems, a, b)) continue;36 int d = SquaredDistance(systems[a], systems[b]);37 if (best < 0 || d < bestD)38 {39 best = b;40 bestD = d;41 }42 }43 if (best >= 0 && bestD <= 420 && systems[a].Links.Count < 4 && systems[best].Links.Count < 4 && rng.Chance(55))44 {45 AddLane(systems, a, best);46 }47 }48}4950int ok = 0;51for (int seed = 1; seed <= 200; seed++)52{53 if (IsConnected(Galaxy(seed))) ok++;54}55Console.WriteLine("семена 1-200: свързани " + ok + " от 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. Какво би станало, ако допълнителните пътища се добавят без дървото?

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

Провери

Започни урока отначало

Свързани уроци

• Нужно отпреди: Конструктори и this · Методи на обекта · static: общото за всички · Списъци
• Задачи по темата: Epic Cosmos: империята