Archiv verlassen und diese Seite im Standarddesign anzeigen : Brauche Hilfe: Pathfinding
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:
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
endIch bedanke mich vielmals für jede Hilfe.
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:
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
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:
class Node
attr_accessor :x,:y,:speed_factor,:[...]
end
node = Node.new(...)
nur ein Array zu verwenden wie du es tust?
node = [x,y,speed_factor,...]
Ist das Sortieren durch: Array.sort! besser als meine Methode über:
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.
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 MethodeJa. Prinzipiell kannst du statt deiner Methode auch kurz folgendes schreiben:
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 verwendenWenn 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.
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?
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:
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
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? - KDDieser 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:
costs = current_node.value + node.speed_factoranstatt von:
costs = current_node.costs + node.speed_factor?
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:
node.value = node.cost + distance * MINIMAL_SPEED_FACTORWobei 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.
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:
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:
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?
Die values berechnen sich aus den costs, nicht aus den values.
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).
# 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
Also wäre die "expand_node" Methode nun in dieser Form angebrachter?
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
endIch 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.
next if node.closed && node.exact_value != 0Hier 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.
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:
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.
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.
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.
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)
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:
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
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.
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?
Hier bitte der derzeitige Stand des Scriptes:
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:
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.
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.
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:
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
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
endOder 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:
O - - -
- - - -
- - - -
- - - X
So erstellt das Pathfinding zunächst folgende Bewegungsroute:
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.
Verwende mal eine euklidische Distanz:
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 empfehle zu dem Thema unbedingt A* Pathfinding for Beginners (http://www.policyalmanac.org/games/aStarTutorial.htm) und die dort verlinkten Seiten. Für dein Problem mit der Diagonalbewegung könnte insbesondere Marco Pinter - Toward More Realistic Pathfinding (http://www.gamasutra.com/view/feature/3096/toward_more_realistic_pathfinding.php) interessant sein.
Verwende mal eine euklidische Distanz:
approx_distance = Math.hypot(node.x - to_tile_x, node.y - to_tile_y)
approx_value = exact_value + approx_distance * Node::MINIMAL_SPEED_FACTORJetzt 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)
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.
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.
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.
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:
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).
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. (http://www.file-upload.net/download-3508853/PATHFINDING-TEST.rar.html)
(1.58 mb)
Hier der Download ohne DLL-Dateien. (http://www.file-upload.net/download-3508860/PATHFINDING-TEST-NoDLL-.rar.html)
(104 kb)
Vielen Dank.
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)
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.
Powered by vBulletin® Version 4.2.3 Copyright ©2025 Adduco Digital e.K. und vBulletin Solutions, Inc. Alle Rechte vorbehalten.