Save-Point - ForeverZer0's Pathfinding Advanced

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.