[XP] Advanced Pathfinding

Started by ForeverZer0, May 30, 2011, 04:00:31 pm

Previous topic - Next topic

ForeverZer0

May 30, 2011, 04:00:31 pm Last Edit: February 01, 2012, 09:22:20 pm by ForeverZer0
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


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.




Screenshots

Can quickly and easily navigate a maps like these, lag-free:
Spoiler: ShowHide

Spoiler: ShowHide



Demo

Demo Link


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


  • 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 Notes

Please report any bugs/issues you may encounter so they can be resolved.
Enjoy!end
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

G_G

You're an ass. >:U I seriously was going to create this using that same algorithm.

Nice job! :)

ForeverZer0

Its the least complicated I could find. There are some straight-up confusing ones out there...
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Blizzard

I beat you all to it. :V: *points to Blizz-ABS*
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

ForeverZer0

Yes, I noticed that. :P

Its still nice to have a system not dependent on another for those who don't use Blizz-ABS.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Blizzard

Actually it shouldn't be very much dependent on Blizz-ABS. The only part is the interpretation of the movement commands.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Vexus

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)
Current Project/s:

Poe

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.

Vexus

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.
Current Project/s:

ForeverZer0

There is a little bug I need to fix. Its pretty simple, so I'll fix it in a bit and re-upload.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Vexus

Current Project/s:

ForeverZer0

I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Poe

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?

Vexus

Current Project/s:

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Vexus

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.
Current Project/s:

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Blizzard

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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Vexus

This is what I placed in the event:



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).
Current Project/s:

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Vexus

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.
Current Project/s:

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Vexus

After killing the enemy but it doesn't happen often.
Current Project/s:

Heretic86

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.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

Increase "$game_map.collision_retry"
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

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.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

Is the destination coordinates passable the moment when the call is made?
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

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.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

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.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

Hmmm.
Upload me your demo where it fails, and I'll see if I can find anything.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

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


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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

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...
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

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 am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Heretic86

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())
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ForeverZer0

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 am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Blizzard

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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Heretic86

@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?
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

Heretic86

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?
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ThallionDarkshine

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.

ForeverZer0

You do realize that that method is the actual implementation of the A* algorithm?
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

ThallionDarkshine

Oh, sorry. I just went to the Wikipedia page and found that you needed to get the node with the lowest score.

Heretic86

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.
Current Scripts:
Heretic's Moving Platforms

Current Demos:
Collection of Art and 100% Compatible Scripts

(Script Demos are all still available in the Collection link above.  I lost some individual demos due to a server crash.)

ThallionDarkshine

Alright, I'll try and see if it works.

Darian

July 18, 2012, 09:53:57 am #45 Last Edit: July 18, 2012, 09:55:00 am by Darian
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! :)

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

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!





ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

July 18, 2012, 05:26:25 pm #49 Last Edit: July 18, 2012, 06:18:31 pm by Darian
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.


ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

Great, Thank you!! I'll try it out :)

Darian

July 20, 2012, 11:36:36 am #52 Last Edit: July 20, 2012, 11:46:38 am by Darian
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?

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

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!!

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

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!

Darian

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...

ForeverZer0

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.
I am done scripting for RMXP. I will likely not offer support for even my own scripts anymore, but feel free to ask on the forum, there are plenty of other talented scripters that can help you.

Darian

Yes that makes sense to me, that could be the reason!
Would be cool if you could have a look :)
Thank you!

Terv

January 27, 2013, 04:00:06 pm #60 Last Edit: January 27, 2013, 04:34:27 pm by Terv
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 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.

Blizzard

Didn't F0 fix that problem already? Or wasn't there at least some kind of workaround?
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Terv

January 27, 2013, 04:56:53 pm #62 Last Edit: January 27, 2013, 05:10:23 pm by Terv
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)  :(

Blizzard

Alright, who'd going to sit down and fix this?
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Terv

January 28, 2013, 03:23:33 pm #64 Last Edit: February 08, 2013, 01:55:07 pm by Terv
Someone from the German forums might have a crack at it. I'll post here in case he changes his mind.

Terv

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 for the description of the bug.

Blizzard

It seems that nobody at this forum likes free money.

I'll do it tomorrow.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Terv

Pure awesomeness. No, it doesn't make a difference which demo you take.

KK20

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. :\

Other Projects
RPG Maker XP Ace  Upgrade RMXP to RMVXA performance!
XPA Tilemap  Tilemap rewrite with many features, including custom resolution!

Nintendo Switch Friend Code: 8310-1917-5318
Discord: KK20 Tyler#8901

Join the CP Discord Server!

Blizzard

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.
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.

Terv

February 09, 2013, 06:00:11 am #70 Last Edit: February 09, 2013, 06:01:25 am by Terv
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 of it.

Blizzard

February 09, 2013, 06:26:01 am #71 Last Edit: February 09, 2013, 09:23:06 am by Blizzard
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:
Check out Daygames and our games:

King of Booze 2      King of Booze: Never Ever
Drinking Game for Android      Never have I ever for Android
Drinking Game for iOS      Never have I ever for iOS


Quote from: winkioI do not speak to bricks, either as individuals or in wall form.

Quote from: Barney StinsonWhen I get sad, I stop being sad and be awesome instead. True story.