Hey there,
I want to use ForeverZer0's pathfinding so events can approach the player in a more intelligent way (thus not getting stuck or blocked by walls like they do when using the built-in approaching).
In order to archieve this you have to update the target's x/y coords repeatedly, ~1-4 times per second. However whenever I use a pathfind script call on an event that hasn't finished a previous call yet, some kind of strange behaviour takes place:
So what I want to know is how to make an already existing Pathfind object calculate and execute a new path, or how to delete it and then make a new one (avoiding those wierd stacking issues happening with multiple pathfindings on one event).
This already works using Near Fantastica's Pathfinding; however that one is utterly inferior both performance- and quality-wise, partially causing screen freezes for seconds.
Here's the script:
I want to use ForeverZer0's pathfinding so events can approach the player in a more intelligent way (thus not getting stuck or blocked by walls like they do when using the built-in approaching).
In order to archieve this you have to update the target's x/y coords repeatedly, ~1-4 times per second. However whenever I use a pathfind script call on an event that hasn't finished a previous call yet, some kind of strange behaviour takes place:
- When player did not move since entering the map: "Stack level too deep" as soon as event reaches him
- When player moved while event is approaching him: event keeps running between two recent waypoints after event has reached him
So what I want to know is how to make an already existing Pathfind object calculate and execute a new path, or how to delete it and then make a new one (avoiding those wierd stacking issues happening with multiple pathfindings on one event).
This already works using Near Fantastica's Pathfinding; however that one is utterly inferior both performance- and quality-wise, partially causing screen freezes for seconds.
Here's the script:
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# Advanced Pathfinding
# Author: ForeverZer0
# Version: 1.1
# Date: 5.30.2011
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# Introduction:
# This is an advanced an highly intelligent pathfinding system. It allows for
# the user to either through script or script call quickly and easily have
# events or the game player automatically walk a path to a given set of
# coordinates. The system is smart enough to quickly find paths through
# relatively complex areas, and adjust on the fly for any obstacle that moves
# to block its path. I used the A* algorithm, basic search algorithm used
# often for robotics. More on this algorithm can be read about here:
#
# http://en.wikipedia.org/wiki/A*_search_algorithm
#
# Features:
# - Fast and intelligent pathfinding
# - Easy to use script calls
# - Optional "range" parameter can have character find alternate locations
# if the preferred one is blocked and they are within the given range.
# - Optional callbacks can be given to have something execute if when the
# character reaches its goal, or when it fails to do so.
#
# Instructions:
# - Place script below default scripts, and above "Main".
# - Use the following script call:
#
# pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#
# The X and Y are the only required arguments. The others can be omitted.
#
# X - The x-coordinate to pathfind to.
# Y - The y-coordinate to pathfind to.
#
# CHARACTER - Either an instance of the character ($game_player,
# $game_map.events[ID], etc) or the ID of a character. The ID
# will be the event ID. Use -1 for the game player.
#
# SUCCESS_PROC - A Proc object that will be executed when the player
# reaches the defined coordinates.
# FAILURE_PROC - A Proc object that will be executed when the player
# cannot reach the defined coordinates.
#
# - As default, the pathfinder will make 35 attempts to recalculate a route
# that gets blocked. This value can be changed in game with the script
# call:
# $game_map.collision_retry = NUMBER
#
# You can change the default value if desired by looking down to the first
# class below in the main script.
# - For longer pathfind routes, it is sometimes necessary to reset the
# search limiter. This may cause increased lag when an object blocks the
# character from being able to move, but will increase the range that the
# system can work with. Use the following script call:
#
# $game_map.search_limiter = NUMBER (Default 1000)
#
# - If you are experiencing any compatibility problems, go to the Game_Map
# class below and set @recalculate_paths to false. This will take away some
# of the efficiency of recalculating collisions, but will improve may fix
# your problem.
#
# Compatibility:
# Highly compatible. May experience issues with Custom Movement scripts,
# but even then, it is unlikely.
#
# Credits/Thanks:
# - ForeverZer0, for the script
# - Special thanks to Jragyn for help making the big maze for the demo and
# help testing.
# - Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the
# original search algorithm that was implemented
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#===============================================================================
# ** Game_Map
#===============================================================================
class Game_Map
attr_accessor :collision_retry
attr_accessor :recalculate_paths
attr_accessor :search_limiter
alias zer0_pathfinding_init initialize
def initialize
# Initialize instance variables used for pathfinding.
@collision_retry = 35
@recalculate_paths = true
@search_limiter = 1000
# Original method
zer0_pathfinding_init
end
end
#===============================================================================
# ** Interpreter
#===============================================================================
class Interpreter
def pathfind(x, y, *args)
args[0] = @event_id if args[0] == nil
args[1] = 0 if args[1] == nil
# Add a simpler call for using as a script call
Pathfind.new(Node.new(x, y), *args)
end
end
#==============================================================================
# ** Pathfind
#==============================================================================
class Pathfind
attr_reader :route
attr_accessor :range
attr_reader :goal
attr_reader :found
attr_reader :character
attr_accessor :success_proc
attr_accessor :failure_proc
attr_accessor :target
attr_accessor :collisions
def initialize(node, char = -1, range = 0, *callbacks)
# Set the character. Can either us an ID or an instance of a Game_Character.
# A value of -1, which is default, is the Game_Player.
if char.is_a?(Integer)
@character = (char == -1) ? $game_player : $game_map.events[char]
elsif char.is_a?(Game_Character)
@character = char
end
# Set forcing flag. Will be disabled for recalculating on the fly.
@forcing = true
# Call a public method, since this method may need to be used again,
# and "initialize" is private.
setup(node, range, *callbacks)
end
def setup(node, range = 0, *callbacks)
# Initialize the node we are trying to get to.
@target = Node.new(node.x, node.y)
@goal = @target.clone
# Set beginning nodes and required variables.
@start_node = Node.new(@character.x, @character.y)
@nearest = Node.new(0, 0, 0, -1)
@range, @found, @collisions = range, false, 0
# Set callbacks for success and failure if included, else nil.
@success_proc = callbacks[0]
@failure_proc= callbacks[1]
# Initialize sets to track open and closed nodes
@open_set, @close_set = [@start_node], {}
# Find the optimal path
calculate_path
end
def calculate_path
# Only do calculation if goal is actually passable, unless we only
# need to get close or within range
if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
# Initialize counter
counter, wait = 0, 0
until @open_set.empty?
counter += 1
# Give up if pathfinding is taking more than 500 iterations
if counter >= $game_map.search_limiter
@found = false
break
end
# Get the node with lowest cost and add it to the closed list
@current_node = get_current
@close_set[[@current_node.x, @current_node.y]] = @current_node
if @current_node == @goal ||
(@range > 0 && @goal.in_range?(@current_node, @range))
# We reached goal, exit the loop!
@target = @goal
@goal, @found = @current_node, true
break
else # if not goal
# Keep track of the node with the lowest cost so far
if @current_node.heuristic < @nearest.heuristic ||
@nearest.heuristic < 1
@nearest = @current_node
end
# Get adjacent nodes and check if they can be added to the open list
neighbor_nodes(@current_node).each {|neighbor|
# Skip Node if it already exists in one of the lists.
next if can_skip?(neighbor)
# Add node to open list following the binary heap conventions
@open_set.push(neighbor)
arrange(@open_set.size - 1)
}
end
end
end
# If no path was found, see if we can get close to goal
unless @found
if @range > 0 && @nearest.heuristic > 0
# Create an alternate path.
setup(@nearest, @range, @success_proc, @failure_proc)
elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
(@collisions > $game_map.collision_retry))
# If out of retries, call the Proc for failure if defined
@failure_proc.call
end
end
# Create the move route using the generated path
create_move_route
end
def create_move_route
# There's no path to generate if no path was found
return if !@found
# Create a new move route that isn't repeatable
@route = RPG::MoveRoute.new
@route.repeat = false
# Generate path by starting from goal and following parents
node = @goal
while node.parent
# Get direction from parent to node as RPG::MoveCommand
code = case direction(node.parent.x, node.parent.y, node.x, node.y)
when 2 then 4 # Up
when 4 then 3 # Left
when 6 then 2 # Right
when 8 then 1 # Down
else; 0
end
# Add movement code 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 (@forcing && !@route.list.empty?)
@collisions = 0
@character.paths.push(self)
@character.force_move_route(@route) if @character.paths.size == 1
end
# Reset forcing flag if needed
@forcing = true
# Return the constructed RPG::MoveRoute
return @route
end
def arrange(index)
# Rearrange nodes in the open_set
while index > 0
# Break loop unless current item's cost is less than parent's
break if @open_set[index].score > @open_set[index / 2].score
# Bring lowest value to the top.
temp = @open_set[index / 2]
@open_set[index / 2] = @open_set[index]
@open_set[index] = temp
index /= 2
end
end
def get_current
return if @open_set.empty?
return @open_set[0] if @open_set.size == 1
# Set current node to local variable and replace it with the last
current = @open_set[0]
@open_set[0] = @open_set.pop
# Loop and rearrange array according to the A* algorithm until done.
y = 0
loop {
x = y
# If two children exist
if 2 * x + 1 < @open_set.size
if @open_set[2 * x].score <= @open_set
# Advanced Pathfinding
# Author: ForeverZer0
# Version: 1.1
# Date: 5.30.2011
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# Introduction:
# This is an advanced an highly intelligent pathfinding system. It allows for
# the user to either through script or script call quickly and easily have
# events or the game player automatically walk a path to a given set of
# coordinates. The system is smart enough to quickly find paths through
# relatively complex areas, and adjust on the fly for any obstacle that moves
# to block its path. I used the A* algorithm, basic search algorithm used
# often for robotics. More on this algorithm can be read about here:
#
# http://en.wikipedia.org/wiki/A*_search_algorithm
#
# Features:
# - Fast and intelligent pathfinding
# - Easy to use script calls
# - Optional "range" parameter can have character find alternate locations
# if the preferred one is blocked and they are within the given range.
# - Optional callbacks can be given to have something execute if when the
# character reaches its goal, or when it fails to do so.
#
# Instructions:
# - Place script below default scripts, and above "Main".
# - Use the following script call:
#
# pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#
# The X and Y are the only required arguments. The others can be omitted.
#
# X - The x-coordinate to pathfind to.
# Y - The y-coordinate to pathfind to.
#
# CHARACTER - Either an instance of the character ($game_player,
# $game_map.events[ID], etc) or the ID of a character. The ID
# will be the event ID. Use -1 for the game player.
#
# SUCCESS_PROC - A Proc object that will be executed when the player
# reaches the defined coordinates.
# FAILURE_PROC - A Proc object that will be executed when the player
# cannot reach the defined coordinates.
#
# - As default, the pathfinder will make 35 attempts to recalculate a route
# that gets blocked. This value can be changed in game with the script
# call:
# $game_map.collision_retry = NUMBER
#
# You can change the default value if desired by looking down to the first
# class below in the main script.
# - For longer pathfind routes, it is sometimes necessary to reset the
# search limiter. This may cause increased lag when an object blocks the
# character from being able to move, but will increase the range that the
# system can work with. Use the following script call:
#
# $game_map.search_limiter = NUMBER (Default 1000)
#
# - If you are experiencing any compatibility problems, go to the Game_Map
# class below and set @recalculate_paths to false. This will take away some
# of the efficiency of recalculating collisions, but will improve may fix
# your problem.
#
# Compatibility:
# Highly compatible. May experience issues with Custom Movement scripts,
# but even then, it is unlikely.
#
# Credits/Thanks:
# - ForeverZer0, for the script
# - Special thanks to Jragyn for help making the big maze for the demo and
# help testing.
# - Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the
# original search algorithm that was implemented
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#===============================================================================
# ** Game_Map
#===============================================================================
class Game_Map
attr_accessor :collision_retry
attr_accessor :recalculate_paths
attr_accessor :search_limiter
alias zer0_pathfinding_init initialize
def initialize
# Initialize instance variables used for pathfinding.
@collision_retry = 35
@recalculate_paths = true
@search_limiter = 1000
# Original method
zer0_pathfinding_init
end
end
#===============================================================================
# ** Interpreter
#===============================================================================
class Interpreter
def pathfind(x, y, *args)
args[0] = @event_id if args[0] == nil
args[1] = 0 if args[1] == nil
# Add a simpler call for using as a script call
Pathfind.new(Node.new(x, y), *args)
end
end
#==============================================================================
# ** Pathfind
#==============================================================================
class Pathfind
attr_reader :route
attr_accessor :range
attr_reader :goal
attr_reader :found
attr_reader :character
attr_accessor :success_proc
attr_accessor :failure_proc
attr_accessor :target
attr_accessor :collisions
def initialize(node, char = -1, range = 0, *callbacks)
# Set the character. Can either us an ID or an instance of a Game_Character.
# A value of -1, which is default, is the Game_Player.
if char.is_a?(Integer)
@character = (char == -1) ? $game_player : $game_map.events[char]
elsif char.is_a?(Game_Character)
@character = char
end
# Set forcing flag. Will be disabled for recalculating on the fly.
@forcing = true
# Call a public method, since this method may need to be used again,
# and "initialize" is private.
setup(node, range, *callbacks)
end
def setup(node, range = 0, *callbacks)
# Initialize the node we are trying to get to.
@target = Node.new(node.x, node.y)
@goal = @target.clone
# Set beginning nodes and required variables.
@start_node = Node.new(@character.x, @character.y)
@nearest = Node.new(0, 0, 0, -1)
@range, @found, @collisions = range, false, 0
# Set callbacks for success and failure if included, else nil.
@success_proc = callbacks[0]
@failure_proc= callbacks[1]
# Initialize sets to track open and closed nodes
@open_set, @close_set = [@start_node], {}
# Find the optimal path
calculate_path
end
def calculate_path
# Only do calculation if goal is actually passable, unless we only
# need to get close or within range
if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
# Initialize counter
counter, wait = 0, 0
until @open_set.empty?
counter += 1
# Give up if pathfinding is taking more than 500 iterations
if counter >= $game_map.search_limiter
@found = false
break
end
# Get the node with lowest cost and add it to the closed list
@current_node = get_current
@close_set[[@current_node.x, @current_node.y]] = @current_node
if @current_node == @goal ||
(@range > 0 && @goal.in_range?(@current_node, @range))
# We reached goal, exit the loop!
@target = @goal
@goal, @found = @current_node, true
break
else # if not goal
# Keep track of the node with the lowest cost so far
if @current_node.heuristic < @nearest.heuristic ||
@nearest.heuristic < 1
@nearest = @current_node
end
# Get adjacent nodes and check if they can be added to the open list
neighbor_nodes(@current_node).each {|neighbor|
# Skip Node if it already exists in one of the lists.
next if can_skip?(neighbor)
# Add node to open list following the binary heap conventions
@open_set.push(neighbor)
arrange(@open_set.size - 1)
}
end
end
end
# If no path was found, see if we can get close to goal
unless @found
if @range > 0 && @nearest.heuristic > 0
# Create an alternate path.
setup(@nearest, @range, @success_proc, @failure_proc)
elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
(@collisions > $game_map.collision_retry))
# If out of retries, call the Proc for failure if defined
@failure_proc.call
end
end
# Create the move route using the generated path
create_move_route
end
def create_move_route
# There's no path to generate if no path was found
return if !@found
# Create a new move route that isn't repeatable
@route = RPG::MoveRoute.new
@route.repeat = false
# Generate path by starting from goal and following parents
node = @goal
while node.parent
# Get direction from parent to node as RPG::MoveCommand
code = case direction(node.parent.x, node.parent.y, node.x, node.y)
when 2 then 4 # Up
when 4 then 3 # Left
when 6 then 2 # Right
when 8 then 1 # Down
else; 0
end
# Add movement code 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 (@forcing && !@route.list.empty?)
@collisions = 0
@character.paths.push(self)
@character.force_move_route(@route) if @character.paths.size == 1
end
# Reset forcing flag if needed
@forcing = true
# Return the constructed RPG::MoveRoute
return @route
end
def arrange(index)
# Rearrange nodes in the open_set
while index > 0
# Break loop unless current item's cost is less than parent's
break if @open_set[index].score > @open_set[index / 2].score
# Bring lowest value to the top.
temp = @open_set[index / 2]
@open_set[index / 2] = @open_set[index]
@open_set[index] = temp
index /= 2
end
end
def get_current
return if @open_set.empty?
return @open_set[0] if @open_set.size == 1
# Set current node to local variable and replace it with the last
current = @open_set[0]
@open_set[0] = @open_set.pop
# Loop and rearrange array according to the A* algorithm until done.
y = 0
loop {
x = y
# If two children exist
if 2 * x + 1 < @open_set.size
if @open_set[2 * x].score <= @open_set