Brauche Hilfe: Pathfinding

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