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.