Damit die Charaktere in einer Szene nicht einfach auf geradem Weg zum Zielpunkt laufen (weil sie ja sonst einfach durch bestimmte Kulissenobjekte durchrennen würden), müssen wir also irgendwie festlegen, wo entlang sie sich überhaupt bewegen dürfen. Für dieses Problem durfte ich mir eine Lösung überlegen. (Schon komisch eigentlich, dass ich immer diese ganzen Mathe-Sachen einprogrammieren muss 😅)
Die Basis für alles - das Wegpunktnetz
In der Geistfrei GmbH habe ich das Wegfindungs-Problem so gelöst, dass einfach ein Wegpunktnetz für jeden Raum (und Charakter) erstellt wird, auf dem sich der jeweilige Charakter frei bewegen kann. (Roland hat das Thema bereits in seinem Post "Quo vadis, Herr Stone? – Das Wegpunktnetz" angesprochen.) Der Charakter bewegt sich dabei nur auf den "Kanten" dieses Netzes, von Punkt zu Punkt (er kann dabei natürlich auch auf der "Kante" zwischen zwei Punkten stehenbleiben). So sieht ein Wegpunktnetz übrigens grafisch dargestellt aus:
Man erkennt, dass jeder Knotenpunkt einen eindeutigen Bezeichner, eine XYZ-Koordinate und Verbindungen zu mindestens einem anderen Knotenpunkt hat. Die Bezeichner sind mehr oder weniger willkürlich – wir haben jedoch darauf geachtet, dass wichtige Wegpunkte, die wir direkt im Szenenscript ansprechen, einen eindeutigen Bezeichner haben (Pinboard, Hank, Exit). Schauen wir uns dieses Wegpunktnetz weiter unten mal in vereinfachter Form an und spielen den Dijkstra-Pathfinding-Algorithmus durch.
Wie funktioniert nun Dijkstra?
Der Dijkstra-Algorithmus liefert uns alle kürzesten Wege innerhalb eines Graphen von einem gegegeben Startpunkt aus. Das heißt, wenn wir in unserem Beispiel von Punkt C01 zu Pinboard gehen wollen, bekommen wir auch sämtliche kürzesten Wege von Punkt C01 zu jedem anderen Punkt geliefert. Ich habe dazu ein kleines animiertes Gif entworfen, mit dem ich euch einen ersten kleinen Überblick über den Algorithmus geben möchte. (Der Einfachheit halber habe ich die Wegpunkte unseres ursprünglichen Netzes – wie oben im Szenenbild zu sehen – umbenannt von A bis L).
Mehr Punkte sind von Punkt A aus nicht zu erreichen, also machen wir mit Punkt B weiter. Von Punkt B aus kann man Punkt A und Punkt C erreichen. Punkt A hatten wir uns bereits angeschaut, denn da kamen wir her. Dieser ist somit abgehakt. Bleibt noch Punkt C. Die gesamte Wegstrecke über Punkt B nach Punkt C beträgt aber 5 (2 plus 3) und ist damit länger als der Weg nach C von A ausgehend. Also korrigieren wir nichts bei Punkt C - denn natürlich würden wir nur korrigiren, wenn die neue Wegstrecke kürzer wäre. Punkt B ist damit abgehakt, wir schauen uns Punkt C an.
Von Punkt C gehts nach A, B und D. A und B sind bereits abgehakt, bleibt nur noch Punkt D. Die Gesamtwegstrecke nach Punkt D beträgt 7 (4 von A nach C und 3 von C nach D). Um Punkt D zu erreichen, sind wir über Punkt C gekommen - also notieren wir bei D (7, C). Punkt C haken wir nun ebenfalls ab. Und wir machen mit Punkt D weiter …
Diese Vorgehensweise nutzt man für den gesamten Graphen, und zwar bis alle Punkte abgehakt sind. Wenn man dann wie in unserem Beispiel den Weg wissen will, der von A nach H führt, schaut man sich an, welcher Punkt unserem Punkt H vorangegangen ist. In unserem Beispiel ist es F. Und zu Punkt F kommt man über E, zu E über D, zu D über C und zu C über A. Kurz: H<-F<-E<-D<-C<-A. Diese Information muss man nun von hinten lesen und dann weiß man, in welcher Reihenfolge unser Charakter das Wegpunktnetz ablaufen muss, um von Punkt A nach Punkt H zu gelangen.
Alles vollkommen easy also!
Spaß beiseite – den Dijkstra-Algorithmus anhand von Tabellen oder gar anhand eines Textes nachzuvollziehen ist natürlich nicht so einfach. Wer sich das Ganze genauer durch den Kopf gehen lassen möchte, der kann sich dazu folgendes Video auf YouTube anschauen: Dijkstra-Algorithmus Tutorial [german / HD].Da wird der Dijkstra-Algorithmus ziemlich anschaulich erklärt.