Advanced Pathfinding
Authors: ForeverZer0
Version: 1.1
Type: Autonomous Character Movement
Key Term: Custom Movement System
IntroductionThis 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: A* Search Algorithm (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.
ScreenshotsCan quickly and easily navigate a maps like these, lag-free:
(http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Maze1.png)
(http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Maze2.png)
DemoDemo Link (http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Advanced%20Pathfinding.zip)
ScriptHere'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[x].score
y = 2 * x
if @open_set[2 * x + 1].score <= @open_set[y].score
y = 2 * x + 1
end
end
# If only one child exists
elsif 2 * x < @open_set.size &&
@open_set[2 * x].score <= @open_set[x].score
y = 2 * x
end
# Swap a child if it is less than the parent.
break if x == y
temp = @open_set[x]
@open_set[x] = @open_set[y]
@open_set[y] = temp
}
# Return the original first node (which was removed)
return current
end
def direction(x1, y1, x2, y2)
# Return the numerical direction between coordinates.
return 6 if x1 > x2 # Right
return 4 if x1 < x2 # Left
return 2 if y1 > y2 # Bottom
return 8 if y1 < y2 # Top
return 0
end
def neighbor_nodes(node)
# Create array to hold the nodes, then check each direction.
nodes = []
nodes.push(get_neighbor(node.x + 1, node.y, node)) # Right
nodes.push(get_neighbor(node.x - 1, node.y, node)) # Left
nodes.push(get_neighbor(node.x, node.y + 1, node)) # Down
nodes.push(get_neighbor(node.x, node.y - 1, node)) # Up
# Remove any nil elements, then return results.
return nodes.compact
end
def get_neighbor(x, y, parent)
# Calculate direction, return new node if passable.
direction = direction(x, y, parent.x, parent.y)
if @character.passable?(parent.x, parent.y, direction)
# The heuristic is simply the distance
heuristics = ((x - @goal.x).abs + (y - @goal.y).abs)
return Node.new(x, y, parent, parent.cost + 1, heuristics)
end
end
def can_skip?(node)
# Branch by if node is in either the open or closed set.
if @open_set.include?(node)
index = @open_set.index(node)
return true if @open_set[index].score <= node.score
# Swap them and update list order
@open_set[index] = node
arrange(index)
return true
elsif @close_set[[node.x, node.y]] != nil
# If the existing passed node has a lower score than this one.
return true if @close_set[[node.x, node.y]].score <= node.score
# Update the existing node
@close_set[[node.x, node.y]] = node
end
# Return false if no criteria was met.
return false
end
end
#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
attr_accessor :paths
attr_accessor :move_route_forcing
attr_accessor :move_route
alias zer0_pathfinding_init initialize
def initialize
# Add public instance variable for paths
@paths = []
# Original method
zer0_pathfinding_init
end
def next_route
# Stop any custom move route that may be occuring.
if @move_route != nil
# Set index and disable forcing of current route
@move_route_index = @move_route.list.size
@move_route_forcing = false
# Reset to what it was originally
@move_route = @original_move_route
@move_route_index = @original_move_route_index
@original_move_route = nil
end
# Remove first path from the paths array.
@paths.shift
# If there is another path to follow...
if @paths[0] != nil
# Setup path again to reflect any changes since original creation
@forcing = false
@paths[0].setup(@paths[0].target, @paths[0].range,
@paths[0].success_proc, @paths[0].failure_proc)
force_move_route(@paths[0].route) if @paths[0].found
end
end
alias zer0_recalculate_paths_move move_type_custom
def move_type_custom
if $game_map.recalculate_paths
# Interrupt if not stopping
return if jumping? || moving?
# Loop until finally arriving at move command list
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
# 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
# If there was a path to follow and we reached goal
if @paths[0] != nil
if self.x == @paths[0].goal.x &&
y == @paths[0].goal.y && @paths[0].success_proc
# Call success Proc if goal is reached and it is defined.
@paths[0].success_proc.call
end
next_route
end
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 then move_down # Move down
when 2 then move_left # Move left
when 3 then move_right # Move right
when 4 then move_up # Move up
when 5 then move_lower_left # Move lower left
when 6 then move_lower_right # Move lower right
when 7 then move_upper_left # Move upper left
when 8 then move_upper_right # Move upper right
when 9 then move_random # Move random
when 10 then move_toward_player # Move toward player
when 11 then move_away_from_player # Move away from player
when 12 then move_forward # Step forward
when 13 then move_backward # Step backward
when 14 then jump(command.parameters[0], command.parameters[1]) # Jump
end
# If movement failure occurs when "Ignore If Can't Move" is unchecked.
if !@move_route.skippable && !moving? && !jumping?
# If path is current and collision limit is not reached
if @paths[0] != nil &&
@paths[0].collisions < $game_map.collision_retry
# Setup path again to update starting location.
# original goal node is used because pathfinding changes
# the goal node to current node
goal, range = @paths[0].target, @paths[0].range
reach = @paths[0].success_proc
fail = @paths[0].failure_proc
counter = @paths[0].collisions + 1
# Find another path to goal
@paths[0] = Pathfind.new(goal, self, range, reach, fail)
@paths[0].collisions = counter
force_move_route(@paths[0].route) if @paths[0].found
# Wait a bit before starting to follow the new path
@wait_count = 6
return
elsif paths[0] != nil
# Call failure Proc if defined and set move index.
@move_route_index = @move_route.list.size
@paths[0].failure_proc.call if @paths[0].failure_proc != nil
next_route
end
# End method
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 then turn_down # Turn down
when 17 then turn_left # Turn left
when 18 then turn_right # Turn right
when 19 then turn_up # Turn up
when 20 then turn_right_90 # Turn 90° right
when 21 then turn_left_90 # Turn 90° left
when 22 then turn_180 # Turn 180°
when 23 then turn_right_or_left_90 # Turn 90° right or left
when 24 then turn_random # Turn at Random
when 25 then turn_toward_player # Turn toward player
when 26 then turn_away_from_player # Turn away from player
end
@move_route_index += 1
return
end
# 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 then @move_speed = command.parameters[0] # Change speed
when 30 then @move_frequency = command.parameters[0] # Change freq
when 31 then @walk_anime = true # Move ON
when 32 then @walk_anime = false # Move OFF
when 33 then @step_anime = true # Stop ON
when 34 then @step_anime = false # Stop OFF
when 35 then @direction_fix = true # Direction ON
when 36 then @direction_fix = false # Direction OFF
when 37 then @through = true # Through ON
when 38 then @through = false # Through OFF
when 39 then @always_on_top = true # On top ON
when 40 then @always_on_top = false # On top OFF
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 then @opacity = command.parameters[0] # Change Opacity
when 43 then @blend_type = command.parameters[0] # Change Blending
when 44 then $game_system.se_play(command.parameters[0]) # Play SE
when 45 then result = eval(command.parameters[0]) # Script
end
# Increment move index.
@move_route_index += 1
end
end
else
# Original method
zer0_recalculate_paths_move
end
end
end
#==============================================================================
# ** Node
#==============================================================================
class Node
attr_accessor :x
attr_accessor :y
attr_accessor :parent
attr_accessor :cost
attr_accessor :heuristic
def initialize(x, y, parent = nil, cost = 0, heuristic = 0)
# Set public instance variables.
@x, @y, @parent, @cost, @heuristic = x, y, parent, cost, heuristic
end
def score
# Return the current "score" of this node
return @cost + @heuristic
end
def in_range?(node, range)
# Return true/false if Nodes are within RANGE of each other.
return (@x - node.x).abs + (@y - node.y).abs <= range
end
def ==(node)
# Returns true/false of whether self and other are equal.
return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
end
end
InstructionsPlace script below default scripts and above "Main".
Further instructions are within the script and demo.
CompatibilityHighly compatible. Only issue may be with other custom movement scripts.
Credits and 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
Author's NotesPlease report any bugs/issues you may encounter so they can be resolved.
Enjoy!end
You're an ass. >:U I seriously was going to create this using that same algorithm.
Nice job! :)
Its the least complicated I could find. There are some straight-up confusing ones out there...
I beat you all to it. :V: *points to Blizz-ABS*
Yes, I noticed that. :P
Its still nice to have a system not dependent on another for those who don't use Blizz-ABS.
Actually it shouldn't be very much dependent on Blizz-ABS. The only part is the interpretation of the movement commands.
Sorry for the kind of necro post but I getting an error with this script when I make a set move route event that walks near the edge and tries to walk again (Which in theory it should just make the event stay in the same spot).
The error is:
Line 469
Undefined method 'failure proc' for nil:NilClass
Now this error I don't understand why it's happening as I'm not using this script on this particular event (Testing some ways to do some puzzles into the map with move rocks).
So if you could reply with a way to fix it it would be great else I'll probably have to switch to something else sadly. (This one is currently the best one I found when dealing with fps drop)
it's because you haven't set a failure proc for your event, yet the script is expecting there to be one because you haven't turned on "ignore if can't move" in the custom route window. turning this on will fix the problem.
But I don't want it to pass through unpassable tiles.
Also when I tried making the part of the failure only it was keeping on giving me errors.
Still I can't understand why I'm having the error when I'm not even calling the script.
There is a little bug I need to fix. Its pretty simple, so I'll fix it in a bit and re-upload.
Great thanks :)
Fixed.
Quote from: Vexus on February 01, 2012, 05:07:26 pm
But I don't want it to pass through unpassable tiles.
just to be clear on this, "ignore if can't move" will make it skip movement that would go through unpassable tiles, it doesn't make your event pass through them.
i see the slight delay in starting custom movement is gone now too. might i ask what the bug was?
Thanks it worked.
I just fixed a condition, the same one that mad.array mentioned in his edit to the script. I had made a "else" statement, when it should have been an "elsif" statement when determining if the failure proc should execute.
Hi again.
I'm not sure if it's a problem on my end but I'm trying to make your script working with your event range condition but am getting an error.
I'm making events that will chase your player when they are x range away and it works and when the event comes near the battle starts. Now obviously after the fight the event has to disappear no? so I ticked the can escape button and put an erase event in both win or escape.
I tried it only with escape but probably the same error would be given if I won.
The error is:
'Path Finding' line 178: SystemStackError occurred.
stack level too deep.
Does not happen often but it happened twice now.
Any idea why?
Thanks.
I'm not really sure why that would happen. Those errors are thrown when a method ends up calling itself, either directly or indirectly through other methods. I don't really see how erasing the event would cause that, since all erasing really does is creates a blank new page of the event and sets it as the current page for the event.
It's possible that you did a mistake in your script where you check tiles that have already been checked earlier. If a path could not be found (e.g. the target tile is cut off from the start tiles completely), then an infinite loop would happen which could cause this.
Another thing would be that RGSS does not support recursion. If you call a function from within itself, (YO DAWG style) even if it has not been called immediately, then this can happen as well. Your path finder should not calculate the path recursively. You have to implement it using a loop.
This is what I placed in the event:
(http://img829.imageshack.us/img829/1236/somniumevent.png)
The pathfind shouldn't loop as I made it go back to position if I manage to outrun the monster.
Strangely enough I tried several scripts for enemies behaviours but using this as method is the least on lagging the game.
Ps. would having a big map (240x200) affect the event's pathfinding? I get several fps issues when an event uses pathfinding to go in a location and the only solution I have is adding like 400 wait after the pathfind in the event (Same for this event even if the event has to go back 4 tiles only the fps goes down to 20 from 40).
I double-checked, and I cannot for the life of me see anywhere in the script that would cause recursion.
I factored in the path being blocked during the movement, but after it was already calculated, and set a max number of tries it is allowed to do it. The "recalculating" method basically just clears the current data and restarts the whole process from the current location, even calling the same method. I know that it can successfully recalculate (see pig map in demo), so that should not be it, otherwise it would not work at all, it would fail in the first retry.
I imagine the reason for your lag is in the event above, the pathfind call is being made every frame that the event is on the screen and not within 4 tiles of the player. Calculating a path is not a simple call, and not meant to be called every frame.
Maybe but having an extra event per npc/monster that require pathfinding would be a huge load of work as I'm trying to do a lively town with npcs doing their things during the day before night.
The easiest solution I found was the wait thing in the event which shouldn't give me problems right?
Got events tied with your time script could that cause some conflictions?
Thanks.
At what exact point does the error happen? When the event collides with something, as soon as you come out of battle, as soon as the player gets away from the enemy, etc.?
And no, the time script should have no bearing on actual events.
After killing the enemy but it doesn't happen often.
Another verifiable bug.
Recalculating a path because something moved in the way of the originally recalculated path seems to cause pathfinding to fail if it is run again a 2nd time, regardless of shifting map. Problem also appears to be intermittent, but occurs about 90% of the time.
Ok, heres what I did. New project, no script conflicts, no other scripts. Made a semi complex route for the player to move to using pathfind(3, 12, $game_player), and put some random events moving around so the path would have to be recalculated a 2nd time. It does complete successfully the first time. But, try to pathfind again, and it immediatly returns as invalid or impossible, regardless if the path is being blocked or not.
Increase "$game_map.collision_retry"
Ok, I bumped it up a little...
I changed it from 35 to 100, then tried again a few more times, and ended up at:
@collision_retry = 350000000000000
and it still does it.
Is the destination coordinates passable the moment when the call is made?
It goes back and forth, so the player waits for the event to move out of the way, then eventually does finish. However, once finished, which works great, and the path is completely clear, if I try to pathfind again, it seems to totally fail. I figure its something I have set wrong, just cant see why once it finishes, and try any pathinfinding at all, 2nd attempt wont start.
Quote from: ForeverZer0 on April 20, 2012, 11:10:00 pm
Is the destination coordinates passable the moment when the call is made?
I don't mean the first call, but following ones.
Yes.
I even went so far as to clear out all of the events that move in the players way on the 2nd attempt.
By the way, thank you for supporting your script.
Hmmm.
Upload me your demo where it fails, and I'll see if I can find anything.
Okie dokie.
http://www.775.net/~heretic/downloads/rmxp/PathfindBug.exe
Thank you for taking a look.
Its because at the time the call is made, there is no possible path that can be followed that will take the character to the destination.
Take a look at this fantastic example I slaved away at and made:
(http://i1086.photobucket.com/albums/j452/ForeverZer0/bug.png)
If the calls is made when the events block the path like that, the system begins searching for a path to the destination, but it can never get further than its small area up top where it is blocked into, therefore the pathfind is unsuccessful.
You can try a few things.
The easiest would be to not create situations like that. Its an automated search algorithm written in Ruby, not true intelligence, therefore stupid little things like that can screw it up.
Second, although I have not tested it, would be to increase the range in the script call. Just because it is allowed a range of error does not mean that it will quit the second it gets within it; it will still try to reach the exact target.
Third, and this is flirting with disaster a bit, and risking a hanging script would be to call the pathfind again as a failure proc. You will definitely want to test this solution vigorously if you decide the other two won't work and are going to use it.
I'll see if it is a viable option to provide some type of fix for this without breaking the scripts normal functionality, maybe some type of "at least go as far as you can" type procedure for characters to follow.
Ok, let me ask this way then. Im not too concerned that if a path is totally blocked that it fails. That makes perfect sense. But on the 2nd go, shouldnt that failure proc reset so it says to try it again? On the 2nd go, even when all the events are cleared, an unobstructed pathfind call says it failed. Thats where Im having difficulty...
This is what you have in your example:
pathfind(2, 12, $game_player)
You aren't defining any type of proc to run when it fails.
I realize that, because I am not sure what to do when it fails to "reset" the failed property, so when pathfind is called again, it does try instead of immediately returning that it failed. Is that even something I can do?
pathfind(3, 12, $game_player, reset_fail_proc())
I think I see.
I don't remember super good, but it may be that the Procs don't get setup if the initial call fails. I made them more for once the pathfind is already in process. I don't even think any data gets added to a Game_Character's "paths" variable if the first call fails.
The best advice I can give is to avoid these situations, but in case you want to try it, here is an EXTREMELY ugly hack that introduces risks all kinds of bugs and crashes if things don't go according to plan.
class Pathfind
alias freeze_my_game_if_event_dont_get_the_fuck_outta_the_way calculate_path
def calculate_path
freeze_my_game_if_event_dont_get_the_fuck_outta_the_way
if !@found
Pathfind.new(@goal, @character, @range, @success_proc, @failure_proc)
end
end
end
I haven't tried this at all, but you can see what it does. If it can't find a path, it creates a new Pathfind object. It will continue this until a path is opened or the game crashes. If you wanted, you could add a some simple counters to prevent repeated attempts that might prevent a freeze, but at the same time they won't guarantee success.
I have had the same issue in Blizz-ABS. I handled it in such a way that I created a progressive algorithm where you queue paths that you need to be found and then it would calculate 200 nodes (I actually don't remember the actual number) per frame for all of them together. That way lag would be avoided, but sometimes the path would not be found immediately in the same frame so enemies may stop for a short moment, especially if the path could not be calculated since there is a roadblock. I just wanted to throw in this idea/possibility to handle this problem in a constructive way.
@F0...
Ok, I think I found something...
On line 242:
@character.force_move_route(@route) if @character.paths.size == 1
... after having to make an adjustment, a new path is added to the paths[] array so the above line doesnt force_move_route, and immediately comes back as if it has completed.
Does that help at all?
Okay there Cookie Monster (F0's current avatar), I fixed this little problem. Simple one liner. A Cookie Monster walks into a bar, sits down next to a Master Scripter and says " @character.paths = []", ah, nevermind, wrong kind of one liner...
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
# Heretic - Clear any existing paths from previous pathfind calls
@character.paths = []
# Call a public method, since this method may need to be used again,
# and "initialize" is private.
setup(node, range, *callbacks)
end
Added code is Bolded. This is for anyone else that might experience this minor glitch in an otherwise fantastic script.
Here is what happens. Any time any event is set to pathfind more than once, and has to recalculate during path execution of the first pathfind call, extra paths are calculated and added to the @paths array, but not cleared. Thus, the 2nd time that same event is set to pathfind, it will automatically fail to execute because of "@character.force_move_route(@route) if @character.paths.size == 1" finding that more than one path is in the @paths array. It will reset for Events when maps are changed, but once $game_player has to recalculate, it fails across all maps.
@F0 - I know I am persistent about fixing stuff, but I havent offended you at all, have I?
Heretic - your added code actually made a new error in the demo. When the event is moving, and its path is blocked, it first sets paths[0] equal to a new instance of pathfinding. Then your code sets paths to [], and finally the collision retry code tries to access one of the variables of paths[0].
ForeverZer0 - Your getCurrent code is very confusing. I replaced it with 6 lines of code getting the node in open set with the lowest score.
You do realize that that method is the actual implementation of the A* algorithm?
Oh, sorry. I just went to the Wikipedia page and found that you needed to get the node with the lowest score.
Quote from: ThallionDarkshine on May 16, 2012, 10:35:07 pm
Heretic - your added code actually made a new error in the demo. When the event is moving, and its path is blocked, it first sets paths[0] equal to a new instance of pathfinding. Then your code sets paths to [], and finally the collision retry code tries to access one of the variables of paths[0].
...
Youre right. I went back, tried to rethink it out and came up with the same solution, just in a different spot.
I was able to recreate the problem, but hopefully I just had it in the wrong spot. Try putting @paths = [] right after @stop_count = 0 in def move_type_custom.
Alright, I'll try and see if it works.
Great script!
It works perfectly for me in an event and when using it via "call script" in the RMXP.
I'm new to the RGSS and I'm currently writing one of my first own scripts (a battle system).
So I would like to use this cool Pathfinding script there, but I don't know how to include it.
For my own script I've a class containing an initialize-methode and an update-methode. But where and how do I have to include this Pathfinding script? (I've of course pasted it above MAIN and as said before it works perfectly inside an event calling it.)
Could you please give me the lines so I can use the
pathfind(x, y, id, range, s, f)
like in an event?
Thank you! :)
Take a peek at the Interpreter section of script. There you will see some examples of how to use pathfinding without making the call with the event command. I'm on my phone at the moment, but I can offer more detailed help later if you still need it.
Thank you! I think I found it.
And it works :)
#Pathfind.new(Node.new(x, y), *args)
Pathfind.new(Node.new(8, 6), 13)
Two questions:
1) How can implement the success and fail argument there?
2) Following situation:
Legend:
O = free tile
S = starting point
E = end point
P = walked path
So when executing this situation, then the path is the following:
So the event goes straight down and then left. I would like to see rather a diagonal pattern:
How can I enable this? I would like to have the most direct way, especially when walking short distances. It seems to be that the algorithm doesn't include diagonal movement? How can I implement this :)
Thanks for your quick help!
The script does not support 8-directional movement by default, only 4. It would take a sizable edit to add the functionality. It would not be especially difficult, but would require quite a few additional checks when the system is laying out the path, and adding commands for the diagonal movements based off what was possible.
I really don't write scripts anymore, so I am sorry to say that I won't be making the edits. After the release of ARC, I may create a ARC port of the script (if we don't include pathfinding functionality in the default scripts), and in that case I will likely add the ability, but that isn't anything to plan on.
It wouldn't be super hard to add the functionality if you or another scripter would like to take a stab at it. Find the area in the script where it builds the move routes, and add the appropriate checks and commands. All it requires is an understanding of how RPG::MoveRoutes and map passability work, you don't need to understand the algorithm or the more advanced logic of the script to do it. I can provide advice to anyone who would like to try it.
Thanks again for the fast reply!
I fully understand your situation.
Okay, so before I will start scripting or ask someone else do you - or someone else here - know another pathfinding script which supports 8 directional movement?
Foreverzer0, could you please just tell me how I can add the option for the success argument here (when calling it not via an event):
#Pathfind.new(Node.new(x, y), *args)
Pathfind.new(Node.new(8, 6), 13)
That would help me a bit :)
EDIT: I got it!! :)
s = Proc.new { print 'Goal Reached!'}
f = Proc.new { print 'Failed!' }
#pathfind(x, y, id, range, s, f)
Pathfind.new(Node.new(Mouse.tile_x, Mouse.tile_y), 13, 0, s, f)
Nevertheless a pathfinding system with 8 movement would be cool. If anyone knows something where to find it, please let me know.
Oops, yes, I forgot to answer your original question. :facepalm:
You need to create a Proc object and pass it as an argument. The Proc can be anything you wish really, you can have it call a method, change a variable, etc.
I do not know what you want to do, so its a bit hard to tell you what argument to pass, but here would be an example:
Lets say that I want to flip a switch whenever the pathfind successfully completes:
Pathfind.new(Node.new(8, 6), 13, 0, Proc.new { $game_switches[1] = true })
The node is the coordinates, 13 is the event ID, 0 is the range, and the Proc is the procedure that will be executed on a successful route completion.
I am not aware of a pathfinding script that supports 8-directional movement, but to be honest I have never really looked into any others, so that does not mean to much.
Great, Thank you!! I'll try it out :)
I'm now trying "to do waypoints" with your script.
Example: I simply put two commands in two lines like this:
Pathfind.new(Node.new(Mouse.tile_x, Mouse.tile_y), @char_id)
Pathfind.new(Node.new(Mouse.tile_x, Mouse.tile_y+6), @char_id)
So it works well, the character goes first to the tile where the mouse is and then 6 tiles more south.
But when executing the same piece of code later again in my script, the character just doesn't move. I can't explain this - what is wrong?
EDIT: Moreover is there perhaps another way to do waypoints with your scripts?
I don't know, I can't see what extactly the situation is when the call is made.
One thing to keep in mind, if the "range" is set to 0, the destination tile must be passable, and the route must be open at the point of the call. If its not, nothing happens.
Ok for better explaining I modified your script game example and uploaded it here:
http://www.filedropper.com/advancedpathfindingdarian
Here's the script:
class Cycle
def initialize
@s = Proc.new { print 'Waypoint Reached!'}
@f = Proc.new { print 'Failed! ' }
@range = 0
@first_switch = "on"
end
def update
if @first_switch == "on"
p "phase for the first two waypoints"
Pathfind.new(Node.new(2, 3), 1, @range, @s, @f)
Pathfind.new(Node.new(3, 6), 1, @range, Proc.new { @second_switch = "on" }, @f)
@first_switch = "off"
#@second_switch = "on" # WHEN activating this line, the third waypoint works.
end
if @second_switch == "on"
p "phase for the third waypoint"
Pathfind.new(Node.new(4, 10), 1, @range, @s, @f)
@second_switch = "off"
end
end
end
I've implented the Cycle in the Scene_Map (and update Methode there).
There are 3 waypoints on the map: These three little sand spots which will be visited from north to south.
The third waypoint won't be reached. It will only work when I set the switch manually in line 17 (removing the comment).
Why is this? :)
Thank you very much for your time!!
A simpler method to what you want would be to simply set new Pathfinds as the success procs:
s2 = Proc.new { Pathfind.new(Node.new(4, 10), 1, 0) }
s1 = Proc.new { Pathfind.new(Node.new(3, 6), 1, 0, s2) }
Pathfind.new(Node.new(2, 3), 1, 0, s1)
I tried this, and it appears to be some type of problem with calling consecutive paths. Something isn't quite making sense to me, though. I used the above code, and it worked for the first two points, but didn't do anything for the third. I replaced the "s2" with a simple proc to display some text, and that worked, but when I replaced it with another Pathfind, it does nothing. It may be that the check for setting up a new path is already passed when the success proc is called, and it would require a wiat of a frame before continuing. Not sure I didn't test that in-depth. If I get some later, I will take a second look.
Yes, I had the same experience. The third pathfinding order doesn't work. I tried several variants with switches, but it doesn't help either.
It would be great if you could try something with your more advanced scripting skills :)
Thank you!
I found something! :)
With cases it seems to work:
class Cycle
def initialize
@s = Proc.new { print 'Waypoint Reached!'}
@f = Proc.new { print 'Failed! ' }
@range = 0
@phase = 1
end
def update
case @phase
when 1
Pathfind.new(Node.new(2, 3), 1, @range, @s, @f)
@phase = 2
when 2
Pathfind.new(Node.new(3, 6), 1, @range, @s, @f)
@phase = 3
when 3
Pathfind.new(Node.new(4, 10), 1, @range, @s, @f)
@phase = 4
end
end
end
Now it works. But strangely, though it's phase = 4 at the end the character keeps still walking between the last two waypoints. Could you explain this? That's strange...
The pathfinds will stack within the character's path variable, so you actually don't need a condition setting phases or anything.
This works within a script call, although the repeat of the last two steps persists...
Pathfind.new(Node.new(2, 3), 1, 0)
Pathfind.new(Node.new(3, 6), 1, 0)
Pathfind.new(Node.new(4, 10), 1, 0)
For some reason, it appears the path is not being removed before the next begins or something. I'll have to look into it.
Yes that makes sense to me, that could be the reason!
Would be cool if you could have a look :)
Thank you!
Hey there,
I want to use Zero'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.
I have uploaded (http://ubuntuone.com/3hskBOQgJveG9G5aySSNRd) Zero's Demo including a test map where you can see the described behaviour.
I really hope someone can spare a couple minutes and take a look at this issue. A well-working approach machanism is important to me, and I bet to many others too. I'm willing to pay 20$ to anyone solving this (probably small) issue.
Didn't F0 fix that problem already? Or wasn't there at least some kind of workaround?
Quote from: ForeverZer0 on July 20, 2012, 07:43:24 pm
The pathfinds will stack within the character's path variable, so you actually don't need a condition setting phases or anything.
This works within a script call, although the repeat of the last two steps persists...
Pathfind.new(Node.new(2, 3), 1, 0)
Pathfind.new(Node.new(3, 6), 1, 0)
Pathfind.new(Node.new(4, 10), 1, 0)
For some reason, it appears the path is not being removed before the next begins or something. I'll have to look into it.
This bug here probably has got the same cause (the last two calls somehow overlapping and thus repeating endlessly). He knows about it but didn't fix it yet, sadly.
I have also run into this issue when setting up waypoints for all the NPCs in the villages; instead of staying at a market stall they keep running there and back. I just love Z0's scripts and this one is again the best of its kind, but that tiny bug renders it almost completely useless for me (and a friend, for that matter) :(
Alright, who'd going to sit down and fix this?
Someone from the German forums might have a crack at it. I'll post here in case he changes his mind.
QuoteI'll post here in case he changes his mind.
He did, anyone interested in taking a look? Don't forget about the 20$ :naughty:
See above (http://forum.chaos-project.com/index.php/topic,9784.msg173294.html#msg173294) for the description of the bug.
It seems that nobody at this forum likes free money.
I'll do it tomorrow.
Pure awesomeness. No, it doesn't make a difference which demo you take.
It was one of those nights where I didn't want to do homework and was bored beyond belief.
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# 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
attr_accessor :forcing
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[x].score
y = 2 * x
if @open_set[2 * x + 1].score <= @open_set[y].score
y = 2 * x + 1
end
end
# If only one child exists
elsif 2 * x < @open_set.size &&
@open_set[2 * x].score <= @open_set[x].score
y = 2 * x
end
# Swap a child if it is less than the parent.
break if x == y
temp = @open_set[x]
@open_set[x] = @open_set[y]
@open_set[y] = temp
}
# Return the original first node (which was removed)
return current
end
def direction(x1, y1, x2, y2)
# Return the numerical direction between coordinates.
return 6 if x1 > x2 # Right
return 4 if x1 < x2 # Left
return 2 if y1 > y2 # Bottom
return 8 if y1 < y2 # Top
return 0
end
def neighbor_nodes(node)
# Create array to hold the nodes, then check each direction.
nodes = []
nodes.push(get_neighbor(node.x + 1, node.y, node)) # Right
nodes.push(get_neighbor(node.x - 1, node.y, node)) # Left
nodes.push(get_neighbor(node.x, node.y + 1, node)) # Down
nodes.push(get_neighbor(node.x, node.y - 1, node)) # Up
# Remove any nil elements, then return results.
return nodes.compact
end
def get_neighbor(x, y, parent)
# Calculate direction, return new node if passable.
direction = direction(x, y, parent.x, parent.y)
if @character.passable?(parent.x, parent.y, direction)
# The heuristic is simply the distance
heuristics = ((x - @goal.x).abs + (y - @goal.y).abs)
return Node.new(x, y, parent, parent.cost + 1, heuristics)
end
end
def can_skip?(node)
# Branch by if node is in either the open or closed set.
if @open_set.include?(node)
index = @open_set.index(node)
return true if @open_set[index].score <= node.score
# Swap them and update list order
@open_set[index] = node
arrange(index)
return true
elsif @close_set[[node.x, node.y]] != nil
# If the existing passed node has a lower score than this one.
return true if @close_set[[node.x, node.y]].score <= node.score
# Update the existing node
@close_set[[node.x, node.y]] = node
end
# Return false if no criteria was met.
return false
end
end
#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
attr_accessor :paths
attr_accessor :move_route_forcing
attr_accessor :move_route
alias zer0_pathfinding_init initialize
def initialize
# Add public instance variable for paths
@paths = []
# Original method
zer0_pathfinding_init
end
def next_route
# Stop any custom move route that may be occuring.
if @move_route != nil
# Set index and disable forcing of current route
@move_route_index = @move_route.list.size
@move_route_forcing = false
# Reset to what it was originally
@move_route = @original_move_route
@move_route_index = @original_move_route_index
@original_move_route = nil
end
# Remove first path from the paths array.
@paths.shift
# If there is another path to follow...
if @paths[0] != nil
# Setup path again to reflect any changes since original creation
@paths[0].forcing = false
@paths[0].setup(@paths[0].target, @paths[0].range,
@paths[0].success_proc, @paths[0].failure_proc)
force_move_route(@paths[0].route) if @paths[0].found
end
end
alias zer0_recalculate_paths_move move_type_custom
def move_type_custom
if $game_map.recalculate_paths
# Interrupt if not stopping
return if jumping? || moving?
# Loop until finally arriving at move command list
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
# 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
# If there was a path to follow and we reached goal
if @paths[0] != nil
if self.x == @paths[0].goal.x &&
y == @paths[0].goal.y && @paths[0].success_proc
# Call success Proc if goal is reached and it is defined.
@paths[0].success_proc.call
end
next_route
end
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 then move_down # Move down
when 2 then move_left # Move left
when 3 then move_right # Move right
when 4 then move_up # Move up
when 5 then move_lower_left # Move lower left
when 6 then move_lower_right # Move lower right
when 7 then move_upper_left # Move upper left
when 8 then move_upper_right # Move upper right
when 9 then move_random # Move random
when 10 then move_toward_player # Move toward player
when 11 then move_away_from_player # Move away from player
when 12 then move_forward # Step forward
when 13 then move_backward # Step backward
when 14 then jump(command.parameters[0], command.parameters[1]) # Jump
end
# If movement failure occurs when "Ignore If Can't Move" is unchecked.
if !@move_route.skippable && !moving? && !jumping?
# If path is current and collision limit is not reached
if @paths[0] != nil &&
@paths[0].collisions < $game_map.collision_retry
# Setup path again to update starting location.
# original goal node is used because pathfinding changes
# the goal node to current node
goal, range = @paths[0].target, @paths[0].range
reach = @paths[0].success_proc
fail = @paths[0].failure_proc
counter = @paths[0].collisions + 1
# Find another path to goal
@paths[0] = Pathfind.new(goal, self, range, reach, fail)
@paths[0].collisions = counter
force_move_route(@paths[0].route) if @paths[0].found
# Wait a bit before starting to follow the new path
@wait_count = 6
return
elsif paths[0] != nil
# Call failure Proc if defined and set move index.
@move_route_index = @move_route.list.size
@paths[0].failure_proc.call if @paths[0].failure_proc != nil
next_route
end
# End method
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 then turn_down # Turn down
when 17 then turn_left # Turn left
when 18 then turn_right # Turn right
when 19 then turn_up # Turn up
when 20 then turn_right_90 # Turn 90° right
when 21 then turn_left_90 # Turn 90° left
when 22 then turn_180 # Turn 180°
when 23 then turn_right_or_left_90 # Turn 90° right or left
when 24 then turn_random # Turn at Random
when 25 then turn_toward_player # Turn toward player
when 26 then turn_away_from_player # Turn away from player
end
@move_route_index += 1
return
end
# 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 then @move_speed = command.parameters[0] # Change speed
when 30 then @move_frequency = command.parameters[0] # Change freq
when 31 then @walk_anime = true # Move ON
when 32 then @walk_anime = false # Move OFF
when 33 then @step_anime = true # Stop ON
when 34 then @step_anime = false # Stop OFF
when 35 then @direction_fix = true # Direction ON
when 36 then @direction_fix = false # Direction OFF
when 37 then @through = true # Through ON
when 38 then @through = false # Through OFF
when 39 then @always_on_top = true # On top ON
when 40 then @always_on_top = false # On top OFF
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 then @opacity = command.parameters[0] # Change Opacity
when 43 then @blend_type = command.parameters[0] # Change Blending
when 44 then $game_system.se_play(command.parameters[0]) # Play SE
when 45 then result = eval(command.parameters[0]) # Script
end
# Increment move index.
@move_route_index += 1
end
end
else
# Original method
zer0_recalculate_paths_move
end
end
end
#==============================================================================
# ** Node
#==============================================================================
class Node
attr_accessor :x
attr_accessor :y
attr_accessor :parent
attr_accessor :cost
attr_accessor :heuristic
def initialize(x, y, parent = nil, cost = 0, heuristic = 0)
# Set public instance variables.
@x, @y, @parent, @cost, @heuristic = x, y, parent, cost, heuristic
end
def score
# Return the current "score" of this node
return @cost + @heuristic
end
def in_range?(node, range)
# Return true/false if Nodes are within RANGE of each other.
return (@x - node.x).abs + (@y - node.y).abs <= range
end
def ==(node)
# Returns true/false of whether self and other are equal.
return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
end
end
The solution was actually a lot easier than I expected it to be. Namely this, found under Game_Character in the method
next_route:
Which confused me since Game_Character doesn't even have this instance variable. But class Pathfinding did, which I think was the original intention. Thus I did this:
@paths[0].forcing = false
and then turning
:forcing into an attr_accessor. To my surprise, it looked like it worked. I honestly did not expect that at all. Sorry Blizz. :\
I tinkled a bit around with it and I realized that the way the code is structured, it would require lots of changes in order to fix that problem as it is a conceptual problem. But maybe KK20 is right and this is actually all that needs to be done.
Since I actually already decided to take the code of the path finder from Blizz-ABS and make a separate script and I'm mostly done with it already (took about an hour and a half so far and I only need to set up the demo properly and implement persistent path calculation), I'll finish this script anyway. Terv can decide who gets the money.
1. I love boring homework!
2. The 'Stack level too deep' is fixed now, and approaching events actually stop now at the player.
3. However they do not seem to update their target x/y often enough anymore, just running to one (outdated) player.x/y after the other. Here's a demo (http://ubuntuone.com/0Z2GzZhnDl3r3VSP4KTsVW) of it.
Then I guess my path finder will do the proper work after all. :)
EDIT: Here you go: http://forum.chaos-project.com/index.php/topic,12851.0
I'll be expecting the money then. :naughty: