Brauche Hilfe: Pathfinding

[-KD-]

Das Problem liegt darin, dass die Einheiten nun zufällige Zickzackrouten zu laufen scheinen

...

Dein Pathfinding verwendet nur orthogonale Richtungen. Darum ist es klar, dass Zickzacklinien rauskommen (wenn du nur die Bewegungsrichtungen Oben/Unten/Links/Rechts erlaubst, kann er auch keine diagonalen Wege finden).

Manchmal gehen sie sogar einen Schritt zurück um danach wieder forwärts zu gehen.

...

Das dürfte allerdings nicht passieren...

Ich würde dir raten das Pathfinding mal auf einer 20x15 Map auszuprobieren und alle berechneten exakten Kosten als Sprites über den dazugehörigen Feldern anzeigen zu lassen. Dann siehst du wie das Script arbeitet, welche Werte es berechnet und in welcher Reihenfolge es die Felder ansieht. So findet sich vielleicht der Fehler.

[Cornix]

Das ist es eben nicht, die @adjacent_nodes sind ein quadratischer Kreis, also alle Nodes deren Abstand nicht mehr als 1 auf X- und Y-Achse betragen.

Demnach sind diagonale Bewegungen durchaus erlaubt.
Und ich glaube genau deswegen kommen diese komischen Zickzackbewegungen auch auf da sie immer in Verbindung mit diagonalen Bewegungen entstehen.

Hier ein Beispiel aus einem realen Test, die Figur hat sich tatsächlich in diesem Pattern bewegt, alle Felder 1 - F haben die gleichen Bewegungskosten, jedes X ist unpassierbar, diese Felder sind überhauptnicht als adjacent Nodes gespeichert.

Code:

F X X X X
E X 1 3 X
D X 2 4 5
C X X X 6
B A 9 8 7

Ich bin mir natürlich bewusst, dass der Algorithmus derzeit diagonale Bewegungen mit der gleichen Geschwindigkeit als horizontale Bewegungen ansieht was natürlich falsch ist da sie mathematisch gesehen das Quadratwurzel(2) fache mehr benötigen sollten.
Könnte das der Grund dafür sein? Wie müsste ich den Algorithmus umschreiben um diese diagonalen Bewegungen auszuarbeiten?

(Nebenbei bemerkt, ich habe das Gefühl, dass es damals funktioniert hätte, es könnte natürlich auch an fehlenden Tests gelegen haben)

[-KD-]

Ich bin mir natürlich bewusst, dass der Algorithmus derzeit diagonale Bewegungen mit der gleichen Geschwindigkeit als horizontale Bewegungen ansieht was natürlich falsch ist da sie mathematisch gesehen das Quadratwurzel(2) fache mehr benötigen sollten.

...

Jein. Die Berechnung darfst du selbst festlegen. Der euklidische Abstand ist am realistischsten, aber du kannst auch einen Maximum-Abstand verwenden (das also der diagonale Schritt genauso lang ist wie ein orthogonaler).

Das Problem ist nur: Du musst den gewählten Abstand auch konsistent verwenden. Derzeit verwendest du zwei Abstände: Einen Manhattan-Abstand in deiner Schätzfunktion (der diagonale Schritt ist gleich lang wie zwei orthogonale) und einen Maximum-Abstand in deiner Kostenfunktion. Das heißt, die approx_values werden über einen anderen Abstand berechnet als die exact_cost. Unglücklicherweise ist der Manhattan-Abstand länger als der Max-Abstand. Das führt dazu, dass die approx_values zu hoch geschätzt werden. Wenn das passiert, funktioniert der Algorithmus nicht mehr. Wie zuvor schon mal gesagt: Du darfst den Lowerbound (also die approx_values) nur zu niedrig schätzen, nicht aber zu hoch.

Man kann es auch an einem Beispiel erklären. Du berechnest die distanz derzeit so: distanz = x-abstand + y-abstand. Das würde bedeuten, das bei einem diagonalen Feld die Distanz gleich 2 ist. Nun berechnest du also den Lowerbound mit 2 * Min-Wegkosten. Nun erlaubst du aber auch einen diagonalen Schritt mit Kosten 1 * Wegkosten. Das heißt es gibt exakte Kosten, die kürzer sind als die zuvor berechneten Minimalkosten.

Die Lösung wäre eine Anpassung deiner Schätzfunktion:

Code:

distance_x = node.x - to_tile_x
distance_y = node.y - to_tile_y
approx_distance = [distance_x.abs + distance_y.abs].max
# oder effizienter
approx_distance = distance_x
approx_distance = distance_y if distance_y > distance_x

[Cornix]

Ich habe es ausprobiert, es wurde nun noch ein wenig schlimmer.
Die Figur bewegt sich nun beinahe ausschließlich Diagonal. Eine Strecke welche eigentlich nur 4 Nodes in grader Linie abzugehen wäre wird nun zu über zwanzig Nodes welche sich diagonal zweimal durch die Karte ziehen.

[-KD-]

Hm, irgendwo ist da der Wurm drin... Die exakten Kosten steigen ja trotzdem mit jedem Feld an und die aprox_values werden aus den exakten Kosten berechnet. Demzufolge dürfte das gar nicht passieren. Kannst du nochmal die Formeln für die Berechnung der approx_value und exact_value posten?

[Cornix]

Hier bitte der derzeitige Stand des Scriptes:

Code:

      distance_x = (node.x - to_tile_x).abs
      distance_y = (node.y - to_tile_y).abs
      approx_distance = distance_x + distance_y
      #the exact costs to reach this node
      exact_value = current_node.exact_value + node.cost
      #the approximated costs from this node to the end node
      approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTOR

In diesem Zustand funktioniert das Pathfinding in den meisten Fällen sehr gut, nur manchmal neigen die Figuren zu seltsamen Zickzackmustern in kleinem Maßstab welche die eine oder andere überflüssige Diagonalbewegung beinhalten.
In sehr seltenen Fällen (und das ist leider auch schwer reproduzierbar) scheinen sie sogar kurzzeitig in die falsche Richtung laufen zu wollen.

Und so sieht das Script mit den von dir angesprochenen Veränderungen aus:

Code:

      distance_x = (node.x - to_tile_x).abs
      distance_y = (node.y - to_tile_y).abs
      approx_distance = distance_x
      approx_distance = distance_y if distance_y > distance_x
      #the exact costs to reach this node
      exact_value = current_node.exact_value + node.cost
      #the approximated costs from this node to the end node
      approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTOR

Nun scheinen sich die Figuren im Grunde nurnoch diagonal fortbewegen zu wollen sofern es möglich ist.

Falls du es einmal selbst ausprobieren möchtest so könnte ich dir das Projekt in derzeitigem
Zustand auch einmal zukommen lassen, nur damit du siehst welche Art von "eigenartiger" Bewegung ich meine.

Edit:
Ich habe nocheinmal die alte Version, also das erste der beiden Scripte in diesem Beitrag, getestet, es scheint nun soweit zu funktionieren wie es sollte.
Ich scheine wahrscheinlich noch irgendetwas anderes bei meiner letzten Arbeit verändert zu haben an das ich mich nichtmehr so recht errinern kann. Auf jedenfall sind die angesprochenen Probleme somit scheinbar verschwunden.
Ich werde das Script fürs erste dabei belassen und weitere Tests durchführen.

Danke nocheinmal für deine Zeit.

[-KD-]

Nun scheinen sich die Figuren im Grunde nurnoch diagonal fortbewegen zu wollen sofern es möglich ist.

...

Also wenn Diagonalbewegungen genauso teuer sind wie orthogonale Bewegungen, ist es ja erlaubt jeden orthogonalen Schritt durch einen diagonalen Schritt zu ersetzen. Warum das Script das auch so macht, ist eine andere Sache.


Eine alternative Möglichkeit: Verbiete diagonale Schritte einfach. Das macht den Algorithmus auch effizienter. Wenn du am Ende die MoveRoute rausbekommst (als Array von Richtungsangaben) brauchst du ja bloß in einer Schleife drüberlaufen und je zwei nicht entgegengesetzte Richtungsangaben in eine diagonale Richtung umwandeln.
Das funktioniert dann, wenn diagonale Schritte immer nur dann möglich sind, wenn man stattdessen auch zwei orthogonale Schritte machen könnte.

[Cornix]

Das ist eine wirklich gute Idee, nur muss ich einmal darüber nachdenken wie ich am besten aus dem Array von Nodes ein Array mit Richtungsangaben erstelle.
Wie wäre dieser Versuch, als erstes die alte Methode um die Move_Route zu erstellen, danach die neue mit Richtungsangaben in Form von Integern:

Code:

  def generate_move_route_old(start_node,end_node)
    #the move_route is an array containing the locations of all nodes
    move_route = [end_node]
    predecessor = end_node.predecessor
    loop do
      if predecessor.nil?
        break 
      end
      move_route.insert(0,predecessor)
      predecessor = predecessor.predecessor
      if predecessor == start_node
        break
      end
    end
    return move_route
  end

Code:

  def generate_move_route(start_node,end_node)
    move_route = []
    current_node = end_node
    loop do
      predecessor = current_node.predecessor
      if predecessor.nil?
        break
      end
      cx = current_node.x
      cy = current_node.y
      px = predecessor.x
      py = predecessor.y
      if cx < px
        # move right
        next_direction = LEFT#RIGHT
      elsif cx > px
        # move left
        next_direction = RIGHT#LEFT
      elsif cy < py
        # move up
        next_direction = UP#DOWN
      else
        # move down
        next_direction = DOWN#UP
      end
      old_direction = move_route[move_route.size - 1]
      if old_direction.nil?
        move_route.insert(0,next_direction)
      else
        direction_sum = old_direction + next_direction
        case direction_sum
        when 4
          # move down_left
          move_route[move_route.size - 1] = DOWN_LEFT
        when 5
          # move down_right
          move_route[move_route.size - 1] = DOWN_RIGHT
        when 9
          # move up_left
          move_route[move_route.size - 1] = UP_LEFT
        when 10
          # move up_right
          move_route[move_route.size - 1] = UP_RIGHT
        else
          move_route.insert(0,next_direction)
        end
      end
      current_node = predecessor
    end
    return move_route
  end

Oder kann man dies noch besser lösen?

Edit: Ich habe bereits gemerkt, die Diagonalbewegungen werden noch nicht korrekt übersetzt. Ich weis auch warum, ich weis nur noch nicht wie ich es lösen soll.

Das Problem ist folgendes, soll sich meine Figur in folgendem Beispiel von O bis X bewegen:

Code:

O - - -
- - - -
- - - -
- - - X

So erstellt das Pathfinding zunächst folgende Bewegungsroute:

Code:

7 - - -
6 - - -
5 - - -
4 3 2 1

Bei der umwandlung von den nodes zu den Bewegungsrichtungen wird bei mir derzeit nur der Schritt von 3 über 4 zu 5 zu einer Diagonalbewegung umgewandelt da die Schritte 2 und 6 nicht aufeinanderfolgen.

Ich muss leider nocheinmals um Hilfe bitten.

[-KD-]

Verwende mal eine euklidische Distanz:

Code:

approx_distance = Math.hypot(node.x - to_tile_x, node.y - to_tile_y)
approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTOR

Jetzt hat die Luftlinie einen kürzeren Lowerbound und wird daher bevorzugt.

(Math.hypot(a, b) ist Wurzel(a^2 + b^2))

[DFYX]

Ich empfehle zu dem Thema unbedingt A* Pathfinding for Beginners und die dort verlinkten Seiten. Für dein Problem mit der Diagonalbewegung könnte insbesondere Marco Pinter - Toward More Realistic Pathfinding interessant sein.

[Cornix]

Verwende mal eine euklidische Distanz:

Code:

approx_distance = Math.hypot(node.x - to_tile_x, node.y - to_tile_y)
approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTOR

Jetzt hat die Luftlinie einen kürzeren Lowerbound und wird daher bevorzugt.

(Math.hypot(a, b) ist Wurzel(a^2 + b^2))

...

Ich habe mich nun entschlossen deinen vorherigen Vorschlag umzusetzen nurnoch "gerade" Bewegungen zuzulassen und die Diagonalen Verbindungen beim Pathfinding auszuschließen. Es ist nämlich wirklich in meinem Interesse, dass eine diagonale Bewegung nicht möglich ist falls sie nicht auch durch zwei gerade Bewegungen möglich wäre, sprich in diesem Beispiel sollte die Bewegung nicht möglich sein:
(Bewegung von 1 nach 4, ein als X gekennzeichnetes Tile ist nicht passierbar)

Code:

1 - - -
- 2 X X
X X 3 -
- - - 4

Würde es daher immernoch von Nutzen sein die Hypotenuse der Distanz zu berechnen?

Außerdem ist es nun ersteinmal wichtig für mich, die Umwandlung der geraden Schritte in Diagonalschritte möglichst schnell und effizient zu machen. Die Tatsache, dass nicht alle Schritte umgewandelt werden ist kein besonders großes Problem, falls sie dieser Fehler nicht mit wenig Rechenaufwand beheben lässt werde ich es auch einfach dabei belassen.

An DFYX:
Danke für die Links.
Ich habe mich bereits mit dem A*-Pathfinding auseinandergesetzt, immerhin habe ich meine erste Version des Pathfindings komplett mit Hilfe eines solchen Turtorials geschrieben. Wobei es mir nun geht ist insbesondere die Effektivität am RPG-Maker XP so gut wie möglich zu steigern.
Der zweite Link ist zwar sehr interessant, jedoch nicht wirklich von Interesse für mein Anliegen.
Die grobe Tilemap ist wichtiger Bestandteil meines Projektes und Bewegungen welche versuchen diese Kanten auszugleichen sind nicht nötig, weiter noch, sie wären eher störend für den Spieler.

[-KD-]

Code:

Würde es daher immernoch von Nutzen sein die Hypotenuse der Distanz zu berechnen?

Ja. Wenn du die Manhattan-Distanz oder die Max-Distanz verwendest, dann ist es egal ob du erst 5 Felder runter und dann 5 Felder nach rechts läufst, oder ob du 5 Mal abwechselnd ein Feld nach rechts und ein Feld nach unten gehst. Bei der euklidischen Distanz ist die zweite Lösung besser.
Du änderst zwar nur den approx_value (das heißt für die exakte Lösung ist es weiterhin egal), aber das sorgt ja dennoch dafür, dass das abwechselnd nach rechts und nach unten laufen bevorzugt wird (weil diese Knoten einen niedrigeren approx_value haben und daher als erstes besucht werden).

Wichtig beim Ändern der approx_value Berechnung ist immer, dass du nie zu hoch schätzt. Man kann aber zeigen dass die euklidische Distanz nie höher als die Manhattan-Distanz oder die Max-Distanz sein kann (nennt sich Dreiecksungleichung). Darum ist das in diesem Fall erlaubt nur den approx_value anzupassen und die exakten Kosten weiterhin nach dem gewohnten Schema berechnen zu lassen.

Achja, wegen dem Berechnen der diagonalen Schritte: das ist das letzte worüber du dir Sorgen machen musst. Der Pathfinding-Algorithmus muss unter Umständen sehr sehr viele Knoten anschauen. Der Algorithmus, der aus diesen Knoten diagonale macht muss hingegen nur so viele Knoten anschauen, wie es Schritte auf dem Weg gibt. Das ist im Normalfall extrem wenig. Außerdem kannst du diese Umrechnung auch "lazy" machen. Also erst wenn das Event (oder für wen auch immer du den Pfad berechnest) sich wirklich bewegt, wird geguckt ob es die nächsten zwei orthogonalen Schritte durch einen diagonalen Schritt ersetzen kann.

[DFYX]

Achja, wegen dem Berechnen der diagonalen Schritte: das ist das letzte worüber du dir Sorgen machen musst. Der Pathfinding-Algorithmus muss unter Umständen sehr sehr viele Knoten anschauen. Der Algorithmus, der aus diesen Knoten diagonale macht muss hingegen nur so viele Knoten anschauen, wie es Schritte auf dem Weg gibt. Das ist im Normalfall extrem wenig. Außerdem kannst du diese Umrechnung auch "lazy" machen. Also erst wenn das Event (oder für wen auch immer du den Pfad berechnest) sich wirklich bewegt, wird geguckt ob es die nächsten zwei orthogonalen Schritte durch einen diagonalen Schritt ersetzen kann.

...

Wobei das unter Umständen die Berechnung der Weglänge verzerrt, weil es in der Regel schneller ist, diagonal zu laufen.