The galaxy from a seed

In short: Epic Cosmos is a whole space strategy built lesson by lesson. The first lesson builds the galaxy: a seeded generator, 12 to 20 systems on a 5 by 4 grid, lanes as a graph (first a minimum spanning tree, then extra ones), a connectivity check with breadth-first search and weighted planets.

Problem

A new galaxy every time

In this series we make a second game, very different from Arcanum: Epic Cosmos, a turn-based space strategy, again whole and again in the console. There is no single hero walking over a map. You run an empire: one system with a capital, a few resources and a first fleet. You colonise planets, research technologies, build a fleet and compete with two or three rivals who play on their own. Victory is conquering the galaxy, researching the Stargate or winning on economy, and if nobody manages it, the strongest wins after 150 turns.

A game like this only makes sense if every game is in a new galaxy: the systems are elsewhere, the lanes run elsewhere, the planets are rich in other things. But there is the opposite demand too. A bug that a player reports has to repeat exactly. A save must not weigh a whole galaxy. And the site check runs the game in four languages and compares the outputs byte by byte.

Both demands fit into one number: the seed. The galaxy is not stored, it is made again from the seed, the same every time. This lesson is about how it is made. It starts with the game and then builds its first part.

The start of the game

Turn 1/150  Terran Empire (A)                           score 20
M70+8 G60+4 C20+3 U5+1  science +3
Nothing is being researched (r number). Banked science: 0
Terran Empire starts in the Elara system: a capital, a
shipyard, a lab and your first fleet.
Colonise planets, research technologies, build a fleet. In
battle I beats B, B beats F, F beats I.
Victory: conquer everyone, research the Stargate or produce
9800. After 150 turns the strongest wins. Type help.

Enter or map: back to the map   help: commands

Try it

Play

This is the real game: the JavaScript version, running in the browser. There are no keys here. You type a command on the line under the screen and press Enter. Start with help, then map, then sys 1: you will see the map, the system you are in and its planets.

Epic Cosmos: the empire

One system, a first fleet and a whole galaxy. The rivals are already thinking.

▶ Play

CommandSendNew game

Type the commands on the line below and press Enter (help lists them all; an empty line is map). Saves stay in this browser.

The most important commands (help shows all of them, an empty line is map):

• map shows the map of the galaxy: [ 1 ] are the systems, the dots are the lanes, the letters are the empires.
• sys N shows system N: its planets, what they produce and which fleets are there.
• emp shows the empires, tech the technology tree, fleets the fleets.
• col P colonises planet P, b mine P builds a mine on it, r X researches a technology.
• ship T N P builds N ships of type T, go A B sends a fleet from system A to B along the lanes.
• end ends the turn, wait N skips up to N turns, save 1 and load 1 are for saving.

Victory is one of three: conquest (every empire except yours falls), science (you research the Stargate, the last technology) or economy (you produce 9800 in total). The game lasts 150 turns at most.

More precisely, if you are curious

The game in the browser is the same file you will see in the lessons and run on your computer. Only the block that reads the arguments and writes the saves to files in Node is replaced: here the input comes from the field under the screen, and the saves are in the browser's memory (localStorage). Every new game on the page gets a seed from the clock, so its galaxy differs from the one on the maps below (those use seed 2026, the terminal default). The save keeps the seed.

The idea

What is in it

• A galaxy of 12 to 20 systems and 3 or 4 empires. Each system has one to three planets. There are four resources: metal (M), gas (G), crystal (C) and uranium (U).
• Planets and buildings. You colonise a planet and build a mine (more resources), a lab (science), a shipyard (ships) and a fortress (defence).
• A technology tree: thirteen technologies with prerequisites, from “Deep drilling” to “Stargate”. You cannot research something before you have researched what it depends on.
• Fleets. Four kinds of ship: interceptor, bomber, frigate and dreadnought. In battle the interceptor beats the bomber, the bomber beats the frigate and the frigate beats the interceptor (rock, paper, scissors). Fleets move along the lanes.
• A battle where the moves are resolved at the same time. All the orders of a turn are carried out together, not one after another.
• Rivals with artificial intelligence and a character. Warlord (attacks), Builder (expands and builds) and Scholar (chases science). Each one weighs what brings the most benefit this turn.
• Diplomacy: peace and war, with a minimum time of peace. Random events: a meteor, pirates, unrest, a breakthrough and more.
• Victory in three ways, saving in three slots and a simulation of thousands of AI-only games that is used to tune the balance.

The whole playthrough that the game is checked with is 192 commands and 5175 lines of output: from the first turn to the end.

The idea

The map of the code

The game is one file of about 3900 lines in each language. Inside it is divided into parts (regions), and each part belongs to one of six layers:

Layer	Parts	Lines
Data and text	io-text text data data-load	1023
Input, output, drawing	random buffer terminal map-draw	230
The screens and the commands	screen screen-stack screens commands	584
The world: galaxy and technologies	world graph galaxy-gen tech-tree topo event-bus	474
The empires: fleets, economy, rivals	fleets battle economy diplomacy events ai-rivals turn victory	1194
Saving, simulation, running	save load simulate main node	395

The numbers are from the JavaScript version and are computed when the site is built. Some of the parts you already know from Arcanum: the random generator, the buffer and the screens, the screen stack and the event bus are the same ideas. What is new is in the layers “The world” and “The empires”. This lesson is about random, world, graph and galaxy-gen.

The idea

One code, four languages, one output

The game is written four times: in Java, C#, Python and JavaScript, part by part and with the same names. The site check runs it in all four languages with the recorded 192 commands (in Bulgarian, English, German and Spanish) and demands exactly the same output, byte by byte. It runs the balance simulation too. If one version rolls a die differently, the galaxy is another one and the check fails.

Here is the map from the first turn (the command map) of the galaxy with seed 2026. The systems are [ 1 ] … [16], the dots between them are the lanes, and Aa, Bb, Cc and Dd are the capitals of the four empires.

Turn 1/150  Terran Empire (A)                           score 20
M70+8 G60+4 C20+3 U5+1  science +3
Nothing is being researched (r number). Banked science: 0
    [ 1]..........[ 2]..
    Aa            .   ...[ 3]........[ 4]..........[ 5]
                         .. ..     ..Bb .          . .
                           ....  ..      ..         .
                             [ 6]          .     .[ 8]
                             . .          [ 7]... .  .
                               .          ..         .
                               .         .            .
              ...[10]........[11].....[12]            .
      [ 9]....   . . ...     . .     ..   ...        [13]
      Dd   ....    .    ....   .   ..        ...     Cc
               .... .       ... ...             ...  .
                  [14]........[15]                [16]
                  .           .                   .

A:Terran Empire C:Lyra Union    D:Vega Academy  B:Orion Hegemon

help: commands   end: end the turn   sys N: a system

And the system you start in (sys 1): two planets (one is yours, with a mine, a lab, a shipyard and a fortress) and the first fleet.

Turn 1/150  Terran Empire (A)                           score 20
M70+8 G60+4 C20+3 U5+1  science +3
Nothing is being researched (r number). Banked science: 0
System 1 Elara, yellow star. Lanes to: 2
Planet 1 Elara I, ocean (Terran Empire)
  richness M3 G3 C2 U1
  mines 1  lab yes  yard yes  fort 1
Planet 2 Elara II, gas giant (free)
  richness M1 G4 C1 U0
Fleet of Terran Empire: 3I 2B 2F

Enter or map: back to the map   help: commands

How does the output come out the same when every language has its own Random? The game does not use the built-in generator. It has its own, small and identical everywhere, with whole numbers only. It is the first topic of the lesson.

The idea

Run it on your computer

The whole file is here: [Cosmos.java](/games/cosmos/en/Cosmos.java), [Cosmos.cs](/games/cosmos/en/Cosmos.cs), [cosmos.py](/games/cosmos/en/cosmos.py), [cosmos.js](/games/cosmos/en/cosmos.js). Put it in an empty folder and run it:

dotnet new console -n Cosmos
cd Cosmos
# replace Program.cs with Cosmos.cs
dotnet run

In the terminal the game clears the screen and uses colour. With --plain it prints the frames as plain text. With --seed=2026 the galaxy is always the same (that is also the default seed), and with --lang=en the game is in English (there are de and es too). With --simulate=200 it plays 200 AI-only games and prints the balance. The saves are in a saves folder next to the game.

The program is one file with several classes and Main in Cosmos.

The idea

How we will build it

The module is six lessons. Each one takes a part of the game, explains why it is the way it is and builds it with smaller programs that you can run, then shows the same part in the real file.

1. The galaxy from a seed (this lesson): a seeded generator, stars and planets, lanes as a graph, connectivity.
2. The technology tree: a directed graph without cycles, prerequisites, topological order, what can be researched now.
3. Fleets and space battle: resolving the moves at the same time, ship roles, a battle simulation.
4. The rivals: empires with artificial intelligence, utility scoring, the character of an empire.
5. The turn of the galaxy: the phases of a turn, random events, diplomacy, the event bus.
6. The whole strategy: victory, saving, balance with a simulation.

The idea

The seed

The generator is in the random region of the game. Here it is, as in the canon:

// mulberry32: a small seeded generator. Only 32-bit integers (uint and unchecked), so it
// gives the same sequence in every language.
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);
        }
    }

    // From 0 to n-1, no fractions.
    public int NextInt(int n)
    {
        return (int)(Next32() % (uint)n);
    }

    // From min to max, both included.
    public int Range(int min, int max)
    {
        return min + NextInt(max - min + 1);
    }

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

    // Shuffles the list in place (Fisher-Yates, from the back).
    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;
        }
    }
}

Only three lines are the core: next32 changes one number (state) and derives another from it, nextInt(n) takes its remainder when divided by n, and range, chance and shuffle are built on nextInt. Nothing else changes between two calls. That is why two copies of the generator with the same starting number (the seed) give the same sequence, and with a different number they give a different one.

The program shows this: three generators, two with seed 2026 and one with 2027, give six numbers each from 0 to 99. Then a list of eight cells is shuffled with shuffle, the way the game shuffles the cells of the grid:

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 {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($"shuffled cells: {string.Join(" ", cells)}");

Output

seed 2026: 75 58 22 36 57 62
seed 2026: 75 58 22 36 57 62
seed 2027: 50 47 63 23 32 32
shuffled cells: 3 2 6 4 1 0 5 7

The first two lines are identical down to the number, and the third has nothing in common with them. The shuffle is the same in the four languages because shuffle only calls nextInt in a strictly fixed order: from the end to the start, and at each step it picks whom to swap with. This is the Fisher-Yates shuffle.

In C#, Random here is the game's own class, not System.Random. The state is a uint, and the unchecked block lets the multiplications overflow as they do in the other languages.

The idea

The galaxy is a graph

A galaxy is two things: systems (stars with planets) and lanes between them, along which fleets move. A structure like this is called a graph: the systems are the vertices, the lanes are the edges. A lane is between two systems and works in both directions.

The simplest way to store it is for every system to know its neighbours. A system is a class with a number, a place on the map and a list 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;
    }
}

In the game the same class is in the world region: it also has a name, the colour of the star (red, yellow or blue) and a list of its planets.

class StarSystem
{
    public int Id;
    public string Name;
    public int X;
    public int Y;
    // The class of the star: 0 red, 1 yellow, 2 blue.
    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 lane between A and B means that B is in A's list and A is in B's list. That is why a lane is added by one function that writes in two places. The lists are kept sorted by number: insertSorted inserts at the right place, not at the end.

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);
}

The order matters for one thing: when the game walks through the neighbours, it always sees them in the same order, in every language. If they were in the order they were added, the different versions would reach the same things by a different path and the outputs would differ.

The program creates six systems, adds the lanes in a jumbled order and prints the neighbours of each. The system numbers on the screen start from 1, and in memory from 0: numbers adds 1 before showing them.

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 {system.Id + 1}: {Numbers(system.Links)}");
}
Console.WriteLine("lane 1-3: " + (HasLane(systems, 0, 2) ? "yes" : "no"));
Console.WriteLine("lane 1-4: " + (HasLane(systems, 0, 3) ? "yes" : "no"));

Output

system 1: 2 3 5
system 2: 1 5
system 3: 1 4
system 4: 3 6
system 5: 1 2
system 6: 4
lane 1-3: yes
lane 1-4: no

Look at system 1: the lanes to systems 5 (added first), 3 and 2 are printed as “2 3 5”, in ascending order, not in the order of adding. Systems 1 and 3 have a lane, 1 and 4 do not.

The idea

Is the galaxy connected?

The game only makes sense if you can get from every system to every other one. Otherwise fleets cannot pass, and an empire on an island cannot be attacked. We want a connected graph: from every vertex there is a path to every other.

The check is breadth-first search (BFS). You start from one system and send out a wave: first the system itself is at distance 0, then its neighbours at 1, their neighbours at 2, and so on. The queue holds the systems waiting for their turn. The systems the wave does not reach stay at −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;
}

The graph is connected exactly when the wave from system 1 reaches all of them: no −1.

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

The program builds two “islands” (systems 1 to 4 and 5 to 7), prints the distances from system 1 and whether the galaxy is connected. Then it adds one lane between them:

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("distances from system 1: " + string.Join(" ", Bfs(systems, 0)));
Console.WriteLine("connected: " + (IsConnected(systems) ? "yes" : "no"));

AddLane(systems, 3, 4);
Console.WriteLine("distances from system 1: " + string.Join(" ", Bfs(systems, 0)));
Console.WriteLine("connected: " + (IsConnected(systems) ? "yes" : "no"));

Output

distances from system 1: 0 1 2 3 -1 -1 -1
connected: no
distances from system 1: 0 1 2 3 4 5 6
connected: yes

Before the lane, systems 5, 6 and 7 are −1: the wave did not pass. After the lane between 4 and 5 the wave reaches them with distances 4, 5 and 6.

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

Check

In the game the same function is in the graph region, but the search also keeps the parent of every system: the one it was discovered from. Walking back along the parents gives the shortest path:

// Breadth-first search from one system: distance in lanes (-1 is unreachable) and the parent on the way.
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 };
}

// The shortest path as a list of systems, both ends included; empty if there is no path.
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;
}

The game uses this path when a fleet heads for a distant target: go 1 9 does not say which systems to pass through, and on every turn the fleet takes the next step of the shortest path (nextStep). The rivals' artificial intelligence uses the same function.

One detail that is only honest to mention: isConnected is in the canon, but the game itself never calls it. Connectivity is guaranteed by the tree, and the function is there for checking, like the one in the program above and in the exercise below.

The idea

Stars on a grid

Now let us make the galaxy itself. Systems are not thrown at random points of the map: some would pile up on top of each other, and others would be left alone in empty space. The game uses a grid: the map is 5 columns by 4 rows, 20 cells. From them 12 to 20 are chosen, and in each chosen cell the star sits at a random place.

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;
}

Three steps: shuffle shuffles the numbers of the cells, the first count are taken and sorted (so the systems are numbered from left to right and from top to bottom), and in each cell the star gets a small random offset. The cells keep the stars apart, and the randomness makes them different from game to game.

In the game the number of systems is not given. The first roll of the generator decides it: 12 + nextInt(9) is a number from 12 to 20.

The idea

Lanes: first the tree, then the extras

What remains is to decide which stars are connected. If you put lanes on random pairs, you cannot be sure nothing will end up on an island. If you put in all the lanes, the map becomes a spider web. The game uses a two-step solution.

First a tree. You start from system 1. At every step you look for the shortest lane from a system in the tree to a system outside it and add it. The new system joins the tree. You repeat until all of them are in. This algorithm is called a minimum spanning tree (Prim). The tree has exactly number of systems − 1 lanes, and it is clear why the graph is connected: each new system enters with one lane to those already connected.

Then the extras. A tree has no cycles: between two systems there is exactly one route, and that route may be long. So every system also gets a lane to the nearest system it has no lane with yet, but only if that system is close enough, neither has 4 lanes already, and the die roll is under 55%. This gives circular routes and a choice.

The distance is the square of the distance, without a root (we only compare which is smaller): dy is multiplied by 3 because the characters in the console are taller than they are wide.

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);
        }
    }
}

Two details make the output the same. With equal distances the first one found wins (d < bestD, not <=), i.e. the smaller number. And the chance (rng.chance(55)) comes last in the condition with &&: the die is rolled only for a lane that would otherwise be added. If it were rolled earlier, both variants would be reasonable, but every roll takes a number from the generator and everything after it would change: the same seeds would give other galaxies.

See it

The galaxy in motion

The twelve systems of the galaxy with seed 18. Watch the counters at the top: the islands drop from 12 to 1 while the lanes of the tree grow; then come the extra lanes in another colour, and last the wave of the search.

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);
        }
    }
}

Step by step, in words

1. 12 stars on a 5 by 4 grid (20 cells): the chosen cells light up. There is not a single lane yet, so every system is an island: 12 islands.
2. First the minimum spanning tree (Prim). It starts at system 1. Each step looks for the shortest lane from a system in the tree to a system outside it.
3. The lane found is added and the new system joins the tree. After 5 lanes, 7 islands are left: every lane joins two islands into one.
4. 11 lanes and one island. Each new system enters with exactly one lane, so none can be left alone: the galaxy is connected before the extra lanes.
5. Then the extra lanes (another colour): to the nearest unlinked system, if it is close, has fewer than 4 lanes and the roll is under 55%. That gives 3 detours.
6. The check: breadth-first search from system 1. The wave moves layer by layer and writes down each system's distance in lanes (0, 1, 2…).
7. Not a single −1: the wave reached all 12 systems, so the galaxy is connected. With the same seed this picture is the same every time.

The idea

The whole galaxy from one seed

What is left is to put it together: seed, number of systems, stars, lanes. The function galaxy(seed) is the whole generator. The second function, describe, turns a galaxy into text: that way two galaxies are compared with a single ==.

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;
}

The program makes the galaxy with seed 18 (12 systems, 14 lanes: 11 from the tree and 3 extra), then makes it again with the same seed and with the next one, and finally checks 200 different seeds:

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} ({lanes - systems.Count + 1} extra)");
Console.WriteLine("connected: " + (IsConnected(systems) ? "yes" : "no"));

string first = Describe(systems);
Console.WriteLine("same seed again, same galaxy: " + (Describe(Galaxy(18)) == first ? "yes" : "no"));
Console.WriteLine("another seed, another galaxy: " + (Describe(Galaxy(19)) != first ? "yes" : "no"));

int ok = 0;
for (int seed = 1; seed <= 200; seed++)
{
    if (IsConnected(Galaxy(seed))) ok++;
}
Console.WriteLine("seeds 1-200: connected " + ok + " of 200");

Output

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
lanes: 14 (3 extra)
connected: yes
same seed again, same galaxy: yes
another seed, another galaxy: yes
seeds 1-200: connected 200 of 200

Three things matter here. First, the same seed is the same galaxy down to the last coordinate. Second, the next seed is a completely different galaxy. Third, all 200 are connected: this is not luck but a consequence of the tree. This check is a small property test: we do not ask “what does this galaxy look like” but “is it true for every galaxy that it is connected”.

This is what the real function in the game looks like. It does the same, but it also gives each star a name (the names are shuffled with one more shuffle) and a colour (red, yellow or blue), and it works on the shared world 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);
    }
    // The minimum spanning tree (Prim): on equal distances the smaller number wins.
    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;
    }
    // Extra lanes: to the nearest neighbor not yet linked, if it is not too far.
    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);
        }
    }
}

Everything the game knows lives in the class World: the seed, the generator, the systems, the planets, the empires and the fleets. That is why a save is in one place and newWorld(seed) is the only thing that makes a galaxy:

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;
    }
}

And how newWorld uses it. The seed becomes the world: the number of systems, the lanes, then the capitals of the empires and the planets, and finally each empire gets a home world:

// The whole world from one seed. human is the player (none in the simulation), personalities is an optional
// list of characters, one per empire.
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;
}

The capitals are chosen with a breadth-first search: the first is the leftmost system, and each next one is the farthest (by lanes) from those already chosen. That way the empires start as far from each other as possible:

// The capitals: the first is the leftmost system; each next one is farthest (by lanes) from those already chosen.
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;
}

The idea

Planets with weights

Every system has one to three planets, and they are not all equally likely: one planet has a 30% chance, two have 45%, three have 25%. The kind of planet has weights too (rocky, gas giant, icy, ocean, volcanic). We need a function that picks an element by weight.

The idea: roll a number from 0 up to the sum of the weights and walk along the list, subtracting the weight of each element, until the roll is smaller than the current weight.

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;
}

With weights 30, 45 and 25 the sum is 100. A roll from 0 to 29 is index 0, from 30 to 74 index 1, from 75 to 99 index 2. The program rolls 1000 times (the planets are index + 1) and then separately takes the planet counts of the first eight systems:

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($"planets in 1000 systems: 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($"the first 8 systems: {Numbers(planets)}");

Output

planets in 1000 systems: 1=299 2=467 3=234
the first 8 systems: 2 3 2 2 3 3 1 1

Out of 1000 systems about 30%, 45% and 25% have 1, 2 and 3 planets. It is not exact: weights are probabilities, not quotas. But with the same seed the numbers are always the same.

A planet is a class with a kind, richness for the four resources and an owner:

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;
    }
}

The real generatePlanets uses the same function twice: for the count and for the kind of each planet. Then it rolls one more number for each resource (richness from 0 to 4), and the colour of the star adds one to a resource: red to gas, yellow to metal, blue to crystal.

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);
            }
            // The star weighs in: red gives gas, yellow metal, blue crystal.
            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);
        }
    }
}

Try it

Predict the output

Six systems, numbered from 0. The lanes are 0-1, 1-2, 2-3, 0-4, 4-3 and 3-5: a ring of five systems and one more attached to it. What does the program print?

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)));

Answer

1 2 3 3 2 4

0 1 2 2 1 3

0 1 2 3 1 4

Check

Try it

Find the bug

A colleague changed one line in the tree loop. The program makes galaxies from 200 seeds and counts the connected ones. Before, all 200 were; now it is:

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("seeds 1-200: connected " + ok + " of 200");

Output

seeds 1-200: connected 150 of 200

Which line is guilty?

Pick the line with the bug.

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("seeds 1-200: connected " + ok + " of 200");

Check

More precisely

What is not in this system

A galaxy from a seed has few rules, but behind them are choices.

The tree is simple. Prim's algorithm here has three nested loops: for a tree of 20 systems that is a few thousand comparisons. In a bigger graph (millions of vertices) a priority queue is used and Prim runs in O(E log V). Here the plain loop is shorter, easy to read and identical in the four languages.

The extra lanes are not guaranteed. That is why some galaxies are almost trees: long chains with no detours. This is a decision for the game: such maps are more tactical (a key pass to guard). How many extra lanes there are (55%, at most 4 per system, nearby) is tuned with a simulation, like the balance.

Connectivity is a choice, not a law. In other games islands are fine: not everything is reachable. Here it is the other way round: connectivity is a condition of the game. That is why it is good to check it, as the program does with 200 seeds.

The seed is not the whole story. The same seed gives the same galaxy only as long as the generator calls nextInt in the same order. If you add one new roll at the start, all the galaxies of all the old seeds change, and old saves load into a different world. That is why in a real game a change to the generation must be a change of the version: the game's save has a format version for exactly such cases.

Lanes work in both directions. The graph here is undirected. The technology tree (the next lesson) is different: “A must come before B” is one-way. There the graph is directed.

Exercise

Islands

Solve the task in your editor.

Islands. The program reads from the input, on the first line, the number of systems n and the number of lanes m, and then m lines with two numbers each (from 1). It prints how many islands the galaxy has (islands are groups of systems connected to each other), how many systems the largest island has and whether the galaxy is connected.

With input 8 5 | 1 2 | 2 3 | 4 5 | 6 7 | 7 8 (one per line) the output is:

Output

islands: 3
largest island: 3
connected: no

Hint: run a breadth-first search from the first system that has not been seen yet, and mark everything it reaches. As many times as you start again, that is how many islands there are.

More tasks

• The shortest path. Extend the program to read two more numbers and print the shortest path between them through the systems, or “no path” if there is none. The parent of each system is the key.
• How many lanes to add? What is the smallest number of lanes to add to make a galaxy with k islands connected? Try a few examples and find the rule.
• How many seeds are not connected without the tree? Remove the tree loop and run the check on 200 seeds. How many galaxies are connected by the extra lanes alone?

Test

Test yourself

1. Why is the galaxy the same every time with the same seed?

Because Random in every language gives the same sequenceBecause the generator is a formula: the next number depends only on the previous one, and the code calls the generator in the same orderBecause the galaxy is saved to disk and read back from there

2. A galaxy with 12 systems has a minimum spanning tree. How many lanes does it have?

126611

3. After a breadth-first search from system 1 the distances are “0 1 2 3 -1 -1 -1”. What does −1 mean?

The system was already visitedThe system is at distance minus one, behind the startThe system was not reached: there is no path to it, so the galaxy is not connected

4. Weights 30, 45 and 25, and the roll is 55. How many planets does the system get?

231

5. The Epic Cosmos save contains a line seed=… Why does it not keep the systems and lanes too?

Because the lanes are invented again and may be differentBecause they are kept somewhere elseBecause the galaxy is made again from the seed and comes out the same; the save keeps only what the game changes

6. What would happen if the extra lanes were added without the tree?

Some galaxies would not be connected: the extra lanes are random and nothing guarantees that they connect everythingThe galaxy would always be disconnectedNothing: the lanes would still connect everything

Check

Start the lesson over

Related lessons

• Builds on: Constructors and this · Instance methods · static: what all objects share · Lists
• Tasks on this topic: Epic Cosmos: the empire