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.