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