Den (eigenen?) Weg finden

In diesem Artikel möchte ich einen Gedanken zur Wegfindung von NSCs mit euch teilen. Wie kann ein NSC einen Weg finden, ohne dass ein offizieller Pfad existiert? Und ohne dass – noch viel schlimmer – geskriptete Wege hinterlegt werden? Aber gleichzeitig auch ohne dass der NSC allwissend ist, die Wege besser findet als der Spieler und ohne dass er, alles bisher gewesene ignorierend, außerhalb von Städten und offiziellen Wegen rein nach Himmelsrichtungen läuft? Nun habe ich schon mehrfach das Wort offizieller Weg / Pfad genutzt, was ist eigentlich ein Weg?

“Wege entstehen dadurch, dass man sie geht.” (Franz Kafka)

Dieses schöne Zitat von Kafka war sicherlich im übertragenen Sinn gemeint, stimmt aber auch in seiner wörtlichen Bedeutung.

Wir erkennen auch nicht ausgezeichnete, uns aber bekannte Wege, aber auch Wege, die einfach erkennbar viele andere vor uns gegangen sind, als Wege und verstärken diese Wege noch, indem auch wir sie gehen. Algorithmisch lässt sich das mit dem Ameisenalgorithmus umsetzen:

Die Futtersuche der Ameise

Eine der wohl bekanntesten Metaheuristiken mit Naturanalogie, der Ameisenalgorithmus, beruht auf der Futtersuche der argentinischen Ameise und wurde erstmals in [1] beschrieben. Jede Ameise hinterlässt auf ihrem Weg Pheromone, die von anderen Ameisen wahrgenommen werden können. Wenn eine Ameise eine Entscheidung bezüglich ihres Weges treffen muss, wächst die Wahrscheinlichkeit, einen bestimmten Weg einzuschlagen mit der Menge der auf diesem Weg wahrgenommenen Pheromone. Dieses System ist selbstverstärkend, je mehr Ameisen einen bestimmten Weg einschlagen haben, desto höher ist die Wahrscheinlichkeit, dass die nächste Ameise wieder diesen Weg wählt. Dies wird noch dadurch verstärkt, dass die Pheromone verfliegen, selten genutzte Wege verlieren also immer weiter an Attraktivität. Doch wieso finden die Ameisen damit den kürzesten Weg und “einigen” sich nicht auf irgendeinen (eventuell sehr langen) Weg? Ganz einfach: Die Ameisen, die bei ihrem ersten Ausschwärmen einen kürzeren Weg gefunden haben als andere sind schon bei der Futterstelle, wenn andere Ameisen noch auf dem Weg dorthin sind. Auf dem Weg zurück nehmen sie also nur ihre eigenen Pheromone wahr und entscheiden sich mit einer hohen Wahrscheinlichkeit dafür, einen ebenso kurzen Weg wieder zurück zu nehmen und verstärken ihre Pheromonspur weiter. Wenn die Ameisen, die längere Wege genommen haben, dann bei der Futterstelle angekommen sind und den Weg zurück zum Nest suchen, dann nehmen sie ihre schwache Pheromonspur des längeren Weges wahr und wesentlich stärker die Pheromonspur der Ameisen, die kürzere Wege gefunden haben (und diese durch mehrfaches Ablaufen schon verstärkt haben) und entscheiden sich also mit hoher Wahrscheinlichkeit dafür, den kürzeren Weg zurück zu nehmen. Wieder im Nest angelangt schwärmt die Ameise sofort wieder aus. Vor ihr liegt nun der stark mit Pheromonen belegte, kurze Weg über den sie zurück gekommen ist und die längeren Wege, die einige Ameisen auf dem Hinweg genommen haben, auf denen die Pheromone schon verfliegen – die Entscheidung für den kürzeren Weg ist sehr wahrscheinlich. Der kürzere Weg wird also einfach dadurch immer attraktiver, dass die Ameisen, die sich für diesen Weg entscheiden schneller am Ziel sind, also häufiger Pheromone ablegen. Eine sehr elegante Art, den kürzesten Weg zu kommunizieren, ohne dass eine einzelne Ameise wirklich weiß, dass sie den kürzesten Weg gefunden hat.

Durch diese Art der Wegfindung bleiben die Ameisen flexibel. Wenn ein Weg versperrt ist, und keine Pheromone ihnen bei der Wegfindung helfen können, suchen sie sich wieder selber Wege und der Prozess an der Stelle des Hindernisses beginnt von vorne. Zu jeder Zeit besteht auch die Möglichkeit, dass einzelne Ameisen sich eben für unattraktive (wenig mit Pheromonen belegte Wege) entscheiden. Wenn also zum Beispiel ein Hindernis entfernt wird, also plötzlich kürzere Wege verfügbar werden, so besteht die Chance, dass – obwohl auf diesem neuen, kurzen Weg keine Pheromone liegen – sich Ameisen auf diesen Weg verirren und mit Hilfe der oben beschriebenen Mechanik dieser Weg an Attraktivität gewinnt.

Der Ameisenalgorithmus ist nicht nur eine der bekanntesten Metaheuristiken, er ist auch eine der beliebtesten. Anwendungsmöglichkeiten bieten sich recht offensichtlich in der Tourenplanung und bei Netzwerkproblemen, aber er lässt sich durch geschickte Anpassung der Problemdarstellung auch für Zuordnungs- und Sequenzierungsprobleme nutzen.

Wegsuche von NSCs

Um diese Grundstruktur auf die Wegsuche von NSCs zu übertragen, braucht man so gut wie keine Anpassungen vornehmen. Alle Akteure im Spiel, NSCs und Spieler gleichermaßen, sind Ameisen, die Pheromone hinterlassen. Durch das häufige Ablaufen von ähnlichen Wegen bildet sich eine für die NSCs wahrnehmbare Pheromonspur (zu interpretieren in der Stadt als Wege, die sie häufig abgelaufen sehen oder von anderen NSCs oder Spieler genannt bekommen, in der Natur zu interpretieren als sich langsam herausbildende Trampelpfade). Die Wahrscheinlichkeit, dass sie auf ihrem Weg in eine Richtung einer in eine ähnliche Richtung verlaufende Pheromonspur folgen, steigt mit Stärke der Pheromonspur (mit steigender Anzahl von Charakteren, die diesen Weg einschlagen / mit steigendem Ausprägungsgrad des Trampelpfades).

Fazit und Ausblick

Der Ameisenalgorithmus scheint alle Anforderungen an die Wegfindung der NSCs zu erfüllen, die Ergebnisse lassen den NSC gute und kurze (von vielen anderen NSCs und Spielern gegangene) Wege finden, ohne Wissen zu besitzen, das ein einzelner NSC eigentlich nicht besitzen könnte. Die Speicherung der bisher abgelaufenen Wege ermöglicht es uns, einerseits eine solche Pheromonmatrix zu erstellen, andererseits auch die Ermittlung und Anzeige von Trampelpfaden, was ein weiteres schönes Feature wäre. Die Erweiterung um zusätzliche Anforderungen wie die Nutzbarkeit des Pfades mit Karren oder Pferden ließe sich durch separate Pheromonmatrizen umsetzen. Diese Information sollten wir auch wirklich getrennt speichern, da auch die Textur des Trampelpfades erkennen lassen sollte, dass dies ein Pferde- oder Karrenweg ist. Andere Faktoren wie die Gefahr bestimmter Wege würde ich momentan eher über die KI selbst steuern – bestimmte gefährliche Gegenden möchte der NSC generell meiden und würde Wege, die durch diese Gebiete führen, daher ausschließen.

Natürlich hat eine solche Umsetzung auch Grenzen. Zwei große Einschränkungen sehe ich zu diesem Zeitpunkt: Am Anfang jeder Durchführung eines Ameisenalgorithmus gibt es eine Initialisierungsphase, in der zu wenige Daten bereits vorliegen und damit die Bewegungen der Ameisen noch nicht oder zu wenig durch Pheromonwerte beeinflusst werden. In wirtschaftlichen Anwendungsfällen wird diese Phase oft über heuristisch vorbelegte Pheromonmatrizen verkürzt, in unserem Fall hieße das: Wenn keine verlässlich starken Pheromonwerte erkennbar sind, brauchen wir eine Heuristik, um erste Wege zu finden. Eine Heuristik ist schnell gefunden, laufe einfach immer in die (gefühlt) passende Himmelsrichtung. So machen wir das schließlich auch – ich suche meine Wege dann zumindestens so. Der Weg über eine geeignete Heuristik, wenn nicht genug Pheromonwerte vorhanden sind, erscheint mir durchaus gangbar. Die zweite große Einschränkung, in der Ausweichverfahren entwickelt werden müssen, sind Wegplanungen im sehr lokalen Bereich. Für den Weg über einen Marktplatz voller Menschen und Stände ist eine Umsetzung über Pheromonmatrizen nicht sinnvoll – die Peromonmatrix hat hier eher die Information “Überquere Platz Richtung Norden“, erklärt aber nicht, welcher Passant und welcher Marktstand auf welcher Seite zu umrunden ist, eventuell sind hier auch bisher komplett unbeachtete Faktoren von Bedeutung: befreundete NPCs und interessant aussehende Stände könnten die Route beeinflussen. Ein weiteres, noch kritischeres Beispiel ist das Kampfgeschehen. Im Kampfgeschehen sind sicher viele, viele Pheromonwerte speicherbar und erkennbar, aber für die Navigation im Kampf nicht nutzbar. Jeder Weg ist anders, es geht hier nicht so sehr um die Kürze des Weges als viel mehr um die zu erwartende Gefahr oder aber auch um erspähte Gelegenheiten, gute Treffer zu erzielen oder Mitstreitern den Rücken zu decken. Für diese zweite Einschränkung, die lokale Suche nach Wegen in sich stark ändernden Situationen würde ich komplett von der Wegfindung über Pheromone abkommen und nach anderen Verfahren zur Wegfindung suchen.

[1] Goss, S., Aron, S., Deneubourg, J.L., Pasteels, J.M.: Self-organized Shortcuts in the Argentine Ant, Naturwissenschaften 76, 579–581 (1989)

Cookie

Ich bin.. hmm, wie fange ich nun am Besten an? Mit dem Trivialen: Ich bin Cookie :) Und wie drücke ich nun am besten aus, wie ich mich in Science-O-Matics und in !∃2.0 einbringe? Vielleicht kurz zu mir: Ich habe Mathe mit einem Schwerpunkt in der reinen Mathematik studiert, nach meinem Abschluss dann ein Jährchen mal ein wenig Geld verdient in der ABAP Entwicklung, dann bin ich zurück zur Uni, habe mit einem kurzen Exkurs in die mathematische Optimierung mein Wirtschaftsmathe Diplom vollendet und mache gerade meinen Doktor in der quantitativen Forschung der Wirtschaftswissenschaften, also Optimierung auf Wirtschaftsseite, Modelle aufstellen, Algorithmen analysieren, anpassen oder entwickeln, implementieren.. Ist echt cool :D Also im Herzen Mathematikerin. Nein, Informatikerin.. Beides halt ^^ Für !∃2.0 mache ich vor allem Mathemagie und deren Umsetzung, aber auch viele andere Hintergrundmodelle. Sachen, die man in Spielen schon immer mal cool gefunden hätte.. "einfach" mal umgesetzt als eigenständiges Feature. So ist zum Beispiel die Generierung der Umwelt zum größten Teil aus meiner Feder. Hmm.. was schreibt man sonst noch in eine Vorstellung rein? Das Alter? - Vergesst es, nach dem Alter einer Dame fragt man nicht :P Hobbies? Tja, Computerspiele, wie man sich wohl denken kann ^^ Aber auch LARP, Gesellschaftsspiele und Trading Card Games, nähen und Sport würde ich dazu zählen.. Ehrlicherweise auch Shoppen, Schuhe und Klamotten ;) Ach, warum ich Cookie heiße? Das sollte schnell klar werden ohne dass ich es ausführe ;)
Posted in Theory-O-Matic. Tagged with , , .

Hinterlasse eine Antwort

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

Du kannst folgende HTML-Tags benutzen: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>