Ruby Quellcode

#==============================================================================
# ** A* Pathfinding Script
#------------------------------------------------------------------------------
#  Script by            :   RPG (aka Cowlol)
#  Last Update          :   September 26th, 2008
#  Version              :   1.4
#  Contact Information  :   ArePeeGee on AIM
#------------------------------------------------------------------------------
#  A relatively efficient implementation of the A* pathfinding algorithm.
# For more information on A*, check the following links:
#     1. http://www.policyalmanac.org/games/aStarTutorial.htm
#     2. http://www-cs-students.stanford.edu/~amitp/gameprog.html
#------------------------------------------------------------------------------
# Usage:
#
#   First you have to add this script somewhere under the default scripts
#   (and above main), I assume you know how to add a new script section and 
#   paste this script there. I don't know much about the SDK thing, but I 
#   don't think you'll get any trouble when using this scripts with others.
#   Note that this script overwrites the move_type_custom method of the
#   Game_Character class, any other script that modifies that method 
#   might clash with this one.
#
#   Now, simply create a new instance of the A_Star_Pathfinder class and 
#   supply it with the required parameters. For example, to have the player
#   move to tile (x, y), you could  add a script command to a new event
#   page and type something like:
#
#       goal_node = Node.new(x, y)             
#       path = A_Star_Pathfinder.new(goal_node)
#
#   The constructor can take more information, such as the character
#   that will move according to the result of pathfinding (Game_Character, 
#   map event ID, or -1 for player (default)), and whether the character 
#   should follow the path right away (true by default, if you set it to 
#   false, you'll have to call generate_path yourself). 
#   Here's another example of usage:
#
#       node = Node.new(x, y)
#       char = event_id         # same as char = $game_map.events[event_id]
#       path = A_Star_Pathfinder.new(node, char, false)
#       # do other stuff
#       path.generate_path      # and then generate the path
#
#   As an alternative, you can call the constructor without parameters,
#   and call the setup, calculate_path, and generate_path manually.
#   This gives you more control because the setup method allows you to
#   specify more options such as methods to call when the path is
#   reached or couldn't be found (implemented as Proc objects). 
#   You can also specify size of the goal area instead of looking for only 
#   one tile, and indicate whether the character should get as close as 
#   possible to goal if no path was found. Here's an example of such usage:
#
#     path = A_Star_Pathfinder.new
#     goal = Node.new(1, 0)
#     char = $game_player
#     range = 1
#     get_close = true
#     # lambda creates Procs, an alternative is Proc.new { ... }
#     reach = lambda { p "REACHD GOAL!!!" }
#     fail = lambda { p "COULDN'T FIND PATH!!!" }
#     path.setup(goal, char, range, get_close, reach, fail)
#     path.calculate_path
#     path.generate_path
#
#   If you used earlier versions of this script, you were able to supply
#   a limit on the number of pathfinding iterations performed (in case
#   you don't want the script to run for too long); this is now specified
#   by manually changing the constant ITERATION_LIMIT in A_Star_Pathfinder
#   class. A value of -1 (default) means no such limit is used.
#
#   Another interesting constant is COLLISION_WAIT, which is set to 5 by
#   default. This constant controls a feature that allows the character
#   to generate a new path if it was interrupted when following a path.
#   For example, a path might have been generated but as the character
#   was following it another character moved to block the path, setting
#   COLLISION_WAIT to any value bigger than -1 forces the generation of
#   another path to get around blocking characters, with the value of
#   the constant used to add some waiting between such attempts.
#
#   A related constant is COLLISION_LIMIT which imposes a limit on the
#   maximum number of times the character should try to find a new path
#   in case of collision, this is important because rare map design
#   and event movement conditions could result in the character stuck
#   trying to generate new paths forever. If you don't care for that,
#   you could set it to -1 to disregard the limit.
#
#   Starting with version 1.4, characters could be supplied with
#   multiple paths. Once the first path is reached or couldn't be
#   found, the next path is generated and followed, and so on. 
#   If you'd rather new paths were followed immediately instead of
#   waiting for current path to be followed, you'll have to stop
#   all pending paths by calling the stop_all_paths method on the
#   character and then creating the new path. You could also just
#   stop following the current path by calling the stop_path method.
#
#------------------------------------------------------------------------------
# Version Information:
#   - Version 1.4:
#       - Characters can now follow multiple paths. Generating another
#         path while character is following a path adds the new path
#         to a list so that it would be followed after all pending paths
#         were followed, instead of overwriting current path.
#       - Characters now get stop_path and stop_all_paths methods to
#         stop following current path and follow the next one in the
#         list, and to stop all paths and empty the list. stop_all_paths
#         could be used to imitate the old behavior of overwriting
#         current path and following new one immediately.
#       - Fixed various bugs caused by the introduction of multiple paths.
#       - You can now supply integer values in place of Game_Character,
#         the value is the event map ID or -1 for the player character.
#   - Version 1.3:
#       - Changed collision_wait and limit variables to COLLISION_WAIT
#         and ITERATION_LIMIT constants that are changed manually in
#         the script and that apply to all pathfinding. I think this
#         makes the script neater.
#       - Added a COLLISION_LIMIT constant to control number of path-
#         finding attempts on collision.
#       - Added the ability to specify a goal area instead of single node,
#         this is achieved by supplying the setup method with a range of
#         tiles around the goal, with 0 (the default) disabling that
#         feature. Pathfinding succeeds as soon as a tile within the
#         goal's range (see in_range? method) is found.
#       - Character can now try to get as close as possible to tile
#         if a path wasn't found.
#       - Switched to a zlib/libpng license for terms of use, which
#         is mostly a more formal version of the old terms.
#   - Version 1.2:
#       - Fixed a recursive bug with tiles with directional passability,
#         thanks to Twin Matrix for pointing it out!
#       - Removed the cache pass feature because it was useless.
#   - Version 1.1:
#       - Added a mechanism to prevent the generated path from being
#         blocked by other characters. When such a collision happens,
#         the character will try to generate a new path to goal. This
#         can be turned off if you set collision_wait to -1
#       - Now you can provide blocks to be called when the path is
#         reached or if no path is found.
#       - Added the cache pass flag to allow generating passability
#         information in a Table for faster access. This was inspired
#         by a post by Anaryu at 
#         http://www.rmxp.org/forums/showthread.php?t=16589
#       - Better documentation
#   - Version 1.0:
#       - Initial release version.
#------------------------------------------------------------------------------
# Known bugs:
#
#   - Slower than Eivien's pathfinder at:
#       http://www.rmxp.org/forums/showthread.php?t=24242
#     this is not really a bug but I'm interested in learning more
#     about efficient implementations of A*.
#   - Found a bug or have some ideas for the next version? Tell me on AIM!
#------------------------------------------------------------------------------
# Terms of Use:
#
#   I'm releasing this script under a zlib/libpng license which means
#   you can use it any way you like as long as you don't claim it as
#   your own and keep the following notice unchanged. If you have any
#   questions or problems regarding this script, feel free to contact me.
#
#   Copyright (c) 2007 Firas Assad
#
#   This software is provided 'as-is', without any express or implied
#   warranty. In no event will the authors be held liable for any damages
#   arising from the use of this software.
#
#   Permission is granted to anyone to use this software for any purpose,
#   including commercial applications, and to alter it and redistribute it
#   freely, subject to the following restrictions:
# 
#   1.  The origin of this software must not be misrepresented; you must 
#       not claim that you wrote the original software. If you use this 
#       software in a product, an acknowledgment in the product 
#       documentation would be appreciated but is not required.
#
#   2.  Altered source versions must be plainly marked as such, and 
#       must not be misrepresented as being the original software.
#
#   3.  This notice may not be removed or altered from any 
#       source distribution.
#
#
#==============================================================================
 
#==============================================================================
# ** Node
#------------------------------------------------------------------------------
#  A node represents part of the path generated by the pathfinder,
#  It corrosponds to a single tile
#==============================================================================
 
class Node
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_accessor :x                        # x coordinate of current node
  attr_accessor :y                        # y coordinate of current node
  attr_accessor :parent                   # parent node
  attr_accessor :g                        # cost of getting to this node
  attr_accessor :h                        # distance to goal (heuristic)
  #--------------------------------------------------------------------------
  # * Object Initialization
  #--------------------------------------------------------------------------
  def initialize(x, y, parent = nil, g = 0, h = 0)
    @x = x
    @y = y
    @parent = parent
    @g = g
    @h = h
  end
  #--------------------------------------------------------------------------
  # * The Total 'Cost' at This Node (AKA f(n))
  #--------------------------------------------------------------------------
  def cost
    # f(n) = g(n) + h(n)
    return @g + @h
  end
  #--------------------------------------------------------------------------
  # * Two Nodes Are Equal If They Are on the Same Tile
  #--------------------------------------------------------------------------
  def ==(other)
    return false unless other and other.is_a?(Node)
    return true if other.x == @x and other.y == @y
    return false
  end
 
  #--------------------------------------------------------------------------
  # * Check If Another Node is Within This Node's Range
  #--------------------------------------------------------------------------
  def in_range?(other, range)
    # Get absolute value of difference
    abs_sx = (@x - other.x).abs
    abs_sy = (@y - other.y).abs
    return abs_sx + abs_sy <= range
  end
end
 
#==============================================================================
# ** A_Star_Pathfinder
#------------------------------------------------------------------------------
#  This class generates a path using the A* algorithm. Not a very good
#  implementation but I'm still proud of it.
#==============================================================================
 
class A_Star_Pathfinder
  #--------------------------------------------------------------------------
  # * Constants
  #--------------------------------------------------------------------------
  ITERATION_LIMIT = -1        # Maximum number of loop iterations before
                              # the pathfinder gives up. -1 for infinity.
  COLLISION_WAIT = 5          # No. of frames to wait before attempting to
                              # find another path in case of collision; 
                              # -1 disables such collision behevior. 
  COLLISION_LIMIT = 30        # Maximum number of attempts to find another
                              # path in case of collision. -1 for infinity.
  #--------------------------------------------------------------------------
  # * Public Instance Variables
  #--------------------------------------------------------------------------
  attr_reader   :goal_node                # the goal!
  attr_reader   :character                # character looking for a path
  attr_reader   :found                    # was the path found?
  attr_reader   :route                    # the route returned after 
                                          # calling generate_path
  attr_accessor :range                    # Size of goal area
  attr_accessor :get_close                # If true and no path is found then
                                          # get as close as possible.
  attr_accessor :reach_method             # Proc called when goal is reached
  attr_accessor :fail_method              # Proc called when no path is found
  attr_accessor :original_goal_node       # goal node before pathfinding
  attr_accessor :collision_counter        # counter for the number of times path
                                          # was obstructed and re-generated
 
  #--------------------------------------------------------------------------
  # * Object Initialization
  #     goal_node : A Node representing the end point
  #     char      : The character that'd use the result of pathfinding,
  #                 either a Game_Character, event ID, or -1 for player
  #     run       : If true, the path is also generated
  #--------------------------------------------------------------------------
  def initialize(goal_node = nil, char = -1, run = true)
    # If no goal node is provided, this acts as a default constructor that
    # takes no parameters and does nothing. Useful if you do things manually
    unless goal_node
      return
    end
    # Setup variables
    setup(goal_node, char)
    # Find the optimal path
    calculate_path
    # We're done, time to generate the path
    generate_path if run
  end
 
  #--------------------------------------------------------------------------
  # * Setup Initial Values for Variables
  #     goal_node : A Node representing the end point
  #     character : The character that'd use the result of pathfinding
  #     range     : The size of the goal area, 0 means the goal is the
  #                 node, 1 means within 1 tile around goal, etc.
  #     close     : If true the character will try to get as close as
  #                 possible to path if it isn't found.
  #     reach     : A Proc that will be called when the goal is reached
  #     fail      : A proc that will be called if no path was found
  #--------------------------------------------------------------------------
  def setup(goal_node, character, range = 0, close = false,
            reach = nil, fail = nil)
    @original_goal_node = Node.new(goal_node.x, goal_node.y)
    @goal_node = Node.new(goal_node.x, goal_node.y)
    @character = A_Star_Pathfinder.int_to_character(character)
    unless @character
      raise "A_Star_Pathfinder Error : Invalid Character"
    end
    @start_node = Node.new(@character.x, @character.y)
    @range = range
    @get_close  = close
    @reach_method = reach
    @fail_method = fail
 
    @open_list = Array.new            # List of nodes to be checked,
                                      # implemented as a binary heap
    @open_list.push(@start_node)    
    @closed_list = Hash.new           # Set of nodes already checked, this
                                      # is a hash of arrays of [x, y] pairs
                                      # representing map tiles
    @found = false
    # Saves node with lowest h in case we want to get close to it
    @nearest = Node.new(0, 0, 0, -1)
  end
 
  #--------------------------------------------------------------------------
  # * Search For the Optimal Path
  #--------------------------------------------------------------------------
  def calculate_path
    iterations_counter = 0
    # Only do calculation if goal is actually passable, unless we only
    # need to get close or within range
    if @character.passable?(@goal_node.x, @goal_node.y, 0) or 
       @get_close or
       @range > 0
      until @open_list.empty?
        iterations_counter = iterations_counter + 1
        # Prevents script hanging
        Graphics.update if (iterations_counter % 200 == 0) 
        # If we hit the iteration limit, exit
        if ITERATION_LIMIT != -1 and iterations_counter >= ITERATION_LIMIT
          @found = false
          break
        end
        # Get the node with lowest cost and add it to the closed list
        @current_node = find_lowest_cost
        @closed_list[[@current_node.x, @current_node.y]] = @current_node
        if @current_node == @goal_node or 
           (@range > 0 and @goal_node.in_range?(@current_node, @range))
          # We reached goal, exit the loop!
          @original_goal_node = @goal_node
          @goal_node = @current_node
          @found = true
          break
        else # if not goal
          # Keep track of the node with the lowest cost so far
          if @current_node.h < @nearest.h or @nearest.h < 1
            @nearest = @current_node
          end
          # Get adjacent nodes and check if they can be added to the open list
          adjacent_nodes = get_adjacent_nodes(@current_node)
          for adj_node in adjacent_nodes
            if skip_node?(adj_node)
              # Node already exists in one of the lists, skip it
              next
            end
            # Add node to open list following the binary heap conventions
            heap_add(@open_list, adj_node)
          end
        end
      end
    end
    # If no path was found, see if we can get close to goal
    unless @found
      if @get_close and @nearest.h > 0
        @goal_node = @nearest
        setup(@goal_node, @character, @range, @get_close, @reach_method, 
                 @fail_method)
        calculate_path
      else
        # Call the fail method if one is provided
        if @fail_method
          @fail_method.call
        end
      end
    end
  end
 
  #--------------------------------------------------------------------------
  # * Return Game_Character Object From Integer Arguments
  #     char  : If -1, the player character is returned; for other integers,
  #             map event with ID matching the integer is returned
  #--------------------------------------------------------------------------  
  def self.int_to_character(char)
    if char.is_a?(Integer)
      if char == -1
        char = $game_player
      else
        char = $game_map.events[char]
      end
    end
    return char
  end
 
  #--------------------------------------------------------------------------
  # * Add an Item to the Binary Heap (for open_list). This is Based on
  #   Algorithm Here: http://www.policyalmanac.org/games/binaryHeaps.htm
  #     array : Array to add the node to
  #     item  : Item to add!
  #--------------------------------------------------------------------------
  def heap_add(array, item)
    # Add the item to the end of the array
    array.push(item)
    # m is the index of the 'current' item
    heap_update(array, array.size - 1)
  end
 
  #--------------------------------------------------------------------------
  # * Make Sure the Item at Index is in the Right Place
  #     array : Array to update
  #     index : Index of the item
  #--------------------------------------------------------------------------
  def heap_update(array, index)
    m = index
    while m > 0
      # If current item's cost is less than parent's
      if array[m].cost <= array[m / 2].cost
        # Swap them so that lowest cost bubbles to top
        temp = array[m / 2]
        array[m / 2] = array[m]
        array[m] = temp
        m /= 2
      else
        break
      end
    end
  end
 
  #--------------------------------------------------------------------------
  # * Remove an Item from the Binary Heap (for open_list) & Return it.
  #   This is Based on Algorithm Here: 
  #   http://www.policyalmanac.org/games/binaryHeaps.htm
  #     array : Array to remove the node from
  #--------------------------------------------------------------------------
  def heap_remove(array)
    if array.empty?
      return nil
    end
    #Get original first element
    first = array[0]
    # Replace first element with last one
    last = array.slice!(array.size - 1)
    if array.empty?
      return last
    else
      array[0] = last
    end
    v = 0   # Stores a smaller child, if any
    # Loop until no more swapping is needed
    while true
      u = v
      # If both children exist
      if 2 * u + 1 < array.size
        v = 2 * u if array[2 * u].cost <= array[u].cost
        v = 2 * u + 1 if array[2 * u + 1].cost <= array[v].cost
      # If only one child exists
      elsif 2 * u < array.size
        v = 2 * u if array[2 * u].cost <= array[u].cost
      end
      # If at least one child is less than parent, swap them
      if u != v
        temp = array[u]
        array[u] = array[v]
        array[v] = temp
      else
        break
      end
    end
    # Return the original first node (which was removed)
    return first
  end
 
  #--------------------------------------------------------------------------
  # * Can We Skip This Node? (because it already exists in a list)
  #     node : Node to check
  #--------------------------------------------------------------------------
  def skip_node?(node)
    skip_node = false
    copy = @open_list.index(node)
    if copy
      #If the existing copy is 'better' than the new one, skip new node
      if @open_list[copy].cost <= node.cost
        skip_node = true
      else
        # Otherwise swap them, making sure heap is in right order
        @open_list[copy] = node
        heap_update(@open_list, copy)
        skip_node = true
      end
    end
    # The closed list is a hash so this is relatively easier
    if @closed_list[[node.x, node.y]]
      # If the existing copy is 'better' than the new one
      if @closed_list[[node.x, node.y]].cost <= node.cost
        skip_node = true
      else
        # Update the existing node
        @closed_list[[node.x, node.y]] = node
      end
    end
    # Return the result
    return skip_node
  end
 
  #--------------------------------------------------------------------------
  # * Find Node With Lowest Cost on the Open List
  #--------------------------------------------------------------------------
  def find_lowest_cost
    # Just return top of the heap
    return  heap_remove(@open_list)
  end
 
  #--------------------------------------------------------------------------
  # * Distance Between Two Points (Heuristic)
  #--------------------------------------------------------------------------
  def distance(x1, y1, x2, y2)
    # A simple heuristic value (Manhattan distance)
    return ((x1 - x2).abs + (y1 - y2).abs)
  end
 
  #--------------------------------------------------------------------------
  # * Get a List of Adjacent Nodes
  #     node : The 'center' node
  #--------------------------------------------------------------------------
  def get_adjacent_nodes(node)
    # Array to hold the nodes
    nodes = Array.new
    # Right
    new_x = node.x + 1
    new_y = node.y
    add_node(nodes, new_x, new_y, node)
    # Left
    new_x = node.x - 1
    new_y = node.y
    # Down
    add_node(nodes, new_x, new_y, node)
    new_x = node.x
    new_y = node.y + 1
    add_node(nodes, new_x, new_y, node)
    # Up
    new_x = node.x
    new_y = node.y - 1
    add_node(nodes, new_x, new_y, node)
    return nodes
  end
 
  #--------------------------------------------------------------------------
  # * Add a Node to an Array
  #--------------------------------------------------------------------------
  def add_node(array, x, y, parent)
    direction = get_direction(x, y, parent.x, parent.y)
    if @character.passable?(parent.x, parent.y, direction)
      # The cost of movement one step to a new tile is always 1
      g = parent.g + 1
      # The heuristic is simply the distance
      h = distance(x, y, @goal_node.x, @goal_node.y)
      new_node = Node.new(x, y, parent, g, h)
      array.push(new_node)
    end
  end
 
  #--------------------------------------------------------------------------
  # * Get Direction From a Point to Another
  #--------------------------------------------------------------------------
  def get_direction(x1, y1, x2, y2)
    # If first point is to the ... of the second
    if x1 > x2        # right
      return 6
    elsif x1 < x2     # left
      return 4
    elsif y1 > y2     # bottom
      return 2
    elsif y1 < y2     # top
      return 8
    end
    # Otherwise they are on the same position
    return 0
  end
 
  #--------------------------------------------------------------------------
  # * Generate the Path by Following Parents and Return it 
  #   as RPG::MoveRoute
  #     follow : If true the path is assigned to the character as a
  #     forced move route.
  #--------------------------------------------------------------------------
  def generate_path(follow = true)
    # There's no path to generate if no path was found
    if !@found
      return
    end
    # 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_node
    code = 0    # Movement code for RPG::MoveCommand
    while node.parent
      # Get direction from parent to node as RPG::MoveCommand
      direction = get_direction(node.parent.x, node.parent.y, node.x, node.y)
      case direction
        when 2 # Up
          code = 4
        when 4 # Left
          code = 3
        when 6 # Right
          code = 2
        when 8 # Down
          code = 1
      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 follow and !@route.list.empty?
      @character.add_path(self)
    end
    # Return the constructed RPG::MoveRoute
    return @route
  end
end
 
#==============================================================================
# ** Game_Character 
#------------------------------------------------------------------------------
#  Just make the move_route variables public
#==============================================================================
 
class Game_Character
  attr_accessor :move_route_forcing
  attr_accessor :move_route
  attr_accessor :a_star_paths         # all the paths assigned to character
  #--------------------------------------------------------------------------
  # * Object Initialization
  #--------------------------------------------------------------------------
  # Alias to add path variable, 'stack level too deep' error is prevented
  # since $@ (error locations) is set after player presses F12
  unless $@
    alias :a_star_pathfinder_old_initialize :initialize
  end
  def initialize
    a_star_pathfinder_old_initialize
    @a_star_paths = []
  end
  #--------------------------------------------------------------------------
  # * Add a Path to be Followed by Character
  #-------------------------------------------------------------------------- 
  def add_path(path)
    path.collision_counter = 0
    @a_star_paths.push(path)
    if @a_star_paths.size == 1
      force_move_route(path.route)
    end
  end
 
  #--------------------------------------------------------------------------
  # * Stop Custom Movement
  #--------------------------------------------------------------------------
  def stop_custom_movement
    if @move_route
      @move_route_index = @move_route.list.size
      # 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
    end
  end
 
  #--------------------------------------------------------------------------
  # * Follow Next Path, if Any
  #--------------------------------------------------------------------------   
  def follow_next_path
    stop_custom_movement
    @a_star_paths.shift
    if @a_star_paths[0]
      # Setup path again to reflect any changes since original creation
      goal = @a_star_paths[0].original_goal_node
      char = @a_star_paths[0].character
      range = @a_star_paths[0].range
      close = @a_star_paths[0].get_close
      reach = @a_star_paths[0].reach_method
      fail = @a_star_paths[0].fail_method
      @a_star_paths[0].setup(goal, char, range, close, reach, fail)
      @a_star_paths[0].calculate_path
      @a_star_paths[0].generate_path(false)
      force_move_route(@a_star_paths[0].route) if @a_star_paths[0].found
    end
  end
 
  #--------------------------------------------------------------------------
  # * Stop Following Current Path
  #-------------------------------------------------------------------------- 
  def stop_path
    if @a_star_paths[0]
      stop_custom_movement
      follow_next_path 
    end
  end
 
  #--------------------------------------------------------------------------
  # * Stop All Generated Paths
  #-------------------------------------------------------------------------- 
  def stop_all_paths
    stop_custom_movement
    @a_star_paths = []
  end
 
  #--------------------------------------------------------------------------
  # * Move Type : Custom (move event, pattern, etc.)
  #   Note: The script overwrites this method, which _might_ lead to
  #   compatibility problems with other scripts. You can remove this
  #   method to fix any such problem, but the character won't be able
  #   to detect the need to recalculate the path.
  #--------------------------------------------------------------------------
  def move_type_custom
    # Interrupt if not stopping
    if jumping? or moving?
      return
    end
    # For each move command starting from the index
    while @move_route_index < @move_route.list.size
      # Get the move command at index
      command = @move_route.list[@move_route_index]
      # If command code is 0 (end of list)
      if command.code == 0
        # If [repeat action] option is ON
        if @move_route.repeat
          # Reset move route index to the top of the list
          @move_route_index = 0
        end
        # If [repeat action] option is OFF
        unless @move_route.repeat
          # If move route is forced and not repeating
          if @move_route_forcing and not @move_route.repeat
            # The move route is no longer forced (moving ended)
            @move_route_forcing = false
            # Restore original move route
            @move_route = @original_move_route
            @move_route_index = @original_move_route_index
            @original_move_route = nil
### CODE ADDED HERE ############################################################
            # If there was a path to follow and we reached goal
            if @a_star_paths[0]
              if self.x == @a_star_paths[0].goal_node.x and 
                  y == @a_star_paths[0].goal_node.y
                # Call the reach method if one was provided
                if @a_star_paths[0].reach_method
                  @a_star_paths[0].reach_method.call
                end
              end
              follow_next_path 
            end
### ADDED CODE ENDS ############################################################
          end
          # Clear stop count
          @stop_count = 0
        end
        return
      end # if command.code == 0
      # For move commands (from move down to jump)
      if command.code <= 14
        # Branch by command code
        case command.code
        when 1  # Move down
          move_down
        when 2  # Move left
          move_left
        when 3  # Move right
          move_right
        when 4  # Move up
          move_up
        when 5  # Move lower left
          move_lower_left
        when 6  # Move lower right
          move_lower_right
        when 7  # Move upper left
          move_upper_left
        when 8  # Move upper right
          move_upper_right
        when 9  # Move at random
          move_random
        when 10  # Move toward player
          move_toward_player
        when 11  # Move away from player
          move_away_from_player
        when 12  # 1 step forward
          move_forward
        when 13  # 1 step backward
          move_backward
        when 14  # Jump
          jump(command.parameters[0], command.parameters[1])
        end
        # If movement failure occurs when [Ignore if can't move] option is OFF
        if not @move_route.skippable and not moving? and not jumping?
### CODE ADDED HERE ############################################################
          # If there's a path but it couldn't be followed (probably because
          # another character blocked it)
          if @a_star_paths[0] and 
             A_Star_Pathfinder::COLLISION_WAIT >= 0 and
             (A_Star_Pathfinder::COLLISION_LIMIT < 0 or
             @a_star_paths[0].collision_counter <= A_Star_Pathfinder::COLLISION_LIMIT)
            # Setup path again to update starting location.
            # original goal node is used because pathfinding changes
            # the goal node to current node
            goal = @a_star_paths[0].original_goal_node
            char = @a_star_paths[0].character
            range = @a_star_paths[0].range
            close = @a_star_paths[0].get_close
            reach = @a_star_paths[0].reach_method
            fail = @a_star_paths[0].fail_method
            counter = @a_star_paths[0].collision_counter
            # Find another path to goal
            @a_star_paths[0] = A_Star_Pathfinder.new
            @a_star_paths[0].setup(goal, char, range, close, reach, fail)
            @a_star_paths[0].calculate_path
            @a_star_paths[0].generate_path(false)
            @a_star_paths[0].collision_counter = counter + 1
            force_move_route(@a_star_paths[0].route) if @a_star_paths[0].found
            # Wait a bit before starting to follow the new path
            @wait_count = A_Star_Pathfinder::COLLISION_WAIT
            return
          elsif @a_star_paths[0]
            # If collision wait is -1 or reached collision limit,
            # stop character and call any fail method
            @move_route_index = @move_route.list.size
            if @a_star_paths[0].fail_method 
              @a_star_paths[0].fail_method.call
            end
            follow_next_path 
          end
### ADDED CODE ENDS ############################################################
          return
        end
        # Advance index
        @move_route_index += 1
        return
      end # if command.code <= 14
      # If waiting
      if command.code == 15
        # Set wait count (from provided parameter)
        @wait_count = command.parameters[0] * 2 - 1
        @move_route_index += 1
        return
      end # if command.code == 15
      # If direction change (turning) command
      if command.code >= 16 and command.code <= 26
        # Branch by command code
        case command.code
        when 16  # Turn down
          turn_down
        when 17  # Turn left
          turn_left
        when 18  # Turn right
          turn_right
        when 19  # Turn up
          turn_up
        when 20  # Turn 90° right
          turn_right_90
        when 21  # Turn 90° left
          turn_left_90
        when 22  # Turn 180°
          turn_180
        when 23  # Turn 90° right or left
          turn_right_or_left_90
        when 24  # Turn at Random
          turn_random
        when 25  # Turn toward player
          turn_toward_player
        when 26  # Turn away from player
          turn_away_from_player
        end
        @move_route_index += 1
        return
      end # if command.code >= 16 and command.code <= 26
      # If other command (commands that don't 'return')
      if command.code >= 27
        # Branch by command code
        case command.code
        when 27  # Switch ON
          $game_switches[command.parameters[0]] = true
          $game_map.need_refresh = true
        when 28  # Switch OFF
          $game_switches[command.parameters[0]] = false
          $game_map.need_refresh = true
        when 29  # Change speed
          @move_speed = command.parameters[0]
        when 30  # Change freq
          @move_frequency = command.parameters[0]
        when 31  # Move animation ON
          @walk_anime = true
        when 32  # Move animation OFF
          @walk_anime = false
        when 33  # Stop animation ON
          @step_anime = true
        when 34  # Stop animation OFF
          @step_anime = false
        when 35  # Direction fix ON
          @direction_fix = true
        when 36  # Direction fix OFF
          @direction_fix = false
        when 37  # Through ON
          @through = true
        when 38  # Through OFF
          @through = false
        when 39  # Always on top ON
          @always_on_top = true
        when 40  # Always on top OFF
          @always_on_top = false
        when 41  # Change Graphic
          # Can't change into a tile
          @tile_id = 0
          @character_name = command.parameters[0]
          @character_hue = command.parameters[1]
          # Update direction
          if @original_direction != command.parameters[2]
            @direction = command.parameters[2]
            @original_direction = @direction
            @prelock_direction = 0
          end
          # Update frame
          if @original_pattern != command.parameters[3]
            @pattern = command.parameters[3]
            @original_pattern = @pattern
          end
        when 42  # Change Opacity
          @opacity = command.parameters[0]
        when 43  # Change Blending
          @blend_type = command.parameters[0]
        when 44  # Play SE
          $game_system.se_play(command.parameters[0])
        when 45  # Script
          result = eval(command.parameters[0])
        end
        # Update move_route_index and move to next move command in the list
        @move_route_index += 1
      end # if command.code >= 27
    end # while @move_route_index < @move_route.list.size
  end 
 
end