Atlantis PbeM neu geschrieben (Teil 7): Das Objektmodell – aus Zeigern werden Objekte

Nach Teil 6 kann der Python-Port das Regelbuch von Atlantis PbeM erzeugen, Byte für Byte wie die Referenz. Spielen kann er trotzdem noch nicht. Es gibt keine Regionen, keine Gebäude, keine Einheiten und keine Fraktionen – nur Tabellen, Einstellungen und Text.

Schritt 6 der Roadmap ändert das. Er portiert das Objektmodell: die Klassen, aus denen eine laufende Partie besteht, und vor allem ihre Beziehungen untereinander.

Kurz die Begriffe, falls Du hier in die Serie einsteigst: Eine Region ist ein Hexfeld mit Terrain, Bevölkerung, Rohstoffen und Markt. Ein Objekt ist ein Gebäude oder eine Flotte in einer Region; für alles, was im Freien steht, besitzt jede Region zusätzlich ein Dummy-Objekt. Eine Einheit ist eine Gruppe von Männern, Monstern oder Magiern mit Inventar und Fertigkeiten. Eine Fraktion gehört einem Spieler und besitzt Einheiten. Der Nexus ist die Startebene, von der neue Fraktionen in die Welt gelangen.

Im C++-Code hängt dieses Modell über rohe Zeiger zusammen: Unit::faction, Unit::object, Object::region, ARegion::neighbors[6]. Dazu kommen Listen wie ARegion::objects, Object::units und ARegion::hell für tote Einheiten.

Sieben Header bilden einen Include-Zyklus.

Das Problem beim Portieren ist dabei weniger, aus Unit* eine Python-Referenz zu machen. Schwierig ist das Verhalten rundherum. Wenn eine Einheit stirbt: Wer bekommt ihr Inventar? Aus welcher Liste verschwindet sie? Wo landet sie bis zur endgültigen Löschung? Welche anderen Objekte zeigen noch auf sie?

Eine Funktion, die statt 12 plötzlich 13 zurückgibt, findet ein Test schnell. Eine vergessene Beziehung im Objektgraphen kann deutlich länger unbemerkt bleiben.

Der größte Schritt bisher

Die Portierungskarte aus Teil 2 fasst das Objektmodell zu einer Gruppe von 9.392 C++-Zeilen zusammen: aregion.cpp mit 3.271 Zeilen, unit.cpp mit 2.223, economy.cpp mit 1.218, object.cpp mit 632 und faction.cpp mit 630. Dazu kommen Märkte, Produktion, Quests sowie die Listen für Items und Fertigkeiten.

Das ist allerdings größer als der tatsächliche Umfang dieses Schritts.

Lesen und Schreiben des Spielstands gehören in Schritt 8, Berichte in Schritt 10, Zugverarbeitung in Schritt 11 und Weltgenerierung in Schritt 7. Fast alles in economy.cpp gehört ebenfalls dorthin; allein dort stecken 61 Aufrufe des Zufallsgenerators.

Deshalb wurde der Scope enger gezogen:

Dieser Schritt portiert die Modellklassen mit ihren Feldern, ihre Konstruktion, ihre Beziehungen und Methoden, die nur vom vorhandenen Objektzustand, den Datentabellen und GameDefs abhängen.

Alles andere bleibt bei seinem späteren Schritt.

Das hat eine etwas ungewohnte Konsequenz für die Portierungsstatistik. Die großen .cpp-Dateien bleiben auf in progress, obwohl aus ihnen bereits viel Python-Code entstanden ist. Fertig markiert wird eine Datei erst, wenn wirklich nichts Relevantes mehr fehlt.

Die Abdeckungsquote bewegt sich dadurch in diesem Teil kaum.

Das ist mir lieber als eine Zahl, die den Fortschritt schöner aussehen lässt, als er ist.

Woher kommen die Regeln?

Ein Problem taucht sofort auf, wenn aus C++-Globals Python-Objekte werden.

Die Referenz hat Globals, einen Zeiger auf die Konfiguration des Regelwerks, und globale Datentabellen. unit.cpp liest rund 80-mal aus Globals und 176-mal aus den Tabellen.

Sogar der Konstruktor von Unit braucht die Einstellungen:

// reference/unit.cpp
movepoints = Globals->PHASED_MOVE_OFFSET % Globals->MAX_SPEED;

Seit Teil 5 gilt für den Port: keine globalen Tabellen und kein globales Globals. GameData und GameDefs sind Objekte.

Man könnte sie nun durch jede Methodensignatur reichen. Bei so vielen Zugriffen würde das allerdings schnell zu Methoden wie

unit.foo(data, defs, ...)

führen, obwohl die Einheit ohnehin Teil genau eines Spiels ist.

Drei Varianten standen zur Wahl: data und defs an jede Methode übergeben, ein kleineres Kontextobjekt einführen oder das Game selbst zum Kontext machen.

Gewonnen hat die dritte Variante:

# src/atlantis_ng/core/game/__init__.py
@dataclass(eq=False)
class Game:
    data: GameData = field(repr=False)
    defs: GameDefs = field(repr=False)
    progressions: Progressions = field(repr=False)
    rng: Rng = field(default_factory=Rng, repr=False)
    factions: list[Faction] = field(default_factory=list[Faction], repr=False)
    regions: ARegionList = field(init=False, repr=False)
    quests: QuestList = field(init=False, repr=False)

Jedes Modellobjekt kennt sein Spiel. Aus Globals->X wird beispielsweise self.game.defs.x.

Das macht die Abhängigkeit nicht kleiner, aber ehrlich. Eine Einheit hängt ohnehin über ihre Fraktion, ihr Objekt und dessen Region an der Welt. Ein separates Kontextobjekt hätte diese Verbindung hauptsächlich versteckt.

Der Preis ist ebenfalls klar: Ein Modellobjekt existiert in diesem Port nicht sinnvoll ohne ein Game, und die Abhängigkeit steht nicht in jeder einzelnen Methodensignatur.

Freie Funktionen nehmen data und defs weiterhin explizit entgegen.

repr=False bei den großen Feldern ist übrigens keine reine Kosmetik. Ohne diese Angabe hätte eine fehlgeschlagene Dataclass-Assertion schnell alle sechzehn Spieldatentabellen in die Testausgabe geschrieben.

Identität statt Wertgleichheit

Die Modellklassen verwenden @dataclass(eq=False).

Das wirkt zunächst wie ein Detail, ist aber für diesen Port ziemlich zentral.

Ein Unit* in C++ bezeichnet eine bestimmte Einheit. Zwei Einheiten sind nicht deshalb dieselbe Einheit, weil Name, Inventar und Fertigkeiten zufällig gleich sind.

Bei unseren Modellklassen bleibt mit eq=False die Identitätssemantik von object erhalten. Zwei Instanzen vergleichen nur dann gleich, wenn es tatsächlich dasselbe Objekt ist. Sie behalten damit auch den Identitäts-Hash von object und können als Schlüssel in Dictionaries oder als Mitglieder von Sets verwendet werden.

Das braucht der Port beispielsweise für Faction::activity, das in C++ eine Map mit ARegion* als Schlüssel ist.

Die Entscheidung ist also keine typische „Dataclass-Einstellung“, sondern eine direkte Übersetzung der Zeigersemantik.

Die Listen sind weniger kompliziert. safe::list aus der Referenz schützt Iteratoren, wenn während einer Iteration Elemente entfernt werden. Im Python-Port werden normale Listen verwendet; an den betreffenden Stellen iteriert der Code über einen Snapshot der Liste.

Später zeigte ausgerechnet eine Klasse, die Wertgleichheit haben soll, wie schnell man zwischen beiden Modellen durcheinanderkommt.

Die Sonde

Bei einfachen Methoden kann man die Erwartungen aus dem C++-Code ableiten.

Bei Besitz- und Beziehungsfragen wollte ich mich darauf nicht verlassen.

Deshalb bekommt auch dieser Schritt eine C++-Sonde: tools/reference/model_probe.cpp. Sie wird gegen dieselbe gepinnte Referenz gelinkt wie die bisherigen Probes, baut Szenarien auf und schreibt Eingaben und Ergebnisse als JSON.

Das Muster kennen wir aus Teil 4, nur ist das Objektmodell deutlich größer.

Die Gegenargumente waren offensichtlich: Die Sonde kostet selbst viel Code. Sie prüft nur Szenarien, die wir ausdrücklich bauen. Und Sonde und Port entstehen im selben Projekt – ein Denkfehler kann also theoretisch auf beiden Seiten landen.

Trotzdem ist sie wertvoll.

Bei ItemList::Weight kann ich eine Erwartung noch mit dem Taschenrechner prüfen. Bei der Frage, welche Einheit nach dem Tod einer anderen deren Gegenstände erhält, möchte ich lieber sehen, was die Referenz tatsächlich tut.

Die Sonde begann mit 363 Zeilen und endete bei 2.094. Ihre Szenarien-Fixture wuchs von 150 auf 335 KB.

Sie wuchs zusammen mit den vier Pull Requests dieses Schritts: zuerst Listen, Märkte, Produktion, Quests und Befehle; dann Fraktionen, Objekte und Regionsstruktur; anschließend die Einheit und zuletzt der Rest der Region.

Für manche Tests muss die Sonde tiefer in Game greifen, als die öffentliche Schnittstelle erlaubt. regions und factions sind privat. Der Fork besitzt dafür bereits eine Freundesklasse für seine C++-Tests:

// tools/reference/model_probe.cpp
// game.h befriends this class for the fork's unit tests; the probe uses the same door to reach
// the regions and factions of a game.
class UnitTestHelper {
public:
    static ARegionList& regions(Game& game) { return game.regions; }
    static std::list<Faction *>& factions(Game& game) { return game.factions; }
};

Die Sonde definiert dieselbe Freundesklasse und benutzt den bereits vorgesehenen Testzugang.

Die Referenz selbst bleibt unverändert.

Ein float im Markt

Der erste Pull Request bringt die kleineren Teile des Modells: Items, Fertigkeiten, Märkte, Produktion, Quests, die 68 Befehlstypen aus orders.h – die Portierungskarte hatte vorher 69 gezählt – und das Grundgerüst von Game.

Die erste echte Überraschung steckt in Market::post_turn:

// reference/market.cpp
float ratio = ItemDefs[item].baseprice / (10 * (float)Globals->BASE_MAN_COST);
// hack: included new wage factor of ten in float assignment above
price = (int)((float) wages * 4 * ratio);

Diese Rechnung läuft in der Referenz mit einfacher Gleitkommagenauigkeit.

Das ist beobachtbar.

Für Zentauren bei einem Lohn von 25 landet die float-Variante beim Preis 12. Rechnet man dieselben Werte mit double, kommt nach der abschließenden Konvertierung 11 heraus.

CPythons float entspricht einem C-double. Der Port erzwingt deshalb an den relevanten Stellen wieder 32-Bit-Gleitkommagenauigkeit:

# src/atlantis_ng/core/market.py
def _f32(value: float) -> float:
    """``value`` rounded to a C ``float``, so the men's price comes out as the reference's."""
    return struct.unpack("f", struct.pack("f", value))[0]

Die Sonde prüft das über ein Raster aus 14 Märkten, sieben Bevölkerungswerten und sechs Löhnen.

Direkt daneben steckt das nächste kleine C++-Detail.

Bei ganzzahliger Division schneidet

(tarprice - price) / 5

in C++ zur Null hin ab. Pythons // rundet dagegen Richtung minus unendlich. Sobald price über tarprice liegt, können sich die Ergebnisse um eins unterscheiden.

Das sind genau die Fehler, die bei einem Port harmlos aussehen: Die Zahl ist plausibel, nur eben ein Silberstück falsch.

Die Welt als Orakel

Für Fraktionen, Objekte und Regionen reichen kleine handgebaute Szenarien irgendwann nicht mehr aus.

Also bekam die Sonde einen zweiten Modus:

model_probe world

Er erzeugt über Game::NewGame eine vollständige standard-Welt mit demselben Seed wie das Vergleichs-Harness aus Teil 3 und dumpt ihren Zustand.

Der erste Versuch war mit 3,5 MB zu groß. Er enthielt alle 2.049 Regionen samt Objekten, Produkten und Märkten in ausführlicher JSON-Form.

Für ein Fixture, das bei jeder Abweichung im Diff landet, ist das wenig angenehm.

Die zweite Fassung speichert deshalb die Topologie aller Regionen, aber den ausführlichen Zustand nur für eine Stichprobe. Objekte und Produkte werden kompakter als positionale Arrays geschrieben, Märkte fallen aus dem Weltdump heraus.

Damit sank die Fixture zunächst auf 485 KB.

Die Stichprobe enthält jede Region mit Stadt oder Gebäude sowie jede 32. Region: 332 Regionen, darunter 115 Städte.

Die Python-Seite erzeugt dieselbe Grundtopologie mit dem portierten MakeRegions, setzt für die Stichprobe den Zustand aus der Fixture ein und ruft anschließend dieselben Methoden auf wie die Sonde: Küstenerkennung, Straßen, Poldistanz, Bewegungskosten, Löhne, Entwicklung und Kurzdarstellung.

Der Vergleich lief beim ersten Versuch durch.

Was eine frisch erzeugte Welt nicht enthält, ergänzt ein handgebautes 4-mal-4-Level: verbundene und unterbrochene Straßen, eine unfertige Straße, Turm, Farm und Gasthaus, eine Stadt, mehrere Wetterzustände und drei Flotten. Dazu kommen Segeltests aus verschiedenen Richtungen mit und ohne PREVENT_SAIL_THROUGH.

Dort waren zwei Erwartungen im Test falsch: einmal eine Konstante, die als rohe Zahl eingetragen worden war, und einmal der Name des Dummy-Objekttyps. Die Referenzdaten entschieden beide Fragen.

In diesem Pull Request kam außerdem ein Stück economy.cpp früher als ursprünglich geplant: die zufallsfreien Berechnungen für Bevölkerung, Löhne, Entwicklung und Stadtgröße.

Der Grund war praktisch. Mit dem Weltdump existierte jetzt genau das Orakel, das diesen Funktionen vorher gefehlt hatte.

Die Abweichung vom Plan wurde im Journal festgehalten, bevor der Code verschoben wurde.

Die Einheit und der Importzyklus

Der dritte Pull Request ist der größte: core/unit.py wächst auf 1.904 Zeilen. Dazu kommen alle Methoden von Objekt, Fraktion und Region, die auf Einheiten zugreifen und deshalb bisher warten mussten.

Dabei taucht ein Problem auf, das in C++ anders gelöst wird.

unit.h und faction.h brauchen sich gegenseitig. C++ kann dafür Vorwärtsdeklarationen verwenden. Python führt Module beim Import aus, also kann daraus ein zirkulärer Import entstehen.

Im Port sieht die Verbindung so aus:

# src/atlantis_ng/core/unit.py
from atlantis_ng.core import faction as factions  # isort: skip

und auf der anderen Seite:

# src/atlantis_ng/core/faction.py
from atlantis_ng.core import unit as units  # isort: skip

Wichtig ist, dass beide Seiten das jeweils andere Modul importieren, nicht sofort einzelne Namen daraus.

Bei diesem konkreten Zyklus funktioniert das, weil Python das bereits angelegte Modulobjekt in sys.modules kennt und factions.AttitudeType beziehungsweise units.Reveal erst ausgewertet werden, wenn die betreffende Methode später läuft.

Ein

from atlantis_ng.core.faction import AttitudeType

würde den Namen dagegen schon während des Imports benötigen. Ist faction.py zu diesem Zeitpunkt noch nicht bis zu seiner Definition gekommen, scheitert der Import wegen des teilweise initialisierten Moduls.

orders.py hatte ein ähnliches Problem mit UnitId. Dort wird der Name nur in Typannotationen gebraucht und deshalb unter TYPE_CHECKING importiert.

Beziehungen müssen auf beiden Seiten stimmen

Die Verbindung zwischen Einheit und Objekt steckt im Wesentlichen in einer Methode.

In der Referenz:

// reference/unit.cpp
void Unit::MoveUnit(Object *toobj)
{
    if (object) std::erase(object->units, this);
    object = toobj;
    if (object) {
        object->units.push_back(this);
        ...
    }
}

Im Port:

# src/atlantis_ng/core/unit.py
def move_unit(self, toobj: Object | None) -> None:
    if self.object is not None:
        self.object.units.remove(self)
    self.object = toobj
    if toobj is None:
        return
    toobj.units.append(self)
    ...

Eine Einheit speichert also nicht bloß ein neues object. Gleichzeitig muss sie aus der Liste des alten Objekts verschwinden und in der des neuen auftauchen.

Hier zahlt sich eq=False aus: list.remove vergleicht zwar mit ==, bei diesen Modellklassen bedeutet das aber Identität. Entfernt wird genau diese Einheit.

Noch deutlicher wird der Unterschied zwischen C++-Besitz und Python-Referenzen beim Tod einer Einheit.

ARegion::Kill sucht zunächst eine andere Einheit derselben Fraktion in der Region und überträgt dorthin das Inventar. Soldaten werden nicht wie normale Gegenstände vererbt, bei unfertigen Schiffen gelten eigene Regeln und auf hoher See darf die Übertragung nicht dazu führen, dass die erbende Einheit anschließend ertrinkt.

Danach verschwindet die tote Einheit aus ihrem Objekt und landet in hell.

Die C++-Referenz ruft später in ClearHell delete auf.

Der Python-Port übernimmt die sichtbaren Zustandsänderungen, aber natürlich nicht das manuelle delete. hell wird geleert; gibt es danach keine Referenz mehr auf die Einheit, wird ihr Speicher von Python freigegeben.

Hier tut der Port bewusst weniger als das Original, ohne Spielverhalten wegzulassen.

Ein Absturz, den offenbar niemand ausgelöst hat

Die Sonde sollte auch Unit::SkillStarvation prüfen.

Diese Methode greift, wenn ein hungernder Charakter bei aktivierter SKILL_STARVATION-Regel lieber eine Fertigkeitsstufe verliert als Männer.

Der Referenzlauf kam allerdings nicht bis zum Ergebnis: Die Referenz brach mit einem std::logic_error ab.

Die problematische Schleife sieht so aus:

// reference/unit.cpp
for (c=0;c < sizeof(SkillDefs[i].depends)/sizeof(SkillDefs[i].depends[0]);c++) {
    std::string skname = SkillDefs[i].depends[c].skill;
    if (skname == SkillDefs[j].abbr) {

depends[c].skill ist ein char*. Ungenutzte Abhängigkeitsslots enthalten nullptr.

Der Konstruktor von std::string erwartet hier einen gültigen C-String. Ein Nullzeiger erfüllt diese Vorbedingung nicht; der verwendete libstdc++-Build reagiert darauf mit std::logic_error.

Die Schwesterfunktion CanStudy prüft denselben Slot vorher auf NULL. SkillStarvation tut es nicht.

Keines der acht Regelwerke des Forks aktiviert SKILL_STARVATION. Der Pfad wird also seit Jahren kompiliert, aber offenbar von diesen Regelwerken nie ausgeführt.

Was soll ein Kompatibilitätsport an so einer Stelle reproduzieren?

Es gibt kein brauchbares Referenzergebnis.

Der Port übernimmt deshalb die erkennbare Absicht des Codes: Wenn möglich verliert die Einheit eine Fertigkeitsstufe, die sie ohne Abhängigkeitsbruch vergessen kann; andernfalls verliert sie Männer. Die Tests dafür beruhen auf nachvollziehbaren Szenarien statt auf der Sonde.

Im Journal und in der Portierungskarte steht ausdrücklich, warum dieser Fall anders getestet wird. Eine Änderung am C++-Fork wäre ein eigener Vorgang und nicht Teil des Ports.

Auch diese Tests waren übrigens nicht auf Anhieb richtig. Der Agent hatte 90 Studientage als Fertigkeitsstufe 3 interpretiert.

Es ist Stufe 2.

Hier brauchte es keine Sonde, sondern einen Blick auf die Stufentabelle.

Short und die eigene Schleifenvariable

Direkt daneben liegt Unit::Short, die normale Hungerbehandlung ohne SKILL_STARVATION.

Auch dieser Code hat zwei bemerkenswerte Stellen.

Die Schleife läuft bis einschließlich NITEMS:

for (i = 0; i<= NITEMS; i++)

Gültige Item-Indizes enden aber bei NITEMS - 1. Der letzte Durchlauf liegt also außerhalb der Tabelle.

Der Python-Port beendet die Schleife am letzten gültigen Eintrag. Für den Zugriff hinter dem C++-Array gibt es kein definiertes Ergebnis, das man sinnvoll erhalten könnte.

Die zweite Eigenheit ist dagegen definiert und damit beobachtbares Verhalten.

Unter einem Unterhaltsmultiplikator überschreibt die Funktion ihre eigene Schleifenvariable:

// reference/unit.cpp
if (Globals->MULTIPLIER_USE == GameDefs::MULT_ALL) {
    levels = SkillLevels();
    i = levels * Globals->MAINTENANCE_MULTIPLIER;
    if (i < Globals->MAINTENANCE_COST)
        i = Globals->MAINTENANCE_COST;
    needed -= i;
}

Nach dem ersten Mann einer Sorte läuft die äußere Schleife dadurch von einem Wert weiter, der eigentlich Unterhaltskosten darstellt – nun aber als Item-Index verwendet wird.

standard nutzt diesen Multiplikator nicht. Ein anderes Regelwerk könnte den Pfad aber aktivieren.

Der Port übernimmt deshalb diese merkwürdige Veränderung der Schleifenvariable und kommentiert sie ausdrücklich.

Das ist derselbe Grundsatz wie beim kaputten Satz im Regelbuch aus Teil 6: Definiertes, beobachtbares Referenzverhalten bleibt zunächst erhalten, auch wenn es offensichtlich nicht schön ist.

Ein Heap, der zum Referenzverhalten gehört

Der vierte Pull Request portiert den verbleibenden Regionscode, soweit er keinen Ruleset-Hook benötigt. Dazu gehören der Verfall von Gebäuden und zwei Suchen durch Nachbarregionen und Schächte.

Eine davon, get_connected_distance, bestimmt unter anderem die Reichweite von Zaubern.

Sie ähnelt Dijkstra, hat aber eine entscheidende Abweichung:

// reference/aregion.cpp
if (n && visited_regions.insert({n->xloc, n->yloc, n->zloc}).second) {
    q.push({n, cur_dist + cost });
}

Eine Region gilt bereits als besucht, sobald sie in die Queue kommt – nicht erst dann, wenn ihr kürzester Weg feststeht.

Wird dieselbe Region zuerst über einen teuren Übergang zwischen Ebenen entdeckt, kann ein später gefundener günstigerer Weg sie nicht mehr verbessern.

Damit wird plötzlich wichtig, welche von zwei Queue-Einträgen mit derselben Distanz zuerst verarbeitet wird.

Die Referenz verwendet eine std::priority_queue.

C++ garantiert für Elemente, die der Comparator als gleichrangig behandelt, keine stabile Reihenfolge. In unserem Referenz-Build ergibt sich die konkrete Reihenfolge aus der Heap-Implementierung von libstdc++.

Normalerweise sollte ein Algorithmus davon nicht abhängen.

Dieser tut es.

Für den Kompatibilitätsport wird damit aus einem Implementierungsdetail beobachtbares Referenzverhalten.

Der Python-Port verwendet deshalb nicht einfach heapq, sondern eine kleine _DistanceQueue, die die relevanten Schritte von __push_heap und __adjust_heap aus libstdc++ nachbildet:

# src/atlantis_ng/core/region.py
def _sift_down(self, hole: int, length: int, value: tuple[ARegion, int]) -> None:
    top = hole
    child = hole
    while child < (length - 1) // 2:
        child = 2 * (child + 1)
        if self.heap[child - 1][1] < self.heap[child][1]:
            child -= 1
        self.heap[hole] = self.heap[child]
        hole = child
    if length % 2 == 0 and child == (length - 2) // 2:
        child = 2 * (child + 1)
        self.heap[hole] = self.heap[child - 1]
        hole = child - 1
    self._sift_up(hole, top, value)

Die nächste Frage war wichtiger als die Implementierung selbst:

Kann unser Test diesen Unterschied überhaupt sehen?

Die Sonde besitzt dafür eine handgebaute Welt mit drei Ebenen und zwei Schächten. Sie zeichnet 589 Distanzen auf.

Ein Wegwerfskript ersetzte die portierte Queue probeweise durch zwei Varianten auf Basis von heapq: einmal mit FIFO-, einmal mit LIFO-Reihenfolge bei gleicher Priorität.

Das Ergebnis:

libstdc++ wrong rows: 0 of 589
heapq fifo wrong rows: 3 of 589
heapq lifo wrong rows: 15 of 589

Mit einer scheinbar vernünftigen Queue wären also je nach Tie-Breaker drei oder fünfzehn der 589 Ergebnisse falsch.

Die Fixture kann den Unterschied tatsächlich erkennen.

Und wenn die Queue leer ist?

Die Suche enthält noch einen anderen Randfall.

Ist das Ziel unerreichbar und begrenzt maxdist die Suche nicht, kann die Queue leer werden. Die C++-Referenz versucht danach trotzdem, auf das nächste Element der std::priority_queue zuzugreifen.

Das verletzt die Vorbedingung des Containers: Auf eine leere Queue darf nicht mit top() beziehungsweise pop() zugegriffen werden.

Beim ersten Probe-Szenario mit diesem Fall hing der Referenzprozess rund zehn Minuten, bis das Timeout ihn beendete.

Der Python-Port liefert stattdessen UNREACHABLE_DISTANCE.

Das ist eine bewusste Definition für einen Fall, in dem die Referenz kein definiertes C++-Verhalten vorgibt. Es gibt dort keinen stabilen Rückgabewert, den der Port erhalten könnte.

Eine kleine Ironie am Rand: Die Sonde konnte ihre handgebaute Testwelt nicht direkt in eine ARegionList einsetzen, weil es dafür keine öffentliche Schnittstelle gibt.

Also schreibt sie die Regionen zunächst in das Speicherformat der Referenz und liest sie anschließend mit ReadRegions wieder ein.

Die Referenz baut sich ihre Testwelt damit über ihren eigenen Loader.

Was die Sonde tatsächlich gefunden hat

Über vier Pull Requests hinweg liefen erstaunlich viele Vergleiche sofort durch: 332 Regionen des ersten Weltdumps, später 288 Einheiten der erweiterten Stichprobe, Studien- und Übungsszenarien, Ausrüstungswahl, Gebäudeverfall und die Distanzsuche.

Einen echten Portierungsfehler fand die Sonde trotzdem.

Und ausgerechnet dort ging es wieder um Gleichheit.

deduplicate_unit_list entfernt doppelte UnitIds aus einer Befehlsliste. UnitId ist keines der Modellobjekte mit Identitätssemantik, sondern eine normale Dataclass mit Wertgleichheit. Zwei IDs mit derselben Nummer sollen gleich sein.

Die erste Portfassung entfernte während der Iteration mit list.remove den aktuellen Wert.

list.remove entfernt aber das erste gleiche Element – nicht zwingend genau die Instanz, bei der die Iteration gerade angekommen ist.

Bei einer Liste mit Wiederholungen war das beobachtbar. Die Sonde meldete die Abweichung.

Der Port baut die deduplizierte Liste jetzt neu auf, statt Elemente während der Iteration herauszulöschen.

Die anderen beiden Abweichungen im handgebauten Regionsszenario lagen auf der Testseite. Und die falsch angenommene Hungerstufe fand ebenfalls kein Referenzvergleich, sondern der eigene Unit-Test.

Die Sonde ersetzt also nicht das Nachdenken. Sie ergänzt es.

Was das Orakel kostet

Die Modellsonde ist am Ende größer als manches Programm: 2.094 Zeilen C++.

Dazu kommen zwei Fixtures. Die Szenarien belegen rund 335 KB, der Weltdump nach der Erweiterung 710 KB.

Die Weltstichprobe wurde im dritten Pull Request noch einmal erweitert: Zusätzlich zu den bisherigen Regionen kam ein Drittel der Regionen mit Einheiten im Freien hinzu, damit auch wandernde Monster im Vergleich vorkommen.

Die Kosten waren aber nicht nur Repository-Größe.

Nach dem dritten Pull Request brauchten zwei Welt-Replays zusammen etwa sieben Sekunden. Das meiste davon steckte überraschenderweise in lookup_item.

Die Ursache war ci_key, die ASCII-Normalisierung aus Teil 4. Sie lief für jeden Buchstaben durch Python-Code und wurde einige tausend Mal aufgerufen.

Gemessen kostete ein Lookup dadurch ungefähr zwei Millisekunden.

Erst nach dieser Messung wurde optimiert: str.translate erledigt dieselbe ASCII-Abbildung jetzt über eine vorbereitete Tabelle.

Das war die erste Performance-Optimierung dieser Serie.

Nicht weil die alte Fassung „langsam aussah“, sondern weil ein gemessener Lauf auf genau diese Funktion gezeigt hat.

Stolperfallen

• Zeiger bedeuten Identität, nicht Wertgleichheit. Für die Modellobjekte ist @dataclass(eq=False) deshalb keine Stilfrage. UnitId zeigt zugleich, dass es Klassen gibt, bei denen Wertgleichheit ausdrücklich richtig ist.
• Zirkuläre Imports brauchen einen Blick auf den Zeitpunkt der Namensauflösung. In diesem konkreten Zyklus funktioniert der gegenseitige Modulimport, weil die Attribute erst später benutzt werden. Ein früh ausgewerteter from ... import Name würde auf ein noch nicht vollständig initialisiertes Modul treffen.
• Tote Codepfade sind auch in der Referenz ungetestet. SkillStarvation wird von keinem Regelwerk des Forks aktiviert. Erst die Sonde hat den ungültigen std::string-Konstruktor erreicht.
• Nicht definiertes C++-Verhalten lässt sich nicht sinnvoll konservieren. Ein Zugriff hinter ItemDefs oder auf eine leere priority_queue hat keinen stabilen Referenzwert. Der Port muss für solche Fälle ein eigenes definiertes Verhalten wählen und die Abweichung dokumentieren.
• Ein Implementierungsdetail kann trotzdem beobachtbar werden. Die Reihenfolge gleichrangiger Heap-Einträge garantiert std::priority_queue nicht. Weil der Algorithmus davon abhängt, muss der Port für diese gepinnte Referenz die libstdc++-Reihenfolge reproduzieren.
• Fixtures brauchen ein Datenbudget. Der erste Weltdump hatte 3,5 MB. Topologie für alle Regionen und Detailzustand nur für eine Stichprobe machten daraus ein handhabbares Orakel.
• Erst messen, dann optimieren – auch Testcode. Sieben Sekunden Welt-Replay führten über ein Profil zu ci_key. Erst danach wurde die Implementierung durch str.translate ersetzt.

Der Stand nach Teil 7

Vier Pull Requests, der Code von Schritt 6 ist vollständig.

Zwölf Module bilden das Objektmodell: game, faction, object, region, unit, items, skills, market, production, quests, orders und economy. Zusammen sind das 5.457 Zeilen Python.

Eine Einheit kann jetzt unter anderem in ein Gebäude ziehen, sterben und beerbt werden, studieren, hungern, andere Einheiten sehen, Steuern eintreiben und für den Kampf Ausrüstung wählen. Regionen kennen ihre Nachbarn, Straßen, Gebäude und Einheiten. Flotten berechnen Ladung und Geschwindigkeit. Fraktionen verwalten Beziehungen und Aktivitäten.

Die Modellsonde hat 2.094 Zeilen C++ und zwei Modi. Ihre Fixtures umfassen rund 335 KB Szenarien und 710 KB Weltdaten.

306 schnelle Tests laufen in etwa fünf Sekunden. Zehn Referenztests bauen die Sonde frisch in Docker und vergleichen ihre Ausgabe mit den Fixtures; der CI-Job brauchte für den vierten Pull Request 1:42 Minuten.

Die Portierungsabdeckung steht bei 27,8 Prozent: 13.329 von 47.949 Zeilen.

Das ist nur ein Prozentpunkt mehr als nach Teil 6, obwohl rund 5.500 Zeilen Python dazugekommen sind. Der Grund steckt im Scope dieses Schritts: Keine der großen Modelldateien ist im Sinne der Portierungskarte bereits vollständig abgeschlossen. unit.cpp behält sein Datei-I/O für Schritt 8 und seine Berichte für Schritt 10. aregion.cpp enthält zusätzlich noch Weltgenerierung.

Die Statistik springt erst, wenn diese späteren Schritte die Dateien wirklich abschließen.

Einige Methoden fehlen ebenfalls bewusst noch. SetGateStatus, GetPlanarDistance und die Suche nach der nächsten Startstadt hängen an Funktionen, die jedes Regelwerk in seiner eigenen world.cpp implementiert. Sie kommen im nächsten Schritt zusammen mit dem Ruleset-Interface. Monsterhöhlen entstehen nur beim Weltbau. Die Weltstatistikfunktionen schreiben ausschließlich Logs, und auch das Logging bekommt erst noch eine klare Schnittstelle.

Einen vollständigen Zug kann die Python-Engine weiterhin nicht berechnen.

Aber zum ersten Mal existiert der Objektgraph, auf dem ein Zug überhaupt stattfinden kann.

Als Nächstes muss daraus eine Welt werden.

Schritt 7 portiert die Weltgenerierung von standard: Ebenen, Kontinente, Terrain, Städte und Namen, alles aus einem festen Seed. Der Weltdump, der in diesem Teil noch Orakel für Regionen und Objekte war, wird dann zum Done-Kriterium:

derselbe Seed, dieselbe Welt – Region für Region.

Weiterlesen

• Atlantis PbeM neu geschrieben (Teil 6) – das Regelbuch und die Frage, wann kaputtes Referenzverhalten trotzdem erhalten bleibt.
• Atlantis PbeM neu geschrieben (Teil 4) – die Zufallssonde, deren Muster die Modellsonde übernimmt.
• Dataclasses: Klassen ohne Boilerplate – eq=False, field(repr=False) und default_factory, alles hier im Einsatz.
• Type Hints in der Praxis: mypy, Pyright und Co. – warum orders.py UnitId nur unter TYPE_CHECKING importiert.

Sources: unit.cpp, aregion.cpp, market.cpp und game.h des Forks, std::priority_queue, std::push_heap, libstdc++ stl_heap.h, Python heapq, Python struct, Python dataclasses, Python: der Importmechanismus.