Die Galaxie aus einem Startwert

Kurz gesagt: Epic Cosmos ist eine ganze Weltraumstrategie, die Lektion für Lektion entsteht. Die erste Lektion baut die Galaxie: ein Generator mit Startwert, 12 bis 20 Systeme auf einem 5-mal-4-Raster, Wege als Graph (zuerst ein minimaler Spannbaum, dann zusätzliche), eine Prüfung des Zusammenhangs mit Breitensuche und Planeten mit Gewichten.

Problem

Jedes Mal eine neue Galaxie

In dieser Reihe bauen wir ein zweites Spiel, ganz anders als Arkanum: Epic Cosmos, eine rundenbasierte Weltraumstrategie, wieder ganz und wieder in der Konsole. Hier läuft nicht ein einzelner Held über eine Karte. Du führst ein Reich: ein System mit einer Hauptstadt, ein paar Rohstoffe und eine erste Flotte. Du besiedelst Planeten, erforschst Technologien, baust eine Flotte und trittst gegen zwei oder drei Rivalen an, die allein spielen. Gewonnen wird durch Eroberung der Galaxie, durch die Erforschung des Sternentors oder durch Wirtschaft, und wenn es keiner schafft, gewinnt nach 150 Runden der Stärkste.

Ein solches Spiel ergibt nur Sinn, wenn jede Partie in einer neuen Galaxie spielt: Die Systeme liegen woanders, die Wege laufen woanders, die Planeten sind reich an anderem. Es gibt aber auch die gegenteilige Forderung. Ein Fehler, den ein Spieler meldet, muss sich genau wiederholen. Ein Spielstand darf nicht eine ganze Galaxie wiegen. Und die Prüfung der Seite lässt das Spiel in vier Sprachen laufen und vergleicht die Ausgaben Byte für Byte.

Beide Forderungen passen in eine Zahl: den Startwert. Die Galaxie wird nicht gespeichert, sondern aus dem Startwert neu erzeugt, jedes Mal gleich. Diese Lektion zeigt, wie das geht. Sie beginnt mit dem Spiel und baut dann seinen ersten Teil.

Der Anfang des Spiels

Runde 1/150  Terranisches Reich (A)                    Punkte 20
M70+8 G60+4 C20+3 U5+1  Forschung +3
Nichts wird erforscht (r Nummer). Gesparte Forschung: 0
Terranisches Reich beginnt im System Elara: Hauptstadt, Werft,
Labor und deine erste Flotte.
Besiedle Planeten, erforsche Technologien, baue eine Flotte.
Im Kampf schlägt I das B, B schlägt F, F schlägt I.
Sieg: alle erobern, das Sternentor erforschen oder 9800
produzieren. Nach 150 Runden gewinnt der Stärkste. Tippe help.

Enter oder map: zur Karte   help: Befehle

Probier es aus

Spielen

Das ist das echte Spiel: die JavaScript-Version, im Browser gestartet. Hier gibt es keine Tasten. Du tippst einen Befehl in die Zeile unter dem Bildschirm und drückst Enter. Beginne mit help, dann map, dann sys 1: Du siehst die Karte, das System, in dem du bist, und seine Planeten.

Epic Cosmos: das Imperium

Ein System, eine erste Flotte und eine ganze Galaxie. Die Rivalen denken schon.

▶ Spielen

BefehlSendenNeues Spiel

Tippe die Befehle in die Zeile unten und drücke Enter (help zeigt alle; eine leere Zeile ist map). Spielstände bleiben in diesem Browser.

Die wichtigsten Befehle (help zeigt alle, eine leere Zeile ist map):

• map zeigt die Karte der Galaxie: [ 1 ] sind die Systeme, die Punkte sind die Wege, die Buchstaben sind die Reiche.
• sys N zeigt System N: seine Planeten, was sie liefern und welche Flotten dort stehen.
• emp zeigt die Reiche, tech den Technologiebaum, fleets die Flotten.
• col P besiedelt Planet P, b mine P baut dort eine Mine, r X erforscht eine Technologie.
• ship T N P baut N Schiffe vom Typ T, go A B schickt eine Flotte von System A nach B über die Wege.
• end beendet die Runde, wait N überspringt bis zu N Runden, save 1 und load 1 sind zum Speichern.

Der Sieg ist einer von dreien: Eroberung (alle Reiche außer deinem fallen), Wissenschaft (du erforschst das Sternentor, die letzte Technologie) oder Wirtschaft (du produzierst insgesamt 9800). Das Spiel dauert höchstens 150 Runden.

Genauer, für Neugierige

Das Spiel im Browser ist dieselbe Datei, die du in den Lektionen siehst und auf deinem Computer startest. Nur der Block, der in Node die Argumente liest und die Spielstände in Dateien schreibt, ist ersetzt: Hier kommt die Eingabe aus dem Feld unter dem Bildschirm, und die Spielstände liegen im Speicher des Browsers (localStorage). Jedes neue Spiel auf der Seite bekommt einen Startwert von der Uhr, darum unterscheidet sich seine Galaxie von der auf den Karten weiter unten (die haben den Startwert 2026, den Standard im Terminal). Der Spielstand behält den Startwert.

Die Idee

Was alles drinsteckt

• Eine Galaxie aus 12 bis 20 Systemen und 3 oder 4 Reiche. Jedes System hat ein bis drei Planeten. Es gibt vier Rohstoffe: Metall (M), Gas (G), Kristall (C) und Uran (U).
• Planeten und Gebäude. Du besiedelst einen Planeten und baust eine Mine (mehr Rohstoffe), ein Labor (Forschung), eine Werft (Schiffe) und eine Festung (Verteidigung).
• Ein Technologiebaum: dreizehn Technologien mit Voraussetzungen, von „Tiefbohrung“ bis „Sternentor“. Du kannst nichts erforschen, bevor du das erforscht hast, wovon es abhängt.
• Flotten. Vier Schiffsarten: Abfangjäger, Bomber, Fregatte und Schlachtschiff. Im Kampf schlägt der Abfangjäger den Bomber, der Bomber die Fregatte und die Fregatte den Abfangjäger (Stein, Schere, Papier). Flotten bewegen sich über die Wege.
• Ein Kampf, bei dem die Züge gleichzeitig aufgelöst werden. Alle Befehle einer Runde werden zusammen ausgeführt, nicht nacheinander.
• Rivalen mit künstlicher Intelligenz und Charakter. Kriegsherr (greift an), Baumeister (expandiert und baut) und Gelehrter (jagt der Forschung nach). Jeder wägt ab, was ihm in dieser Runde am meisten bringt.
• Diplomatie: Frieden und Krieg, mit einer Mindestdauer des Friedens. Zufällige Ereignisse: ein Meteorit, Piraten, Unruhen, ein Durchbruch und mehr.
• Sieg auf drei Wegen, Speichern in drei Plätzen und eine Simulation von tausenden Partien nur mit KI, mit der die Balance eingestellt wird.

Der ganze Durchlauf, mit dem das Spiel geprüft wird, sind 192 Befehle und 5175 Zeilen Ausgabe: von der ersten Runde bis zum Ende.

Die Idee

Die Karte des Codes

Das Spiel ist eine Datei von etwa 3900 Zeilen in jeder Sprache. Darin ist es in Teile (Regionen) gegliedert, und jeder Teil gehört zu einer von sechs Schichten:

Schicht	Teile	Zeilen
Daten und Texte	io-text text data data-load	1023
Eingabe, Ausgabe, Zeichnen	random buffer terminal map-draw	230
Die Bildschirme und die Befehle	screen screen-stack screens commands	584
Die Welt: Galaxie und Technologien	world graph galaxy-gen tech-tree topo event-bus	474
Die Reiche: Flotten, Wirtschaft, Rivalen	fleets battle economy diplomacy events ai-rivals turn victory	1194
Speichern, Simulation, Start	save load simulate main node	395

Die Zahlen stammen aus der JavaScript-Version und werden beim Bauen der Seite berechnet. Einiges kennst du schon aus Arkanum: der Generator random, der Puffer und die Bildschirme, der Stapel von Bildschirmen und der Ereignisbus sind dieselben Ideen. Neu ist die Schicht „Die Welt“ und „Die Reiche“. Diese Lektion handelt von random, world, graph und galaxy-gen.

Die Idee

Ein Code, vier Sprachen, eine Ausgabe

Das Spiel ist viermal geschrieben: in Java, C#, Python und JavaScript, Teil für Teil und mit denselben Namen. Die Prüfung der Seite lässt es in allen vier Sprachen mit den aufgezeichneten 192 Befehlen laufen (auf Bulgarisch, Englisch, Deutsch und Spanisch) und verlangt Byte für Byte dieselbe Ausgabe. Sie lässt auch die Balance-Simulation laufen. Würfelt eine Version anders, ist die Galaxie eine andere, und die Prüfung schlägt fehl.

Hier die Karte der ersten Runde (der Befehl map) der Galaxie mit Startwert 2026. Die Systeme sind [ 1 ] … [16], die Punkte dazwischen sind die Wege, und Aa, Bb, Cc und Dd sind die Hauptstädte der vier Reiche.

Runde 1/150  Terranisches Reich (A)                    Punkte 20
M70+8 G60+4 C20+3 U5+1  Forschung +3
Nichts wird erforscht (r Nummer). Gesparte Forschung: 0
    [ 1]..........[ 2]..
    Aa            .   ...[ 3]........[ 4]..........[ 5]
                         .. ..     ..Bb .          . .
                           ....  ..      ..         .
                             [ 6]          .     .[ 8]
                             . .          [ 7]... .  .
                               .          ..         .
                               .         .            .
              ...[10]........[11].....[12]            .
      [ 9]....   . . ...     . .     ..   ...        [13]
      Dd   ....    .    ....   .   ..        ...     Cc
               .... .       ... ...             ...  .
                  [14]........[15]                [16]
                  .           .                   .

A:Terranisches  C:Lyra-Union    D:Vega-Akademie B:Orion-Hegemon

help: Befehle   end: Runde beenden   sys N: ein System

Und das System, in dem du beginnst (sys 1): zwei Planeten (einer gehört dir, mit Mine, Labor, Werft und Festung) und die erste Flotte.

Runde 1/150  Terranisches Reich (A)                    Punkte 20
M70+8 G60+4 C20+3 U5+1  Forschung +3
Nichts wird erforscht (r Nummer). Gesparte Forschung: 0
System 1 Elara, gelber Stern. Wege nach: 2
Planet 1 Elara I, ozeanisch (Terranisches Reich)
  Reichtum M3 G3 C2 U1
  Minen 1  Labor ja  Werft ja  Festung 1
Planet 2 Elara II, Gasriese (frei)
  Reichtum M1 G4 C1 U0
Flotte (Terranisches Reich): 3I 2B 2F

Enter oder map: zur Karte   help: Befehle

Wie kommt dieselbe Ausgabe heraus, wenn jede Sprache ihr eigenes Random hat? Das Spiel nutzt den eingebauten Generator nicht. Es hat einen eigenen, kleinen und überall gleichen, nur mit ganzen Zahlen. Er ist das erste Thema der Lektion.

Die Idee

Auf dem eigenen Computer starten

Die ganze Datei liegt hier: [Cosmos.java](/games/cosmos/de/Cosmos.java), [Cosmos.cs](/games/cosmos/de/Cosmos.cs), [cosmos.py](/games/cosmos/de/cosmos.py), [cosmos.js](/games/cosmos/de/cosmos.js). Leg sie in einen leeren Ordner und starte sie:

java Cosmos.java

Im Terminal löscht das Spiel den Bildschirm und färbt. Mit --plain druckt es die Bilder als einfachen Text. Mit --seed=2026 ist die Galaxie immer dieselbe (das ist auch der Standard-Startwert), und mit --lang=de ist das Spiel auf Deutsch (es gibt auch en und es). Mit --simulate=200 spielt es 200 Partien nur mit KI und druckt die Balance. Die Spielstände liegen im Ordner saves neben dem Spiel.

Java 21 startet eine Datei mit vielen Klassen direkt, ohne javac.

Die Idee

Wie wir es bauen

Das Modul besteht aus sechs Lektionen. Jede nimmt einen Teil des Spiels, erklärt, warum er so ist, und baut ihn mit kleineren Programmen, die du starten kannst; danach zeigt sie denselben Teil in der echten Datei.

1. Die Galaxie aus einem Startwert (diese Lektion): ein Generator mit Startwert, Sterne und Planeten, Wege als Graph, Zusammenhang.
2. Der Technologiebaum: ein gerichteter Graph ohne Kreise, Voraussetzungen, topologische Ordnung, was jetzt erforscht werden kann.
3. Flotten und Weltraumschlacht: gleichzeitiges Auflösen der Züge, Rollen der Schiffe, eine Schlachtsimulation.
4. Die Rivalen: Reiche mit künstlicher Intelligenz, Bewertung des Nutzens, der Charakter eines Reichs.
5. Der Zug der Galaxie: die Phasen einer Runde, zufällige Ereignisse, Diplomatie, der Ereignisbus.
6. Die ganze Strategie: Sieg, Speichern, Balance mit einer Simulation.

Die Idee

Der Startwert

Der Generator steckt in der Region random des Spiels. Hier ist er, wie im Original:

// mulberry32: ein kleiner Generator mit Seed. Nur 32-Bit-Ganzzahlen (int und >>>; der Zustand ist ein long,
// auf 32 Bit maskiert), darum liefert er in jeder Sprache dieselbe Folge.
static class Random {
    long state;

    Random(long seed) {
        this.state = seed & 0xFFFFFFFFL;
    }

    long next32() {
        this.state = (this.state + 0x6d2b79f5L) & 0xFFFFFFFFL;
        int z = (int) this.state;
        z = (z ^ (z >>> 15)) * (z | 1);
        z = z ^ (z + (z ^ (z >>> 7)) * (z | 61));
        return (z ^ (z >>> 14)) & 0xFFFFFFFFL;
    }

    // Von 0 bis n-1, ohne Bruchzahlen.
    int nextInt(int n) {
        return (int) (this.next32() % n);
    }

    // Von min bis max, beide eingeschlossen.
    int range(int min, int max) {
        return min + this.nextInt(max - min + 1);
    }

    boolean chance(int percent) {
        return this.nextInt(100) < percent;
    }

    // Mischt die Liste an Ort und Stelle (Fisher-Yates, von hinten nach vorn).
    void shuffle(List<Integer> items) {
        for (int i = items.size() - 1; i > 0; i--) {
            int j = this.nextInt(i + 1);
            int keep = items.get(i);
            items.set(i, items.get(j));
            items.set(j, keep);
        }
    }
}

Nur drei Zeilen sind der Kern: next32 ändert eine Zahl (state) und leitet daraus eine andere ab, nextInt(n) nimmt ihren Rest bei der Division durch n, und range, chance und shuffle sind auf nextInt aufgebaut. Sonst ändert sich zwischen zwei Aufrufen nichts. Darum liefern zwei Kopien des Generators mit derselben Anfangszahl (dem Startwert) dieselbe Folge, und mit einer anderen Zahl eine andere.

Das Programm zeigt es: drei Generatoren, zwei mit Startwert 2026 und einer mit 2027, liefern je sechs Zahlen von 0 bis 99. Danach wird eine Liste von acht Zellen mit shuffle gemischt, so wie das Spiel die Zellen des Rasters mischt:

int[] seeds = {2026, 2026, 2027};
for (int seed : seeds) {
    Random rng = new Random(seed);
    List<Integer> rolls = new ArrayList<>();
    for (int i = 0; i < 6; i++) rolls.add(rng.nextInt(100));
    System.out.println("Startwert " + seed + ": " + join(rolls));
}

List<Integer> cells = new ArrayList<>();
for (int i = 0; i < 8; i++) cells.add(i);
new Random(2026).shuffle(cells);
System.out.println("gemischte Zellen: " + join(cells));

Ausgabe

Startwert 2026: 75 58 22 36 57 62
Startwert 2026: 75 58 22 36 57 62
Startwert 2027: 50 47 63 23 32 32
gemischte Zellen: 3 2 6 4 1 0 5 7

Die ersten zwei Zeilen sind bis auf die Zahl gleich, die dritte hat nichts mit ihnen zu tun. Das Mischen ist in den vier Sprachen dasselbe, weil shuffle nur nextInt in einer streng festgelegten Reihenfolge aufruft: vom Ende zum Anfang, und in jedem Schritt wird gewählt, mit wem getauscht wird. Das ist der Fisher-Yates-Algorithmus.

In Java ist Random hier die eigene Klasse des Spiels, nicht java.util.Random: Sie hat einen anderen Algorithmus und würde nicht dieselben Zahlen wie die anderen Sprachen liefern.

Die Idee

Die Galaxie ist ein Graph

Eine Galaxie besteht aus zwei Dingen: Systemen (Sterne mit Planeten) und Wegen dazwischen, auf denen sich Flotten bewegen. Eine solche Struktur heißt Graph: Die Systeme sind die Knoten, die Wege die Kanten. Ein Weg liegt zwischen zwei Systemen und gilt in beide Richtungen.

Am einfachsten speicherst du das, indem jedes System seine Nachbarn kennt. Ein System ist eine Klasse mit einer Nummer, einem Ort auf der Karte und einer Liste links:

class StarSystem {
    int id;
    int x;
    int y;
    List<Integer> links = new ArrayList<>();

    StarSystem(int id, int x, int y) {
        this.id = id;
        this.x = x;
        this.y = y;
    }
}

Im Spiel steht dieselbe Klasse in der Region world: Sie hat noch einen Namen, die Farbe des Sterns (rot, gelb oder blau) und eine Liste seiner Planeten.

static class StarSystem {
    int id;
    String name;
    int x;
    int y;
    // Die Klasse des Sterns: 0 rot, 1 gelb, 2 blau.
    int cls = 1;
    List<Integer> links = new ArrayList<>();
    List<Integer> planets = new ArrayList<>();

    StarSystem(int id, String name, int x, int y) {
        this.id = id;
        this.name = name;
        this.x = x;
        this.y = y;
    }
}

Ein Weg zwischen A und B heißt, dass B in der Liste von A und A in der Liste von B steht. Darum wird ein Weg von einer Funktion hinzugefügt, die an zwei Stellen schreibt. Die Listen werden nach Nummer sortiert gehalten: insertSorted fügt an der richtigen Stelle ein, nicht am Ende.

static void insertSorted(List<Integer> list, int value) {
    int at = list.size();
    while (at > 0 && list.get(at - 1) > value) at--;
    list.add(at, value);
}

static boolean hasLane(List<StarSystem> systems, int a, int b) {
    return systems.get(a).links.indexOf(b) >= 0;
}

static void addLane(List<StarSystem> systems, int a, int b) {
    insertSorted(systems.get(a).links, b);
    insertSorted(systems.get(b).links, a);
}

Die Ordnung ist für eines wichtig: Wenn das Spiel die Nachbarn durchläuft, sieht es sie in jeder Sprache immer in derselben Reihenfolge. Stünden sie in der Reihenfolge des Hinzufügens, kämen die verschiedenen Versionen auf unterschiedlichem Weg zum Gleichen, und die Ausgaben wären verschieden.

Das Programm legt sechs Systeme an, fügt die Wege in durcheinander gewürfelter Reihenfolge hinzu und druckt die Nachbarn jedes Systems. Die Systemnummern auf dem Bildschirm beginnen bei 1, im Speicher bei 0: numbers addiert 1, bevor es sie zeigt.

List<StarSystem> systems = new ArrayList<>();
for (int i = 0; i < 6; i++) systems.add(new StarSystem(i, i * 10, 0));
int[][] lanes = {{4, 0}, {0, 2}, {0, 1}, {2, 3}, {3, 5}, {1, 4}};
for (int[] lane : lanes) addLane(systems, lane[0], lane[1]);

for (StarSystem system : systems) {
    System.out.println("System " + (system.id + 1) + ": " + numbers(system.links));
}
System.out.println("Weg 1-3: " + (hasLane(systems, 0, 2) ? "ja" : "nein"));
System.out.println("Weg 1-4: " + (hasLane(systems, 0, 3) ? "ja" : "nein"));

Ausgabe

System 1: 2 3 5
System 2: 1 5
System 3: 1 4
System 4: 3 6
System 5: 1 2
System 6: 4
Weg 1-3: ja
Weg 1-4: nein

Sieh dir System 1 an: Die Wege zu den Systemen 5 (zuerst hinzugefügt), 3 und 2 werden als „2 3 5“ gedruckt, aufsteigend, nicht in der Reihenfolge des Hinzufügens. Die Systeme 1 und 3 haben einen Weg, 1 und 4 nicht.

Die Idee

Ist die Galaxie zusammenhängend?

Das Spiel ergibt nur Sinn, wenn man von jedem System zu jedem anderen kommt. Sonst können Flotten nicht durch, und ein Reich auf einer Insel lässt sich nicht angreifen. Wir wollen einen zusammenhängenden Graphen: Von jedem Knoten gibt es einen Pfad zu jedem anderen.

Die Prüfung ist die Breitensuche (BFS). Du beginnst bei einem System und schickst eine Welle los: erst ist das System selbst im Abstand 0, dann seine Nachbarn im Abstand 1, deren Nachbarn im Abstand 2 und so weiter. Die Warteschlange hält die Systeme, die auf ihre Reihe warten. Die Systeme, die die Welle nicht erreicht, bleiben bei −1.

static int[] bfs(List<StarSystem> systems, int from) {
    int[] dist = new int[systems.size()];
    for (int i = 0; i < dist.length; i++) dist[i] = -1;
    List<Integer> queue = new ArrayList<>();
    queue.add(from);
    dist[from] = 0;
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        for (int next : systems.get(current).links) {
            if (dist[next] < 0) {
                dist[next] = dist[current] + 1;
                queue.add(next);
            }
        }
    }
    return dist;
}

Der Graph ist genau dann zusammenhängend, wenn die Welle von System 1 alle erreicht: kein −1.

static boolean isConnected(List<StarSystem> systems) {
    for (int d : bfs(systems, 0)) {
        if (d < 0) return false;
    }
    return true;
}

Das Programm baut zwei „Inseln“ (Systeme 1 bis 4 und 5 bis 7), druckt die Abstände von System 1 und ob die Galaxie zusammenhängt. Dann fügt es einen Weg zwischen ihnen hinzu:

List<StarSystem> systems = new ArrayList<>();
for (int i = 0; i < 7; i++) systems.add(new StarSystem(i, i * 10, 0));
int[][] lanes = {{0, 1}, {1, 2}, {2, 3}, {4, 5}, {5, 6}};
for (int[] lane : lanes) addLane(systems, lane[0], lane[1]);
System.out.println("Abstände von System 1: " + join(bfs(systems, 0)));
System.out.println("verbunden: " + (isConnected(systems) ? "ja" : "nein"));

addLane(systems, 3, 4);
System.out.println("Abstände von System 1: " + join(bfs(systems, 0)));
System.out.println("verbunden: " + (isConnected(systems) ? "ja" : "nein"));

Ausgabe

Abstände von System 1: 0 1 2 3 -1 -1 -1
verbunden: nein
Abstände von System 1: 0 1 2 3 4 5 6
verbunden: ja

Vor dem Weg sind die Systeme 5, 6 und 7 bei −1: Die Welle ist nicht hingekommen. Nach dem Weg zwischen 4 und 5 erreicht die Welle sie mit den Abständen 4, 5 und 6.

static boolean isConnected(List<StarSystem> systems) {
    for (int d : bfs(systems, 0)) {
        if (d < ) return false;
    }
    return true;
}

Prüfen

Im Spiel steht dieselbe Funktion in der Region graph, aber die Suche behält auch den Vorgänger jedes Systems: das System, von dem aus es entdeckt wurde. Wenn man an den Vorgängern entlang zurückgeht, erhält man den kürzesten Pfad:

// Breitensuche von einem System aus: Abstand in Wegen (-1 ist unerreichbar) und Vorgänger auf dem Weg.
static BfsResult bfs(List<StarSystem> systems, int from) {
    int[] dist = new int[systems.size()];
    int[] parent = new int[systems.size()];
    for (int i = 0; i < dist.length; i++) {
        dist[i] = -1;
        parent[i] = -1;
    }
    List<Integer> queue = new ArrayList<>();
    queue.add(from);
    dist[from] = 0;
    int head = 0;
    while (head < queue.size()) {
        int current = queue.get(head);
        head++;
        for (int next : systems.get(current).links) {
            if (dist[next] < 0) {
                dist[next] = dist[current] + 1;
                parent[next] = current;
                queue.add(next);
            }
        }
    }
    return new BfsResult(dist, parent);
}

// Der kürzeste Weg als Liste von Systemen, beide Enden eingeschlossen; leer, wenn es keinen Weg gibt.
static List<Integer> shortestPath(List<StarSystem> systems, int from, int to) {
    BfsResult result = bfs(systems, from);
    List<Integer> path = new ArrayList<>();
    if (result.dist[to] < 0) return path;
    path.add(to);
    int current = to;
    while (current != from) {
        current = result.parent[current];
        path.add(current);
    }
    Collections.reverse(path);
    return path;
}

Das Spiel nutzt diesen Pfad, wenn eine Flotte zu einem fernen Ziel fliegt: go 1 9 sagt nicht, durch welche Systeme, und in jeder Runde macht die Flotte den nächsten Schritt des kürzesten Pfades (nextStep). Dieselbe Funktion nutzt auch die künstliche Intelligenz der Rivalen.

Eine Einzelheit, die man ehrlicherweise sagen muss: isConnected steht im Original, aber das Spiel selbst ruft sie nie auf. Der Zusammenhang ist durch den Baum garantiert, und die Funktion ist zum Prüfen da, wie die im Programm oben und in der Übung unten.

Die Idee

Sterne auf einem Raster

Jetzt machen wir die Galaxie selbst. Systeme werden nicht auf zufällige Punkte der Karte geworfen: Manche würden sich übereinanderhäufen, andere blieben allein im leeren Raum. Das Spiel nutzt ein Raster: Die Karte hat 5 Spalten und 4 Zeilen, 20 Zellen. Davon werden 12 bis 20 gewählt, und in jeder gewählten Zelle sitzt der Stern an einer zufälligen Stelle.

static final int COLS = 5;
static final int ROWS = 4;
static final int CELL_W = 12;
static final int CELL_H = 4;

static List<StarSystem> placeStars(Random rng, int count) {
    List<Integer> cells = new ArrayList<>();
    for (int i = 0; i < COLS * ROWS; i++) cells.add(i);
    rng.shuffle(cells);
    List<Integer> chosen = new ArrayList<>(cells.subList(0, count));
    Collections.sort(chosen);
    List<StarSystem> systems = new ArrayList<>();
    for (int i = 0; i < count; i++) {
        int col = chosen.get(i) % COLS;
        int row = chosen.get(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;
}

Drei Schritte: shuffle mischt die Nummern der Zellen, die ersten count werden genommen und sortiert (damit die Systeme von links nach rechts und von oben nach unten nummeriert sind), und in jeder Zelle bekommt der Stern eine kleine zufällige Verschiebung. Die Zellen halten die Sterne auseinander, und der Zufall macht sie von Partie zu Partie verschieden.

Im Spiel ist die Zahl der Systeme nicht vorgegeben. Der erste Wurf des Generators bestimmt sie: 12 + nextInt(9) ist eine Zahl von 12 bis 20.

Die Idee

Wege: erst der Baum, dann die zusätzlichen

Es bleibt zu entscheiden, welche Sterne verbunden sind. Setzt du Wege auf zufällige Paare, kannst du nicht sicher sein, dass nichts auf einer Insel landet. Setzt du alle Wege, wird die Karte zum Spinnennetz. Das Spiel nutzt eine Lösung in zwei Schritten.

Zuerst ein Baum. Du beginnst bei System 1. In jedem Schritt suchst du den kürzesten Weg von einem System im Baum zu einem System außerhalb und fügst ihn hinzu. Das neue System kommt in den Baum. Das wiederholst du, bis alle drin sind. Dieser Algorithmus heißt minimaler Spannbaum (Prim). Der Baum hat genau Zahl der Systeme − 1 Wege, und es ist klar, warum der Graph zusammenhängt: Jedes neue System kommt mit einem Weg zu den schon verbundenen.

Dann die zusätzlichen. Ein Baum hat keine Kreise: Zwischen zwei Systemen gibt es genau eine Route, und die kann lang sein. Darum bekommt jedes System auch einen Weg zum nächsten System, mit dem es noch keinen hat, aber nur, wenn dieses nah genug ist, keines von beiden schon 4 Wege hat und der Würfelwurf unter 55 % liegt. So entstehen Rundrouten und eine Wahl.

Der Abstand ist das Quadrat des Abstands, ohne Wurzel (wir vergleichen nur, was kleiner ist): dy wird mit 3 multipliziert, weil die Zeichen in der Konsole höher als breit sind.

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.size();
    boolean[] inTree = new boolean[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.get(a), systems.get(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.get(a), systems.get(b));
            if (best < 0 || d < bestD) {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems.get(a).links.size() < 4 && systems.get(best).links.size() < 4 && rng.chance(55)) {
            addLane(systems, a, best);
        }
    }
}

Zwei Einzelheiten machen die Ausgabe gleich. Bei gleichen Abständen gewinnt der zuerst gefundene (d < bestD, nicht <=), also die kleinere Nummer. Und die Wahrscheinlichkeit (rng.chance(55)) steht in der Bedingung mit && zuletzt: Gewürfelt wird nur für einen Weg, der sonst hinzukäme. Würde früher gewürfelt, wären beide Varianten vernünftig, aber jeder Wurf nimmt eine Zahl vom Generator, und alles danach würde sich ändern: Aus denselben Startwerten entstünden andere Galaxien.

Sieh es dir an

Die Galaxie in Bewegung

Die zwölf Systeme der Galaxie mit Startwert 18. Achte auf die Zähler oben: Die Inseln sinken von 12 auf 1, während die Wege des Baums wachsen; danach kommen die zusätzlichen Wege in einer anderen Farbe und zuletzt die Welle der Suche.

static void connect(List<StarSystem> systems, Random rng) {
    int count = systems.size();
    boolean[] inTree = new boolean[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.get(a), systems.get(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.get(a), systems.get(b));
            if (best < 0 || d < bestD) {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems.get(a).links.size() < 4 && systems.get(best).links.size() < 4 && rng.chance(55)) {
            addLane(systems, a, best);
        }
    }
}

Schritt für Schritt, in Worten

1. 12 Sterne auf einem 5-mal-4-Raster (20 Zellen): Die gewählten Zellen leuchten auf. Noch gibt es keinen einzigen Weg, also ist jedes System eine Insel: 12 Inseln.
2. Zuerst der minimale Spannbaum (Prim). Er beginnt bei System 1. In jedem Schritt wird der kürzeste Weg von einem System im Baum zu einem System außerhalb gesucht.
3. Der gefundene Weg wird hinzugefügt, und das neue System kommt in den Baum. Nach 5 Wegen bleiben 7 Inseln: Jeder Weg macht aus zwei Inseln eine.
4. 11 Wege und eine Insel. Jedes neue System kommt mit genau einem Weg dazu, also bleibt keines allein: Die Galaxie ist schon vor den zusätzlichen Wegen verbunden.
5. Dann die zusätzlichen Wege (andere Farbe): zum nächsten noch nicht verbundenen System, wenn es nah ist, weniger als 4 Wege hat und der Wurf unter 55 % liegt. So entstehen 3 Umwege.
6. Die Prüfung: Breitensuche ab System 1. Die Welle läuft Schicht für Schicht und notiert für jedes System seinen Abstand in Wegen (0, 1, 2 …).
7. Kein einziges −1: Die Welle hat alle 12 Systeme erreicht, also ist die Galaxie verbunden. Mit demselben Startwert sieht dieses Bild jedes Mal gleich aus.

Die Idee

Die ganze Galaxie aus einem Startwert

Es bleibt, alles zusammenzusetzen: Startwert, Zahl der Systeme, Sterne, Wege. Die Funktion galaxy(seed) ist der ganze Generator. Die zweite Funktion, describe, macht aus einer Galaxie einen Text: So lassen sich zwei Galaxien mit einem einzigen == vergleichen.

static List<StarSystem> galaxy(int seed) {
    Random rng = new Random(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 = "";
    for (StarSystem system : systems) {
        text += (system.id + 1) + " (" + system.x + "," + system.y + "): " + numbers(system.links) + "\n";
    }
    return text;
}

Das Programm erzeugt die Galaxie mit Startwert 18 (12 Systeme, 14 Wege: 11 vom Baum und 3 zusätzliche), erzeugt sie dann noch einmal mit demselben und mit dem nächsten Startwert und prüft zum Schluss 200 verschiedene Startwerte:

List<StarSystem> systems = galaxy(18);
System.out.print(describe(systems));
int lanes = 0;
for (StarSystem system : systems) lanes += system.links.size();
lanes /= 2;
System.out.println("Wege: " + lanes + " (" + (lanes - systems.size() + 1) + " zusätzliche)");
System.out.println("verbunden: " + (isConnected(systems) ? "ja" : "nein"));

String first = describe(systems);
System.out.println("derselbe Startwert noch einmal, dieselbe Galaxie: " + (describe(galaxy(18)).equals(first) ? "ja" : "nein"));
System.out.println("anderer Startwert, andere Galaxie: " + (!describe(galaxy(19)).equals(first) ? "ja" : "nein"));

int ok = 0;
for (int seed = 1; seed <= 200; seed++) {
    if (isConnected(galaxy(seed))) ok++;
}
System.out.println("Startwerte 1-200: verbunden " + ok + " von 200");

Ausgabe

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
Wege: 14 (3 zusätzliche)
verbunden: ja
derselbe Startwert noch einmal, dieselbe Galaxie: ja
anderer Startwert, andere Galaxie: ja
Startwerte 1-200: verbunden 200 von 200

Drei Dinge sind hier wichtig. Erstens: derselbe Startwert ist dieselbe Galaxie bis zur letzten Koordinate. Zweitens: der nächste Startwert ist eine ganz andere Galaxie. Drittens: alle 200 sind zusammenhängend: Das ist kein Glück, sondern eine Folge des Baums. Diese Prüfung ist ein kleiner Eigenschaftstest: Wir fragen nicht „wie sieht diese Galaxie aus“, sondern „stimmt es für jede Galaxie, dass sie zusammenhängt“.

So sieht die echte Funktion im Spiel aus. Sie macht dasselbe, gibt aber jedem Stern auch einen Namen (die Namen werden mit einem weiteren shuffle gemischt) und eine Farbe (rot, gelb oder blau) und arbeitet auf der gemeinsamen Welt world:

static void generateSystems(World world, int count) {
    Random rng = world.rng;
    List<Integer> cells = new ArrayList<>();
    for (int i = 0; i < MAP_COLS * MAP_ROWS; i++) cells.add(i);
    rng.shuffle(cells);
    List<Integer> chosen = new ArrayList<>(cells.subList(0, count));
    Collections.sort(chosen);
    List<Integer> names = new ArrayList<>();
    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.get(i) % MAP_COLS;
        int row = chosen.get(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.get(i)], x, y);
        system.cls = rng.nextInt(3);
        world.systems.add(system);
    }
    // Der minimale Spannbaum (Prim): bei gleichen Abständen gewinnt die kleinere Nummer.
    boolean[] inTree = new boolean[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.get(a), world.systems.get(b));
                if (bestA < 0 || d < bestD) {
                    bestA = a;
                    bestB = b;
                    bestD = d;
                }
            }
        }
        addLane(world.systems, bestA, bestB);
        inTree[bestB] = true;
    }
    // Zusätzliche Wege: zum nächsten noch nicht verbundenen Nachbarn, wenn er nicht zu weit ist.
    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.get(a), world.systems.get(b));
            if (best < 0 || d < bestD) {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && world.systems.get(a).links.size() < 4 && world.systems.get(best).links.size() < 4 && rng.chance(55)) {
            addLane(world.systems, a, best);
        }
    }
}

Alles, was das Spiel weiß, lebt in der Klasse World: der Startwert, der Generator, die Systeme, die Planeten, die Reiche und die Flotten. Darum liegt der Spielstand an einer Stelle, und newWorld(seed) ist das Einzige, was eine Galaxie macht:

static class World {
    long seed;
    Random rng;
    int turn = 1;
    List<StarSystem> systems = new ArrayList<>();
    List<Planet> planets = new ArrayList<>();
    List<Empire> empires = new ArrayList<>();
    List<Fleet> fleets = new ArrayList<>();
    List<QueueItem> queue = new ArrayList<>();
    List<Offer> offers = new ArrayList<>();
    List<String> news = new ArrayList<>();
    List<String> turnLines = new ArrayList<>();
    EventBus bus = new EventBus();
    Victory victory = null;
    Map<Integer, Integer> fortLeft = new LinkedHashMap<>();
    Stats stats = new Stats();
    LastInfo last = new LastInfo();
    boolean quiet = false;
    int alert = 0;
    int pace = 100;

    World(long seed) {
        this.seed = seed;
        this.rng = new Random(seed);
    }

    int livingCount() {
        int n = 0;
        for (Empire e : this.empires) {
            if (e.alive) n++;
        }
        return n;
    }
}

Und so nutzt newWorld sie. Aus dem Startwert wird die Welt: die Zahl der Systeme, die Wege, dann die Hauptstädte der Reiche und die Planeten, und zuletzt bekommt jedes Reich einen Heimatplaneten:

// Die ganze Welt aus einem Seed. human ist der Spieler (in der Simulation keiner), personalities ist eine optionale
// Liste von Charakteren, einer pro Reich.
static World newWorld(long seed, boolean human, String[] personalities, boolean 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<Integer> defs = new ArrayList<>();
    defs.add(0);
    List<Integer> pool = new ArrayList<>(List.of(1, 2, 3));
    rng.shuffle(pool);
    for (int i = 0; i < rivals; i++) defs.add(pool.get(i));
    List<Integer> capitals = pickCapitals(world, defs.size());
    generatePlanets(world, capitals);
    for (int i = 0; i < defs.size(); i++) {
        Empire empire = new Empire(i, EMPIRE_DEFS.get(defs.get(i)), defs.size());
        if (personalities != null) {
            empire.personality = PERSONALITIES.get(personalities[i]);
        }
        empire.human = human && i == 0;
        world.empires.add(empire);
        placeHomeworld(world, empire, capitals.get(i));
    }
    return world;
}

Die Hauptstädte werden mit einer Breitensuche gewählt: Die erste ist das System ganz links, und jede weitere ist die (nach Wegen) von den schon gewählten am weitesten entfernte. So beginnen die Reiche möglichst weit voneinander:

// Die Hauptstädte: die erste ist das am weitesten links liegende System; jede nächste ist (nach Wegen) am weitesten von den schon gewählten.
static List<Integer> pickCapitals(World world, int count) {
    List<Integer> chosen = new ArrayList<>();
    int first = 0;
    for (StarSystem system : world.systems) {
        if (system.x < world.systems.get(first).x) first = system.id;
    }
    chosen.add(first);
    int[] nearest = bfs(world.systems, first).dist.clone();
    while (chosen.size() < count) {
        int best = -1;
        for (StarSystem system : 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;
}

Die Idee

Planeten mit Gewichten

Jedes System hat ein bis drei Planeten, und nicht alle sind gleich wahrscheinlich: Ein Planet hat 30 % Chance, zwei haben 45 %, drei haben 25 %. Auch die Art des Planeten hat Gewichte (felsig, Gasriese, vereist, Ozean, vulkanisch). Wir brauchen eine Funktion, die ein Element nach Gewicht wählt.

Die Idee: Du würfelst eine Zahl von 0 bis zur Summe der Gewichte und gehst die Liste entlang, wobei du das Gewicht jedes Elements abziehst, bis der Wurf kleiner als das aktuelle Gewicht ist.

static int pickWeighted(Random rng, int[] weights) {
    int total = 0;
    for (int w : 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;
}

Bei den Gewichten 30, 45 und 25 ist die Summe 100. Ein Wurf von 0 bis 29 ist Index 0, von 30 bis 74 Index 1, von 75 bis 99 Index 2. Das Programm würfelt 1000-mal (die Planeten sind Index + 1) und nimmt dann getrennt die Planetenzahlen der ersten acht Systeme:

int[] weights = {30, 45, 25};
Random rng = new Random(2026);
int[] counts = new int[3];
for (int i = 0; i < 1000; i++) counts[pickWeighted(rng, weights)]++;
System.out.println("Planeten in 1000 Systemen: 1=" + counts[0] + " 2=" + counts[1] + " 3=" + counts[2]);

Random few = new Random(7);
List<Integer> planets = new ArrayList<>();
for (int i = 0; i < 8; i++) planets.add(pickWeighted(few, weights));
System.out.println("die ersten 8 Systeme: " + numbers(planets));

Ausgabe

Planeten in 1000 Systemen: 1=299 2=467 3=234
die ersten 8 Systeme: 2 3 2 2 3 3 1 1

Von 1000 Systemen haben etwa 30 %, 45 % und 25 % jeweils 1, 2 und 3 Planeten. Es stimmt nicht genau: Gewichte sind Wahrscheinlichkeiten, keine Quoten. Aber mit demselben Startwert sind die Zahlen immer gleich.

Ein Planet ist eine Klasse mit einer Art, dem Reichtum an den vier Rohstoffen und einem Besitzer:

static class Planet {
    int id;
    int systemId;
    int index;
    int typeIndex;
    int[] rich;
    int owner = -1;
    int mines = 0;
    int lab = 0;
    int yard = 0;
    int fort = 0;
    int siege = 0;

    Planet(int id, int systemId, int index, int typeIndex, int[] rich) {
        this.id = id;
        this.systemId = systemId;
        this.index = index;
        this.typeIndex = typeIndex;
        this.rich = rich;
    }
}

Das echte generatePlanets nutzt dieselbe Funktion zweimal: für die Zahl und für die Art jedes Planeten. Dann würfelt es für jeden Rohstoff noch eine Zahl (Reichtum von 0 bis 4), und die Farbe des Sterns addiert zu einem Rohstoff eins: rot zu Gas, gelb zu Metall, blau zu Kristall.

static void generatePlanets(World world, List<Integer> capitals) {
    Random rng = world.rng;
    int[] typeWeights = new int[PLANET_TYPES.size()];
    for (int i = 0; i < PLANET_TYPES.size(); i++) typeWeights[i] = PLANET_TYPES.get(i).weight;
    for (StarSystem system : world.systems) {
        boolean 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);
            PlanetType type = PLANET_TYPES.get(typeIndex);
            int[] rich = new int[RES_COUNT];
            for (int r = 0; r < RES_COUNT; r++) {
                int value = clamp(type.base[r] + rng.nextInt(3) - 1, 0, 4);
                rich[r] = value;
            }
            // Der Stern wiegt mit: der rote gibt Gas, der gelbe Metall, der blaue Kristall.
            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.size(), system.id, index, typeIndex, rich);
            world.planets.add(planet);
            system.planets.add(planet.id);
        }
    }
}

Probier es aus

Sage die Ausgabe voraus

Sechs Systeme, ab 0 nummeriert. Die Wege sind 0-1, 1-2, 2-3, 0-4, 4-3 und 3-5: ein Ring aus fünf Systemen und ein weiteres, das daran hängt. Was druckt das Programm?

List<StarSystem> systems = new ArrayList<>();
for (int i = 0; i < 6; i++) systems.add(new StarSystem(i, i * 10, 0));
int[][] lanes = {{0, 1}, {1, 2}, {2, 3}, {0, 4}, {4, 3}, {3, 5}};
for (int[] lane : lanes) addLane(systems, lane[0], lane[1]);
System.out.println(join(bfs(systems, 0)));

Antwort

0 1 2 3 1 4

0 1 2 2 1 3

1 2 3 3 2 4

Prüfen

Probier es aus

Finde den Fehler

Ein Kollege hat eine Zeile in der Schleife des Baums geändert. Das Programm erzeugt Galaxien aus 200 Startwerten und zählt die zusammenhängenden. Vorher waren es alle 200, jetzt sind es:

static void connect(List<StarSystem> systems, Random rng) {
    int count = systems.size();
    boolean[] inTree = new boolean[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.get(a), systems.get(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.get(a), systems.get(b));
            if (best < 0 || d < bestD) {
                best = b;
                bestD = d;
            }
        }
        if (best >= 0 && bestD <= 420 && systems.get(a).links.size() < 4 && systems.get(best).links.size() < 4 && rng.chance(55)) {
            addLane(systems, a, best);
        }
    }
}

int ok = 0;
for (int seed = 1; seed <= 200; seed++) {
    if (isConnected(galaxy(seed))) ok++;
}
System.out.println("Startwerte 1-200: verbunden " + ok + " von 200");

Ausgabe

Startwerte 1-200: verbunden 150 von 200

Welche Zeile ist schuld?

Wähle die Zeile mit dem Fehler.

1static void connect(List<StarSystem> systems, Random rng) {2 int count = systems.size();3 boolean[] inTree = new boolean[count];4 inTree[0] = true;5 for (int step = 1; step < count - 1; step++) {6 int bestA = -1;7 int bestB = -1;8 int bestD = 0;9 for (int a = 0; a < count; a++) {10 if (!inTree[a]) continue;11 for (int b = 0; b < count; b++) {12 if (inTree[b]) continue;13 int d = squaredDistance(systems.get(a), systems.get(b));14 if (bestA < 0 || d < bestD) {15 bestA = a;16 bestB = b;17 bestD = d;18 }19 }20 }21 addLane(systems, bestA, bestB);22 inTree[bestB] = true;23 }24 for (int a = 0; a < count; a++) {25 int best = -1;26 int bestD = 0;27 for (int b = 0; b < count; b++) {28 if (b == a || hasLane(systems, a, b)) continue;29 int d = squaredDistance(systems.get(a), systems.get(b));30 if (best < 0 || d < bestD) {31 best = b;32 bestD = d;33 }34 }35 if (best >= 0 && bestD <= 420 && systems.get(a).links.size() < 4 && systems.get(best).links.size() < 4 && rng.chance(55)) {36 addLane(systems, a, best);37 }38 }39}4041int ok = 0;42for (int seed = 1; seed <= 200; seed++) {43 if (isConnected(galaxy(seed))) ok++;44}45System.out.println("Startwerte 1-200: verbunden " + ok + " von 200");

Prüfen

Genauer

Was in diesem System nicht steckt

Eine Galaxie aus einem Startwert hat wenige Regeln, aber dahinter stehen Entscheidungen.

Der Baum ist einfach. Der Algorithmus von Prim hat hier drei verschachtelte Schleifen: Für einen Baum aus 20 Systemen sind das einige tausend Vergleiche. In einem größeren Graphen (Millionen Knoten) nimmt man eine Prioritätswarteschlange, und Prim läuft in O(E log V). Hier ist die einfache Schleife kürzer, leicht zu lesen und in den vier Sprachen gleich.

Die zusätzlichen Wege sind nicht garantiert. Darum sind manche Galaxien fast Bäume: lange Ketten ohne Umwege. Das ist eine Entscheidung für das Spiel: Solche Karten sind taktischer (ein Schlüsselpass, den man bewacht). Wie viele zusätzliche Wege es gibt (55 %, höchstens 4 je System, in der Nähe), wird mit einer Simulation eingestellt, wie die Balance.

Zusammenhang ist eine Wahl, kein Gesetz. In anderen Spielen sind Inseln in Ordnung: Nicht alles ist erreichbar. Hier ist es umgekehrt: Der Zusammenhang ist eine Bedingung des Spiels. Darum ist es gut, ihn zu prüfen, wie es das Programm mit 200 Startwerten tut.

Der Startwert ist nicht die ganze Geschichte. Derselbe Startwert gibt dieselbe Galaxie nur, solange der Generator nextInt in derselben Reihenfolge aufruft. Fügst du am Anfang einen neuen Wurf hinzu, ändern sich alle Galaxien aller alten Startwerte, und alte Spielstände laden in eine andere Welt. Darum muss in einem echten Spiel eine Änderung der Erzeugung eine Änderung der Version sein: Der Spielstand hat eine Formatversion für genau solche Fälle.

Wege gelten in beide Richtungen. Der Graph ist hier ungerichtet. Der Technologiebaum (nächste Lektion) ist anders: „A muss vor B kommen“ gilt nur in eine Richtung. Dort ist der Graph gerichtet.

Übung

Inseln

Löse die Aufgabe in deinem Editor.

Inseln. Das Programm liest in der ersten Zeile der Eingabe die Zahl der Systeme n und die Zahl der Wege m, danach m Zeilen mit je zwei Nummern (ab 1). Es druckt, wie viele Inseln die Galaxie hat (Inseln sind Gruppen von Systemen, die untereinander verbunden sind), wie viele Systeme die größte Insel hat und ob die Galaxie zusammenhängt.

Mit der Eingabe 8 5 | 1 2 | 2 3 | 4 5 | 6 7 | 7 8 (je eine Zeile) lautet die Ausgabe:

Ausgabe

Inseln: 3
größte Insel: 3
verbunden: nein

Tipp: Starte eine Breitensuche beim ersten System, das noch nicht gesehen wurde, und markiere alles, was sie erreicht. Wie oft du neu beginnst, so viele Inseln gibt es.

Weitere Aufgaben

• Der kürzeste Pfad. Erweitere das Programm so, dass es zwei weitere Nummern liest und den kürzesten Pfad zwischen ihnen durch die Systeme druckt oder „kein Pfad“, wenn es keinen gibt. Der Vorgänger jedes Systems ist der Schlüssel.
• Wie viele Wege muss ich hinzufügen? Wie viele Wege muss man mindestens hinzufügen, damit eine Galaxie mit k Inseln zusammenhängt? Probiere ein paar Beispiele und finde die Regel.
• Wie viele Startwerte hängen ohne den Baum nicht zusammen? Entferne die Schleife des Baums und lass die Prüfung mit 200 Startwerten laufen. Wie viele Galaxien hängen allein durch die zusätzlichen Wege zusammen?

Test

Teste dich

1. Warum ist die Galaxie mit demselben Startwert jedes Mal dieselbe?

Weil der Generator eine Formel ist: Die nächste Zahl hängt nur von der vorigen ab, und der Code ruft den Generator immer in derselben Reihenfolge aufWeil die Galaxie auf der Platte gespeichert und von dort gelesen wirdWeil Random in jeder Sprache dieselbe Folge liefert

2. Eine Galaxie mit 12 Systemen hat einen minimalen Spannbaum. Wie viele Wege hat er?

111266

3. Nach einer Breitensuche ab System 1 sind die Abstände „0 1 2 3 -1 -1 -1“. Was bedeutet −1?

Das System wurde schon besuchtDas System wurde nicht erreicht: Es gibt keinen Pfad dorthin, die Galaxie ist also nicht zusammenhängendDas System hat den Abstand minus eins, liegt also hinter dem Start

4. Gewichte 30, 45 und 25, der Wurf ist 55. Wie viele Planeten bekommt das System?

132

5. Der Spielstand von Epic Cosmos enthält eine Zeile seed=… Warum speichert er nicht auch Systeme und Wege?

Weil sie woanders gespeichert werdenWeil die Wege neu erfunden werden und anders sein könnenWeil die Galaxie aus dem Startwert neu erzeugt wird und gleich herauskommt; der Spielstand behält nur, was das Spiel verändert

6. Was würde passieren, wenn die zusätzlichen Wege ohne den Baum hinzugefügt würden?

Manche Galaxien wären nicht zusammenhängend: Die zusätzlichen Wege sind zufällig, und nichts garantiert, dass sie alles verbindenDie Galaxie wäre immer getrenntNichts: Die Wege würden trotzdem alles verbinden

Prüfen

Lektion von vorn beginnen

Verwandte Lektionen

• Baut auf: Konstruktoren und this · Instanzmethoden · static: was alle Objekte teilen · Listen
• Aufgaben zum Thema: Epic Cosmos: das Imperium