Brauche Hilfe: Pathfinding

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

[-KD-]

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.

...

Dann brauchst du kein richtiges Pathfinding. Eine einfache Tiefensuche würde sich genauso verhalten. Das Problem ist: Wenn du die Approx-Kosten einfach überschätzt (oder nur noch mit ihnen arbeitest), fängt der Algorithmus an einfach immer in Himmelsrichtung auf das Ziel zuzulaufen. Dabei ist dann völlig unerheblich welches Terrain verwendet wird.
Logischerweise ist das echte Pathfinding langsamer, weil es ja den richtigen Weg berechnet und nicht einfach nur auf das Ziel zuläuft.

Ich hab mal einen kleinen Benchmark gemacht. Die 20x15 Map als wirres Labyrinth, für das ein Pathfinder schon etwas Aufwand braucht. Start und Ziel waren in entgegengesetzten Ecken der Map. Zeit für die ganze Berechnung: 1-2 Millisekunden. Damit die FPS nicht herabsinkt müsstest du aufpassen, nicht mehr als, sagen wir 20, solcher Pathfindings pro Frame durchzuführen. Ich weiß ja nicht wie viele Events bei dir jeden Frame ein Pathfinding durchführen müssen, aber im Normalfall sollte das in Ordnung gehen. Problematischer wird es höchstens bei sehr großen Maps. Aber da würde ich, sollte es wirklich Performanceprobleme geben, zu anderen Mitteln greifen (z.B. über vorausberechnete Wegpunkte)

[Cornix]

Es soll ein RTS-Spiel werden.
Das Maximum der Karten habe ich, eher willkürlich, auf 176x176 gesetzt, an Einheiten werden sicherlich zwischen 25 bis 100 Stück die Karte gleichzeitig vorhanden sein, doch wird das Pathfinding natürlich nicht regelmäßig für jede einzelne gleichzeitig benötigt werden.
Die Karten werden in den allermeisten Fällen nur sehr wenige völlig unpassierbare Tiles besitzen, und selbst wenn es mehrere sind werden diese eher in größeren Ansammlungen in kurzer Distanz zueinander liegen, ein Meer oder ein Fluss zum Beispiel.

Aber gut, ich werde ersteinmal weiterarbeiten und die Performance am Ende der Alpha nocheinmal zum Thema erklären und im Nachhinein schauen was verbessert werden kann.