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
end
Zitieren
