Brauche Hilfe: Pathfinding

[-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.

[Cornix]

Vielen Dank, über die Hypothenuse die approx_value's zu setzen funktioniert wunderbar, dadurch entsteht auch nichtmehr die Ungenauigkeit der Umwandlung von zwei geraden Bewegungen in eine entsprechende diagonale Bewegung.

Die von mir früher vorgestellte Funktion ist überdies hinaus veraltet und nicht richtig, hier mein derzeitiges Script welches in allen derzeitigen Tests tadelose Arbeit geleistet hat:

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
      elsif cx > px
        # move left
        next_direction = RIGHT
      elsif cy < py
        # move up
        next_direction = UP
      else
        # move down
        next_direction = DOWN
      end
      old_direction = move_route[0]
      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[0] = DOWN_LEFT
        when 5
          # move down_right
          move_route[0] = DOWN_RIGHT
        when 9
          # move up_left
          move_route[0] = UP_LEFT
        when 10
          # move up_right
          move_route[0] = UP_RIGHT
        else
          move_route.insert(0,next_direction)
        end
      end
      current_node = predecessor
    end
    return move_route
  end

Die Konstanten DOWN_LEFT bis UP_RIGHT sind Integer von 0 bis 7 angeordnet wie auf dem Nummernblock der Tastatur (1 == 0, 5 ausgelassen).

[Cornix]

Entschuldigung, dass ich dieses Thema wiederbeleben muss, aber ich habe noch einige Arbeiten am Pathfinding vorgenommen, unter anderem bin ich deinem (@-kd-) Tipp gefolgt und habe ein kleines Testprogramm geschrieben welches dazu dient die genauen exact- und approx Werte für jeden Node während einer Suche darzustellen.

Die Ergenisse sind gespalten. Ich habe gemerkt, dass die Suche in manchen Fällen sehr viel schneller und kürzer sein kann falls ich die Approx-Values für jeden node nur durch die Distanz Berechnen lasse und ohne die Kosten. Allerdings wird dann nur ein Weg zum Ziel gesucht, keinesfalls der kürzeste.

Ich bin mir noch nicht sicher wie ich die Korrelation zwischen Distanz und Kosten setzen sollte um in den meisten Fällen die beste Geschwindigkeit zu erreichen denn was ich beobachten konnte war folgendes Verhalten:
War die Distanz von einem Knoten zum Zielknoten sehr viel schwerer gewichtet bei der Berechnung der approx_values dieses Knotens als die tatsächlichen Kosten um ihn zu erreichen, so war der Rechenaufwand (Die Anzahl der Knoten die überprüft wurden) in den allermeisten Fällen sehr viel geringer, je stärker die Distanz gewichtet wurde desto weniger überflüssige Überprüfungen wurden durch den Algorithmus durchgeführt.
Allerdings war die Genauigkeit der Suche genauso gefallen wie die Performance stieg. Das heist die Chance nicht den kürzesten sondern lediglich einen möglichen Weg zu finden stieg.

Ich wäre euch sehr verbunden falls ihr dieses kleine Programm einmal testen könntet, euch die Ergenisse einmal anschaut und mir vielleicht sagen könnt ob ich vielleicht irgendwo einen Fehler gemacht haben muss, oder falls nicht, wie ich am besten die Gewichtung zwischen Distanz und Kosten bei der Berechnung der approx_values setzen sollte.

Hier der Download mit den benötigten DLL-Dateien um das Projekt auch ohne RTP testen zu können.
(1.58 mb)

Hier der Download ohne DLL-Dateien.
(104 kb)

Vielen Dank.