Alt-F4 #63 - Dana Dev-Blog: Spaghettirezeptgraphen 12.08.2022
übersetzt von EDLEXUS
Nach einer etwas längeren Pause kommt Alt-F4 zurück mit einer Ausgabe, die an die guten alten FFF erinnert: einem Dev-Blog! Hier geht es allerdings nicht um das Spiel an sich, sondern um eine sehr eigene und besondere Mod. Credne hat Dana in diese Welt gesetzt, und es hat einiges benötigt, um dahin zu kommen. Viele technische Details und verrückte Fußballideen werden folgen, also viel Spaß damit!
Dana Dev-Blog: Über Spaghetti in Rezeptgraphen Credne
Dana … Was ist das?
Dana ist eine Mod, welche versucht eine einfache Frage in Factorio zu beantworten: “Wie stelle ich Item X her?”.
Es gibt bereits einige Mods, die diese Frage beantworten: FNEI, Recipe Book, What is it really used for und viele weitere. Diese Mods haben einen gemeinsamen Ansatz: Sagen wir einmal, ein neuer Spieler möchte herausfinden, wie Wissenschaftspakete für Chemie (die blauen) hergestellt werden. Der Spieler verwendet eine der verbreiteten Mods (oder Factorios eigene Rezeptübersicht) und findet ein einzelnes Rezept, welches rote Schaltkreise, Schwefel und Motoreinheiten benötigt. Jetzt wundert sich der neue Spieler “Wie mache ich rote Schaltkreise?”, sucht danach, sieht ein einzelnes Rezept, welches Plastik, Kupferkabel und grüne Schaltkreise benötigt. Der nächste Gedanke ist: “Wie mache ich Plastik?”: Ein Rezept mit Flüssiggas. “Wie mache ich Flüssiggas?”: Vier Rezepte, welche man sich alle nacheinander anschauen muss, und so weiter. Dieser Prozess ist zeitaufwändig, nervig und es ist wahrscheinlich, das der Spieler einen Schritt vergisst (wie Schwefel oder Stahl).
Dana kommt aus der Frustration, diesen Prozess für große Modpacks für eine lange Zeit anzuwenden, und verwendet einen etwas anderen Ansatz, um diese Fragen zu beantworten:
In Dana geht es um Tiefe: Wenn man fragt, wie Wissenschaftspakete für Chemie hergestellt werden, zeigt es alle benötigten Schritte, um das Produkt aus Rohstoffen herzustellen. Und das tut es direkt im Spiel, indem es einen schönen™ und verständlichen™ Rezeptgraph zeichnet. Spieler können darin mit WASD navigieren, mit dem Mausrad rein-&rauszoomen und Knoten oder Kanten auswählen, für zusätzliche Informationen. Es ist auch möglich, einen vollständigen Herstellungsgraph des aktuellen Spiels zu zeichnen (der für Vanilla wird später gezeigt) oder einen “Verwendungs-“Graph, der zeigt, was aus einem Material hergestellt werden kann.
Dana ist dazu designt, problemlos mit Mods klarzukommen, welche Rezepte oder Gegenstände erweitern/verändern/entfernen. Es gibt keine hardgecodete Konfiguration, welche mit Dana mitgeliefert wird. Im Video hat es Kupfer zwischen Eisen und der Raffinerie platziert, Schweröl über dem Leichtöl und entschieden, wie die Linien dazwischen gezeichnet werden sollen, entschieden was die X/Y-Koordinaten der einzelnen Elemente sein soll und vieles mehr. Alles was Dana dafür zur Verfügung hatte, war eine vollständige Liste mit allen Items, Rezepten und was die natürlich vorkommenden Rohstoffe sind. Das wird mit einem Graph-Layout-Algorithmus erreicht (ein Stück Code, welches die Rezepte/Items nimmt und entscheidet, wo sie platziert werden sollen und wie die Verbindungen aussehen sollen). Dieser Algorithmus ist speziell für Factorio entwickelt und soll Thema dieses Artikels sein.
Dev-Blog: Zeichnen der Graphen-Spaghetti
Der heutige Artikel wird einige (hoffentlich interessante) Details über die inneren Abläufe in Dana’s schönem™ und verständlichen™ Graphengenerator verraten. Un einen allgemeinen Einstieg zu geben, sind Dana’s Graphen sogenannte layered graphs. Das bedeutet, dass Gegenstände und Rezepte in Knotenebenen platziert sind, welche durch Kantenebenen geteil sind.
Das erste was Dana tut ist zu entscheiden, wie viele Ebenen benötigt werden, und in welche Ebene jedes Item/Gegenstand platziert wird. Der zweite Schritt ist zu entscheiden, welche horizontale Koordinate jedem Item/Rezept zugeordnet wird. Der dritte Schritt sind die Kantenebenen. Der letzte Schritt ist es, jedem Element eine vertikale Koordinate zuzuordnen, da jetzt die Anzahl der Ebenen und ihre Höhe bekannt ist.
Der gesamte Layout-Algorithmus ist zu groß und zu technisch für einen Alt-F4-Artikel, so dass wir uns im Folgenden nur auf den dritten Schritt konzentrieren werden, in dem die Kantenebenen gebaut werden. Hier ist die Problemstellung: bei zwei gegebenen aufeinanderfolgenden Knotenebenen, zeichne die benötigten Kanten in der Kantenebene, um einen schönen™ und verständlichen™ Graphen zu zeichnen:
Praktischerweise ist das mehr oder weniger eine Übung für Kindergartenkinder:
Da 5-Jährige dieses Problem lösen können, sollte es ja nicht so schwer zu programmieren sein, oder?
Das Design: “schöner™” und “verständlicher™” Graph?
Zuerst nehmen wir Zettel und Stift (oder dein bevorzugtes Bildbearbeitungsprogramm) und beantworten eine wichtige Frage: wie sollte die Kanten aussehen? Wie man sich vorstellen kann, ist es relativ schwer zu definieren, was einen Graphen schön™ und verständlich™ macht.
Vielleicht einfach gerade Linien, wie bei den meisten Graphrendern?
Das erfüllt die Anforderungen für kleine Graphen, aber ist nicht schön™ und verständlich™ für breite Graphen. Fast parallele Linien, welche sich schneiden sind nicht leicht nachzuverfolgen und Gegenden mit vielen Kanten werden einfach zu einem unverständlichen Blob. Die gute alte gerade Linie ist nicht gut genug für Vanilla, von gemoddeten Spielen ganz zu schweigen!
Also zurück ans Reißbrett für eine schönere™ und verständlichere™ Lösung. Erinnern wir uns einmal an einige generelle Richtlinien für Nutzerfreundlichkeit bei Graphenkanten:
- Minimiere Schnittpunkte von Kanten, besonders wenn sie fast parallel verlaufen.
- Minimiere gekrümmte Kanten.
- Minimiere die Länge der Kanten.
Zusätzlich dazu gibt es einige allgemeine UI-Designregeln:
- Die Nutzerfreundlichkeit bricht ein, wenn gescrollt werden muss, um Informationen von verschiedenen Stellen des Interfaces zu vergleichen. Um das zu vermeiden muss der Graph so kompakt wie möglich sein.
- Weniger ist Mehr: wenn die selbe Menge an Informationen mit vier Linien anstatt zwanzig Linien dargestellt werden kann, ist das die bessere Lösung.
Es ist nun Zeit, nach besseren Ideen zu suchen. Und der beste Weg, irgendwas zu suchen ist, wie wir alle wissen, es zu googlen in Factorio “T” drücken:
Factorios Graphnenrenderer hat einen cleveren Weg, Knaten zu rendern. Jede Kante besteht aus drei Segmenten: zwei vertikalen und einem horizontalen. Dieser Ansatz ist geeigneter für breite Graphen, da:
- Es keine Schnittpunkte zwischen beinahe parallelen Kanten gibt. Alle Schnittpunkte treten mit rechnten Winkeln auf, was optimal dafür ist, nicht der falschen Linie zu folgen.
- Die Dichte der Linien ist unter Kontrolle: Es gibt immer genug Platz zwischen parallelen Linien um sie voneinander zu unterscheiden.
Der Preis für die Lesbarkeit ist benötigter vertikaler Platz: Es muss genug Platz zwischen zwei Technologiezeilen sein, um alle benötigten horizontalen Elemente ohne Kollisionen unterzubringen:
Um die Kosten zu minimieren gibt es eine einfache, aber wichtige Optimierung: Was wäre wenn Linie nicht nur zwei Elemente verbinden, sondern eine größere Anzahl? Zeichne einfach eine breite horizontale Linie für jedes Item/Technologie und füge so viele vertikale Linien wie nötig hinzu, um alle Knoten zu verbinden.
Sehr viel kompakter, weniger Schnickschnack, definitiv schön™ und verständlich™. Das gibt den Graphen einen “Main-Bus”-Vibe, welcher hoffentlich jedem Factoriospieler gut bekannt ist, während zeitgleich alle Richtlinien gut genug eingehalten werden. Das ist auch mit Factorios eigener Render-API möglich, da die Kanten nur eine Verbindung von Linien, Dreiecken und Kreisen ist. Das erlaubt es Dana, den gesamten Factorio Craftinggraph fast auf einem Bildschirm darzustellen:
Der Code-Teil
Das war jetzt alles was wir am Reißbrett entwerfen konnten, jetzt ist es Zeit, das Problem mit Code zu erschlagen! Das ist allerdings selbst nicht ganz frei von Problemen. Factoriomods werden in einer Sprache namens Lua geschrieben, und Lua hat ein unglaublich wüstes Ökosystem. Es gibt keine Hoffnung eine Bibliothek zu finden, die solche Verbindungen erstellen kann.
Eine Lösung wäre es, eine Bibliothek aus einer anderen Sprache zu portieren. Es gibt eine große Anzahl an Bibliotheken, um Graphen zu zeichnen, aber bei DAna handelt es sich mittlerweile um einen Hypergraphen, da wir es mit Verbindungen zwischen mehr als zwei Knoten zu tun haben. Obwohl Hypergraph erstmal unglaublich viel cooler klingt, gibt es leider nur wenige Bibliotheken, um sie zu zeichnen und auch im allgemeinen deutlich weniger wissenschaftliche Literatur zu diesem Thema.
Dana hat deshalb einen Router, welcher beinahe von Grundauf dafür geschaffen wurde. Beinahe deshalb, da es viel Inspiration aus anderen Feldern gab, aber dafür muss man sich mit einigen unerwarteten Themen befassen…
Inspiration aus dem PCB-Design
Es gibt zufälligerweise Leute, deren Hauptberuf es ist, Punkte in 2D zu verbinden: Leiterplatten (PCB) -Designer. Und für Probleme, welche fast identisch zu Dana’s Problemen sind, haben sie jahrzehntealte und gut dokumentierte Algorithmen: Channel routers.
Bevor wir uns die Lösung ansehen, ist das erste was Dana sich daraus abschaut ist ein ordentlicher Weg, das Problem zu modelliern. Das Ziel unseres Kantenrouters ist zweierlei: Bestimme die Anzahl an channels zwischen zwei Knotenzeilen und ordne ein channel jedem horizontalen Segment zu.
Der Ort, an dem jede horizontale Linie beginnt und endet wird einfach durch die Position der Knoten bestimmt, die sie verbinden müssen. Die vertikalen Linien sind einfache Projektionen von den Konten zu den horizontalen Linien.
Vielleicht könnte Dana diese Lösung einfach kopieren. Wir Platzieren die Kanten einfach so wie Leiterbahnen auf den Leiterplatten der 80er Jahre!
Naja, das ist jetzt nicht wirklich zufriedenstellend. Diese Algorithmen wurden mit den Grenzen der PCB-Industrie entworfen, wo Kantenschnittpunkte in der Regel kein Problem sind, nur die finale Größe der Leiterplatte sind wichtig. Wenn es aber zu schönen™ Graphen kommt, ist diese spaghettighafte Lösung eher schlecht. Um das zu beheben, versorgt Dana den Router mit einer teilweisen Reihenfolge der horizontalen Linien: etwas was sagt, das A über B platziert werden muss, um Schnittpunkte zu minimieren.
Inspiration von Sportwettkämpfen
Um eine gute vertikale Reihenfolge zu finden, beginnen wir mit einer einfachen Idee: Für jedes Paar (A,B) an horizontalen Linien berechnen wir dir Anzahl an Schnittpunkten, wenn wir A über B platzieren, und dann das selbe mit B über A. Wir können herausfinden, das A über B einige Schnittpunkte kostet (oder einspart) oder sich gegenseitig nichts nimmt.
Leider resultiert diese Technik möglicherweise in Paradoxon. Wenn A über B, B über C und C über A platziert werden muss, ist keinem geholfen. Um einie ordentliche Reihenfolge aufzustellen, muss Dana einige der aufgestellten Richtwerte opfern, aber in einer Art und Weise, die die wenigste Anzahl an neuen Schnittpunkten hinzufügt.
Jetzt ist der perfekte Moment, um völlig Zusammenhangslos über Sport zu reden. Fassen wir den oberen Abschnitt einmal mit Sportbegriffen zusammen. A hat gegen B gewonnen, B hat gegen C gewonnen und C hat gegen A gewonnen. Um die korrekte Reihenfolge zu bestimmen, muss Dana einige Ergebnisse ignorieren, aber in einer Art und Weise, die die wenigsten Ergebnisse ignoriert.
Das fundamentale Problem ist das selbe. Glücklicherweise ist das Sportproblem so alt wie die Sportwettbewerbe, und das gute bei solchen alten Problem ist, das eine Menge schlauer Leute sich darüber Gedanken gemacht haben!
Ein generischer Weg dieses Problem zu lösen ist mit Graphentheorie, wo unser Sportproblem äquivalent zum Feedback Arc Set-Problem ist. Die schlechte Nachricht: dabei handelt es sich um ein NP-schweres Optimierungsproblem handelt. Das bedeutet, das es unglaublich lange dauern kann, eine Lösung zu finden, selbst wenn es nur ein paar Dutzend Beteiligte gibt. Die gute Nachricht: es gibt einen Haufen Forschungsarbeiten, welche Heuristiken vorschlagen. Diese Lösungen sind nicht optimal, aber nah genug dran an einer optimalen Lösungen in einer gut genugen Zeit. Es gibt verschiedene Heuristiken, je nachdem wie viel Rechnenzeit aufgewendet werden soll, wie nah an der optimalen Lösung man sein muss oder welche Graphart man verwendet.
Dana verwendet Heuristiken von Eades, P., Lin, X. and Smyth, W.F. (1993), mit einigen trivialen Modifikationen für gewichtete Graphen. Das ist ein extrem schneller und hoffentlich gut genuger Algorithmus, um eine Reihenfolge zu schaffen (die Pyanodongraphen müssen ja irgendwie vor dem Ende des Universums rauskommen). Es ist gut genug um ein deutlich besseres Ergebnis im vergleich zur letzten Lösung zu erreichen:
Fazit
Jetzt nochmal im Schnelldurchgang: Dana veranstaltet ein Sportwettbewerb zwischen Factorioitems. Ihre Platzierzungen werden dann verwendet, um einige Widerstände, Kondensatoren und Spulen auf einer imaginären Leiterplatte zu verbinden. Das befähigt Dana dazu, schöne™ und verständliche™ Graphen zu zeichnen.
Vertrau mir, ich bin ein Ingenieur.
Beitragen
Wie immer suchen wir nach Leuten, die zu Alt-F4 beitragen wollen, sei es mit einem Artikel oder durch Hilfe bei Übersetzungen. Wenn du etwas Interessantes im Kopf hast, das du mit der Community in einer eleganten Art teilen möchtest, hier kannst du das tun. Falls du dir unsicher bist, beantworten wir gerne Fragen zu Inhalt und Struktur. Falls das nach etwas klingt, woran du interessiert bist, tritt unserem Discord bei, um es nicht zu verpassen!