Back
09.07.2024
#Business
#GameDev
#Design

A Post on Pathfinding

⚡ What Gamedevs know...
Image Source



Deutsche Supermärkte sind in der Regel nach dem gleichen Muster aufgebaut: Der Kunde betritt den Laden und stößt zunächst auf die Frühstücksabteilung: Brot, Marmelade, Cornflakes, Nutella. Der Kunde geht weiter ins Innere des Ladens und erreicht die Mittagsabteilung: Nudeln, Reis, Konserven und Gewürze. Die Customer-Journey endet mit Wein und Erdnussflips - der Abend sozusagen. Das Sortiment im deutschen Einzelhandel folgt normalerweise dem Tagesablauf eines funktionierenden Bürgers.

Ich sage normalerweise, weil es eine Ausnahme gibt. Sie heißt Nutella, eine fiese und unwiderstehliche Schokoladensoße, die Diabetes verursacht und einfach hervorragend schmeckt. Man kann Nutella aufs Brot schmieren, als Zutat beim Backen verwenden oder direkt aus dem Glas löffeln und danach in Scham versinken. Eine Zeit lang - zumindest bis in die 2010er Jahre, als Nutella-Ersatzprodukte auf den Markt kamen - legten Supermarkt-Kunden weite Strecken zurück, um Nutella zu kaufen. Es gibt sogar ein Phänomen, das unter Einzelhändlern als Nutella-Prinzip bekannt ist und das beschreibt, wie die Aussicht auf Nutella genutzt werden kann, um Kunden in die Filliale zu locken.

Das Nutella-Prinzip in der Nussschale

Stellen Sie sich Folgendes vor: Ein Einzelhandelsverkäufer möchte seine Marktposition stärken, indem er die Konkurrenz unterbietet, und macht deshalb ein Sonderangebot für Nutella. Im kommenden Monat wird Nutella auf den lächerlich niedrigen Preis von 0,39 € pro Glas reduziert. Bei einem Einkaufspreis von, sagen wir, 0,59 € macht der Einzelhändler einen Verlust von 0,20 € pro Stück. Preislich hat er nun seine Konkurrenten unterboten, aber er macht einen Verlust. Um einen Gewinn zu erzielen, versteckt er die Nutella an einem völlig abgelegenen Ort im Supermarkt und preist sein Sonderangebot in den lokalen Medien so laut und überzeugend wie möglich an (wobei er die Tatsache, dass die Nutella versteckt ist, verschweigt). Nun stürmen die hungrigen Kunden herein und suchen nach dem Nutella-Sonderangebot. Aber sie werden es nicht finden. Sie müssen suchen.

Hier kommt das Nutella-Prinzip ins Spiel. Weil der Kunde von Regal zu Regal wandert, beginnt er Wege zu gehen. Unterwegs macht er Impulskäufe - er kauft Dinge, die er eigentlich nicht kaufen wollte. Auf diese Weise erzielt der Einzelhändler einen Gewinn - und erreicht sein übergeordnetes Ziel, alles lose Geld in sein Haus zu locken.

Das Nutella-Prinzip zeigt, dass meine Professoren an der Uni teilweise Unrecht hatten: Es stimmt, dass Software dem Pragmatismus folgt und dass datengesteuerte Anwendungen die abgefragten Daten ohne Umwege liefern sollten. Aber wenn die Nutzer das bekommen, was sie gesucht haben, werden sie gehen, und wir stehen allein zwischen den Regalen mit all den Produkten, die wir nicht verkaufen können.

Ziel des Nutella-Prinzips ist es daher, Wege zu schaffen, die die Kunden bereit sind zu gehen. Dabei soll die Frustrationstoleranz nicht ausgereizt werden. Der Spagat besteht darin, dem Kunden das Nutella zu zeigen, aber auch all die anderen Köstlichkeiten in der Konsumlandschaft.

Das mag ein bisschen nach Marketing-Scam 101 klingen, aber die allgemein akzeptierte Ansicht im wirklichen Leben, im Spiel, im Marketing und in der Religion ist, dass der Weg das Ziel ist. Die Reise sollte daher so spannend wie möglich sein. Nicht nur im Einzelhandel, sondern überall dort, wo Reisen gemacht werden - im Webdesign, im Tourismus, in der Spielebranche, im Bildungswesen und überall sonst, wo wir allein zwischen den Regalen mit all den Produkten stehen, die wir nicht verkaufen können.

Pathfinding und Künstliche Intelligenz

Für einen Blick in die Zukunft lohnt sich die Konsultation der beiden wichtigsten Inspirationsquellen für technische Innovationen: Science-Fiction Literatur und Gaming. Da ich seit Jahren keine Romane mehr lese, schaue ich auf die Gaming Industrie.

Eine Nachricht fiel mir auf: EA Games ließ vor kurzem ein Patent für Route-Navigation Systeme fallen.

Die Route-Navigation von EA Games kennt vermutlich jeder Gamer: Es ist der Pfeil aus Need For Speed Underground 2, der oben eingeblendet wird und die Richtung zum Ziel zeigt, oder Runner’s Vision aus Mirror’s Edge Catalyst. Da EA Games mitsamt dazugehörigen Studios vorzugsweise auf der Frotbite-Engine entwickeln, kenne ich die technischen Details nicht. In der Unreal Engine jedoch, das weiß ich, basieren Path-Finding Systeme meistens auf Nav-Meshes.

Screenshot aus Need For Speed Underground 2 Screenshot aus Need for Speed Underground 2

Bei Navmeshes werden per Drag-and-Drop walkable-zones im Level definiert, und es wird definiert, unter welchen Bedingungen eine Zone als walkable gilt, zum Beispiel wenn die Neigung des Bodens weniger als 40° beträgt, oder die Höhe der Hindernisse in der Zone weniger als 1 Meter beträgt. Bereiche, die nicht walkable sind, färbt die Engine rot, während das Pathfinding-System eine Strecke berechnet, die um das Hindernis herumführt.

Werden Elemente im Level bewegt, berechnet das Navmesh die Zonen neu. Damit das ständige Neuberechnen von Zonen hardwaretechnisch nicht zum Harakiri wird, empfiehlt sich das Adaptive Tile Refreshing der einzelnen Navmeshes, die je nach Dynamik und Beweglichkeit von Level-Abschnitten ihre Zonen mit entsprechenden Intervallen aktualisieren und miteinander im Austausch stehen. Weil Probleme solcher Art meist in die selbe Größendimension fallen wie das World Partitioning von Open World Games, hat sich in der Unreal Engine der Standard durchgesetzt, Navmeshes und World-Partitioning zu verknüpfen.

Das hat Auswirkungen auf den Pathfinding-Algorithmus. Je segmetierter die Navmeshes, desto segmentierter das Pathfinding. Ähnlich wie ein Quadrat allmählich zum Kreis wird, in dem man immer wieder die Winkel der Ecken halbiert, wird aus einer reelen Map ein Grid, wenn man die Areale nur immer weiter unterteilt. Die Konsequenz davon ist, dass Path-Finding latent grid-based ist, und das globale Optimum des Pathfindings - wer hätte es gedacht - zum A* tendiert.

Fortschritte im Deep-learning schwappen auch in das Pathfinding von Videospielen über. Im Juni 2015 entwickelte ein Programmierer namens Seth Bling ein neuronales Netzwerk namens MarI/O. Das neuronale Netzwerk lernte den optimalen Speedrun für Super Mario World. Basierend auf der Neuroevolution von Augmentierungstopologien, erzeugte MarI/O neuronale Netze mit Hilfe genetischer Algorithmen. Dabei wusste MarI/O nur das Level-Layout und die Positionen der Hindernisse. Das Ziel bestand darin, die Fitnessfunktion so weit wie möglich auf die Zielgerade hin zu transportieren - und zwar schnellstmöglich. Seth Bling ließ das Programm laufen, und nach 34 Generationen, die insgesamt 24 Stunden dauerten, beendete MarI/O das erste Level Level, indem es durch das gesamte Level sprang und allen Power-Ups und Gegnern auswich. Nach 17 Tagen errechnete MarI/O den optimalen Speedrun.

Ich habe hier das Grundgerüst eines Racing-Games, bei dem NPCs lernen, eine Strecke zu fahren. Ähnlicher Ansatz wie bei MarI/O, nur nicht so meisterlich umgesetzt. Bei dieser Methode werden Raycasting und Gradient-Descent in ein duales System kombiniert. Im Grunde wird ein Pawn-Actor mit beliebig vielen Rays ausgestattet, die ihre jeweilige Entfernung bis zur ersten Kollision messen. Die Entfernungen werden von einer Learnfunktion ausgewertet, derart, dass die Anzahl der Kollision gen 0 tendiert.

Ich habe an anderer Stelle schon darauf hingewiesen, dass Deep Learning nichts anderes ist als eine bestimmte Methode, Optimierungsfunktionen zu lösen, und verweise hier auf ein anschauliches Beispiel. Problem dabei ist, dass Deep Learning, solange es keine Transformer-Architektur verwendet, höllisch ineffizient ist, und es ist davon auszugehen, dass Epic Games noch eine Weile brauchen wird, um die nicht-mehr-ganz-so-neuen-Fortschritte aus der Transformer-Architektur in Unreal Engine’s Blueprints zu implementieren. Bis die Racecars meines Beispiels fahrbare Resulate lieferten, vergingen 50 Minuten. Solange die Transformer-Architektur keinen Einzug in die Unreal Engine findet (oder in irgendeine andere Game Engine) bleibt der Neuronale Ansatz des Pathfindings somit, zumindest für die Mainstream Gaming-Industrie, vorerst auf der Strecke.

Deep Learning Fail

Und doch stoße ich bei meinen Recherchen über Deep Learning immer wieder auf das, was Deep Learning so interessant macht: Es ist das Amüsement, das dabei entsteht, ein Deep Learning Modell beim Lernen zu beobachten. Der erste Gehversuch bei Epoche 0, erstes adaptives Verhalten bei Epoche 10, bis ein Glitch in der Matrix das Modell dazu veranlasst, methodisch von der Rolle zu fallen und auf Lösungansätze kommt, die sowas von abwegig sind, dass kein Mensch mit einem IQ >= 30 sich so etwas zumuten würde. Mit Blick auf unsere Maker Culture gefällt mir der Ansatz, die Fertigung eines Produktes als das eigentliche Produkt zu sehen, und das fertige Produkt nur als das finale Extra.

Seifenblasen und Quantencomputer

Warum ist auf Seifenblasen eigentlich Farbe zu sehen? Seife ist farblos, wie kann es also sein, das Seifenblasen, die aus farbloser Seife bestehen, in Farben wie Cyan, Violett, Türkis und Orange erstrahlen?

Die Antwort lautet Quantenmechanik: Eine Seifenblase besteht nicht aus einer einzigen Oberfläche, sondern aus zwei: Einer inneren Oberfläche und einer äußeren Oberfläche, die wenige Nanometer voneinander entfernt liegen. Fällt Licht auf die Seifenblase, wird das Licht manchmal von der äußeren Oberfläche reflektiert und manchmal von der inneren Oberfläche. Das Interval, das Licht bei seinem quantenmechanischem A/B-Verhalten zeigt, liegt auf dem Lichtspektrum genau dort, wo die Farben angesiedelt sind: nach den Radiowellen (~0.003 Thz) beginnt das Farbspektrum weit dahinter bei Rot (~384 THz), über Orange (~500 Thz), Gelb (~520Thz), Grün (~550 Thz), Türkis (~620 Thz), bis Indigo (~660Thz) und Violet (~750 Thz), und mit großen Abstand jenseits davon beginnen die Frequenzbereiche der Röntgenstrahlung (~3EHz), die weder für unser menschliches Auge sichtbar, noch für diesen Beitrag relevant sind.

Dass auf Seifenblasen Farbe zu sehen ist, ist nicht nur ein quantenmechanisches Phänomen, sondern auch DIE Frage nach dem Verhalten von Licht und der Entstehung unseres Universums. Dabei ist das doppelspurige Verhalten von Licht auf Seifenblasen mein bevorzugter Ansatz, um Quantencomputer zu erklären: Ersetze die Seifenblase mit einem Halbleiter, und das Ergebnis ist ein Q-Bit.

Was das mit Pathfinding zu tun hat? Nun, die Informatik hat die Tendenz, alte Ideen wiederzubeleben, wenn Fortschritte in der Hardware in Serienreife gehen, und wenn Q-Bits in Serienreife gehen und in der Lage sein werden, alle plausiblen Wege zu einem festgelegten Ziel gleichzeitig in einem Berechnungszusammenhang zu halten, wird Pathfinding vermutlich eine Renaissance erleben.

Conclusion

Die Pointe dieses Beitrags könnte - etwas schnulzig dahergesagt - mit der Aussage enden, dass der Path das eigentliche Finding ist. Bis heute gibt es keine Universallösung, mit Ausnahme vom A*. Dabei warte ich gespannt auf neue Fortschritte in der Hardware, und den frischen algorithmischen Wind, der inklusive ist, einzufangen und im Rahmen meiner Projekte zu implementieren.