ForeverZer0's Pathfinding Advanced

[DerVVulfman]

ForeverZer0's Pathfinding Advanced
Version: 1.0r

Introduction
This is an advanced an highly inteligent 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 relalatively complex areas, and asjust 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 Proc Class defined callbacks can be given to have something execute if when the character reaches its goal, or when it fails to do so.
  
• Compatible Near Fantastica Pathfinding v1 methods included:
  • find_path(x, y)
    
  • clear_path

Screenshots
None. Its characters moving around the screen.



Demo
None.



Script

The Header and Instructions

Code:

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# ForeverZer0's Pathfinding Advanced
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# By DerVVulfman
# Based on the works of ForeverZer0
# Version: 1.0r
# Date: 02.18.2025 (MM/DD/YYYY)
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#                     >   INTRODUCTION AND HEADER PAGE   <
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# INTRODUCTION:
# =============
#   This is an advanced an highly inteligent 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 co-
#   ordinates.  The system is smart enough to quickly find paths through rela-
#   latively complex areas,  and asjust 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.
#   - Compatible Near Fantastica Pathfinding v1 methods included:
#      - find_path(x,y)
#      - clear_path
#
#
# = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#
# INSTALLATION:
# =============
#   - Place script below default scripts, and above "Main".
#
#
# = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#
# INSTRUCTIONS:
# =============
#
#   - The system is used by way of Script Calls, and there are five varieties
#     of note:
#    
#     Script Call: Pathfind
#     ---------------------
#     To actively execute pathfinding, use the following script call:
#
#     SYNTAX: pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#             --or--
#             self.pathfind(X, Y)
#             --or--
#             self.find_path(X, Y)
#            
#             * The latter two used within Game_Character and only deals with
#               the specific character influenced (usable by Move Routes) and
#               only permits the defined value settings. No custom ranges nor
#               callbacks are passed.
#              
#     < Parameters>
#     * X:            The x-coordinate / destination from which to pathfind
#     * Y:            The y-coordinate / destination from which to pathfind
#     * CHARACTER:    (Optional) The event or character to move
#     * RANGE:        (Optional) How close to the destination for a success
#     * SUCCESS_PROC: (Optional) The process executed if the destination reached
#     * FAILURE_PROC: (Optional) The process executed if pathfinding failed
#
#     Of the above, only the x and y values are required. The other parameters
#     have default settings, and are described more in detail below:
#
#     CHARACTER:    (Default: $game_player) This defines the object under the
#                   influence of the pathfinding system. It may be the player,
#                   an event ($game_map.events[id], etc.), or the ID of an
#                   event on the current map.  Use -1 for the Game Player.
#
#     SUCCESS_PROC: (Default: nil) A Proc (procedure) object that is executed
#                   when the player,  event or character reaches its destina-
#                   tion. It expected that the Proc was defined  before the
#                   pathfind command was executed.
#
#     FAILURE_PROC: (Default: nil) A Proc object that will be executed if the
#                   player, event or character fails to reach its destination
#                   and has gone through its alloted number of retries. For
#                   more information, see Script Call: Retries.
#
#        Example:
#        + - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
#        |  @>Script: def create_proc                              |
#        |          :   Proc.new                                   |
#        |          : end                                          |
#        |          : a_proc = create_proc { p "I win" }           |
#        |          : b_proc = create_proc { p "I lose" }          |
#        |          : pathfind 17, 4, 1, 0, a_proc, b_proc         |
#        |  @>Event Erase                                          |
#        |  @>                                                     |
#        + - - - - - - - - - - - - - - - - - - - - - - - - - - - - +
#
#     The above example shows the quick generation of two procedures. The first
#     procedure (a_proc) will print the words "I win" when executed, and the
#     second procedure (b_proc) will instead display the words "I lose".
#
#     After that, I execute a pathfind call that will move an event to the
#     coordinates of (17,4). the event is event #1, and it must actually
#     reach and be at the coordinates as there is 0 leeway in the range...
#     ... ergo 17, 4, 1, 0  (x, y, event_id, range)
#
#     The last two values assigned are the procedures to be called, a_proc
#     is the "I win" procedure that will execute if the event actually reaches
#     its destination. Need I say more?
#    
#     Okay, more.   You can set the SUCCESS_PROC to nil and have a FAILURE_PROC
#     if you only want a procedure to execute on failure.
#
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
#     Script Call: Clear Path
#     --------------------
#   - In order  to abruptly halt the movement  of an event controlled  by the
#     pathfinding system, you may use the following script call:
#
#     SYNTAX: clear_path(CHARACTER)
#             --or--
#             self.clear_path
#            
#             * The latter used within Game_Character and only deals with the
#               specific character influenced (usable by Move Routes).
#
#     < Parameters>
#     * CHARACTER:    (Default: $game_player) This defines the object under the
#                     influence of the pathfinding system. It may be the player,
#                     an event ($game_map.events[id], etc.), or the ID of an
#                     event on the current map.  Use -1 for the Game Player.
#
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
#     Script Call: Retries
#     --------------------
#   - By default, the pathfinder will make 35 attempts to recalculate a route
#     that gets blocked. This value can be changed in game by the script call:
#
#     SYNTAX: pathfind_retries(NUMBER)
#
#     < Parameters>
#     * NUMBER:       (Default: 35) The number of retries before it fails
#
#     This script call will allow you to set the number of retries possible
#     before the system considers the pathfinding attempt to be a failure.
#
#     As it has a default value, just running "pathfind_retries" alone will
#     reset the number of retries back to 35.
#
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
#     Script Call: Range
#     --------------------
#   - For longer pathfind routes, it is sometimes necessary to increase the
#     pathfind system's range. 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:
#
#     SYNTAX: pathfind_range(NUMBER)
#
#     < Parameters>
#     * NUMBER:       (Default: 1000) The number of steps needed for travel
#
#     As it has a default value, just running "pathfind_range" alone will
#     reset the steps/range back to 1000.
#
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
#     Script Call: Enhanced
#     --------------------
#   - Normally, the pathfinding system runs in an enhanced mode that allows
#     for a more efficient means to recalculate collisions if the pathway
#     suddenly becomes blocked. However, if you run into problems, it can
#     be turned off with the below script call:
#
#     SYNTAX: pathfind_enhanced(BOOLEAN)
#
#     < Parameters>
#     * BOOLEAN:      (Default: true) A boolean (or true/false) value
#
#     As it has a default value, just running "pathfind_enhanced" alone will
#     turn enhanced mode back on.
#
#
# = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#
# COMPATIBILITY:
# ==============
#   Designed for RPGMaker XP.  Consistent with Ruby 2.7 Coding Standards.
#   Highly compatible. May experience issues with Custom Movement scripts,
#   but even then, it is unlikely.
#
#
# = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#
# CREDITS/THANKS:
# ===============
#   - ForeverZer0, for the original 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
#
#
# = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
#
# TERMS and CONDITIONS:
# =====================
#   Free for use, even in commercial scripts. However, I require due credit for
#   myself and all others listed in Credits/Thanks.
#
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+

The Engine Code

Code:

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# ForeverZer0's Pathfinding Advanced
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
# By DerVVulfman
# Based on the works of ForeverZer0
# Version: 1.0
# Date: 02.18.2025 (MM/DD/YYYY)
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#                             >      ENGINE      <
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+


#==============================================================================
# ** Game_Map
#------------------------------------------------------------------------------
#  This class handles the map. It includes scrolling and passable determining
#  functions. Refer to "$game_map" for the instance of this class.
#==============================================================================

class Game_Map

  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :collision_retry          # Number of tries before path fails
  attr_accessor :recalculate_paths        # Flag if enhanced re-pathing is on
  attr_accessor :search_limiter           # The steps range for travel distance
  attr_accessor :clear_item               # map character halted in pathfinding

  #--------------------------------------------------------------------------
  # * Alias Listings
  #--------------------------------------------------------------------------
  alias zer0_pathfinding_init initialize

  #--------------------------------------------------------------------------
  # * Object Initialization
  #--------------------------------------------------------------------------
  def initialize
    #
    # Initialize instance variables used for pathfinding.
    @collision_retry      = 35
    @recalculate_paths    = true
    @search_limiter       = 1000
    @clear_item           = nil
    #
    # Perform the original method
    zer0_pathfinding_init
    #
  end

end



#==============================================================================
# ** Interpreter
#------------------------------------------------------------------------------
#  This interpreter runs event commands. This class is used within the
#  Game_System class and the Game_Event class.
#==============================================================================

class Interpreter

  #--------------------------------------------------------------------------
  # * Pathfind
  #     x            : x-coordinates
  #     y            : y-coordinats
  #     character    : (optional) instance or ID of a game-map event/character
  #     range        : (optional) How close to target location needed  
  #     success_proc : (optional) Procedure run when the destination is reached
  #     fail_proc    : (optional) Procedure run when the destination is blocked
  #--------------------------------------------------------------------------
  def pathfind(x, y, *args)
    #
    # Ensure arguments passed are valid
    args[0] = @event_id   if args[0].nil?
    args[1] = 0           if args[1].nil?
    #
    # Create the instance of the target's Pathfind object (simpler script call)
    Pathfind.new(Node.new(x, y), *args)
    #
  end

  #--------------------------------------------------------------------------
  # * Clear the path
  #     x            : x-coordinates
  #     y            : y-coordinats
  #     character    : (optional) instance or ID of a game-map event/character
  #--------------------------------------------------------------------------
  def clear_path(char = -1)
    #
    # 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
    #
    # Pass value into Game_Map instance variable
    $game_map.clear_item = @character
    #
  end

  #--------------------------------------------------------------------------
  # * Pathfind system retries permitted
  #     value : (default:35) Times pathfinding is attempted before fail
  #--------------------------------------------------------------------------  
  def pathfind_retries(value=35)
    #
    # Ensure only integer values allowed
    return if value.nil?
    return unless value.is_a?(Integer)
    #
    # Ensure values are in valid range
    return if value < 1
    return if value > 100
    #
    # Pass value into Game_Map instance variable
    $game_map.collision_retry = value
    #
  end

  #--------------------------------------------------------------------------
  # * Pathfind System Enhanced
  #     value : (default:true) If pathfinding is in enhanced mode
  #--------------------------------------------------------------------------  
  def pathfind_enhanced(value=true)
    #
    # Ensure only true/false (boolean) values are passed
    return unless value.is_a?(TrueClass) || value.is_a?(FalseClass)
    #
    # Pass value into Game_Map instance variable
    $game_map.recalculate_paths = value
    #
  end

  #--------------------------------------------------------------------------
  # * Pathfind system range in steps
  #     value : (default:1000) Range or number of steps for a calculated path
  #--------------------------------------------------------------------------  
  def pathfind_range(value=1000)
    #
    # Ensure only integer values allowed
    return if value.nil?
    return unless value.is_a?(Integer)
    #
    # Ensure values are in valid range
    return if value < 1
    return if value > 5000
    #
    # Pass value into Game_Map instance variable
    $game_map.search_limiter = value
    #
  end

end



#==============================================================================
# ** Pathfind
#------------------------------------------------------------------------------
#  This class handles the point-to-point navigation system.  It observes the
#  Game_Character class and is used within the Game_Event class ($game_event).
#==============================================================================

class Pathfind

  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_reader   :route                    # Move Route
  attr_accessor :range                    # How close to target location needed
  attr_reader   :goal                     # Destination node used for comparison
  attr_reader   :found                    # Ssuccess flag
  attr_reader   :character                # Subject character on map                  
  attr_accessor :success_proc             # procedure to be called on success
  attr_accessor :failure_proc             # procedure to be called on failure
  attr_accessor :target                   # Final destination node
  attr_accessor :collisions               # Number of collision retry attempts
  
  #--------------------------------------------------------------------------
  # * Object Initialization
  #     node      : Destination node location for pathrfinding
  #     char      : (optional) instance or ID of a game-map event/character
  #     range     : (optional) Default 0: How close to target location needed
  #     callbacks : (optional) Procedures run when the path is reahed/failed
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # * Setup
  #     node      : Destination node location for pathrfinding
  #     range     : (optional) Default 0: How close to target location needed
  #     callbacks : (optional) Procedures run when the path is reahed/failed
  #--------------------------------------------------------------------------
  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 to Game Player if no character exists
    @character = $game_player if @character.nil?
    #
    # 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

  #--------------------------------------------------------------------------
  # * Calculate path to target
  #--------------------------------------------------------------------------
  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?
        # Increase count
        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

  #--------------------------------------------------------------------------
  # * Create move route
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # * Arrange pathfinding nodes
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # * Get Current Node
  #--------------------------------------------------------------------------
  def get_current
    #
    # Exit method if no nodes present in the set or if set reduced to 1
    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

  #--------------------------------------------------------------------------
  # * Get event's facing direction as numeric value (2,4,6,8,0)
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # & Check neighboring nodes
  #--------------------------------------------------------------------------
  def neighbor_nodes(node)
    #
    # Create array to hold the nodes
    nodes = []
    #
    # Check each direction.
    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

  #--------------------------------------------------------------------------
  # * Get neighboring node
  #     x      : x-coordinate of pathfind destination
  #     y      : y-coordinate of pathfind destination
  #     parent : parent event/character moving to destination
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # * Get if the scope be skipped?
  #     node ; Node
  #--------------------------------------------------------------------------
  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
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#==============================================================================

class Game_Character

  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :paths                    # pathfinding array
  attr_accessor :move_route_forcing       # forced move route flag
  attr_accessor :move_route               # move route

  #--------------------------------------------------------------------------
  # * Alias Listings
  #--------------------------------------------------------------------------
  alias zer0_pathfinding_init initialize
  alias zer0_recalculate_paths_move move_type_custom

  #--------------------------------------------------------------------------
  # * Object Initialization
  #--------------------------------------------------------------------------
  def initialize
    #
    # Add public instance variable for paths
    @paths = []
    #
    # Original method
    zer0_pathfinding_init
    #
  end

  #--------------------------------------------------------------------------
  # * Move Type : Custom
  #--------------------------------------------------------------------------
  def move_type_custom
    #
    # If Game_Map has a flagged character whose move route is to clear
    unless $game_map.clear_item.nil?
      # Clear the move route and reset if the character is self
      if $game_map.clear_item  == self
        move_type_clear
        $game_map.clear_item = nil
      end
    end
    #
    # Execute pathfinder version of custom if paths exist and can recalculate
    return move_type_pathfinder if $game_map.recalculate_paths && @paths != []
    #
    # Exit method if no move route or list
    return if @move_route.nil?
    return if @move_route.list.nil?
    #
    # Original method
    zer0_recalculate_paths_move
    #
  end

  #--------------------------------------------------------------------------
  # * Pathfind for Self Character
  #     x            : x-coordinates
  #     y            : y-coordinats
  #--------------------------------------------------------------------------
  def pathfind(x, y)
    #
    # Exit if invalid
    return if self.nil?
    #
    # Process Pathfind call
    Pathfind.new(Node.new(x, y), self.id)
    #
  end

  #--------------------------------------------------------------------------
  # * Find Path for Self Character (method name used by Near Fantastica V1)
  #     x            : x-coordinates
  #     y            : y-coordinats
  #--------------------------------------------------------------------------
  def find_path(x, y)
    #
    # Exit if invalid
    return if self.nil?
    #
    # Process Pathfind call
    Pathfind.new(Node.new(x, y), self.id)
    #
  end

  #--------------------------------------------------------------------------
  # * Clear Path for Self Character (method name used by Near Fantastica V1)
  #--------------------------------------------------------------------------
  def clear_path
    #
    # Exit if invalid
    return if self.nil?
    #
    # Pass self into Game_Map instance variable
    $game_map.clear_item = self
    #
  end

  #--------------------------------------------------------------------------
  # * Clear the move route
  #--------------------------------------------------------------------------
  def move_type_clear
    #
    @paths                      = []    
    @move_route                 = nil
    @move_route_index           = 0
    @original_move_route        = nil
    @original_move_route_index  = 0
    #
  end

  #--------------------------------------------------------------------------
  # * Next Route
  #--------------------------------------------------------------------------
  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

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding
  #--------------------------------------------------------------------------
  def move_type_pathfinder
    #
    # Interrupt if not stopping
    return if jumping? || moving?
    #
    # Exit if no valid move route or list
    return if @move_route.nil?
    return if @move_route.list.nil?
    #
    # 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
        # Reset the move route index to the top if [repeat action] option is ON
        @move_route_index = 0 if @move_route.repeat
        # Process non-repeating move route with test for path success
        move_type_path_repeat_success
        return
      end
      #
      # For moveement commands (from move down to jump)
      if command.code <= 14
        # Perform normal movement based on command codes
        move_type_path_movements(command)
        # If movement failure occurs when "Ignore If Can't Move" is unchecked.
        if !@move_route.skippable && !moving? && !jumping?
          # Test for new path or on failure
          move_type_path_correction
          # End method
          return
        end
        # Advance index
        @move_route_index += 1
        return
        #
      end
      #
      # 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 direction change (turning) commands
      if command.code >= 16 and command.code <= 26
        # Perform facing turn
        move_type_path_turning(command)
        # Advance index
        @move_route_index += 1
        return
      end
      #
      # If other command (commands that don't 'return')
      if command.code >= 27
        # Perform all other commands in move route list
        move_type_path_other(command)
        # Increment move index.
        @move_route_index += 1
      end
      #
    end
  end

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding non-repeat move route with possible success
  #     command : move command
  #--------------------------------------------------------------------------
  def move_type_path_repeat_success
    #
    # Exit method if [repeat action] option is ON
    return if @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
      unless @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

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding with normal movement commands
  #     command : move command
  #--------------------------------------------------------------------------
  def move_type_path_movements(command)
    #
    # 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
    #
  end

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding correct path or failed
  #--------------------------------------------------------------------------
  def move_type_path_correction
    #
    # 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.
      goal      = @paths[0].target
      range     = @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
      #
    end
    #
    # 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

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding with normal turn-facing commands
  #     command : move command
  #--------------------------------------------------------------------------
  def move_type_path_turning(command)
    #
    # 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
    #
  end

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding with other move route commands
  #     command : move command
  #--------------------------------------------------------------------------
  def move_type_path_other(command)
    #
    # 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 ;  @move_speed    = command.parameters[0]     # Change speed
    when 30 ; @move_frequency = command.parameters[0]     # Change freq
    when 31 ; @walk_anime     = true                      # Move ON
    when 32 ; @walk_anime     = false                     # Move OFF
    when 33 ; @step_anime     = true                      # Stop ON
    when 34 ; @step_anime     = false                     # Stop OFF
    when 35 ; @direction_fix  = true                      # Direction ON
    when 36 ; @direction_fix  = false                     # Direction OFF
    when 37 ; @through        = true                      # Through ON
    when 38 ; @through        = false                     # Through OFF
    when 39 ; @always_on_top  = true                      # On top ON
    when 40 ; @always_on_top  = false                     # On top OFF
    when 41 ; move_type_path_graphic(command)             # Change Graphic
    when 42 ; @opacity    = command.parameters[0]         # Change Opacity
    when 43 ; @blend_type = command.parameters[0]         # Change Blending
    when 44 ; $game_system.se_play(command.parameters[0]) # Play SE
    when 45 ; result = eval(command.parameters[0])        # Script
    end
    #
  end

  #--------------------------------------------------------------------------
  # * Move Type : Pathfinding with graphic change
  #     command : move command
  #--------------------------------------------------------------------------
  def move_type_path_graphic(command)
    #
    # Can't change into a tile
    @tile_id = 0
    @character_name = command.parameters[0]
    @character_hue  = command.parameters[1]
    #
    # Update direction
    unless @original_direction == command.parameters[2]
      @direction          = command.parameters[2]
      @original_direction = @direction
      @prelock_direction  = 0
    end
    #
    # Update frame
    unless @original_pattern == command.parameters[3]
      @pattern          = command.parameters[3]
      @original_pattern = @pattern
    end
    #
  end

end



#==============================================================================
# ** Node
#------------------------------------------------------------------------------
#  This class governs traversable map points refered to within A* pathfinding
#  systems as nodes.
#==============================================================================

class Node

  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :x                        # x-coordinate to destination
  attr_accessor :y                        # y-coordinate to destination
  attr_accessor :parent                   # event/char moving to destination
  attr_accessor :cost                     # cost in distance
  attr_accessor :heuristic                # distance between nodes or goal

  #--------------------------------------------------------------------------
  # * Object Initialization
  #     x         : x-coordinate
  #     y         : y-coordinate
  #     parent    : parent event/character moving to destination
  #     cost      : cost in distance
  #     heuristic : distance between nodes or goal
  #--------------------------------------------------------------------------  
  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

  #--------------------------------------------------------------------------
  # * Get the heuristic cost score of this node
  #--------------------------------------------------------------------------  
  def score
    return @cost + @heuristic
  end

  #--------------------------------------------------------------------------
  # * Get if the node is in range of another
  #     node  : Node
  #     range : range
  #--------------------------------------------------------------------------  
  def in_range?(node, range)
    return (@x - node.x).abs + (@y - node.y).abs <= range
  end

  #--------------------------------------------------------------------------
  # * Get if a node tested is the same/self
  #--------------------------------------------------------------------------  
  def ==(node)
    return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
  end

end

Instructions
Paste Below Scene_Debug and above Main. Likely, it will need be above other scripts or script-sets that utilize pathfinding codes or algorythms.



Compatibility

Designed for RPGMaker XP. Consistent with Ruby 2.7 Coding Standards.

Highly compatible. May experience issues with Custom Movement scripts, but even then, it is unlikely.



Credits and Thanks

• ForeverZer0, for the original 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
I was asked to look into the original work as it had issues with move routes that were blocked/impeded which brought up critical errors. It pretty much involved a couple lines of code added just to exit methods before the errors occurred.

Three of the original script calls have now been passed into the Interpreter class to make it cleaner from a user's perspective. And more safeguard measures and default options were added.

And a lot of the language within the Instruction/Header page is mostly the same as the original. Only that some instructions were made clearer.



Terms and Conditions
Free for use, even in commercial scripts. However, I require due credit for myself and all others listed in Credits/Thanks.