Guten Tag.schnellsten (nicht kürzesten) Weg durch ein Gebiet sucht.nicht immer den richtigen Weg findet falls die Performance dadurch sehr viel verbessert werden könnte.
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.
Zitieren