A* Pathfinding Script
Version: 1.1
Introduction
Yeah, I know there are already tons of similar scripts out there, but I think this one is more efficient than some of the other scripts I tried and also has better documentation. In case you don't know, A* is an algorithm to find the optimal path from a node to another. In case of RPG Maker XP, it can find the path a character (event or player) should take from their current position to an other tile on the map. The character can then follow that path as if it was specified as a move route. This is useful in strategy games where the player clicks on or selects a position and the unit automatically moves there, avoiding any obstacles along the way. As I said, this script is fairly efficient. For comparison, here's the time it takes my script to find a path through a simple map of a given size (in tiles):
50x50: 0.03 seconds
100x100: 0.25 seconds
500x500: 5.5 seconds
I tried the same maps with another script and got the following results:
50x50: 0.141 seconds
100x100: 1.5 seconds
500x500: script hanging
(Though it should be noted that the script here produces even better results at the moment)
The code is also well-documented. This is the first time I implement A*, and I had to go through several tutorials and other implementations to do it, so I know how it feels when you want to learn something but the code you're learning from lacks good documentation.
There's not much to show really. Just a character groing from point A to point B. Instead, download the demo and see for yourself.
Demo
Script Demo
To experiment with the demo, trying changing the map size and complexity, also move event 2 (called Goal) to a different location to cause the player to follow it.
You can also try the older Demo which lacks some features but is generally simpler and less likely to cause any compatibility problems.
Script
Instructions
First you have to add this script somewhere under the default scripts (and above main), I assume you know how to add a new script section and paste this script there. I don't know much about the SDK thing, but I don't think you'll get any trouble when using this scripts with others. Note that this script overwrites the move_type_custom of Game_Character, any other script that does that might clash with this one.
Now, simply create a new instance of the A_Star_Pathfinder class and supply it with the required parameters. For example, you could create it in an event page by adding a script command and typing something like:
The constructor can take more information, such as the character that will move according to the result of pathfinding (player by default), whether the character should follow the path right away (true by default, if you set it to false, you'll have to call generate_path yourself), as well as the option to supply a limit to the number of pathfinding iterations (good if you suffer from lag on large maps). Here's another example of usage:
As an alternative, you can provide nothing to the constructor, and call the setup, calculate_path, and generate_path manually. This gives you more control because the setup method allows you to change specify more variables such as methods to call when the path is reached or couldn't be found (implemented as Proc objects). You can also specify the number of frames to wait before trying to generate a new path in the case that the character's path is blocked. Here's an example of such usage:
The last argument to the setup method is a boolean variable that, if set to true, will allow storing passability information in a table that is computed only when needed. You'd have to call make_pass_map yourself after setup, and the pathfinder will use the table to lookup passability. This optimization is helpful for maps with lots of events as it cuts down the time needed to loop through events to check their passability, but the method to generate the passability map is currently slow and since it is called on collision with other events it could slow down pathfinding instead of improving it. Personally I think it's too much for most applications, but it could be useful in certain situations.
For more information, check the script comments~
FAQ
Waiting for some~
Version Info
Version 1.1:
- Added a mechanism to prevent the generated path from being blocked by other characters. When such a collision happens, the character will try to generate a new path to goal. This can be turned off if you set collision_wait to -1
- Now you can provide blocks to be called when the path is reached or if no path is found.
- Added the cache pass flag to allow generating passability information in a Table for faster access. This was inspiredby a post by Anaryu at http://www.rmxp.org/forums/showthread.php?t=16589
- Better documentation
Version 1.0:
- Initial release version.
Compatibility
I don't know about the SDK, but I don't think you'll get any trouble when using this scripts with others. Note that this script overwrites the move_type_custom of Game_Character, any other script that does that might clash with this one.
Credits and Thanks
The sites mentioned in the script were a big help. Wikipedia too.
Mr. Mo and Zeriab for suggesting some improvements.
Anaryu for the passability table idea (in another thread).
Eivien for providing another implementation of A* that I can steal learn from!
Author's Notes
Well, I haven't tested some of the new features enough so there are bound to be a few bugs to be fixed. I also want to make it faster, if possible. Maybe get a few tips from Zeriab's anti-lag script and Eivien's path finding script.
Terms and Conditions
None really. Check the big comment at the top of the script for more specific information, but there aren't really any terms aside from not trying to pass the script as your own.
Version: 1.1
Introduction
Yeah, I know there are already tons of similar scripts out there, but I think this one is more efficient than some of the other scripts I tried and also has better documentation. In case you don't know, A* is an algorithm to find the optimal path from a node to another. In case of RPG Maker XP, it can find the path a character (event or player) should take from their current position to an other tile on the map. The character can then follow that path as if it was specified as a move route. This is useful in strategy games where the player clicks on or selects a position and the unit automatically moves there, avoiding any obstacles along the way. As I said, this script is fairly efficient. For comparison, here's the time it takes my script to find a path through a simple map of a given size (in tiles):
50x50: 0.03 seconds
100x100: 0.25 seconds
500x500: 5.5 seconds
I tried the same maps with another script and got the following results:
50x50: 0.141 seconds
100x100: 1.5 seconds
500x500: script hanging
(Though it should be noted that the script here produces even better results at the moment)
The code is also well-documented. This is the first time I implement A*, and I had to go through several tutorials and other implementations to do it, so I know how it feels when you want to learn something but the code you're learning from lacks good documentation.
There's not much to show really. Just a character groing from point A to point B. Instead, download the demo and see for yourself.
Demo
Script Demo
To experiment with the demo, trying changing the map size and complexity, also move event 2 (called Goal) to a different location to cause the player to follow it.
You can also try the older Demo which lacks some features but is generally simpler and less likely to cause any compatibility problems.
Script
Code:
#==============================================================================
# ** A* Pathfinding Script
#------------------------------------------------------------------------------
# Script by : RPG (aka Cowlol)
# Last Update : December 4th, 2007
# Version : 1.1
# Contact Information : ArePeeGee on AIM
#------------------------------------------------------------------------------
# A relatively effecient implementation of the A*. For more information
# on A* check the following links:
# 1. http://www.policyalmanac.org/games/aStarTutorial.htm
# 2. http://www-cs-students.stanford.edu/~amitp/gameprog.html
#------------------------------------------------------------------------------
# Usage:
#
#
# First you have to add this script somewhere under the default scripts
# (and above main), I assume you know how to add a new script section and
# paste this script there. I don't know much about the SDK thing, but I
# don't think you'll get any trouble when using this scripts with others.
# Note that this script overwrites the move_type_custom of Game_Character,
# any other script that does that might clash with this one.
#
# Now, simply create a new instance of the A_Star_Pathfinder class and
# supply it with the required parameters. For example, you could create it
# in an event page by adding a script command and typing something like:
#
# node = Node.new(x, y)
# path = A_Star_Pathfinder.new(node)
#
# The constructor can take more information, such as the character that
# will move according to the result of pathfinding (player by default),
# whether the character should follow the path right away (true by default,
# if you set it to false, you'll have to call generate_path yourself), as
# well as the option to supply a limit to the number of pathfinding
# iterations (good if you suffer from lag on large maps). Here's another
# example of usage:
#
# node = Node.new(x, y)
# char = $game_map.events[event_id]
# path = A_Star_Pathfinder.new(node, char, false)
# # do other stuff
# path.generate_path # and then generate the path
#
# As an alternative, you can provide nothing to the constructor,
# and call the setup, calculate_path, and generate_path manually.
# This gives you more control because the setup method allows you to
# change specify more variables such as methods to call when the path
# is reached or couldn't be found (implemented as Proc objects). You can
# also specify the number of frames to wait before trying to generate a
# new path in the case that the character's path is blocked. Here's an
# example of such usage:
#
# path = A_Star_Pathfinder.new
# goal = Node.new(1, 0)
# char = $game_player
# limit = 1000
# wait = 5
# # lambda creates Procs, an alternative is Proc.new { ... }
# reach = lambda { p "REACHD GOAL!!!" }
# fail = lambda { p "COULDN'T FIND PATH!!!" }
# pass = false
# path.setup(goal, char, limit, wait, reach, fail, pass)
# path.calculate_path
# path.generate_path
#
# The last argument to the setup method is a boolean variable that,
# if set to true, will allow storing passability information in
# a table that is computed only when needed. You'd have to call
# make_pass_map yourself after setup, and the pathfinder will use the
# table to lookup passability. This optimization is helpful for maps
# with lots of events as it cuts down the time needed to loop through
# events to check their passability, but the method to generate the
# passability map is currently slow and since it is called on collision
# with other events it could slow down pathfinding instead of improving it.
# Personally I think it's too much for most applications, but it could be
# useful in certain situations.
#
#------------------------------------------------------------------------------
# Version Info:
#
# - Version 1.1:
# - Added a mechanism to prevent the generated path from being
# blocked by other characters. When such a collision happens,
# the character will try to generate a new path to goal. This
# can be turned off if you set collision_wait to -1
# - Now you can provide blocks to be called when the path is
# reached or if no path is found.
# - Added the cache pass flag to allow generating passability
# information in a Table for faster access. This was inspired
# by a post by Anaryu at
# http://www.rmxp.org/forums/showthread.php?t=16589
# - Better documentation
# - Version 1.0:
# - Initial release version.
#------------------------------------------------------------------------------
# Known bugs:
#
# - Slower than Eivien's pathfinder at:
# http://www.rmxp.org/forums/showthread.php?t=24242
# this is not really a bug but I'm interested in learning more
# about effecient implementations of A*.
# - Found a bug or have some ideas for the next version? Tell me on AIM!
#------------------------------------------------------------------------------
# Terms of Use:
#
# The only thing I ask of you is not to try to pass this script as your
# own. Other than that, feel free to use this script in any way you like,
# be it commercial, free, modification, redistribution, or whatever
# you could think of. That includes translation and putting the script
# on a website or forum. This script is provided as-is, no guarentees.
# I'm not obliged to help you with any problems you run ito while using
# it either, but you could always still try to ask me on AIM. Enjoy~
#==============================================================================
#==============================================================================
# ** Node
#------------------------------------------------------------------------------
# A node represents part of the path generated by the pathfinder,
# It corrosponds to a single tile
#==============================================================================
class Node
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :x # X coordinate of current node
attr_accessor :y # Y coordinate of current node
attr_accessor :parent # Parent node
attr_accessor :g # Cost of getting to this node
attr_accessor :h # Distance to goal (heuristic)
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
def initialize(x, y, parent = nil, g = 0, h = 0)
@x = x
@y = y
@parent = parent
@g = g
@h = h
end
#--------------------------------------------------------------------------
# * The Total 'Cost' at This Node (AKA f(n))
#--------------------------------------------------------------------------
def cost
# f(n) = g(n) + h(n)
return @g + @h
end
#--------------------------------------------------------------------------
# * Two Nodes Are Equal If They Are on the Same Tile
#--------------------------------------------------------------------------
def ==(other)
return false if other == nil or !other.is_a?(Node)
return true if other.x == x and other.y == y
return false
end
end
#==============================================================================
# ** A_Star_Pathfinder
#------------------------------------------------------------------------------
# This class generates a path using the A* algorithm. Not a very good
# implementation but I'm still proud of it.
#==============================================================================
class A_Star_Pathfinder
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_reader :goal_node # the goal!
attr_reader :character # character looking for a path
attr_reader :limit # pathfinding 'depth
attr_reader :found # was the path found?
attr_reader :route # the route returned after
# calling generate_path
attr_accessor :collision_wait # frames to wait in case of
# collision with other characters
attr_accessor :reach_method # Proc called when goal is reached
attr_accessor :fail_method # Proc called when no path is found
attr_accessor :cache_pass # if true, passability information
# is stored in a table
attr_accessor :pass_map # Table of passability info.
#--------------------------------------------------------------------------
# * Object Initialization
# goal_node : A Node representing the end point
# char : The character that'd use the result of pathfinding
# run : If true, the path is also generated
# limit : Maximum number of main loop iterations before the
# the pathfinder gives up. -1 for infinity!
#--------------------------------------------------------------------------
def initialize(goal_node = nil, char = $game_player, run = true, limit = -1)
# If no goal node is provided, this acts as a default constructor that
# takes no parameters and does nothing. Useful if you do things manually
if goal_node == nil
return
end
# Setup variables
setup(goal_node, char, limit)
# Find the optimal path
calculate_path
# We're done, time to generate the path
generate_path if run
end
#--------------------------------------------------------------------------
# * Setup Initial Values for Variables
# goal_node : A Node representing the end point
# character : The character that'd use the result of pathfinding
# limit : Maximum number of main loop iterations before the
# the pathfinder gives up. -1 for infinity!
# wait : No. of frames to wait in case of collision
# (-1 disables such collision behevior)
# reach : A Proc that will be called when the goal is reached
# fail : A proc that will be called if no path was found
# cache : If true, map passibility information is calculated
# once and stored in a table. While this speeds up
# pathfinding on maps with many events, it is an overkill
# for most maps. You have to manually call make_pass_map
# once before calling calculate path.
#--------------------------------------------------------------------------
def setup(goal_node, character, limit, wait = 5,
reach = nil, fail = nil, cache = false)
# The start node is at the character's position
@start_node = Node.new(character.x, character.y)
@goal_node = Node.new(goal_node.x, goal_node.y)
@character = character
@limit = limit
@collision_wait = wait # No. of frames the custom move route
# method should wait before attempting
# to find another path (-1 disables
# these attempts altogether)
@reach_method = reach # Proc to call when goal is reached
@fail_method = fail # Proc to call when no path is found
@cache_pass = cache # If true, map passibility information
# is stored in a table (@pass_map) for
# faster access.
@pass_map = nil # Table holding passability information
# fill it manually with make_pass_map
# if needed
@open_list = Array.new # List of nodes to be checked,
# implemented as a binary heap
@open_list.push(@start_node)
@closed_list = Hash.new # Set of nodes already checked, this
# is a hash of arrays of [x, y] pairs
# representing map tiles
@found = false # Did we find the optimal path?
end
#--------------------------------------------------------------------------
# * Search For the Optimal Path
#--------------------------------------------------------------------------
def calculate_path
c = 0 # A simple counter
# Only do calculation if goal is actually passable
if passable?(@goal_node.x, @goal_node.y)
while @open_list.empty? == false
c = c + 1
Graphics.update if (c % 200 == 0) # Prevents script hanging
# If we hit the iteration limit, exit
if @limit != -1 and c >= @limit
@found = false
break
end
# Get the node with lowest cost and add it to the closed list
@current_node = find_lowest_cost
@closed_list[[@current_node.x, @current_node.y]] = @current_node
if @current_node == @goal_node
# We reached goal, exit the loop!
@goal_node = @current_node
@found = true
break
else
# Get adjacent nodes and check if they can be added to the open list
adjacent_nodes = get_adjacent_nodes(@current_node)
for adj_node in adjacent_nodes
if skip_node?(adj_node)
# Node already exists in one of the lists, skip it
next
end
# Add node to open list following the binary heap conventions
heap_add(@open_list, adj_node)
end
end
end
end
# If no path was found, call the fail method
if not @found
if @fail_method != nil
@fail_method.call
end
end
end
#--------------------------------------------------------------------------
# * Is tile at X, Y passable?
#--------------------------------------------------------------------------
def passable?(x, y)
# If passability caching is enabled
if @cache_pass == true and @pass_map != nil
# Get path information from the table
return @pass_map[x, y] == 1 ? true : false
else
# Otherwise use Game_Character#passable?
return @character.passable?(x, y, 0)
end
end
#--------------------------------------------------------------------------
# * Add an Item to the Binary Heap (for open_list). This is Based on
# Algorithm Here: http://www.policyalmanac.org/games/binaryHeaps.htm
# array : Array to add the node to
# item : Item to add!
#--------------------------------------------------------------------------
def heap_add(array, item)
# Add the item to the end of the array
array.push(item)
# m is the index of the 'current' item
heap_update(array, array.size - 1)
end
#--------------------------------------------------------------------------
# * Make Sure the Item at Index is in the Right Place
# array : Array to update
# index : Index of the item
#--------------------------------------------------------------------------
def heap_update(array, index)
m = index
while m > 0
# If current item's cost is less than parent's
if array[m].cost <= array[m / 2].cost
# Swap them so that lowest cost bubbles to top
temp = array[m / 2]
array[m / 2] = array[m]
array[m] = temp
m /= 2
else
break
end
end
end
#--------------------------------------------------------------------------
# * Remove an Item from the Binary Heap (for open_list) & Return it.
# This is Based on Algorithm Here:
# http://www.policyalmanac.org/games/binaryHeaps.htm
# array : Array to remove the node from
#--------------------------------------------------------------------------
def heap_remove(array)
if array.empty?
return nil
end
#Get original first element
first = array[0]
# Replace first element with last one
last = array.slice!(array.size - 1)
if array.empty?
return last
else
array[0] = last
end
v = 0 # Stores a smaller child, if any
# Loop until no more swapping is needed
while true
u = v
# If both children exist
if 2 * u + 1 < array.size
v = 2 * u if array[2 * u].cost <= array[u].cost
v = 2 * u + 1 if array[2 * u + 1].cost <= array[v].cost
# If only one child exists
elsif 2 * u < array.size
v = 2 * u if array[2 * u].cost <= array[u].cost
end
# If at least one child is less than parent
if u != v
#swap parent and that child
temp = array[u]
array[u] = array[v]
array[v] = temp
else
break
end
end
# Return the original first node (which was removed)
return first
end
#--------------------------------------------------------------------------
# * Can We Skip This Node? (because it already exists in a list)
# node : Node to check
#--------------------------------------------------------------------------
def skip_node?(node)
skip_node = false
# Find any copy of the node in the open list and get its index
# or nil if it's not there
copy = @open_list.index(node)
if copy != nil
#If the existing copy is 'better' than the new one
if @open_list[copy].cost <= node.cost
# Then we skip the new one
skip_node = true
else
# Otherwise we swap the new copy with the old one
# and make sure the heap is in the right order
@open_list[copy] = node
heap_update(@open_list, copy)
skip_node = true
end
end
# The closed list is a hash so this is relatively easier
if @closed_list[[node.x, node.y]] != nil
# If the existing copy is 'better' than the new one
if @closed_list[[node.x, node.y]].cost <= node.cost
skip_node = true
else
# Update the existing node
@closed_list[[node.x, node.y]] = node
end
end
# Return the result
return skip_node
end
#--------------------------------------------------------------------------
# * Find Node With Lowest Cost on the Open List
#--------------------------------------------------------------------------
def find_lowest_cost
# Just return top of the heap
return heap_remove(@open_list)
end
#--------------------------------------------------------------------------
# * Distance Between Two Points (Heuristic)
#--------------------------------------------------------------------------
def distance(x1, y1, x2, y2)
# A simple heuristic value (Manhattan distance)
return ((x1 - x2).abs + (y1 - y2).abs)
end
#--------------------------------------------------------------------------
# * Get a List of Adjacent Nodes
# node : The 'center' node
#--------------------------------------------------------------------------
def get_adjacent_nodes(node)
# Array to hold the nodes
nodes = Array.new
# Right
new_x = node.x + 1
new_y = node.y
add_node(nodes, new_x, new_y, node)
# Left
new_x = node.x - 1
new_y = node.y
# Down
add_node(nodes, new_x, new_y, node)
new_x = node.x
new_y = node.y + 1
add_node(nodes, new_x, new_y, node)
# Up
new_x = node.x
new_y = node.y - 1
add_node(nodes, new_x, new_y, node)
return nodes
end
#--------------------------------------------------------------------------
# * Add a Node to an Array
#--------------------------------------------------------------------------
def add_node(array, x, y, parent)
if passable?(x, y)
# The cost of movement one step to a new tile is always 1
g = parent.g + 1
# The heuristic is simply the distance
h = distance(x, y, @goal_node.x, @goal_node.y)
new_node = Node.new(x, y, parent, g, h)
array.push(new_node)
end
end
#--------------------------------------------------------------------------
# * Get Direction From a Point to Another
#--------------------------------------------------------------------------
def get_direction(x1, y1, x2, y2)
# If first point is to the ... of second point,
if x1 > x2 # right
return 4
elsif x1 < x2 # left
return 6
elsif y1 > y2 # bottom
return 2
elsif y1 < y2 # top
return 8
end
# Otherwise they are on the same position
return 0
end
#--------------------------------------------------------------------------
# * Generate the Path by Following Parents and Return it
# as RPG::MoveRoute
# follow : If true the path is assigned to the character as a
# forced move route.
#--------------------------------------------------------------------------
def generate_path(follow = true)
# There's no path to generate if no path was found
if !@found
return
end
# Create a new move route that isn't repeatable
@route = RPG::MoveRoute.new
@route.repeat = false
# Start from the last node (goal) and build the path by
# adding each node to the front of the route and then
# following the node's parent
node = @goal_node
code = 0 # Movement code for RPG::MoveCommand
while node.parent != nil
# Get direction from parent to node and convert it to code
# understood by RPG::MoveCommand
direction = get_direction(node.parent.x, node.parent.y, node.x, node.y)
case direction
when 2 # Up
code = 4
when 4 # Left
code = 2
when 6 # Right
code = 3
when 8 # Down
code = 1
end
# Unshift adds to the start of the array
@route.list.unshift(RPG::MoveCommand.new(code)) if code != 0
node = node.parent
end
# If the path should be assigned to the character
if follow and !@route.list.empty?
@character.a_star_path = self
@character.force_move_route(@route)
end
# Return the constructed RPG::MoveRoute
return @route
end
#--------------------------------------------------------------------------
# * Generate a Passability Table. A Method that Should be Called Before
# Pathfinding is Attempted if Passibility Caching is Required. It
# Can be Slow and is Also Called when Character Path is Blocked.
# The Table is Returned. An Example of Usage is Generating the Map When
# the Map Loads for the First Time.
#--------------------------------------------------------------------------
def make_pass_map
# A 2D table as big as the map~
@pass_map = Table.new($game_map.width, $game_map.height)
# Fill it with 1s or 0s depending on passability
for y in 0...$game_map.height
for x in 0...$game_map.width
@pass_map[x, y] = @character.passable?(x, y, 0) ? 1 : 0
end
end
# Return the generated pass_map
return @pass_map
end
end
#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
# Just make the move_route variables public
#==============================================================================
class Game_Character
attr_accessor :move_route_forcing
attr_accessor :move_route
attr_accessor :a_star_path # the path the character is following
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
alias :a_star_pathfinder_old_initialize :initialize
def initialize
a_star_pathfinder_old_initialize
@a_star_path = nil
end
#--------------------------------------------------------------------------
# * Move Type : Custom (move event, pattern, etc.)
# Note: The script overwrites this method, which _might_ lead to
# compatibility problems with other scripts. You can remove this
# method to fix any such problem, but the character won't be able
# to detect the need to recalculate the path.
#--------------------------------------------------------------------------
def move_type_custom
# Interrupt if not stopping
if jumping? or moving?
return
end
# For each move command starting from the index
while @move_route_index < @move_route.list.size
# Get the move command at index
command = @move_route.list[@move_route_index]
# If command code is 0 (end of list)
if command.code == 0
# If [repeat action] option is ON
if @move_route.repeat
# Reset move route index to the top of the list
@move_route_index = 0
end
# If [repeat action] option is OFF
unless @move_route.repeat
# If move route is forced and not repeating
if @move_route_forcing and not @move_route.repeat
### CODE ADDED HERE ############################################################
# If there was a path to follow
if @a_star_path != nil
# And if we reached the goal
if self.x == @a_star_path.goal_node.x and
y == @a_star_path.goal_node.y
# Call the reach method if one was provided
if @a_star_path.reach_method != nil
@a_star_path.reach_method.call
end
end
# Don't need this variable anymore
@a_star_path = nil
end
### ADDED CODE ENDS ############################################################
# The move route is no longer forced (moving ended)
@move_route_forcing = false
# Restore original move route
@move_route = @original_move_route
@move_route_index = @original_move_route_index
@original_move_route = nil
end
# Clear stop count
@stop_count = 0
end
return
end # if command.code == 0
# For move commands (from move down to jump)
if command.code <= 14
# Branch by command code
case command.code
when 1 # Move down
move_down
when 2 # Move left
move_left
when 3 # Move right
move_right
when 4 # Move up
move_up
when 5 # Move lower left
move_lower_left
when 6 # Move lower right
move_lower_right
when 7 # Move upper left
move_upper_left
when 8 # Move upper right
move_upper_right
when 9 # Move at random
move_random
when 10 # Move toward player
move_toward_player
when 11 # Move away from player
move_away_from_player
when 12 # 1 step forward
move_forward
when 13 # 1 step backward
move_backward
when 14 # Jump
jump(command.parameters[0], command.parameters[1])
end
# If movement failure occurs when [Ignore if can't move] option is OFF
if not @move_route.skippable and not moving? and not jumping?
### CODE ADDED HERE ############################################################
# If there's a path but it couldn't be followed (probably because
# another character blocked it)
if @a_star_path != nil and @a_star_path.collision_wait >= 0
# The basic properties of the path don't change, only the
# start position (character's current location) does
goal = @a_star_path.goal_node
char = @a_star_path.character
limit = @a_star_path.limit
wait = @a_star_path.collision_wait
reach = @a_star_path.reach_method
fail = @a_star_path.fail_method
cache = @a_star_path.cache_pass
# Find another path to goal
@a_star_path = A_Star_Pathfinder.new
@a_star_path.setup(goal, char, limit, wait, reach, fail, cache)
# If passibility caching is enabled we need to regenerate the
# map to update passibility information (slow)
if @a_star_path.cache_pass == true
@a_star_path.make_pass_map
end
@a_star_path.calculate_path
@a_star_path.generate_path
# Force this method to wait before attempting to generate
# another path
@wait_count = @a_star_path.collision_wait
end
### ADDED CODE ENDS ############################################################
return
end
# Advance index
@move_route_index += 1
return
end # if command.code <= 14
# If waiting
if command.code == 15
# Set wait count (from provided parameter)
@wait_count = command.parameters[0] * 2 - 1
@move_route_index += 1
return
end # if command.code == 15
# If direction change (turning) command
if command.code >= 16 and command.code <= 26
# Branch by command code
case command.code
when 16 # Turn down
turn_down
when 17 # Turn left
turn_left
when 18 # Turn right
turn_right
when 19 # Turn up
turn_up
when 20 # Turn 90? right
turn_right_90
when 21 # Turn 90? left
turn_left_90
when 22 # Turn 180?
turn_180
when 23 # Turn 90? right or left
turn_right_or_left_90
when 24 # Turn at Random
turn_random
when 25 # Turn toward player
turn_toward_player
when 26 # Turn away from player
turn_away_from_player
end
@move_route_index += 1
return
end # if command.code >= 16 and command.code <= 26
# If other command (commands that don't 'return')
if command.code >= 27
# Branch by command code
case command.code
when 27 # Switch ON
$game_switches[command.parameters[0]] = true
$game_map.need_refresh = true
when 28 # Switch OFF
$game_switches[command.parameters[0]] = false
$game_map.need_refresh = true
when 29 # Change speed
@move_speed = command.parameters[0]
when 30 # Change freq
@move_frequency = command.parameters[0]
when 31 # Move animation ON
@walk_anime = true
when 32 # Move animation OFF
@walk_anime = false
when 33 # Stop animation ON
@step_anime = true
when 34 # Stop animation OFF
@step_anime = false
when 35 # Direction fix ON
@direction_fix = true
when 36 # Direction fix OFF
@direction_fix = false
when 37 # Through ON
@through = true
when 38 # Through OFF
@through = false
when 39 # Always on top ON
@always_on_top = true
when 40 # Always on top OFF
@always_on_top = false
when 41 # Change Graphic
# Can't change into a tile
@tile_id = 0
@character_name = command.parameters[0]
@character_hue = command.parameters[1]
# Update direction
if @original_direction != command.parameters[2]
@direction = command.parameters[2]
@original_direction = @direction
@prelock_direction = 0
end
# Update frame
if @original_pattern != command.parameters[3]
@pattern = command.parameters[3]
@original_pattern = @pattern
end
when 42 # Change Opacity
@opacity = command.parameters[0]
when 43 # Change Blending
@blend_type = command.parameters[0]
when 44 # Play SE
$game_system.se_play(command.parameters[0])
when 45 # Script
result = eval(command.parameters[0])
end
# Update move_route_index and move to next move command in the list
@move_route_index += 1
end # if command.code >= 27
end # while @move_route_index < @move_route.list.size
end
endInstructions
First you have to add this script somewhere under the default scripts (and above main), I assume you know how to add a new script section and paste this script there. I don't know much about the SDK thing, but I don't think you'll get any trouble when using this scripts with others. Note that this script overwrites the move_type_custom of Game_Character, any other script that does that might clash with this one.
Now, simply create a new instance of the A_Star_Pathfinder class and supply it with the required parameters. For example, you could create it in an event page by adding a script command and typing something like:
Code:
node = Node.new(x, y)
path = A_Star_Pathfinder.new(node)The constructor can take more information, such as the character that will move according to the result of pathfinding (player by default), whether the character should follow the path right away (true by default, if you set it to false, you'll have to call generate_path yourself), as well as the option to supply a limit to the number of pathfinding iterations (good if you suffer from lag on large maps). Here's another example of usage:
Code:
node = Node.new(x, y)
char = $game_map.events[event_id]
path = A_Star_Pathfinder.new(node, char, false)
# do other stuff
path.generate_path # and then generate the pathAs an alternative, you can provide nothing to the constructor, and call the setup, calculate_path, and generate_path manually. This gives you more control because the setup method allows you to change specify more variables such as methods to call when the path is reached or couldn't be found (implemented as Proc objects). You can also specify the number of frames to wait before trying to generate a new path in the case that the character's path is blocked. Here's an example of such usage:
Code:
path = A_Star_Pathfinder.new
goal = Node.new(1, 0)
char = $game_player
limit = 1000
wait = 5
# lambda creates Procs, an alternative is Proc.new { ... }
reach = lambda { p "REACHD GOAL!!!" }
fail = lambda { p "COULDN'T FIND PATH!!!" }
pass = false
path.setup(goal, char, limit, wait, reach, fail, pass)
path.calculate_path
path.generate_pathThe last argument to the setup method is a boolean variable that, if set to true, will allow storing passability information in a table that is computed only when needed. You'd have to call make_pass_map yourself after setup, and the pathfinder will use the table to lookup passability. This optimization is helpful for maps with lots of events as it cuts down the time needed to loop through events to check their passability, but the method to generate the passability map is currently slow and since it is called on collision with other events it could slow down pathfinding instead of improving it. Personally I think it's too much for most applications, but it could be useful in certain situations.
For more information, check the script comments~
FAQ
Waiting for some~
Version Info
Version 1.1:
- Added a mechanism to prevent the generated path from being blocked by other characters. When such a collision happens, the character will try to generate a new path to goal. This can be turned off if you set collision_wait to -1
- Now you can provide blocks to be called when the path is reached or if no path is found.
- Added the cache pass flag to allow generating passability information in a Table for faster access. This was inspiredby a post by Anaryu at http://www.rmxp.org/forums/showthread.php?t=16589
- Better documentation
Version 1.0:
- Initial release version.
Compatibility
I don't know about the SDK, but I don't think you'll get any trouble when using this scripts with others. Note that this script overwrites the move_type_custom of Game_Character, any other script that does that might clash with this one.
Credits and Thanks
The sites mentioned in the script were a big help. Wikipedia too.
Mr. Mo and Zeriab for suggesting some improvements.
Anaryu for the passability table idea (in another thread).
Eivien for providing another implementation of A* that I can steal learn from!
Author's Notes
Well, I haven't tested some of the new features enough so there are bound to be a few bugs to be fixed. I also want to make it faster, if possible. Maybe get a few tips from Zeriab's anti-lag script and Eivien's path finding script.
Terms and Conditions
None really. Check the big comment at the top of the script for more specific information, but there aren't really any terms aside from not trying to pass the script as your own.
