Brauche Hilfe: Pathfinding

[Cornix]

Guten Tag.
Für mein derzeitiges Projekt arbeite ich an einem geeigneten Pathfinding-System welches möglichst effektiv den schnellsten (nicht kürzesten) Weg durch ein Gebiet sucht.
Der schnellste Weg soll bedeuten, dass manche Tiles die Geschwindigkeit der Einheit beeinflussen können; Wälder verlangsamen, Gebirge und Wüsten ebenfalls.

Ich habe mir bereits soviel Arbeit gemacht einen funktionierenden A*-Pathfinding-Algorithmus zu schreiben.
Wie gesagt, er funktioniert, er findet den schnellsten Weg in 100% der Fälle.

Allerdings kommt nun ein ganz anderes Problem zu tragen, er verbraucht zu viel Performance.

Mit diesem Script würden schwächere Computer kaum mitkommen, besonders falls mehrere Einheiten Pathfinding benötigen und es sich dazu um eine große Karte handelt.
Ich könnte es in Kauf nehmen wenn die Wegsuche weniger genau ist und nicht immer den richtigen Weg findet falls die Performance dadurch sehr viel verbessert werden könnte.

Hier ist mein derzeitiges Script:

Code:

module Pathfinding
  module_function
  
  def set_map(map)
    @map = map
    
    #create array of all nodes on the map
    @node_list = []
    width = @map.width-1
    height = @map.height-1
    for x in 0..width
      for y in 0..height
        #get the speed modification for every node
        speed_factor = @map.get_movement_speed_factor(x,y)
        #nodes with a speed factor of 0 are impassable
        if speed_factor > 0
          #id in the array, x/y coordinate, and movement speed factor > 0
          node = Node.new(x,y,speed_factor)
          @node_list.push(node)
        end
      end
    end
    #get all adjacent nodes for every node
    for current_node in @node_list
      cx = current_node.x
      cy = current_node.y
      adjacent_nodes = []
      for possible_adjacent_node in @node_list
        ax = possible_adjacent_node.x
        ay = possible_adjacent_node.y
        distance_x = ax-cx
        distance_y = ay-cy
        #a node is adjacent if the horizontal or vertical distance is -1, 0 or 1
        if distance_x.abs < 2 && distance_y.abs < 2
          adjacent_nodes.push(possible_adjacent_node)
        end
      end
      current_node.adjacent_nodes = adjacent_nodes
    end
  end
  
  def find_path(from_tile_x, from_tile_y, to_tile_x, to_tile_y)
    start_node = nil
    for node in @node_list
      #the start_node is the node at from_tile_x / from_tile_y
      if node.x == from_tile_x && node.y == from_tile_y
        start_node = node
      end
    end
    #array of all nodes which have not been expanded yet
    open_nodes = [start_node]
    
    current_node = start_node
    #flag the start node as "opened" == the node is in the open_nodes array
    current_node.opened = true
    #ensure result if the target is the start
    final_node = start_node
    loop do
      #end if no nodes can be expanded anymore == no path found
      if open_nodes.size == 0
        self.cleanup
        return nil
        break
      end
      if current_node.x == to_tile_x && current_node.y == to_tile_y
        final_node = current_node
        #break if the final node has been reached
        break
      else
        final_node = current_node
        #expand the current node
        self.expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
        #the next node to be expanded is the node with the best value
        size = open_nodes.size
        current_node = open_nodes[0]
        for i in 1...size
          check_node = open_nodes[i]
          if check_node.value < current_node.value
            current_node = check_node
          end
        end
      end
    end
    #get the move route, an array containing the nodes to move along in order
    move_route = self.generate_move_route(start_node,final_node)
    #reset all data for the next task
    self.cleanup
    return move_route
  end
  
  def expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
    #iterate through every adjacent node of the current node and add it to the open_nodes array
    for node in current_node.adjacent_nodes
      #if the node is already closed it cannot be opened again
      next if node.closed
      distance_x = node.x - to_tile_x
      distance_y = node.y - to_tile_y
      distance = distance_x.abs + distance_y.abs
      value = current_node.value + node.speed_factor + 350 * distance
      #the value is determined by both, the speed factor and the distance
      if node.opened
        #if the node is already opened
        if value >= node.value
          #do nothing if there is already a better value for this node
          next
        else
          #if the new value is better then the previous save the new value and the predecessor
          node.predecessor = current_node
          node.value = value
        end
      else
        open_nodes.push(node)
        #save the predecessor for this node, the value and that its opened
        node.predecessor = current_node
        node.value = value
        node.opened = true
      end
    end
    open_nodes.delete(current_node)
    current_node.closed = true
  end
  
  def cleanup
    #iterate through every node in reset its values
    for node in @node_list
      node.closed = false
      node.opened = false
      node.value = 999999
      node.predecessor = nil
    end
  end
  
  def generate_move_route(start_node,end_node)
    #the move_route is an array containing the locations of all nodes
    move_route = [[end_node.x,end_node.y]]
    predecessor = end_node.predecessor
    loop do
      break if predecessor.nil?
      move_route.insert(0,[predecessor.x,predecessor.y])
      predecessor = predecessor.predecessor
      if predecessor == start_node
        break
      end
    end
    return move_route
  end
  
  class Node
    #the coordinates of this node
    attr_reader :x
    attr_reader :y
    #how the movement speed of units at this location is modified
    attr_reader :speed_factor
    #whether the node has been expanded or not
    attr_accessor :closed
    #if the node is in the open_list or not
    attr_accessor :opened
    #an array with all adjacent nodes
    attr_accessor :adjacent_nodes
    #the value of this node. the lower the value the more likely will this node be expanded next
    attr_accessor :value
    #the predecessor of this node in the move_route
    attr_accessor :predecessor
    def initialize(x,y,speed_factor)
      @x = x
      @y = y
      #original speed_factor = 0.0 <= float <= 1.0
      @speed_factor = 1000 - (speed_factor * 1000).to_i
      #new speed_factor = 0 <= int <= 1000
      
      @adjacent_nodes = []
      
      @closed = false
      @opened = false
      @value = 999999
      @predecessor = nil
    end
  end
  
end

Ich bedanke mich vielmals für jede Hilfe.

[-KD-]

Wenn du A* nicht dutzende Male pro Frame aufrufst sollte A* effizient genug sein. Das Problem ist deine Implementierung. Das fängt schon bei der set_map Methode an. Der große Vorteil von A* gegenüber anderen Pathfinding-Algorithmen, wie z.B. Dijkstra, ist das A* im Normalfall nicht alle Felder der Map durchsuchen muss. Im Idealfall findet A* sogar sofort den Weg zum Ziel, ohne sich weitere umliegende Felder anzugucken. Du aber sagst in der Initialisierung: Lege für jedes Feld auf der Map ein neues Objekt an und speichere alle umliegenden Felder ab. Das zerschießt dir schonmal total die Performance, wenn du auf einer 500x500 Map alle Felder anguckst, obwohl du nur einen Weg suchst der 15 Felder einschließt. Ganz böse ist deine Suche nach adjazenten Knoten. Dafür iterierst du zweimal über alle Knoten, nur um rauszufinden welche Knoten adjazent sind. Bei einer 500x500 Map macht das 500^4 viele Iterationen!!! (macht genau 62500000000 viele Schleifendurchläufe...)

Prinzipiell musst du dir klar machen, das solche Modelle wie Graphen nur Abstraktionen sind. Nehmen wir mal deine Datenstruktur @node_list. Das ist ein Array, der für jedes Feld der Map ein Objekt mit folgenden Attributen enthält: x, y, adjazente Knoten und Geschwindigkeit. Ich nenne dir mal eine alternative Datenstruktur, die genau dieselben Attribute enthält: Eine Table! Eine 2D Table, deren Einträge die Kosten sind. Was ist die X/Y Koordinate des Table-Eintrages @node_table[10, 20]? Na 10 und 20. Was sind die adjazenten Knoten? 9/20, 11/20, 10/19, 10/21. Das kann ich dir sagen, ohne diese adjazenten Knoten explizit abzuspeichern.
Wenn die Map ein Schachbrettmuster ist, musst du die meisten Sachen nicht abspeichern, du kannst sie dir on the fly berechnen und das ohne Aufwand. Ist der Knoten offen? Ja, wenn seine Kosten gleich 0 sind, nein, wenn seine Kosten ungleich 0 sind.

(Natürlich musst du auch für eine solche Tabelle 500x500 viele Tabelleneinträge anlegen. Das sind aber nur Integer-Werte, die zudem alle mit dem selben Wert 0 initialisiert werden. Das wird über Memcopy gemacht und geht extrem schnell, binnen einer Mikrosekunde! Im Gegensatz dazu muss bei deiner Methode für jedes Feld ein Objekt angelegt werden, was sehr viel Zeit kostet.)

Wie könnte man den Algorithmus effizienter machen? Du definierst dir erstmal eine 2D Table für die Map. Dann iterierst du über alle Events und setzt den Tabelleneintrag, auf dem das Event sich befindet, auf -1, falls das Event nicht begehbar ist. Damit sparst du dir, jedes Mal wenn du dir ein Feld anguckst über alle Events zu iterieren (was in der Performance gewaltige Einbußen macht). Als nächstes legst du eine @open_list an und fügst die Koordinaten und Kosten des Anfangsknotens ein. @open_list = [[0, x, y]]. Danach sortierst du in jedem Schritt den Array (@open_list.sort!, beachte das beim Sortieren von Arrays, die Arrays enthalten, immer das erste Arrayelement als Sortierschlüssel verwendte wird) und holst dir das letzte Element aus dem Array (@open_list.pop). Das ist der Knoten, den du dir als nächstes ansiehst. Warum der letzte? Das ist in der Tat ein Problem, weil beim Sortieren automatisch erstmal von klein nach groß sortiert wird, du aber an den geringsten Kosten interessiert bist. Allerdings ist es effizienter einem Array von hinten Elemente zu entnehmen als von vorne. Eine Lösung des Problems ist, die Kosten immer negativ in den Array einzufügen. Dann sind die geringsten Kosten die größten Zahlen im Array. Nun fügst du alle adjazenten Knoten des soeben herausgeholten Knotens in den Array ein. Achte dabei, dass du nur Knoten einfügst, die in der Tabelle die Kosten 0 haben. Dabei berechnest du deren Kosten (kosten = kosten des herausgeholten Knotens + @map.get_movement_speed_factor(x,y)) und schreibst sie in die Table. Danach schreibst du die geschätzten Kosten in den Array. Das machst du solange, bis du einen Knoten findest der zum Ziel führt.

Nochmal als Pseudocode:

Code:

FUNCTION finde weg nach (x, y) 
  maptable := erzeuge Table der Größe Mapwidth x Mapheight
  FOR events in map DO
    maptable[event.x, event.y] = -1 if event.trough
  END FOR
  open_list := [[0, x, y]]
  UNTIL open_list.empty? DO
    open_list.sort!
    kosten, kx, ky = open_list.pop
    IF (kx, ky) == (x, y) THEN
      RETURN Weg gefunden!
    END IF
    FOR adjazente knoten (ax, ay) in (kx, ky) DO
      IF maptable[ax, ay] == 0 AND movement_speed_factor(ax,ay) > 0 THEN
        neue_kosten = maptable[kx, ky] + movement_speed_factor(ax,ay)
        maptable[ax, ay] = neue_kosten
        geschätzte_kosten = neue_kosten + entfernung von (ax, ay) nach (x, y)
        open_list << [ -geschätzte_kosten, ax, ay]
      END IF
    END FOR
  END UNTIL
  RETURN Weg nicht gefunden!
END FUNCTION

[Cornix]

Danke für die schnelle Antwort!

Die set_map(...) Methode existiert eigentlich nicht, ich hatte sie nur eingefügt um ungefähr zu zeigen woher die @node_list kommt. diese wird nämlich in einer anderen Klasse erstellt und an das Pathfinding-Script übergeben.
In den Nodes speichere ich noch weitere Eigenschaften des Tiles, ich hatte mich entschieden jedes Tile als Node-Objekt zu erstellen um das Speichern der verschiedenen Daten einfacher zu machen.
Außerdem wird die @node_list auch nur ein einziges Mal erstellt und zwar wenn die Karte geladen wird. Eine kurze Ladezeit sollte keine allzu große Zumutung sein hoffe ich. (Daher habe ich auch nicht sonderlich auf Effektivität geachtet.)

Die Tabelle anstatt der Node-Objekte hatte ich auch in Erwägung gezogen, doch die @node_list verwende ich auch für andere Anliegen, außerdem ist sie ja persistent durch das Spiel hindurch vorhanden und unverändert, daher dachte ich mir könnte ich sie auch genau so gut für das Pathfinding verwenden.

Ich benötige die @node_list auch um komplexere Daten zu speichern, so dachte ich mir zum Beispiel, dass Rohstoff-Sammler sich eine Node-Instanz merken von welcher sie ihre Rohstoffe abbauen, ich hatte auch die Idee, dass es vielleicht sehr viel Performance sparen könnte falls ich die Move_Route von dem Resourcenabladepunkt zur Resource in den Nodes speichere (Der Resourcenabladepunkt ist statisch) und daher nur ein einziges Mal den Pfad berechnen muss.

Ist es schneller alle Daten welche ich benötige in ein Array zu speichern, also dieses Array als Ersatz für die Node-Klasse welche ich verwende zu benutzen?
Sprich, anstatt folgendes:

Code:

class Node
attr_accessor :x,:y,:speed_factor,:[...]
end
node = Node.new(...)

nur ein Array zu verwenden wie du es tust?

Code:

node = [x,y,speed_factor,...]

Ist das Sortieren durch: Array.sort! besser als meine Methode über:

Code:

size = open_nodes.size
        current_node = open_nodes[0]
        for i in 1...size
          check_node = open_nodes[i]
          if check_node.value < current_node.value
            current_node = check_node
          end
        end

(Oder wäre es hier vielleicht besser einen Sortieralgorithmus wie Quicksort zu verwenden?)

Vielen Dank nocheinmal.

[-KD-]

Das musst du schon dazu schreiben. Wenns nicht an der Initialisierung liegt, muss das Problem woanders sein. Erstmal zu deinen Fragen:

Ist es schneller alle Daten welche ich benötige in ein Array zu speichern, also dieses Array als Ersatz für die Node-Klasse welche ich verwende zu benutzen?

...

Kommt auf die Rubyversion an. Theoretisch ist es aufwendiger Arrays zu vergleichen als Objekte. In älteren Rubyversionen ist der Zugriff auf Instanzvariablen aber so extrem langsam, dass Objekte dennoch langsamer zu vergleichen sind. Dann sind Arrays etwa 3 Mal schneller. Allerdings sollte das Sortieren binnen weniger Mikrosekunden zu schaffen sein. Ich glaube nicht, dass es daran liegt.

Ist das Sortieren durch: Array.sort! besser als meine Methode

...

Ja. Prinzipiell kannst du statt deiner Methode auch kurz folgendes schreiben:

Code:

open_nodes.max {|node| node.value }

Theoretisch ist die Maximumsuche wesentlich schneller als das Sortieren. Allerdings ist die Sortierzeit davon abhängig, wie viel sortiert werden muss. Ist der Array schon zu 90% sortiert, muss nicht mehr viel gemacht werden und das Sortieren geht extrem schnell. Die Maximumsuche dagegen braucht immer gleich viel Zeit. Da du immer nur wenige Elemente ans Ende des Arrays anhängst, muss nicht all zu viel sortiert werden und das Sortieren dürfte genauso schnell gehen wie die Maximumsuche.

Oder wäre es hier vielleicht besser einen Sortieralgorithmus wie Quicksort zu verwenden

...

Wenn du das Pivotelement immer in die Mitte (bloß nicht an den Anfang!) setzt, müsste Quicksort recht fix gehen. Aber Rubys sort-Methode ist bereits ein ausgeklügelter Quicksort. Von daher musst du das Rad nicht zweimal erfinden (zumal C-interne Methoden immer deutlich schneller sind als in Ruby geschriebene).

Nochmal zu deiner NodeList: Wenn du sie nur einmal erstellst, mag das ja nicht so schlimm sein. Dennoch solltest du sie in einem tabellenförmigen Array speichern. Also so speichern, dass du aus der X/Y-Koordinate direkt die Position im Array errechnen kannst. Dann sparst du dir am Anfang deines Algorithmus das Iterieren über alle Knoten in der NodeList, um den Zielknoten zu finden. Außerdem würde ich dennoch alle Variablen, die zum Pathfinding gehören (Distanz, Predecessor etc.) nicht in den Nodes abspeichern. Sonst musst du am Ende des Pathfindings über alle Nodes iterieren und diese resetten. Stattdessen würde ich dir dennoch meine Tabellenlösung raten. Das Backtracking kannst du direkt in der Tabelle machen, dafür brauchst du keine Predecessor Angaben. Auch würde ich die adjazenten Knoten on the fly berechnen. Sowas in den Node-Objekten abzuspeichern ist einfach Speicherverschwendung.

[Cornix]

Das mit dem Speichern all der Werte verstehe ich, allerdings arbeite ich immer mit dem Hintergedanken, dass die Performance von Scripten im RPG-Maker extrem schlecht ist, der RAM-Verbrauch allerdings nicht sonderlich groß ist bei solchen kleinen Spielchen.
Da ich mit mindestens 1GB RAM auf dem Computer der Anwender rechne denke ich mir immer, dass es sehr viel besser ist mehr RAM zu verbrauchen wenn dadurch Rechenleistung eingespart werden kann, auch wenn es nicht proportional ist.
Ob das an allen Stellen an denen ich es anwende Sinn ergibt ist höchst fragwürdig, wahrscheinlich wird es keinen Unterschied machen die @adjacent_nodes direkt zu berechnen anstatt sie zu speichern, als ich das Script jedoch geschrieben habe dachte ich mir auf die paar kb kommt es nicht an.

Aber soweit ich deiner Antwort entnehmen kann ist der Suchalgorithmus soweit wie er ist schon sehr gut umgesetzt? Gibt es da nicht eine Stelle an welcher sich Performance einsparen lässt?

[-KD-]

Ah, ich glaub ich weiß jetzt warum das bei dir so langsam ist. An deinem Algorithmus stimmt etwas nicht noch nicht. Du musst unterscheiden zwischen den tatsächlichen Wegkosten und dem geschätzten Lowerbounds. Die Lowerbounds sind nur eine Heuristik, die dazu dient das du Wege weglassen kannst, von denen klar ist das sie nicht besser werden können und das du Wege bevorzugst, bei denen es wahrscheinlicher ist, dass sie kürzere Wegkosten haben. Die Lowerbounds darfst du berechnen wie du willst, aber du darfst nicht zu hoch schätzen (sprich: du darfst nicht sagen von A nach B sind es mindestens 10 Wegpunkte, obwohl es einen Weg mit 8 Wegpunkten gibt). Die Lowerbounds sind deine Values. Was dir fehlt sind die tatsächlichen Kosten. Diese müssen exakt sein und dürfen nicht geschätzt werden.

Beispiel: Du suchst einen Weg von A nach C. Dabei findest du einen Knoten B. Die geschätzten minimalen Kosten von A nach C über B sind gleich die exakten Kosten von A nach B plus die geschätzten minimalen Kosten von B nach C. Was machst du aber? Du addierst die geschätzten Minimalkosten von A nach C plus die geschätzten minimalkosten von B nach C. Das ist unter Umständen viel größer und führt dazu, dass die Lowerbounds explodieren je länger der Weg wird. Der Algorithmus bevorzugt daher immer kurze Wege und wird alle kurzen Wege ausprobieren, statt zielstrebig den richtigen Weg zu nehmen. Das dürfte der Grund sein warum dein Algorithmus so langsam ist.

Der korrigierte Sourcecode für die expand_node Methode würde so aussehen:

Code:

def expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
    #iterate through every adjacent node of the current node and add it to the open_nodes array
    for node in current_node.adjacent_nodes
      #if the node is already closed it cannot be opened again
      next if node.closed
      distance_x = node.x - to_tile_x
      distance_y = node.y - to_tile_y
      distance = distance_x.abs + distance_y.abs

      # value sind die geschätzten Minimalkosten zum Zielknoten
      value = current_node.cost + node.speed_factor + distance # warum 350?  - KD
      # costs sind die exakten Kosten zu diesem Knoten
      costs = current_node.cost + node.speed_factor

      #the value is determined by both, the speed factor and the distance
      if node.opened

        # Die geschätzten minimalkosten interessieren hier nicht. Wir wollen wissen ob der
        # Weg zu diesem Knoten wirklich kürzer ist, als zuvor gefundene Wege.
        if costs >= node.costs
          #do nothing if there is already a better value for this node
          next
        else
          
          # Kann dieser Fall überhaupt eintreten? - KD 
          
          #if the new value is better then the previous save the new value and the predecessor
          node.predecessor = current_node
          node.value = value
          node.costs = costs
        end
      else
        open_nodes.push(node)
        #save the predecessor for this node, the value and that its opened
        node.predecessor = current_node
        node.value = value
        node.opened = true
      end
    end
    open_nodes.delete(current_node)
    current_node.closed = true
  end

[Cornix]

Ok, ich vestehe die Überlegung aber die Technik dahinter noch nicht ganz.
Das Attribut ".value" der Nodes wird wie es mir scheint derzeit überhaupt nicht benötigt oder irre ich mich dabei? Ich kann nicht erkennen, dass das value der Nodes an irgendeiner Stelle im Script Verwendung findet.

# warum 350? - KD

...

Dieser Wert stammt noch aus einer alten Version. Er stammt daher, dass der "speed_factor" für jedes Node zwischen 125 und 1000 liegt, falls ich die Distanz im normalen Zustand einbringe würde sie kaum einen Effekt finden, das heist es würde niemals der kürzeste Weg sondern immer der Weg mit den kleinsten Kosten gesucht werden.
Der Wert 350 an dieser Stelle war nur ein Platzhalter um die Kraft des "speed_factors" auszubalancieren.

# Kann dieser Fall überhaupt eintreten? - KD

...

Das weis ich ehrlich gesagt nicht direkt. Ich habe mir niemals Gedanken darüber gemacht ob er es kann. Ich habe die zweite Möglichkeit einfach der Vollständigkeit halber eingeführt.
Denkst du, dass dieser Fall nicht eintreten kann?

Aber falls ich die Distanz zum Endknoten nicht in die Wertung miteinarbeite, dann würden doch zu viele
Nodes überprüft werden welche vielleicht zu wenig Erfolgsversprechend sind.
Falls ich lediglich den "speed_factor" einberechne dann würden immer die effektivsten Wege gesucht werden und Kostenintensive aber kürzere Wege kategorisch ausgeschlossen.
Kann es sein, dass dieser Teil vielleicht hätte wie folgt aussehen sollen:

Code:

costs = current_node.value + node.speed_factor

anstatt von:

Code:

costs = current_node.costs + node.speed_factor

?

[-KD-]

Ok, ich vestehe die Überlegung aber die Technik dahinter noch nicht ganz.
Das Attribut ".value" der Nodes wird wie es mir scheint derzeit überhaupt nicht benötigt oder irre ich mich dabei? Ich kann nicht erkennen, dass das value der Nodes an irgendeiner Stelle im Script Verwendung findet.

...

Du musst unterscheiden zwischen den EXAKTEN Kosten (die habe ich cost genannt) und den GESCHÄTZTEN Minimalkosten (die habe ich value genannt). Die geschätzten Minimalkosten sind nur um zu bestimmen, welchen Knoten du dir als nächstes anguckst. Sie werden also in der Sortierung der Knoten abgefragt. Ansonsten wird immer mit den exakten Kosten gearbeitet. Logisch, dich interessiert ja nicht ob es einen kurzen Weg zum Ziel geben KÖNNTE (denn mehr sagen dir die Minimalkosten nicht, sie sind nur eine Heuristik/Schätzung), sondern ob es auch einen gibt.

Dieser Wert stammt noch aus einer alten Version. Er stammt daher, dass der "speed_factor" für jedes Node zwischen 125 und 1000 liegt, falls ich die Distanz im normalen Zustand einbringe würde sie kaum einen Effekt finden, das heist es würde niemals der kürzeste Weg sondern immer der Weg mit den kleinsten Kosten gesucht werden.
Der Wert 350 an dieser Stelle war nur ein Platzhalter um die Kraft des "speed_factors" auszubalancieren.

...

Wie gesagt: Es sind geschätzte Minimalkosten. Das heißt du darfst nicht einfach irgendeinen Mittelwert nehmen. Du musst den Minimalwert nehmen. Es müsste also heißen:

Code:

node.value = node.cost + distance * MINIMAL_SPEED_FACTOR

Wobei MINIMAL_SPEED_FACTOR eben die Konstante 125 ist.

Das weis ich ehrlich gesagt nicht direkt. Ich habe mir niemals Gedanken darüber gemacht ob er es kann. Ich habe die zweite Möglichkeit einfach der Vollständigkeit halber eingeführt.
Denkst du, dass dieser Fall nicht eintreten kann?

...

Ich vermute mal, du hast ja Kosten für die Felder (=Knoten), nicht für die Kanten. Mal ein Beispiel: Du weißt die Wegkosten zum Feld 5/5 und zum Feld 6/6 und möchtest wissen wie lang der kürzeste Weg zum Feld 6/5 ist. Das Feld 6/5 hat Kosten 100. Es gibt einen Weg der dich mit Kosten 500 zum Feld 5/5 und mit Kosten 600 zum Feld 6/6 führt. Der Weg von Feld 5/5 zu Feld 6/5 hätte dann logischerweise die Kosten 600, der Weg von 6/6 zu 6/5 hätte die Kosten 700. Das heißt es werden einfach nur die Kosten des Feldes 6/5 auf die Kosten des vorherigen Feldes draufaddiert. Entsprechend ist IMMER das vorherige Feld das "schnellere", welches die geringeren Kosten hat. Dein Algorithmus wird also IMMER erst vom Feld 5/5 zum Feld 6/5 gehen und erst danach den alternativen Weg von 6/6 nach 6/5 ausprobieren (und sich diesen gar nicht erst genauer anschauen, weil ja bereits ein Weg nach 6/5 gefunden wurde). Der Fall, dass der Algorithmus erst einen ineffizienten Weg findet und erst später den besseren kann also gar nicht auftreten.

Im allgemeinen Fall, wo du Kantengewichte hast, ist das anders. Angenommen das Feld 6/5 ist eine Treppe. Nun kannst du argumentieren: Es ist ineffizienter eine Treppe hochzulaufen (also von dem Feld 5/5 zum Feld 6/5 zu laufen) als eine Treppe hinunterzulaufen (also von 6/6 nach 6/5). Wenn also Richtungsangaben darüber entscheiden, wie hoch die Kosten für ein Feld sind, dann kann dieser obige Fall auftreten und der Algorithmus muss mehrere Wege ausprobieren.

Aber falls ich die Distanz zum Endknoten nicht in die Wertung miteinarbeite, dann würden doch zu viele
Nodes überprüft werden welche vielleicht zu wenig Erfolgsversprechend sind.
Falls ich lediglich den "speed_factor" einberechne dann würden immer die effektivsten Wege gesucht werden und Kostenintensive aber kürzere Wege kategorisch ausgeschlossen.

...

Die Distanz ist nur für die Minimalkostenschätzung. Sie sagt dir aber nichts über die tatsächlichen Kosten aus. Die Distanz ist Luftlinie bzw. bei dir ist es eine Manhattan-Distanz (keine euklidische). Aber das ist ja egal. Wenn das Ziel nur 3 Schritte von dir entfernt ist, heißt das nicht, dass du nur 3 Schritte zum Ziel brauchst. Wenn nämlich vor dir 'ne Wand ist musst du drumherum laufen und brauchst plötzlich 100 Schritte Umweg ^^ Die Heuristik mit der Distanz meint nur, dass es schlau ist, erstmal den direkten Weg zu versuchen und erst dann einen anderen auszuprobieren, wenn der direkte Weg höhere Kosten verursacht (z.B. weil die Felder vor dir sumpfiges Gelände sind, oder eben weil da eine Wand steht, die sozusagen unendliche Kosten hat) als ein alternativer Weg.

Aus dem Grund errechnen sich die Wegkosten eines Knotens aus den Wegkosten des vorherigen Knotens plus den zusätzlichen "Speed-Factor" des Knotens. Lange Wege werden schon allein deswegen teuer, weil sie aus mehreren Knoten bestehen und da ja für jeden Knoten die Speed-Factor-Kosten mit einfließen wird auch der Weg teurer.


Also nochmal zusammengefasst. Du hast zwei wichtige Werte pro Knoten:
Exakte Kosten "cost"
Geschätzte Minimalkosten "value"

cost errechnet sich aus den cost-Wert des Vorgängerknotens plus den Speed-Factor des Knotens. value errechnet sich aus den cost-Faktor des Knotens plus der minimalen Zahl an Feldern, die man braucht um von diesem Knoten zum Ziel zu gelangen, multipliziert mit den minimalen Speed-Faktor-Kosten.

Der Algorithmus beginnt beim Startknoten und packt alle umliegenden (=adjazenten) Knoten in eine Liste. Von diesen berechnet er cost und value und sortiert die Liste nach den values. Er nimmt den Knoten mit dem höchsten value aus der Liste und wiederholt den Vorgang. Das ganze wird solange gemacht, bis man den Zielknoten gefunden hat.

[Cornix]

Jetzt habe ich verstanden, was ich nicht bedacht hatte war die Suche nach dem zunächst zu untersuchenden Knoten, dort wird immernoch das "value" verwendet.
In Ordnung, vielen Dank für die Hilfe, ich werde die Änderungen sofort einmal einbauen.

Edit:
Nun habe ich aber eine andere Frage:.
Wenn ich diesen Abschnitt:

Code:

      value = current_node.value + node.cost + distance
      #the value is determined by both, the speed factor and the distance
      if node.opened
        #if the node is already opened
        if value >= node.value
          #do nothing if there is already a better value for this node
          next
        else
          #if the new value is better then the previous save the new value and the predecessor
          node.predecessor = current_node
          node.value = value
        end
      else
        open_nodes.push(node)
        #save the predecessor for this node, the value and that its opened
        node.predecessor = current_node
        node.value = value
        node.opened = true
      end

zu folgendem abändere:

Code:

      value = current_node.value + node.cost + distance
      costs = current_node.cost + node.speed_factor
      #the value is determined by both, the speed factor and the distance
      open_nodes.push(node) if !node.opened
      #save the predecessor for this node, the value and that its opened
      node.predecessor = current_node
      node.value = value
      node.costs = costs
      node.opened = true

Wo genau werden dann die "costs" überhaupt noch verwendet? Wenn der nächst beste Knoten immernoch über das value ausgewählt wird?

[-KD-]

Die values berechnen sich aus den costs, nicht aus den values.

Code:

costs = current_node.cost + node.speed_factor
value = costs + distance * MINIMAL_SPEED_FACTOR

Wichtig auch: Ob der Knoten bereits besucht wurde, musst du schon testen. Sonst guckst du dir hinterher einen benachbarten Knoten an und fügst den Knoten doppelt in die open_list ein. Was nicht passieren kann ist, dass ein Knoten sowohl offen als auch teurer ist als der aktuelle Knoten. (Im Prinzip kannst du das also auch so abändern, dass du das Attribut OPEN ganz weglässt und durch cost == 0 ersetzt).

Code:

# Annahme: Kosten von noch nicht besuchten Knoten sind immer 0!!!
if node.costs == 0
  node.cost = current_node.cost + node.speed_factor
  node.value = node.cost + distance * MINIMAL_SPEED_FACTOR
  node.predecessor = current_node
  open_nodes.push(node)
end

[Cornix]

Also wäre die "expand_node" Methode nun in dieser Form angebrachter?

Code:

def expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
    #iterate through every adjacent node of the current node and add it to the open_nodes array
    for node in current_node.adjacent_nodes
      #if the node is already closed it cannot be opened again
      next if node.closed || node.exact_value != 0
      distance_x = node.x - to_tile_x
      distance_y = node.y - to_tile_y
      distance = distance_x.abs + distance_y.abs
      exact_value = current_node.exact_value + node.cost
      approx_value = exact_value + distance * Node::MINIMAL_SPEED_FACTOR
      node.exact_value = exact_value
      node.approx_value = approx_value
      node.predecessor = current_node
      open_nodes.push(node)
    end
    open_nodes.delete(current_node)
    current_node.closed = true
  end

Ich habe die Attribute in "exact_value" und "approx_value" umbenannt für besseres Verständnis.
Ich denke man sollte mit Zeit und Aufwand bei etwas ernstgemeintem nicht geizen.

Das Script scheint soweit zu funktionieren, allerdings kam ich noch nicht dazu es in größerem Umfang zu testen.

[-KD-]

next if node.closed && node.exact_value != 0

...

Hier müsste ein ODER stehen. Oder du lässt die erste Bedingung gleich weg. Wenn die Kosten ungleich 0 sind, muss der Knoten schonmal betrachtet (oder gar betreten) worden sein.

[Cornix]

Ich muss leider nocheinmal nachhaken.
Ich habe nun ein paar Änderungen an meinem Script vorgenommen, muss jetzt allerdings feststellen, dass das Pathfinding nichtmehr richtig funktioniert.
Der Weg wird zwar gefunden, doch mit absoluter Sicherheit nicht der kürzeste Weg.
Das Problem liegt darin, dass die Einheiten nun zufällige Zickzackrouten zu laufen scheinen. Manchmal gehen sie sogar einen Schritt zurück um danach wieder forwärts zu gehen.

Noch ein Hinweis, dieses Verhalten taucht nur bei längeren Strecken auf, bei kurzen Pfaden von 3 oder 4 Nodes ist kein Problem erkennbar, sobald allerdings viele Kurven genommen werden müssen und der Weg länger wird dann nimmt auch die Genauigkeit des Pathfindings ab.

Vielleicht habe ich mich einmal wieder irgendwo vertan?
(An den nodes wurde keinerlei relevante Veränderung vorgenommen)
Hier das neue Script:

Code:

module Pathfinding
  module_function
  
  def node_list= (node_list)
    @node_list = node_list
  end
  
  def find_path(start_node, to_tile_x, to_tile_y)
    #array of all nodes which have not been expanded yet
    open_nodes = [start_node]
    
    current_node = start_node
    loop do
      #end if no nodes can be expanded anymore == no path found
      if open_nodes.size == 0
        self.cleanup
        return nil
      end
      if current_node.x == to_tile_x && current_node.y == to_tile_y
        final_node = current_node
        #break if the final node has been reached
        break
      else
        #expand the current node
        self.expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
        #the next node to be expanded is the node with the best value
        current_node = open_nodes[0]
        for node in open_nodes
          if current_node.approx_value > node.approx_value
            current_node = node
          end
        end
        #current_node = open_nodes.max{|ary,node| node.approx_value}
      end
    end
    #get the move route, an array containing the nodes to move along in order
    move_route = self.generate_move_route(start_node,final_node)
    #reset all data for the next task
    self.cleanup
    return move_route
  end
  
  def expand_node(current_node,open_nodes,to_tile_x,to_tile_y)
    #iterate through every adjacent node of the current node and add it to the open_nodes array
    for node in current_node.adjacent_nodes
      #if the node is already closed it cannot be opened again
      #if the node has an exact value it has been expanded already
      next if node.closed || node.exact_value != 0
      #calculate the approximated distance to the end node
      distance_x = node.x - to_tile_x
      distance_y = node.y - to_tile_y
      approx_distance = distance_x.abs + distance_y.abs
      
      #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
      
      node.exact_value = exact_value
      node.approx_value = approx_value
      node.predecessor = current_node
      open_nodes.push(node)
    end
    #after a node has been expanded it is closed
    open_nodes.delete(current_node)
    current_node.closed = true
  end
  
  def cleanup
    #iterate through every node and reset its data
    for node in @node_list
      node.closed = false
      node.exact_value = 0
      node.approx_value = 999999
      node.predecessor = nil
    end
  end
  
  def generate_move_route(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
  
end

Ich bitte nochmals um Hilfe.

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