Das eigene Spiel: Die Wegfindung

19. Februar 2018 von | Kategorie: Programmierung
Schlagw├Ârter: //

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)

Schreibe einen Kommentar

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

46 − 42 =