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.
Runde 1/150 Terranisches Reich (A) Punkte 20M70+8 G60+4 C20+3 U5+1 Forschung +3Nichts wird erforscht (r Nummer). Gesparte Forschung: 0Terranisches 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 9800produzieren. Nach 150 Runden gewinnt der Stärkste. Tippe help.
Enter oder map: zur Karte help: BefehleProbier 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.
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):
mapzeigt die Karte der Galaxie:[ 1 ]sind die Systeme, die Punkte sind die Wege, die Buchstaben sind die Reiche.sys Nzeigt System N: seine Planeten, was sie liefern und welche Flotten dort stehen.empzeigt die Reiche,techden Technologiebaum,fleetsdie Flotten.col Pbesiedelt Planet P,b mine Pbaut dort eine Mine,r Xerforscht eine Technologie.ship T N Pbaut N Schiffe vom Typ T,go A Bschickt eine Flotte von System A nach B über die Wege.endbeendet die Runde,wait Nüberspringt bis zu N Runden,save 1undload 1sind 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 20M70+8 G60+4 C20+3 U5+1 Forschung +3Nichts 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 SystemUnd 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 20M70+8 G60+4 C20+3 U5+1 Forschung +3Nichts wird erforscht (r Nummer). Gesparte Forschung: 0System 1 Elara, gelber Stern. Wege nach: 2Planet 1 Elara I, ozeanisch (Terranisches Reich) Reichtum M3 G3 C2 U1 Minen 1 Labor ja Werft ja Festung 1Planet 2 Elara II, Gasriese (frei) Reichtum M1 G4 C1 U0Flotte (Terranisches Reich): 3I 2B 2F
Enter oder map: zur Karte help: BefehleWie 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:
python cosmos.pyIm 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.
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.
- Die Galaxie aus einem Startwert (diese Lektion): ein Generator mit Startwert, Sterne und Planeten, Wege als Graph, Zusammenhang.
- Der Technologiebaum: ein gerichteter Graph ohne Kreise, Voraussetzungen, topologische Ordnung, was jetzt erforscht werden kann.
- Flotten und Weltraumschlacht: gleichzeitiges Auflösen der Züge, Rollen der Schiffe, eine Schlachtsimulation.
- Die Rivalen: Reiche mit künstlicher Intelligenz, Bewertung des Nutzens, der Charakter eines Reichs.
- Der Zug der Galaxie: die Phasen einer Runde, zufällige Ereignisse, Diplomatie, der Ereignisbus.
- 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 (Maske & 0xFFFFFFFF und ein handgemachtes# imul), darum liefert er in jeder Sprache dieselbe Folge.MASK32 = 0xFFFFFFFF
# Math.imul aus JavaScript: das Produkt, von dem nur die unteren 32 Bit übrig bleiben.def imul(a, b): return (a * b) & MASK32
# „x >>> 0“ aus JavaScript: eine Zahl auf 32 Bit ohne Vorzeichen (eine Nichtzahl und Unendlich werden zu 0).def to_uint32(value): if value != value or value == float('inf') or value == float('-inf'): return 0 return int(value) & MASK32
class Random: def __init__(self, seed): self.state = to_uint32(seed)
def next32(self): self.state = (self.state + 0x6D2B79F5) & MASK32 z = self.state z = imul(z ^ (z >> 15), z | 1) z = (z ^ (z + imul(z ^ (z >> 7), z | 61))) & MASK32 return (z ^ (z >> 14)) & MASK32
# Von 0 bis n-1, ohne Bruchzahlen. def next_int(self, n): return self.next32() % n
# Von min bis max, beide eingeschlossen. def range(self, low, high): return low + self.next_int(high - low + 1)
def chance(self, percent): return self.next_int(100) < percent
# Mischt die Liste an Ort und Stelle (Fisher-Yates, von hinten nach vorn). def shuffle(self, items): i = len(items) - 1 while i > 0: j = self.next_int(i + 1) keep = items[i] items[i] = items[j] items[j] = keep i -= 1Nur 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:
for seed in [2026, 2026, 2027]: rng = Random(seed) rolls = [rng.next_int(100) for _ in range(6)] print(f"Startwert {seed}: {' '.join(str(v) for v in rolls)}")
cells = list(range(8))Random(2026).shuffle(cells)print(f"gemischte Zellen: {' '.join(str(v) for v in cells)}")Startwert 2026: 75 58 22 36 57 62Startwert 2026: 75 58 22 36 57 62Startwert 2027: 50 47 63 23 32 32gemischte Zellen: 3 2 6 4 1 0 5 7Die 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.
imul das Produkt mit einer Maske auf 32 Bit ab. Ohne das würden die Zahlen weiterwachsen und sich von denen der anderen Sprachen unterscheiden.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: def __init__(self, system_id, x, y): self.id = system_id self.x = x self.y = y self.links = []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.
class StarSystem: def __init__(self, system_id, name, x, y): self.id = system_id self.name = name self.x = x self.y = y # Die Klasse des Sterns: 0 rot, 1 gelb, 2 blau. self.cls = 1 self.links = [] self.planets = []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.
def insert_sorted(items, value): at = len(items) while at > 0 and items[at - 1] > value: at -= 1 items.insert(at, value)
def has_lane(systems, a, b): return b in systems[a].links
def add_lane(systems, a, b): insert_sorted(systems[a].links, b) insert_sorted(systems[b].links, a)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.
systems = [StarSystem(i, i * 10, 0) for i in range(6)]lanes = [(4, 0), (0, 2), (0, 1), (2, 3), (3, 5), (1, 4)]for a, b in lanes: add_lane(systems, a, b)
for system in systems: print(f"System {system.id + 1}: {numbers(system.links)}")print("Weg 1-3: " + ("ja" if has_lane(systems, 0, 2) else "nein"))print("Weg 1-4: " + ("ja" if has_lane(systems, 0, 3) else "nein"))System 1: 2 3 5System 2: 1 5System 3: 1 4System 4: 3 6System 5: 1 2System 6: 4Weg 1-3: jaWeg 1-4: neinSieh 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.
def bfs(systems, start): dist = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 queue.append(nxt) return distDer Graph ist genau dann zusammenhängend, wenn die Welle von System 1 alle erreicht: kein −1.
def is_connected(systems): for d in bfs(systems, 0): if d < 0: return False return TrueDas 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:
systems = [StarSystem(i, i * 10, 0) for i in range(7)]lanes = [(0, 1), (1, 2), (2, 3), (4, 5), (5, 6)]for a, b in lanes: add_lane(systems, a, b)print("Abstände von System 1: " + " ".join(str(d) for d in bfs(systems, 0)))print("verbunden: " + ("ja" if is_connected(systems) else "nein"))
add_lane(systems, 3, 4)print("Abstände von System 1: " + " ".join(str(d) for d in bfs(systems, 0)))print("verbunden: " + ("ja" if is_connected(systems) else "nein"))Abstände von System 1: 0 1 2 3 -1 -1 -1verbunden: neinAbstände von System 1: 0 1 2 3 4 5 6verbunden: jaVor 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.
def is_connected(systems):
for d in bfs(systems, 0):
if d < :
return False
return TrueEin nicht erreichtes System bleibt bei −1, darum sucht die Prüfung eine Zahl unter null. Prüfst du d == 0, findest du nur den Start; bei d > 0 fast jedes System.
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.def bfs(systems, start): dist = [-1] * len(systems) parent = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 parent[nxt] = current queue.append(nxt) return SimpleNamespace(dist=dist, parent=parent)# Der kürzeste Weg als Liste von Systemen, beide Enden eingeschlossen; leer, wenn es keinen Weg gibt.def shortest_path(systems, start, to): result = bfs(systems, start) if result.dist[to] < 0: return [] path = [to] current = to while current != start: current = result.parent[current] path.append(current) path.reverse() return pathDas 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.
COLS = 5ROWS = 4CELL_W = 12CELL_H = 4
def place_stars(rng, count): cells = list(range(COLS * ROWS)) rng.shuffle(cells) chosen = cells[:count] chosen.sort() systems = [] for i in range(count): col = chosen[i] % COLS row = chosen[i] // COLS x = col * CELL_W + rng.next_int(6) y = row * CELL_H + rng.next_int(2) systems.append(StarSystem(i, x, y)) return systemsDrei 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.
def squared_distance(a, b): dx = a.x - b.x dy = (a.y - b.y) * 3 return dx * dx + dy * dydef connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)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.
def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)def bfs(systems, start): dist = [-1] * len(systems) queue = [start] dist[start] = 0 head = 0 while head < len(queue): current = queue[head] head += 1 for nxt in systems[current].links: if dist[nxt] < 0: dist[nxt] = dist[current] + 1 queue.append(nxt) return dist
def is_connected(systems): for d in bfs(systems, 0): if d < 0: return False return TrueSchritt für Schritt, in Worten
- 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.
- 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.
- 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.
- 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.
- 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.
- 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 …).
- 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.
def galaxy(seed): rng = Random(seed) count = 12 + rng.next_int(9) systems = place_stars(rng, count) connect(systems, rng) return systems
def describe(systems): text = "" for system in systems: text += f"{system.id + 1} ({system.x},{system.y}): {numbers(system.links)}\n" return textDas 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:
systems = galaxy(18)print(describe(systems), end="")lanes = sum(len(system.links) for system in systems) // 2print(f"Wege: {lanes} ({lanes - len(systems) + 1} zusätzliche)")print("verbunden: " + ("ja" if is_connected(systems) else "nein"))
first = describe(systems)print("derselbe Startwert noch einmal, dieselbe Galaxie: " + ("ja" if describe(galaxy(18)) == first else "nein"))print("anderer Startwert, andere Galaxie: " + ("ja" if describe(galaxy(19)) != first else "nein"))
ok = 0for seed in range(1, 201): if is_connected(galaxy(seed)): ok += 1print("Startwerte 1-200: verbunden " + str(ok) + " von 200")1 (5,5): 22 (12,4): 1 5 63 (36,5): 4 6 74 (50,5): 35 (17,9): 2 6 96 (24,8): 2 3 5 77 (37,8): 3 6 11 128 (3,12): 99 (17,12): 5 8 1010 (27,12): 911 (40,12): 7 1212 (53,12): 7 11Wege: 14 (3 zusätzliche)verbunden: jaderselbe Startwert noch einmal, dieselbe Galaxie: jaanderer Startwert, andere Galaxie: jaStartwerte 1-200: verbunden 200 von 200Drei 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:
def generate_systems(world, count): rng = world.rng cells = [] for i in range(MAP_COLS * MAP_ROWS): cells.append(i) rng.shuffle(cells) chosen = cells[:count] chosen.sort() names = [] for i in range(len(STAR_NAMES)): names.append(i) rng.shuffle(names) for i in range(count): col = chosen[i] % MAP_COLS row = chosen[i] // MAP_COLS x = col * CELL_W + rng.next_int(6) y = row * CELL_H + rng.next_int(2) system = StarSystem(i, STAR_NAMES[names[i]], x, y) system.cls = rng.next_int(3) world.systems.append(system) # Der minimale Spannbaum (Prim): bei gleichen Abständen gewinnt die kleinere Nummer. in_tree = [False] * count in_tree[0] = True for step in range(1, count): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(world.systems[a], world.systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(world.systems, best_a, best_b) in_tree[best_b] = True # Zusätzliche Wege: zum nächsten noch nicht verbundenen Nachbarn, wenn er nicht zu weit ist. for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(world.systems, a, b): continue d = squared_distance(world.systems[a], world.systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(world.systems[a].links) < 4 and len(world.systems[best].links) < 4 and rng.chance(55): add_lane(world.systems, a, best)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:
class World: def __init__(self, seed): self.seed = seed self.rng = Random(seed) self.turn = 1 self.systems = [] self.planets = [] self.empires = [] self.fleets = [] self.queue = [] self.offers = [] self.news = [] self.turn_lines = [] self.bus = EventBus() self.victory = None self.fort_left = {} self.stats = SimpleNamespace(battles=0, lost=0, colonies=0, techs=0, events=0) self.last = SimpleNamespace(battle=[]) self.quiet = False self.alert = 0 self.pace = 100
def living_count(self): n = 0 for e in self.empires: if e.alive: n += 1 return nUnd 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.def new_world(seed, human, personalities, quiet): load_data() world = World(seed) world.quiet = quiet world.pace = RIVAL_PACE if human else 100 install_subscribers(world, quiet) rng = world.rng count = 12 + rng.next_int(9) generate_systems(world, count) rivals = 2 + rng.next_int(2) if count >= 15 else 2 defs = [0] pool = [1, 2, 3] rng.shuffle(pool) for i in range(rivals): defs.append(pool[i]) capitals = pick_capitals(world, len(defs)) generate_planets(world, capitals) for i in range(len(defs)): empire = Empire(i, EMPIRE_DEFS[defs[i]], len(defs)) if personalities is not None: empire.personality = PERSONALITIES[personalities[i]] empire.human = human and i == 0 world.empires.append(empire) place_homeworld(world, empire, capitals[i]) return worldDie 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.def pick_capitals(world, count): chosen = [] first = 0 for system in world.systems: if system.x < world.systems[first].x: first = system.id chosen.append(first) nearest = list(bfs(world.systems, first).dist) while len(chosen) < count: best = -1 for system in world.systems: if system.id in chosen: continue if best < 0 or nearest[system.id] > nearest[best]: best = system.id chosen.append(best) d = bfs(world.systems, best).dist for i in range(len(nearest)): if d[i] < nearest[i]: nearest[i] = d[i] return chosenDie 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.
def pick_weighted(rng, weights): total = 0 for w in weights: total += w roll = rng.next_int(total) for i in range(len(weights)): if roll < weights[i]: return i roll -= weights[i] return len(weights) - 1Bei 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:
weights = [30, 45, 25]rng = Random(2026)counts = [0, 0, 0]for _ in range(1000): counts[pick_weighted(rng, weights)] += 1print(f"Planeten in 1000 Systemen: 1={counts[0]} 2={counts[1]} 3={counts[2]}")
few = Random(7)planets = [pick_weighted(few, weights) for _ in range(8)]print(f"die ersten 8 Systeme: {numbers(planets)}")Planeten in 1000 Systemen: 1=299 2=467 3=234die ersten 8 Systeme: 2 3 2 2 3 3 1 1Von 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:
class Planet: def __init__(self, planet_id, system_id, index, type_index, rich): self.id = planet_id self.system_id = system_id self.index = index self.type_index = type_index self.rich = rich self.owner = -1 self.mines = 0 self.lab = 0 self.yard = 0 self.fort = 0 self.siege = 0Das 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.
def generate_planets(world, capitals): rng = world.rng type_weights = [] for ptype in PLANET_TYPES: type_weights.append(ptype.weight) for system in world.systems: is_capital = system.id in capitals roll = pick_weighted(rng, [30, 45, 25]) + 1 count = 2 if is_capital and roll < 2 else roll for index in range(count): type_index = pick_weighted(rng, type_weights) ptype = PLANET_TYPES[type_index] rich = [] for r in range(RES_COUNT): value = clamp(ptype.base[r] + rng.next_int(3) - 1, 0, 4) rich.append(value) # Der Stern wiegt mit: der rote gibt Gas, der gelbe Metall, der blaue Kristall. if system.cls == 0: rich[1] = min_of(5, rich[1] + 1) elif system.cls == 1: rich[0] = min_of(5, rich[0] + 1) else: rich[2] = min_of(5, rich[2] + 1) planet = Planet(len(world.planets), system.id, index, type_index, rich) world.planets.append(planet) system.planets.append(planet.id)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?
systems = [StarSystem(i, i * 10, 0) for i in range(6)]lanes = [(0, 1), (1, 2), (2, 3), (0, 4), (4, 3), (3, 5)]for a, b in lanes: add_lane(systems, a, b)print(" ".join(str(d) for d in bfs(systems, 0)))System 0 hat den Abstand 0. Seine Nachbarn 1 und 4 haben 1. Von 1 kommt man zu 2 (Abstand 2), von 4 zu 3 (auch 2): eine Abkürzung über 4, nicht über 1 und 2 (das wären 3). Von 3 kommt man zu 5 (Abstand 3). Die Zahlen stehen in der Reihenfolge der Systeme: „0 1 2 2 1 3“. Die zweite Möglichkeit übersieht den Weg 4-3; die dritte ist die richtige Antwort mit ab 1 gezählten Abständen.
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:
def connect(systems, rng): count = len(systems) in_tree = [False] * count in_tree[0] = True for step in range(1, count - 1): best_a = -1 best_b = -1 best_d = 0 for a in range(count): if not in_tree[a]: continue for b in range(count): if in_tree[b]: continue d = squared_distance(systems[a], systems[b]) if best_a < 0 or d < best_d: best_a = a best_b = b best_d = d add_lane(systems, best_a, best_b) in_tree[best_b] = True for a in range(count): best = -1 best_d = 0 for b in range(count): if b == a or has_lane(systems, a, b): continue d = squared_distance(systems[a], systems[b]) if best < 0 or d < best_d: best = b best_d = d if best >= 0 and best_d <= 420 and len(systems[a].links) < 4 and len(systems[best].links) < 4 and rng.chance(55): add_lane(systems, a, best)
ok = 0for seed in range(1, 201): if is_connected(galaxy(seed)): ok += 1print("Startwerte 1-200: verbunden " + str(ok) + " von 200")Startwerte 1-200: verbunden 150 von 200Welche Zeile ist schuld?
Wähle die Zeile mit dem Fehler.
Die Schleife des Baums ist um einen Schritt zu kurz: count − 1 statt count, darum kommt das letzte System nie in den Baum. Verbinden es die zusätzlichen Wege zufällig (die Chance liegt bei 55 %, und es muss nah sein), ist die Galaxie zusammenhängend; sonst bleibt eine Insel. Der Eigenschaftstest hat genau das gefunden: in 50 von 200 Galaxien. Richtig ist step < count: Die Schritte sind die Zahl der Systeme minus eins (von 1 bis count − 1).
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:
Inseln: 3größte Insel: 3verbunden: neinTipp: 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
kInseln 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