Chaos Project

RPG Maker => RPG Maker Scripts => RMXP Script Database => Topic started by: ForeverZer0 on May 30, 2011, 04:00:31 pm

Title: [XP] Advanced Pathfinding
Post by: ForeverZer0 on May 30, 2011, 04:00:31 pm
Advanced Pathfinding
Authors: ForeverZer0
Version: 1.1
Type: Autonomous Character Movement
Key Term: Custom Movement System



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: A* Search Algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm)


Features




Screenshots

Can quickly and easily navigate a maps like these, lag-free:
Spoiler: ShowHide
(http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Maze1.png)

Spoiler: ShowHide
(http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Maze2.png)



Demo

Demo Link (http://dl.dropbox.com/u/20787370/Scripts/Advanced%20Pathfinding/Advanced%20Pathfinding.zip)


Script

Here's the script.
Spoiler: ShowHide

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# 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



Instructions

Place script below default scripts and above "Main".
Further instructions are within the script and demo.


Compatibility

Highly compatible. Only issue may be with other custom movement scripts.


Credits and Thanks




Author's Notes

Please report any bugs/issues you may encounter so they can be resolved.
Enjoy!end
Title: Re: [XP] Advanced Pathfinding
Post by: G_G on May 30, 2011, 04:05:55 pm
You're an ass. >:U I seriously was going to create this using that same algorithm.

Nice job! :)
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on May 30, 2011, 04:07:55 pm
Its the least complicated I could find. There are some straight-up confusing ones out there...
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on May 30, 2011, 05:21:55 pm
I beat you all to it. :V: *points to Blizz-ABS*
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on May 30, 2011, 05:24:35 pm
Yes, I noticed that. :P

Its still nice to have a system not dependent on another for those who don't use Blizz-ABS.
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on May 30, 2011, 05:32:51 pm
Actually it shouldn't be very much dependent on Blizz-ABS. The only part is the interpretation of the movement commands.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on February 01, 2012, 01:23:32 pm
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)
Title: Re: [XP] Advanced Pathfinding
Post by: Poe on February 01, 2012, 03:23:47 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on February 01, 2012, 05:07:26 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on February 01, 2012, 05:11:31 pm
There is a little bug I need to fix. Its pretty simple, so I'll fix it in a bit and re-upload.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on February 01, 2012, 05:24:23 pm
Great thanks :)
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on February 01, 2012, 09:22:41 pm
Fixed.
Title: Re: [XP] Advanced Pathfinding
Post by: Poe on February 02, 2012, 04:51:57 am
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?
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on February 02, 2012, 09:01:30 am
Thanks it worked.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on February 03, 2012, 12:36:16 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on March 08, 2012, 09:24:00 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on March 08, 2012, 09:56:34 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on March 09, 2012, 02:19:20 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on March 09, 2012, 06:49:02 am
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).
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on March 10, 2012, 01:39:54 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on March 10, 2012, 02:47:37 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on March 10, 2012, 05:36:10 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Vexus on March 10, 2012, 05:43:15 pm
After killing the enemy but it doesn't happen often.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 20, 2012, 08:34:22 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 20, 2012, 10:07:21 pm
Increase "$game_map.collision_retry"
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 20, 2012, 10:59:42 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 20, 2012, 11:10:00 pm
Is the destination coordinates passable the moment when the call is made?
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 20, 2012, 11:39:42 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 20, 2012, 11:49:02 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 21, 2012, 02:51:00 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 21, 2012, 12:32:53 pm
Hmmm.
Upload me your demo where it fails, and I'll see if I can find anything.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 21, 2012, 05:31:06 pm
Okie dokie.

http://www.775.net/~heretic/downloads/rmxp/PathfindBug.exe

Thank you for taking a look.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 21, 2012, 06:16:46 pm
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:
Spoiler: ShowHide
(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.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 21, 2012, 07:14:51 pm
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...
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 21, 2012, 07:40:28 pm
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.

Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on April 21, 2012, 07:58:49 pm
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())
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on April 21, 2012, 09:26:58 pm
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.

Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on April 22, 2012, 03:34:12 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on May 02, 2012, 03:32:15 am
@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?
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on May 05, 2012, 10:00:10 am
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?
Title: Re: [XP] Advanced Pathfinding
Post by: 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].

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.
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on May 16, 2012, 10:53:45 pm
You do realize that that method is the actual implementation of the A* algorithm?
Title: Re: [XP] Advanced Pathfinding
Post by: ThallionDarkshine on May 18, 2012, 10:39:20 am
Oh, sorry. I just went to the Wikipedia page and found that you needed to get the node with the lowest score.
Title: Re: [XP] Advanced Pathfinding
Post by: Heretic86 on May 29, 2012, 07:52:49 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: ThallionDarkshine on June 02, 2012, 09:36:10 pm
Alright, I'll try and see if it works.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 18, 2012, 09:53:57 am
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! :)
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on July 18, 2012, 12:12:29 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 18, 2012, 01:02:26 pm
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

OOS
OOO
EOO


So when executing this situation, then the path is the following:
OOS
OOP
EPP

So the event goes straight down and then left. I would like to see rather a diagonal pattern:

OOS
OPO
EOO


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!




Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on July 18, 2012, 05:11:36 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 18, 2012, 05:26:25 pm
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.

Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on July 18, 2012, 06:18:47 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 18, 2012, 06:21:15 pm
Great, Thank you!! I'll try it out :)
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 20, 2012, 11:36:36 am
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?
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on July 20, 2012, 03:10:10 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 20, 2012, 04:39:55 pm
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!!
Title: Re: [XP] Advanced Pathfinding
Post by: ForeverZer0 on July 20, 2012, 06:10:44 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 20, 2012, 07:26:43 pm
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!
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 20, 2012, 07:34:34 pm
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...
Title: Re: [XP] Advanced Pathfinding
Post by: 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.
Title: Re: [XP] Advanced Pathfinding
Post by: Darian on July 21, 2012, 04:57:58 pm
Yes that makes sense to me, that could be the reason!
Would be cool if you could have a look :)
Thank you!
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on January 27, 2013, 04:00:06 pm
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:



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.
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on January 27, 2013, 04:49:52 pm
Didn't F0 fix that problem already? Or wasn't there at least some kind of workaround?
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on January 27, 2013, 04:56:53 pm
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)  :(
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on January 28, 2013, 02:25:49 am
Alright, who'd going to sit down and fix this?
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on January 28, 2013, 03:23:33 pm
Someone from the German forums might have a crack at it. I'll post here in case he changes his mind.
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on February 08, 2013, 01:55:43 pm
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on February 08, 2013, 02:02:12 pm
It seems that nobody at this forum likes free money.

I'll do it tomorrow.
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on February 08, 2013, 02:32:36 pm
Pure awesomeness. No, it doesn't make a difference which demo you take.
Title: Re: [XP] Advanced Pathfinding
Post by: KK20 on February 09, 2013, 02:33:26 am
It was one of those nights where I didn't want to do homework and was bored beyond belief.
Spoiler: ShowHide

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# 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:
@forcing = false

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. :\
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on February 09, 2013, 05:54:46 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Terv on February 09, 2013, 06:00:11 am
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.
Title: Re: [XP] Advanced Pathfinding
Post by: Blizzard on February 09, 2013, 06:26:01 am
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: