Path Finding
Version: 2.0
Author: modern algebra
Date: April 16, 2008
Version History
- Version 2.0 - Released April 16, 2008. It now creates significantly less lag, and there is also an option to set a maximum amount of iterations to reduce lag at the cost of occasional failure to find a path. You are also able to force a path through call script as well as through a move event, for use in other scripts
- Version 1.0 - Released April 11, 2008
Planned Future Versions
- Version 3.0 - Will look into developing an algorithm that works faster and more efficiently. Allow for recalculation en route if original path is interfered with. Will not force a route in move path and allow for recalculating path instead.
Description
This script finds the shortest path from an event's current position to a target position specified by the user. It then sets that path into action. Be careful when using it though. Depending on the layout of the map, it can take a fair amount of time to calculate. So, don't use it for any huge, funky mazes or anything.
Features
- No more looking at the map and setting a move route command by command. It only takes one command now to go from any square on the map to any other
- Very easy to set a new path
- Always finds the shortest path
- Very little lag for most paths
- Can set a maximum amount of iterations to reduce lag further at the cost of occasional failure
- Will work if you allow diagonal movement as well
Screenshots
N/A for this type of script, really.
Instructions
To use this, merely use the script command inside a Set Move Route event and use this code:
find_path (target x, target y, diagonal, max_iterations)
Where target x and target y are the coordinates of the target. diagonal is an optional boolean value (true or false) denoting whether or not you want the event to be able to move diagonally or not. The value for diagonal defaults to false if it is not set by the user. max_iterations is also optional, and you can set this if you want the algorithm to quit if it is taking too long. The number you set here refers to how many nodes you let it search through before cancelling the process. If this is set to 0 or less, it will take as many iterations as necessary to find the shortest path
A sample Event:
@>Set Move Route: This Event
: : $> Script: find_path (12, 33)
It's that simple. You can also put other move commands around it, use it on any characters that you could move via a normal move route, and set all the same conditions on the move route, such as Wait, Skippable, and Repeat. Like so:
@>Set Move Route: Player (Wait)
: : $> Move Down
: : $> Script: find_path (12, 33, true)
: : $> Move Left
Repeat works by repeating the path, not recalculating it. This means that if the path that was calculated was Down, Down, Left, the character will repeat that pattern, not necessarily going back to the square every time.
You can also set a default value for diagonal and max_iterations by call script with the codes:
$game_system.pathfinding_diagonal = true/false # Allow diagonal movement
$game_system.pathfinding_iterations = integer # When <= 0, no limit
Then, when you do not specifically set diagonal or limit, it will default to the values you set in there
For scripters, you can force-move a character down a path via:
character.force_path (x, y, diagonal, max_iterations)
character is any Game_Character object, such as $game_player or an event.
Script
#==============================================================================
# Path Finding
# Version: 2.0
# Author: modern algebra (rmrk.net)
# Date: April 10, 2008
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Thanks:
# Patrick Lester! For his tutorial on A* Pathfinding algorithm (found at:
# http://www.gamedev.net/reference/articles/article2003.asp) as well as
# another amazingly helpful tutorial on using binary heaps (found at:
# http://www.policyalmanac.org/games/binaryHeaps.htm). Without his excellent
# tutorials, this script would not exist. So major thanks to him.
# Zeriab, for tricking me into believing that this was an actual exercise.
# Also, his table printout actually makes Tables useable :P
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Instructions:
# To use, merely use this code in a script call INSIDE a Move Event:
#
# find_path (target_x, target_y, diagonal, max_iterations)
#
# where target_x and target_y are the target coordinates and diagonal is an
# optional boolean value (true or false) stating whether or not to allow
# diagonal movement. max_iterations is also optional, and you can set this if
# you want the algorithm to quit if it is taking too long. The number you set
# here refers to how many nodes you let it search through before cancelling
# the process. If this is set to 0, it will take as many iterations as
# necessary to find the shortest path.
#
# You can also set a default value for diagonal and max_iterations
# by call script with the codes:
#
# $game_system.pathfinding_diagonal = true/false # Allow diagonal movement
# $game_system.pathfinding_iterations = integer # When <= 0, no limit
#
# For scripters, you can force-move a character down a path via:
#
# character.force_path (x, y, diagonal, max_iterations)
#
# character is any Game_Character object, such as $game_player or an event.
#
# Then, when you do not specifically set diagonal or limit, it will default
# to the values you set in there
#==============================================================================
#==============================================================================
# ** Game_System
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Summary of Changes:
# new instance variables - pathfinding_diagonal, pathfinding_iterations
# aliased method - initialize
#==============================================================================
class Game_System
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Public Instance Variables
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
attr_accessor :pathfinding_diagonal
attr_accessor :pathfinding_iterations
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Object Initialization
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
alias modalg_pathfinding_options_init_j5yt initialize
def initialize
modalg_pathfinding_options_init_j5yt
@pathfinding_diagonal = false
@pathfinding_iterations = 0
end
end
#==============================================================================
# ** Game_Character
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Summary of Changes:
# new methods - find_path
#==============================================================================
class Game_Character
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Find Path
# trgt_x, trgt_y : the target coordinates
# diagonal : Is diagonal movement allowed?
# max_iterations : maximum number of iterations
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
def find_path (trgt_x, trgt_y, diagonal = $game_system.pathfinding_diagonal,
max_iterations = $game_system.pathfinding_iterations)
path = $game_map.find_path (self.x, self.y, trgt_x, trgt_y, diagonal,
max_iterations, self)
# Add the path to the move route being executed.
@move_route.list.delete_at (@move_route_index)
path.each { |i| @move_route.list.insert (@move_route_index, i) }
@move_route_index -= 1
end
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Force Path
# trgt_x, trgt_y : target coordinates
# diagonal : Is diagonal movement allowed?
# max_iterations : maximum number of iterations
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
def force_path (trgt_x, trgt_y, diagonal = $game_system.pathfinding_diagonal,
max_iterations = $game_system.pathfinding_iterations)
path = $game_map.find_path (self.x, self.y, trgt_x, trgt_y, diagonal,
max_iterations, self)
# The path retrieved is actually backwards, so it must be reversed
path.reverse!
# Add an end ccommand
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
end
#==============================================================================
# ** Game_Map
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# Summary of Changes:
# new method - removefrom_binaryheap, find_path
#==============================================================================
class Game_Map
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Remove from Heap
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
def removefrom_binaryheap
@open_nodes[1] = @open_nodes[@listsize]
@listsize -= 1
v = 1
loop do
u = v
w = 2*u
# Check if it's cost is greater than that of it's children
if w + 1 <= @listsize # If both children exist
v = w if @total_cost[@open_nodes[u]] >= @total_cost[@open_nodes[w]]
v = w + 1 if @total_cost[@open_nodes[v]] >= @total_cost[@open_nodes[w + 1]]
elsif w <= @listsize # If only one child exists
v = w if @total_cost[@open_nodes[u]] >= @total_cost[@open_nodes[w]]
end
# Break if parent has less cost than it's children
if u == v
break
else
temp = @open_nodes[u]
@open_nodes[u] = @open_nodes[v]
@open_nodes[v] = temp
end
end
end
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# * Find Path
# src_x, src_y : the source coordinates
# trgt_x, trgt_y : the target coordinates
# diagonal : Is diagonal movement allowed?
# max_iterations : maximum number of iterations
# char : character to follow the path
#--------------------------------------------------------------------------
# Uses the A* method of pathfinding to find a path
#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
def find_path (src_x, src_y, trgt_x, trgt_y, diagonal, max_iterations, char)
# No possible path if the target itself is impassable
path = []
# Finished if Target Location is closed
return path if !char.passable? (trgt_x, trgt_y)
# Initialize
max_elements = width*height + 2
openx = Table.new (max_elements)
openy = Table.new (max_elements)
@open_nodes = Table.new (max_elements)
@total_cost = Table.new (max_elements)
heuristic = Table.new (max_elements)
step_cost = Table.new (width, height)
parent_x = Table.new (width, height)
parent_y = Table.new (width, height)
actual_list = Table.new (width, height)
# Add the source node to the open list
new_openid = 1
@open_nodes[1] = 1
openx[1] = src_x
openy[1] = src_y
dist = [(trgt_x - src_x).abs, (trgt_y - src_y).abs]
heuristic[1] = diagonal ? (dist.max*14) + (dist.min*10) : (dist[0] + dist[1])*10
@total_cost[1] = heuristic[1]
actual_list[src_x, src_y] = 1
@listsize = 1
count = 0
loop do
break if actual_list[trgt_x, trgt_y] != 0
count += 1
# Update Graphics every 500 iterations
Graphics.update if count % 500 == 0
return path if count == max_iterations
return path if @listsize == 0
node = @open_nodes[1]
# Set the x and y value as parent to all possible children
parent_xval, parent_yval = openx[node], openy[node]
actual_list[parent_xval, parent_yval] = 2
removefrom_binaryheap
# Check all adjacent squares
for i in 0...8
break if i > 3 && !diagonal
# Get the node
x, y = case i
when 0 then [parent_xval, parent_yval - 1] # UP
when 1 then [parent_xval, parent_yval + 1] # DOWN
when 2 then [parent_xval - 1, parent_yval] # LEFT
when 3 then [parent_xval + 1, parent_yval] # RIGHT
when 4 then [parent_xval - 1, parent_yval - 1] # UP LEFT
when 5 then [parent_xval + 1, parent_yval - 1] # UP RIGHT
when 6 then [parent_xval - 1, parent_yval + 1] # DOWN LEFT
when 7 then [parent_xval + 1, parent_yval + 1] # DOWN RIGHT
end
# Next if this node is already in the closed list
next if actual_list[x,y] == 2
# Next if this tile in impassable
next unless char.passable? (x, y) # Is the tile passable?
# Take into account diagonal passability concerns
if i > 3
next unless case i
when 4 then char.passable? (x + 1, y) || char.passable? (x, y + 1)
when 5 then char.passable? (x - 1, y) || char.passable? (x, y + 1)
when 6 then char.passable? (x + 1, y) || char.passable? (x, y - 1)
when 7 then char.passable? (x - 1, y) || char.passable? (x, y - 1)
end
end
# Check if this node already open
plus_step_cost = ((x - parent_xval).abs + (y - parent_yval).abs) > 1 ? 14 : 10
temp_step_cost = step_cost[parent_xval, parent_yval] + plus_step_cost
if actual_list[x,y] == 1
# If this is a better path to that node
if temp_step_cost < step_cost[x, y]
# Change Parent, step, and total cost
parent_x[x, y] = parent_xval
parent_y[x, y] = parent_yval
step_cost[x, y] = temp_step_cost
# Find index of this position
index = 1
while index < @listsize
index += 1
break if openx[@open_nodes[index]] == x &&
openy[@open_nodes[index]] == y
end
@total_cost[@open_nodes[index]] = temp_step_cost + heuristic[@open_nodes[index]]
else
next
end
else # If not on open nodes
# Add to open nodes
new_openid += 1 # New Id for new item
@listsize += 1 # Increase List Size
@open_nodes[@listsize] = new_openid
step_cost[x, y] = temp_step_cost
# Calculate Heuristic
d = [(trgt_x - x).abs, (trgt_y - y).abs]
heuristic[new_openid] = diagonal ? (d.max*14) + (d.min*10) : (d[0] + d[1])*10
@total_cost[new_openid] = temp_step_cost + heuristic[new_openid]
parent_x[x, y] = parent_xval
parent_y[x, y] = parent_yval
openx[new_openid] = x
openy[new_openid] = y
index = @listsize
actual_list[x, y] = 1
end
# Sort Binary Heap
while index != 1
temp_node = @open_nodes[index]
if @total_cost[temp_node] <= @total_cost[@open_nodes[index / 2]]
@open_nodes[index] = @open_nodes[index / 2]
index /= 2
@open_nodes[index] = temp_node
else
break
end
end
end
end
# Get actual target node
path_x, path_y = trgt_x, trgt_y
# Make an array of MoveRoute Commands
while path_x != src_x || path_y != src_y
# Get Parent x, Parent Y
prnt_x, prnt_y = parent_x[path_x, path_y], parent_y[path_x, path_y]
# DOWN = 1, LEFT = 2, RIGHT = 3, UP = 4, DL = 5, DR = 6, UL = 7, UR = 8
if path_x < prnt_x # LEFT
# Determine if upper, lower or direct left
code = path_y < prnt_y ? 7 : path_y > prnt_y ? 5 : 2
elsif path_x > prnt_x # RIGHT
# Determine if upper, lower or direct right
code = path_y < prnt_y ? 8 : path_y > prnt_y ? 6 : 3
else # UP or DOWN
code = path_y < prnt_y ? 4 : 1
end
path.push (RPG::MoveCommand.new (code))
path_x, path_y = prnt_x, prnt_y
end
return path
end
end
Credit
Thanks
Support
Please just post here if you encounter any problems.
This script by
modern algebra is licensed under a
Creative Commons Attribution-Non-Commercial-Share Alike 2.5 Canada License.
Discord
Light Style