I was messing around with pathfinding and I came up with a script that works, but not as expected. It uses the A* algorithm and binary heaps, but for some reason it's really slow on complex paths unless I consider the score of each node as only the heuristic (not considering the cost), and it still works perfectly, and so much faster. Could someone try it out and tell me why this is happening?
To use it, call a script:
PathFinder.new(character, x_target, y_target)
The character must be an actual Game_Character class.
It's still very incomplete because I can't figure out what is going on. Here is the script that considers the score of each node as the movement cost + the heuristic:
class Game_Character
attr_accessor :move_route
attr_accessor :move_route_index
def pos_with_dir(x, y, d)
new_x = x + (d == 6 ? 1 : d == 4 ? -1 : 0)
new_y = y + (d == 2 ? 1 : d == 8 ? -1 : 0)
return [new_x, new_y]
end
end
class Node
attr_reader :x
attr_reader :y
attr_reader :heuristic
attr_accessor :parent
attr_accessor :cost
attr_accessor :open
def initialize(x, y, cost, heuristic, parent = nil)
@open = true
@x, @y, @cost, @heuristic, @visited, @parent = x, y, cost, heuristic, false, parent
end
def score
return @heuristic + @cost
end
def visit
@visited = true
end
def visited?
return @visited
end
def pos
return [@x, @y]
end
end
class PathFinder
attr_accessor :open
attr_accessor :closed
def initialize(char, tx, ty)
@char = char
heuristic = (tx - char.x).abs + (ty - char.y).abs
first_node = Node.new(char.x, char.y, 0, heuristic)
@open = [nil, first_node]
@open_tiles = {[char.x, char.y] => first_node}
@target = Node.new(tx, ty, 0, 0)
@closed = {}
@last_node = nil
find_path
end
def find_path
count = 0
while @open.size > 1
#print @open[1].inspect
close(1)
count += 1
if @closed.keys.include?(@target.pos)
@last_node = @closed[@target.pos]
break
end
if count % 200 == 0
Graphics.update
end
end
#print count
backtrack if @last_node != nil
end
def backtrack
list = []
current_node = @last_node
while current_node.parent
difx = current_node.x - current_node.parent.x
dify = current_node.y - current_node.parent.y
move_code = difx == -1 ? 2 : difx == 1 ? 3 : 0
move_code = dify == -1 ? 4 : dify == 1 ? 1 : move_code
command = RPG::MoveCommand.new
command.code = move_code
list.unshift(command)
current_node = current_node.parent
end
route = RPG::MoveRoute.new
route.list = list
route.repeat = false
@char.force_move_route(route)
end
def close(index)
node = @open[index]
node.open = false
remove_heap(index)
@open_tiles.delete([node.x, node.y])
@closed[[node.x, node.y]] = node
expand(node)
end
def expand(node)
return if node.visited?
nodes = []
[2, 4, 6, 8].each do |dir|
new_pos = @char.pos_with_dir(node.x, node.y, dir)
if @char.passable?(new_pos[0], new_pos[1], 0) && !@closed.keys.include?(new_pos)
heuristic = (@target.x - new_pos[0]).abs + (@target.y - new_pos[1]).abs
if @open_tiles.keys.include?(new_pos)
if @open_tiles[new_pos].cost > node.cost + 1
@open_tiles[new_pos].parent = node
@open_tiles[new_pos].cost = node.cost + 1
update_heap(@open_tiles[new_pos])
end
else
nde = Node.new(new_pos[0], new_pos[1], node.cost + 1, heuristic, node)
if nodes[0] != nil && nde.score < nodes[0].score
temp = nodes[0]
nodes[0] = nde
nodes.push(temp)
else
nodes.push(nde)
end
end
end
end
nodes.reverse.each do |nde|
add_heap(nde)
#$scene.spriteset.insert_sprite(nde)
end
node.visit
end
def update_heap(item)
position = @open.rindex(item)
while position != 1 && @open[position].score <= @open[position/2].score
temp = @open[position/2]
@open[position/2] = @open[position]
@open[position] = temp
position /= 2
end
end
def add_heap(item)
position = @open.size
@open[position] = item
@open_tiles[item.pos] = item
while position != 1 && @open[position].score <= @open[position/2].score
temp = @open[position/2]
@open[position/2] = @open[position]
@open[position] = temp
position /= 2
end
end
def remove_heap(item)
last = @open[@open.size-1]
@open_tiles.delete(@open[item].pos)
@open[item] = last
@open.delete_at(@open.size-1)
position = item
while position != @open.size-1 && ((@open[position*2] &&
@open[position].score > @open[position*2].score) ||
(@open[position*2+1] && @open[position].score >
@open[position*2+1].score))
if !@open[position*2+1]
score2 = @open[position*2].score + 1
else
score2 = @open[position*2+1].score
end
if @open[position*2].score < score2
temp = @open[position*2]
@open[position*2] = @open[position]
@open[position] = temp
position *= 2
else
temp = @open[position*2+1]
@open[position*2+1] = @open[position]
@open[position] = temp
position = position * 2 + 1
end
end
end
end
To remove the movement cost from the score of each node, remove the "+ @cost" at line 24.
I know there are a lot of good pathfinders out there, but I just want to make my own for experience purposes.