[RMXP] Advanced Pathfinding

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# Advanced Pathfinding
# Author: ForeverZer0
# Version: 1.0
# Date: 5.30.2011
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# 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
#   relatively 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.
#
# Instructions:
#   - Place script below default scripts, and above "Main".
#   - Use the following script call:
#
#     pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#
#     The X and Y are the only required arguments. The others can be omitted.
#
#     X - The x-coordinate to pathfind to.
#     Y - The y-coordinate to pathfind to.
#
#     CHARACTER - Either an instance of the character ($game_player,
#                 $game_map.events[ID], etc) or the ID of a character. The ID
#                 will be the event ID. Use -1 for the game player.
#
#     SUCCESS_PROC - A Proc object that will be executed when the player
#                    reaches the defined coordinates.
#     FAILURE_PROC - A Proc object that will be executed when the player
#                    cannot reach the defined coordinates.
#
#   - As default, the pathfinder will make 35 attempts to recalculate a route
#     that gets blocked. This value can be changed in game with the script
#     call:
#           $game_map.collision_retry = NUMBER
#
#     You can change the default value if desired by looking down to the first
#     class below in the main script.
#   - For longer pathfind routes, it is sometimes necessary to reset the
#     search limiter. This may cause increased lag when an object blocks the
#     character from being able to move, but will increase the range that the
#     system can work with. Use the following script call:
#
#         $game_map.search_limiter = NUMBER  (Default 1000)
#
#   - If you are experiencing any compatibility problems, go to the Game_Map
#     class below and set @recalculate_paths to false. This will take away some
#     of the efficiency of recalculating collisions, but will improve may fix
#     your problem.
#
# Compatibility:
#   Highly compatible. May experience issues with Custom Movement scripts,
#   but even then, it is unlikely.
#
# Credits/Thanks:
#   - ForeverZer0, for the script
#   - Special thanks to Jragyn for help making the big maze for the demo and
#     help testing.
#   - Credit goes to the Peter Hart, Nils Nilsson and Bertram Raphael for the
#     original search algorithm that was implemented
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+

#===============================================================================
# ** Game_Map
#===============================================================================

class Game_Map

  attr_accessor :collision_retry
  attr_accessor :recalculate_paths
  attr_accessor :search_limiter

  alias zer0_pathfinding_init initialize
  def initialize
    # Initialize instance variables used for pathfinding.
    @collision_retry = 35
    @recalculate_paths = true
    @search_limiter = 1000
    # Original method
    zer0_pathfinding_init
  end
end

#===============================================================================
# ** Interpreter
#===============================================================================

class Interpreter

  def pathfind(x, y, *args)
    args[0] = @event_id if args[0] == nil
    args[1] = 0 if args[1] == nil
    # Add a simpler call for using as a script call
    Pathfind.new(Node.new(x, y), *args)
  end
end

#==============================================================================
# ** Pathfind
#==============================================================================

class Pathfind

  attr_reader   :route
  attr_accessor :range
  attr_reader   :goal
  attr_reader   :found
  attr_reader   :character
  attr_accessor :success_proc
  attr_accessor :failure_proc
  attr_accessor :target
  attr_accessor :collisions

  def initialize(node, char = -1, range = 0, *callbacks)
    # Set the character. Can either us an ID or an instance of a Game_Character.
    # A value of -1, which is default, is the Game_Player.
    if char.is_a?(Integer)
      @character = (char == -1) ? $game_player : $game_map.events[char]
    elsif char.is_a?(Game_Character)
      @character = char
    end
    # Set forcing flag. Will be disabled for recalculating on the fly.
    @forcing = true
    # Call a public method, since this method may need to be used again,
    # and "initialize" is private.
    setup(node, range, *callbacks)
  end

  def setup(node, range = 0, *callbacks)
    # Initialize the node we are trying to get to.
    @target = Node.new(node.x, node.y)
    @goal = @target.clone
    # Set beginning nodes and required variables.
    @start_node = Node.new(@character.x, @character.y)
    @nearest = Node.new(0, 0, 0, -1)
    @range, @found, @collisions = range, false, 0
    # Set callbacks for success and failure if included, else nil.
    @success_proc = callbacks[0]
    @failure_proc= callbacks[1]
    # Initialize sets to track open and closed nodes
    @open_set, @close_set = [@start_node], {}
    # Find the optimal path
    calculate_path
  end

  def calculate_path
    # Only do calculation if goal is actually passable, unless we only
    # need to get close or within range
    if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
      # Initialize counter
      counter, wait = 0, 0
      until @open_set.empty?

        counter += 1
        # Give up if pathfinding is taking more than 500 iterations
        if counter >= $game_map.search_limiter
          @found = false
          break
        end
        # Get the node with lowest cost and add it to the closed list
        @current_node = get_current
        @close_set[[@current_node.x, @current_node.y]] = @current_node
        if @current_node == @goal ||
           (@range > 0 && @goal.in_range?(@current_node, @range))
          # We reached goal, exit the loop!
          @target = @goal
          @goal, @found = @current_node, true
          break
        else # if not goal
          # Keep track of the node with the lowest cost so far
          if @current_node.heuristic < @nearest.heuristic ||
            @nearest.heuristic < 1
            @nearest = @current_node
          end
          # Get adjacent nodes and check if they can be added to the open list
          neighbor_nodes(@current_node).each {|neighbor|
            # Skip Node if it already exists in one of the lists.
            next if can_skip?(neighbor)
            # Add node to open list following the binary heap conventions
            @open_set.push(neighbor)
            arrange(@open_set.size - 1)
          }
        end
      end
    end
    # If no path was found, see if we can get close to goal
    unless @found
      if @range > 0 && @nearest.heuristic > 0
        # Create an alternate path.
        setup(@nearest, @range, @success_proc, @failure_proc)
      elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
        (@collisions > $game_map.collision_retry))
        # If out of retries, call the Proc for failure if defined
        @failure_proc.call
      end
    end
    # Create the move route using the generated path
    create_move_route
  end

  def create_move_route
    # There's no path to generate if no path was found
    return if !@found
    # Create a new move route that isn't repeatable
    @route = RPG::MoveRoute.new
    @route.repeat = false
    # Generate path by starting from goal and following parents
    node = @goal
    while node.parent
      # Get direction from parent to node as RPG::MoveCommand
      code = case direction(node.parent.x, node.parent.y, node.x, node.y)
      when 2 then 4 # Up
      when 4 then 3 # Left
      when 6 then 2 # Right
      when 8 then 1 # Down
      else; 0
      end
      # Add movement code to the start of the array
      @route.list.unshift(RPG::MoveCommand.new(code)) if code != 0
      node = node.parent
    end
    # If the path should be assigned to the character
    if (@forcing && !@route.list.empty?)
      @collisions = 0
      @character.paths.push(self)
      @character.force_move_route(@route) if @character.paths.size == 1
    end
    # Reset forcing flag if needed
    @forcing = true
    # Return the constructed RPG::MoveRoute
    return @route
  end

  def arrange(index)
    # Rearrange nodes in the open_set
    while index > 0
      # Break loop unless current item's cost is less than parent's
      break if @open_set[index].score > @open_set[index / 2].score
      # Bring lowest value to the top.
      temp = @open_set[index / 2]
      @open_set[index / 2] = @open_set[index]
      @open_set[index] = temp
      index /= 2
    end
  end

  def get_current
    return if @open_set.empty?
    return @open_set[0] if @open_set.size == 1
    # Set current node to local variable and replace it with the last
    current = @open_set[0]
    @open_set[0] = @open_set.pop
    # Loop and rearrange array according to the A* algorithm until done.
    y = 0
    loop {
      x = y
      # If two children exist
      if 2 * x + 1 < @open_set.size
        if @open_set[2 * x].score <= @open_set[x].score
          y = 2 * x
          if @open_set[2 * x + 1].score <= @open_set[y].score
            y = 2 * x + 1
          end
        end
      # If only one child exists
      elsif 2 * x < @open_set.size &&
        @open_set[2 * x].score <= @open_set[x].score
        y = 2 * x
      end
      # Swap a child if it is less than the parent.
      break if x == y
      temp = @open_set[x]
      @open_set[x] = @open_set[y]
      @open_set[y] = temp
    }
    # Return the original first node (which was removed)
    return current
  end

  def direction(x1, y1, x2, y2)
    # Return the numerical direction between coordinates.
    return 6 if x1 > x2 # Right
    return 4 if x1 < x2 # Left
    return 2 if y1 > y2 # Bottom
    return 8 if y1 < y2 # Top
    return 0
  end

  def neighbor_nodes(node)
    # Create array to hold the nodes, then check each direction.
    nodes = []
    nodes.push(get_neighbor(node.x + 1, node.y, node)) # Right
    nodes.push(get_neighbor(node.x - 1, node.y, node)) # Left
    nodes.push(get_neighbor(node.x, node.y + 1, node)) # Down
    nodes.push(get_neighbor(node.x, node.y - 1, node)) # Up
    # Remove any nil elements, then return results.
    return nodes.compact
  end

  def get_neighbor(x, y, parent)
    # Calculate direction, return new node if passable.
    direction = direction(x, y, parent.x, parent.y)
    if @character.passable?(parent.x, parent.y, direction)
      # The heuristic is simply the distance
      heuristics = ((x - @goal.x).abs + (y - @goal.y).abs)
      return Node.new(x, y, parent, parent.cost + 1, heuristics)
    end
  end

  def can_skip?(node)
    # Branch by if node is in either the open or closed set.
    if @open_set.include?(node)
      index = @open_set.index(node)
      return true if @open_set[index].score <= node.score
      # Swap them and update list order
      @open_set[index] = node
      arrange(index)
      return true
    elsif @close_set[[node.x, node.y]] != nil
      # If the existing passed node has a lower score than this one.
      return true if @close_set[[node.x, node.y]].score <= node.score
      # Update the existing node
      @close_set[[node.x, node.y]] = node
    end
    # Return false if no criteria was met.
    return false
  end
end

#==============================================================================
# ** Game_Character
#==============================================================================

class Game_Character

  attr_accessor :paths
  attr_accessor :move_route_forcing
  attr_accessor :move_route

  alias zer0_pathfinding_init initialize
  def initialize
    # Add public instance variable for paths
    @paths = []
    # Original method
    zer0_pathfinding_init
  end

  def next_route
    # Stop any custom move route that may be occuring.
    if @move_route != nil
      # Set index and disable forcing of current route
      @move_route_index = @move_route.list.size
      @move_route_forcing = false
      # Reset to what it was originally
      @move_route = @original_move_route
      @move_route_index = @original_move_route_index
      @original_move_route = nil
    end
    # Remove first path from the paths array.
    @paths.shift
    # If there is another path to follow...
    if @paths[0] != nil
      # Setup path again to reflect any changes since original creation
      @forcing = false
      @paths[0].setup(@paths[0].target, @paths[0].range,
        @paths[0].success_proc, @paths[0].failure_proc)
      force_move_route(@paths[0].route) if @paths[0].found
    end
  end

  alias zer0_recalculate_paths_move move_type_custom
  def move_type_custom
    if $game_map.recalculate_paths
      # Interrupt if not stopping
      return if jumping? || moving?
      # Loop until finally arriving at move command list
      while @move_route_index < @move_route.list.size
        # Get the move command at index
        command = @move_route.list[@move_route_index]
        # If command code is 0 (end of list)
        if command.code == 0
          # If [repeat action] option is ON
          if @move_route.repeat
            # Reset move route index to the top of the list
            @move_route_index = 0
          end
          # If [repeat action] option is OFF
          unless @move_route.repeat
            # If move route is forced and not repeating
            if @move_route_forcing and not @move_route.repeat
              # The move route is no longer forced (moving ended)
              @move_route_forcing = false
              # Restore original move route
              @move_route = @original_move_route
              @move_route_index = @original_move_route_index
              @original_move_route = nil
              # If there was a path to follow and we reached goal
              if @paths[0] != nil
                if self.x == @paths[0].goal.x &&
                  y == @paths[0].goal.y && @paths[0].success_proc
                  # Call success Proc if goal is reached and it is defined.
                  @paths[0].success_proc.call
                end
                next_route
              end
            end
            # Clear stop count
            @stop_count = 0
          end
          return
        end # if command.code == 0
        # For move commands (from move down to jump)
        if command.code <= 14
          # Branch by command code
          case command.code
          when 1 then move_down                 # Move down
          when 2 then move_left                 # Move left
          when 3 then move_right                # Move right
          when 4 then move_up                   # Move up
          when 5 then move_lower_left           # Move lower left
          when 6 then move_lower_right          # Move lower right
          when 7 then move_upper_left           # Move upper left
          when 8 then move_upper_right          # Move upper right
          when 9 then move_random               # Move random
          when 10 then move_toward_player       # Move toward player
          when 11 then move_away_from_player    # Move away from player
          when 12 then move_forward             # Step forward
          when 13 then move_backward            # Step backward
          when 14 then jump(command.parameters[0], command.parameters[1]) # Jump
          end
          # If movement failure occurs when "Ignore If Can't Move" is unchecked.
          if !@move_route.skippable && !moving? && !jumping?
            # If path is current and collision limit is not reached
            if @paths[0] != nil &&
              @paths[0].collisions < $game_map.collision_retry
              # Setup path again to update starting location.
              # original goal node is used because pathfinding changes
              # the goal node to current node
              goal, range = @paths[0].target, @paths[0].range
              reach = @paths[0].success_proc
              fail = @paths[0].failure_proc
              counter = @paths[0].collisions + 1
              # Find another path to goal
              @paths[0] = Pathfind.new(goal, self, range, reach, fail)
              @paths[0].collisions = counter
              force_move_route(@paths[0].route) if @paths[0].found
              # Wait a bit before starting to follow the new path
              @wait_count = 6
              return
            else
              # Call failure Proc if defined and set move index.
              @move_route_index = @move_route.list.size
              @paths[0].failure_proc.call if @paths[0].failure_proc != nil
              next_route
            end
            # End method
            return
          end
          # Advance index
          @move_route_index += 1
          return
        end # if command.code <= 14
        # If waiting
        if command.code == 15
          # Set wait count (from provided parameter)
          @wait_count = command.parameters[0] * 2 - 1
          @move_route_index += 1
          return
        end # if command.code == 15
        # If direction change (turning) command
        if command.code >= 16 and command.code <= 26
          # Branch by command code
          case command.code
          when 16 then turn_down                      # Turn down
          when 17 then turn_left                      # Turn left
          when 18 then turn_right                     # Turn right
          when 19 then turn_up                        # Turn up
          when 20 then turn_right_90                  # Turn 90° right
          when 21 then turn_left_90                   # Turn 90° left
          when 22 then turn_180                       # Turn 180°
          when 23 then turn_right_or_left_90          # Turn 90° right or left
          when 24 then turn_random                    # Turn at Random
          when 25 then turn_toward_player             # Turn toward player
          when 26 then turn_away_from_player          # Turn away from player
          end
          @move_route_index += 1
          return
        end
        # If other command (commands that don't 'return')
        if command.code >= 27
          # Branch by command code
          case command.code
          when 27                                              # Switch ON
            $game_switches[command.parameters[0]] = true
            $game_map.need_refresh = true
          when 28                                              # Switch OFF
            $game_switches[command.parameters[0]] = false
            $game_map.need_refresh = true
          when 29 then @move_speed = command.parameters[0]     # Change speed
          when 30 then @move_frequency = command.parameters[0] # Change freq
          when 31 then @walk_anime = true                      # Move ON
          when 32 then @walk_anime = false                     # Move OFF
          when 33 then @step_anime = true                      # Stop ON
          when 34 then @step_anime = false                     # Stop OFF
          when 35 then @direction_fix = true                   # Direction ON
          when 36 then @direction_fix = false                  # Direction OFF
          when 37 then @through = true                         # Through ON
          when 38 then @through = false                        # Through OFF
          when 39 then @always_on_top = true                   # On top ON
          when 40 then @always_on_top = false                  # On top OFF
          when 41                                              # Change Graphic
            # Can't change into a tile
            @tile_id = 0
            @character_name = command.parameters[0]
            @character_hue = command.parameters[1]
            # Update direction
            if @original_direction != command.parameters[2]
              @direction = command.parameters[2]
              @original_direction = @direction
              @prelock_direction = 0
            end
            # Update frame
            if @original_pattern != command.parameters[3]
              @pattern = command.parameters[3]
              @original_pattern = @pattern
            end
          when 42 then @opacity = command.parameters[0]        # Change Opacity
          when 43 then @blend_type = command.parameters[0]     # Change Blending
          when 44 then $game_system.se_play(command.parameters[0]) # Play SE
          when 45 then result = eval(command.parameters[0])    # Script
          end
          # Increment move index.
          @move_route_index += 1
        end
      end
    else
      # Original method
      zer0_recalculate_paths_move
    end
  end
end

#==============================================================================
# ** Node
#==============================================================================

class Node

  attr_accessor :x
  attr_accessor :y
  attr_accessor :parent
  attr_accessor :cost
  attr_accessor :heuristic

  def initialize(x, y, parent = nil, cost = 0, heuristic = 0)
    # Set public instance variables.
    @x, @y, @parent, @cost, @heuristic = x, y, parent, cost, heuristic
  end

  def score
    # Return the current "score" of this node
    return @cost + @heuristic
  end

  def in_range?(node, range)
    # Return true/false if Nodes are within RANGE of each other.
    return (@x - node.x).abs + (@y - node.y).abs <= range
  end

  def ==(node)
    # Returns true/false of whether self and other are equal.
    return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
  end
end