Einzelnen Beitrag anzeigen

Custom

Registriert seit: 18. Aug 2007
Ort: Mainz
203 Beiträge
 
Delphi 7 Enterprise
 
#93

Re: [Game][Alpha]2.6D[Updated:20.2.]

  Alt 23. Feb 2009, 23:14
Sooo ich aktualisiere mal den Stand der Dinge;

Im Moment bin ich an einem Punkt angelangt, der sicherlich einige interessieren wird - Pathfinding(Wegfindung) per KI.
Ziel ist es den kürzten möglichen Weg von A nach B zu finden, ohne dabei gegen eine Wand zu rennen oder in eine Lücke zu fallen. (Problem.jpg)

Die Lösung (Lösung.jpg) wirkt kompliziert ist aber simpel! Ich habe mich entschieden das Problem so zu lösen:
Schritt 1: Ich lege Start- und Zielpunkt fest.
Schritt 2: Ich erstelle eine so genannte Pathmap; ich gehe vom Zielpunkt aus, dem ich den Wert 0 gebe. Dann gebe ich alle Begehbaren Felder die um ihn herum liegen den Wert 1, und allen nicht Begehbaren den wert -1. Diesen Schritt wiederhole ich für alle Felder deren Wert nicht -1 ist, wobei die umherliegenden immer als Wert den aktuellen Wert + 1 bekommen. Das mache ich solange, bis ich beim Startpunkt ankomme(oder einen bestimmten Wert übersteige).
Schritt 3: Ich gehe vom Startpunkt aus und setzte ihn als ersten Wegpunkt. Dann suche ich in den umherliegenden Feldern den niedrigsten Wert und setze ihn als nächsten Wegpunkt. Das wiederhole ich bis ich beim Wert 0, also beim Zielpunkt angekommen bin.

Und schon habe ich den optimalen Weg von A nach B gefudnen.

Im Beispiel suchen wir den Weg der Figur die links an der Wand steht zu der die Rechts auf der Brücke steht. Vielleicht hilft es dem einen oder anderen ja
Miniaturansicht angehängter Grafiken
pathfinding_-_l_sung_653.jpg   pathfinding_-_problem_967.jpg  
  Mit Zitat antworten Zitat