Am 9. März 2019 hat zum ersten Mal eine Spielerin alle zugänglichen Sternensysteme von EVE-Online erkundet. Katia Sae hat nach eigenen Angaben für diese Reise über neun Jahre gebraucht und dabei 7806 Systeme in der Spielwelt besucht.

Die Systeme von EVE lassen sich in zwei Klassen einteilen: Zum einen gibt es den „Known Space“ („K-Space“), in dem die einzelnen Sterne mit Warptoren verknüpft sind. Jeden Stern umgeben ein oder mehrere Tore, von denen jedes in ein anderes System führt. Damit ergibt sich ein Netz von Warpverbindungen, das die Reiserouten der Spieler vorgeben. Die zweite Klasse bilden die Systeme des „Wormhole Space“. Diese sind untereinander um mit dem K-Space über zufällig erscheinende und wieder verschwindende Wurmlöcher verbunden. Während mittels Warptore 5201 Systeme erreichbar sind, umfasst der Wormhole Space in etwa die Hälfte, nämlich 2604.

Mit dem Finger über die Sternkarte

Natürlich inspiriert Katia mit Ihrer Reise unzähliche Spieler wie mich, es ihr gleich zu tun. Allerdings sitzt mein EVE-Character wohl lieber in Hek und ballert sich Quafe mit Schuss (oder so), als knapp 8000 Systeme abzuklappern. Aber mal angenommen, er wäre weniger von der faulen Sorte: Wie lange würde er brauchen, um alle Systeme von EVE zu besuchen? Um die richtigen Wurmlöcher zu finden braucht man eine gute Portion Glück und viel Ausdauer. Was also für die Wurmloch-Systeme schwer zu schätzen ist, sollte sich zumindest für den K-Space grob berechnen lassen: Die Warptore sind auf der Karte verzeichnet und einfach anzufliegen.

Eine Retriever fliegt das Uttindar-Hek-Warptor an.

Nachdem die Reise also auf die 5201 mittels Warptoren verbundenen Systeme von New-Eden beschränkt wurde, stellt sich dem reisefreudigen Piloten die Frage, wie viele Sprünge ein Schiff eigentlich braucht, um alle Systeme zu besuchen. Während einige Systeme Knotenpunkte mit vielen Warptoren darstellen, sind andere Flaschenhälse auf der Karte oder auch Sackgassen. Er wird also einige Systeme mehr als einmal besuchen müssen. Aber das Ziel ist klar: Gesucht wird ein möglichst kurzer Pfad durch alle Systeme, womit die Geschichte ein wenig an das berühmte Traveling Salesman Problem erinnert.

Python im Bordcomputer

Weil der Travelling Spaceman keine Lust hat, diesen optimalen Pfad per Hand auf der Karte zu finden, soll ein kleines Python-Skript helfen. Der Ansatz ist eine teils zufallsbedingte Wegfindung, die in guter alter Brute-Force-Manier ein paar tausend Mal ausgeführt wird. Das Programm umfasst mehrere Aufgabenbereiche:

  • Laden der Sternensysteme und ihrer Warptore über die EVE-Online-API
  • Logik zum Finden eines Pfades durch alle System
  • Würfeln einiger Parameter und häufiges Ausführen
  • Ausgeben des besten Pfades sowie einiger Statistiken

Die Reise beginnt wie die von Katia in Saisio. Der Algorithmus versucht, immer in möglichst wenigen Sprüngen auf ein System zu treffen, das noch nicht besucht wurde. Der einzige Spielraum bei diesem Ansatz ist die Auswahl des Warptores, wenn mehrere Kandidaten zu unbesuchten Systemen zur Verfügung stehen. Wird im momentanen Aufenthaltsort kein passendes Tor gefunden, erweitert sich das Suchfeld Schritt für Schritt. Bleibt er auch hier erfolglos folgt er dem Pfad System für System zurück und sucht dort nach übriggebliebenen Systemen. So wird sichergestellt, dass am Schluss auch alle 5201 Systeme abgeflogen werden können.

Im ersten Ansatz wurde das Warptor rein zufällig ausgewählt. Im nächsten Versuch sollten Tore der selben Konstellation bevorzugt werden. Die Idee dahinter ist, dass die Sterne in New-Eden in Konstellationen angeordnet sind. Während die Systeme einer Konstellation oft viele Verbindungen haben, sind Routen zwischen den Konstellationen seltener und stellen Flaschenhälse dar. Im dritten Versuch sollten dann Systeme mit weniger Anschlussmöglichkeiten zuerst besucht werden. Die Idee ist, dass Sterne mit vielen Toren Knotenpunkte darstellen, die früher oder später durchflogen werden müssen. Als vierten Schritt sollten die beiden vorherigen Methoden kombiniert werden. Der letzte Optimierungsversuch bestand darin, nicht nur die Anzahl der Tore zu berücksichtigen, sondern auch zu prüfen, ob die Systeme, in die sie führen, schon besucht wurden.

Alle Wege führen nach Itamo

Jeder Ansatz wurde einige tausend Male ausgeführt, wobei die Ausführzeit pro Versuch etwa eine Sekunde betrug. Womit wir endlich zu dem kommen, was EVE- aka „Spreadsheet Simulator“-Spieler am liebsten lesen: Statistiken! Als erstes ein Vergleich der verschiedenen Ansätze:

AnsatzKürzesterDurchschnitt
Zufälliges Tor wählen89379081
Gleiche Konstellation bevorzugen88058948
Weniger Tore bevorzugen81948204
Weniger Tore zu unbesuchten Systemen
bevorzugen
79108113
Weniger Tore und gleiche Konstellation bevorzugen78908056
Weniger Tore zu unbesuchten Systemen
und gleiche Konstellation bevorzugen
78258060

Es sieht so aus als ob die Optimierungen tatsächlich etwas optimiert hätten. Jedenfalls klingt eine Pfadlänge von unter 8000 Sprüngen schon mal nicht schlecht. Schauen wir uns mal an, welche Systeme am meisten besucht wurden.

RangSystemKonstellationRegionWarptoreBesuche
1ItamoRuomoThe Forge66,01
2A1-AUHR2-BT6Esoteria45,33
3J-TPTAJ-TPTAFeythabolis55,06
4EysturSveiparHeimatar64,91
5HekBarvigrardMetropolis54,46
1677JitaKimotoroThe Forge71,87

Ganz vorne mit dabei sind Systeme, die mehrere Sackgassen mit der restlichen Galaxie verbinden. Der Spitzenreiter Itamo ist hier ein Paradebeispiel. Verwunderlich ist nur, dass sich der Algorithmus wohl ein paar mal dazu entschieden hat, mehr als sechsmal dort vorbeizuschauen. Demgegenüber wurden 1366 Systeme bei keinem einzigen der Durchläufe mehr als einmal aufgesucht. Zum Vergleich mit dabei: Der berühmte Handelsposten Jita. Obwohl es hier gleich sieben Tore gibt, wurde es im Schnitt weniger als zweimal besucht.

Itamo muss sechsmal besucht werden.

Nach ungefähr 20.000 Versuchen war das beste Ergebnis ein Pfad mit 7825 Sprüngen. Es ist natürlich nicht unwahrscheinlich, dass man mit ein paar Durchläufen mehr (oder noch einigen Optimierungen in der Logik) eine bessere Route finden kann. Der ultimative Vergleich ist natürlich der zur Route unserer Heldin selbst: Katia hat die Reihenfolge der von ihr besuchten Systeme veröffentlicht. Allerdings sind hier nur die jeweils neu besuchten Systeme verzeichnet. Wenn man die Lücken dazwischen mit den notwendigen Sprüngen füllt, ergibt sich eine Route von mindestens 8217 Sternen. Nach unseren Ergebnissen hätte Katia das in fast 400 Sprüngen weniger schaffen können. Aber abgesehen davon, dass sie unterwegs vermutlich noch das eine oder andere zu erledigen hatte: Was sind schon 400 Sterne für jemanden, der eine ganze Galaxie gesehen hat?

Das Katia Sae Monument in Saisio wurde nach ihrer erfolgreichen Reise errichtet.