Das eigene Spiel: Die Wegfindung

[Thumbnail] Das eigene Spiel: Die Wegfindung

Obwohl dieser Algorithmus bereits implementiert ist, berichte ich an dieser Stelle über eben diesen. Denn die Wegfindung funktioniert zwar (aber nicht zu meiner Zufriedenheit). Und da es mein Spiel ist, werde ich dieses Stück Quellcode überarbeiten.

Wie funktioniert’s ?

Die Wegfindung berechnet einen Pfad aus Koordinaten, welcher an die „Nicht-Spieler-Charaktere“ (z.B. Servicepersonal) übergeben wird. Über diese Koordinaten beziehen sich die Figuren Richtungsvektoren, welche letztendlich mit Geschwindigkeit und Zeit multipliziert werden. So arbeitet die Fortbewegung der einzelnen Personen, die sich später im Kino aufhalten werden.

Der Pfad wird von einem A*-Algorithmus generiert. Dieser berechnet den kürzesten Pfad zwischen zwei Knoten (Koordinaten). Dazu benötigt er im Grunde drei Werte:

  • g: Die Kosten vom Start zu dem Knoten, der gerade untersucht wird.
  • h: Die Kosten, um vom untersuchten Knoten zum Ziel zu kommen. Dies ist eine Schätzung (bei mir Luftlinie).
  • f: Die geschätzten Gesamtkosten, wenn man über diesen Knoten zum Ziel reisen würde. Errechnet durch: f = g + h.

Darüber hinaus wird immer der Knoten mit dem niedrigsten f-Wert untersucht. Wurde ein Knoten beleuchtet, wird er der „Closed List“ hinzugefügt, damit dieser nicht weiter bearbeitet wird. Auf weitere Einzelheiten gehe ich an dieser Stelle nicht ein.

Was muss verbessert werden ?

Es gibt ein großes Problem. Die einzelnen NPC wollen exakt den gleichen Punkt erreichen. Dies kann nicht funktionieren, da die einzelnen Figuren einen gewissen Umfang bzw. eine festgelegte Größe haben. Somit verhaken sich die Figuren.

Folglich liegt das Problem nicht in dem A*-Algorithmus. Die Schwierigkeit liegt in der Art und Weise, wie sich die Figuren bewegen. Der Suchalgorithmus macht seine Arbeit gut. Viel mehr muss ich mir überlegen, wie die künstlichen Persönlichkeiten auch parallel zur Ideallinie laufen können. Theoretisch könnte man dies ermöglichen, indem der Richtungsvektor der Figuren verschoben wird. Dies ist eine gute Idee, welche aber nur zum Ziel führt, wenn man die Figuren noch zusätzlich über Bereiche navigiert. So wird gewährleistet, dass der Vektor nicht zu stark verschoben wird. Schließlich soll die Figur auf Grund eines verschobenen Vektors nicht durch eine Wand rennen, während sie eigentlich durch eine Tür spaziert.

Nachtrag:

Das ganze habe ich inzwischen implementiert und es funktioniert. Die NPC stoßen nur noch selten zusammen. Und sollte es passieren, prallen sie voneinander ab und laufen weiter. Ich gebe zu, das sieht an der ein oder anderen Stelle nicht ganz realistisch aus, aber immerhin verhaken sich die Figuren nicht mehr. Solch kleine Verbesserungen können auch in Zukunft behoben werden.

 

Was denkst du über diesen Post?
  • Gut (1)
  • Hilfreich (0)
  • Nicht gut (0)
  • Lustig 😀 (0)

von | Kategorie: Programmierung
Schlagwörter: //

Schreibe einen Kommentar

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

19 − = 9