Pathfinding
Version: 1.0
Author: cozziekuns
Date: New Years Eve, 2011
Version History
- <Version 1.0> 2011.12.31 - Original Release
Planned Future Versions
- <Version 1.1> Allow for dynamic recalculation if one wants to repeat the path-finding process for any reason.
Description
This script allows you to move any character to another tile using the shortest path possible. It takes a significantly longer time on large maps.
Features
- Incredibly fast and accurate pathfinding
- Easy script calls
- Almost no configuration
Screenshots
Not really applicable for this type of thing.
Instructions
To use, create a move route event and as a script command use:
find_path(target_x, target_y)
Additionally, one can force a path through a script using the following call:
force_path(target_x, target_y)
There is a known bug that is present in Modern Algebra's script regarding the recalculation of a path once found. Since some of this script is simply a convert from his VX version (only the algorithm is different by being slightly slower and sloppier :P), the bug is also found in this script.
Script
#===============================================================================
# [VXA] Pathfinding
#-------------------------------------------------------------------------------
# Version: 1.0
# Author: cozziekuns (rmrk)
# Last Date Updated: 12/31/2011 (MM/DD/YYYY)
#===============================================================================
# Description:
#-------------------------------------------------------------------------------
# This script allows you to move any character to another tile using the
# shortest path possible. It takes a significantly longer time on large maps.
#===============================================================================
# Updates
# ------------------------------------------------------------------------------
# o 12/31/2011 - Started Script
#===============================================================================
# To-do List
#-------------------------------------------------------------------------------
# o Allow for dynamic recalculation if one wants to repeat the pathfinding
# process for any reason.
#===============================================================================
# Instructions
#-------------------------------------------------------------------------------
# To use, create a move route event and as a script command use:
#
# find_path(target_x, target_y)
#
# Additionally, one can force a path through a script using the following call:
#
# force_path(target_x, target_y)
#
# There is a known bug that is present in Modern Algebra's script regarding the
# recalculation of a path once found. Since some of this script is simply
# a convert from his VX version (only the algorithm is different by being
# slightly slower and sloppier :P), the bug is also found in this script.
#===============================================================================
#==============================================================================
# ** Game_Map
#==============================================================================
class Game_Map
def find_path(target_x, target_y, sx, sy, passable, char)
path = []
max_elements = width * height + 2
checked_items = 0
@open_list_items = 0
@open_list = Table.new(max_elements)
@nodes = Table.new(max_elements, 2)
open = Table.new(width, height)
closed = Table.new(width, height)
parent = Table.new(width, height, 3)
@f_cost = Table.new(width, height)
@open_list[0] = 0
@nodes[0, 0] = sx
@nodes[0, 1] = sy
next_point = [sx, sy]
closed[sx, sy] = 1
loop do
next_point = delete_from_heap if not next_point == [sx, sy]
return path if next_point.nil?
open[next_point[0], next_point[1]] = 0
closed[next_point[0], next_point[1]] = 2 if not next_point == [sx, sy]
parent_x, parent_y = next_point[0], next_point[1]
for i in 1..4
x, y = case i * 2
when 2; [parent_x, parent_y + 1]
when 4; [parent_x - 1, parent_y]
when 6; [parent_x + 1, parent_y]
when 8; [parent_x, parent_y - 1]
end
next if closed[x, y] == 2
next unless char.passable?(parent_x, parent_y, i * 2)
if not open[x, y] == 1
open[x, y] = 1
parent[x, y, 0] = parent_x
parent[x, y, 1] = parent_y
parent[x, y, 2] = parent[parent_x, parent_y, 2] + 10
g = parent[x, y, 2] + 10
h = ((target_x - x).abs + (target_y - y).abs) * 10
@f_cost[x, y] = g
checked_items += 1
@open_list_items += 1
@nodes[checked_items, 0] = x
@nodes[checked_items, 1] = y
add_to_heap(checked_items)
else
old_g = parent[x, y, 2] + 10
new_g = parent[parent_x, parent_y, 2] + 20
next if old_g < new_g
parent[x, y, 0] = parent_x
parent[x, y, 1] = parent_y
parent[x, y, 2] = new_g
g = parent[x, y, 2] + 10
h = ((target_x - x).abs + (target_y - y).abs) * 10
@f_cost[x, y] = g
end
end
next_point = nil
break if closed[target_x, target_y] == 2
end
path_x, path_y = target_x, target_y
loop do
parent_x = parent[path_x, path_y, 0]
parent_y = parent[path_x, path_y, 1]
if path_x < parent_x
code = 2
elsif path_x > parent_x
code = 3
else
code = path_y < parent_y ? 4 : 1
end
path.push(RPG::MoveCommand.new(code))
path_x, path_y = parent_x, parent_y
break if path_x == sx and path_y == sy
end
return path
end
def add_to_heap(value)
m = @open_list_items
@open_list[m] = value
while m != 1
if fcost(@open_list[m]) < fcost(@open_list[m / 2])
temp = @open_list[m / 2]
@open_list[m / 2] = @open_list[m]
@open_list[m] = temp
m /= 2
else
break
end
end
end
def delete_from_heap
next_point = @open_list[0]
@open_list[0] = @open_list[@open_list_items]
@open_list_items -= 1
v = 1
loop do
u = v
w = 2 * u
if w + 1 <= @open_list_items
v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
v = w + 1 if fcost(@open_list[v - 1]) >= fcost(@open_list[w])
elsif w <= @open_list_items
v = w if fcost(@open_list[u - 1]) >= fcost(@open_list[w - 1])
end
if u != v
temp = @open_list[u - 1]
@open_list[u - 1] = @open_list[v - 1]
@open_list[v - 1] = temp
else
break
end
end
return @nodes[next_point, 0], @nodes[next_point, 1]
end
def fcost(point)
x = @nodes[point, 0]
y = @nodes[point, 1]
return @f_cost[x, y]
end
end
#==============================================================================
# ** Game_CharacterBase
#==============================================================================
class Game_CharacterBase
def find_path(target_x, target_y)
path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
@move_route.list.delete_at(@move_route_index)
path.each { |i| @move_route.list.insert(@move_route_index, i) }
@move_route_index -= 1
end
def force_path(target_x, target_y)
path = $game_map.find_path(target_x, target_y, @x, @y, false, self)
path.reverse!
path.push (RPG::MoveCommand.new(0))
move_route = RPG::MoveRoute.new
move_route.list = path
move_route.repeat = false
force_move_route(move_route)
end
def count_iterations(target_x, target_y)
path = $game_map.find_path(target_x, target_y, @x, @y, true, self)
return path.size
end
end
Credit
- cozziekuns
- Modern Algebra, for his VX version of the script
Thanks
- Patrick Lester, and his well known A* Tutorials (http://www.policyalmanac.org/games/aStarTutorial.htm) which were immensely helpful.
Author's Notes
Happy New Years Eve! I'm in America right now so I don't get an early New Years :mad: