[SCRIPTING] PATHFINDING SCRIPT

#==============================================================================
# ** Pathfinder
#    by Gibmaker
#    just give credit if you use this
#------------------------------------------------------------------------------
#  Efficiently finds a route to a target in the least number of steps
#  Will return an empty move list if no route exists, but it will exhaust
#  the entire map if no route exists which is time-consuming so it's best
#  used in cases where a route is guaranteed to exist.
#
#  Initialization:
#    Pathfinder.new( start_x, start_y, goal_x, goal_y, details[] )
#    "details" contains additional arguments that would be
#    passed to a $game_map.passable? check.  Typically a reference to the
#    event if a route is being devised for an event.
#
#  Public members:
#    move_route      : Path formatted as an RPG::MoveRoute
#    first_direction : First direction of movement in the route (2/4/6/8)
#    path_coords     : List of coordinates of all tiles stepped through
#    path_dirs       : List of all directions moved (2/4/6/8)
#
#  Simple step-toward-player implementation:
#
#  event.force_move_route( Pathfinder.new(
#    event.x, event.y, $game_player.x, $game_player.y, event ).move_route )
#==============================================================================

class Pathfinder
  #============================================================================
  # * Invariants
  #============================================================================
  DIRS = [2, 4, 6, 8]
  #============================================================================
  # * Publics
  #============================================================================
  attr_reader :path_coords
  attr_reader :path_dirs
  #============================================================================
  # * Initialize
  #   The path is filled out immediately
  #============================================================================
  def initialize(start_x, start_y, goal_x, goal_y, details = [], known_max = nil)
    @start_x = start_x
    @start_y = start_y
    @goal_y = goal_y
    @goal_x = goal_x
    @details = [details].flatten
    # Initialize working variables
    # @steps plots the number of actual steps that were taken to reach a spot
    @steps = Table.new($game_map.width, $game_map.height)
    # Holds all nodes that are open but not visited yet
    @live_nodes = {}
    # Set constraint
    if known_max
      # Explore every possible route within the given maximum distance
      @constraint = { :type => :known_maximum, :value => known_max }
    else
      # No known route length yet, so prefer stepping toward the target
      @constraint = { :type => :minimum_expected_distance }
    end
    # Set the starting position
    open(start_x, start_y, 1)
    # Find a path!
    if program_path
      set_path_coords
      # Check for a path using the known_max paradigm; compare
      if @constraint[:type] == :minimum_expected_distance
        alt_path = Pathfinder.new(@start_x, @start_y, @goal_x, @goal_y,
          @details, length )
        if alt_path.length < length
          @path_coords = alt_path.path_coords
        end
      end
      set_path_dirs
    else
      @path_coords = []
      @path_dirs = []
    end
    # Clean up temp variables
    @steps = @live_nodes = nil
  end
  #============================================================================
  # * Distance to goal
  #   The minimum possible steps to reach the goal + 1, assuming there are no
  #   obstacles in the way.
  #   +1 because the default starting value for the table is 0 in all positions
  #   so the goal tile itself will receive a value of 1
  #============================================================================
  def distance(x, y)
    (x - @goal_x).abs + (y - @goal_y).abs + 1
  end
  #============================================================================
  # * Coords at
  #============================================================================
  def coords_at(x, y, dir)
    return x + (dir == 6 ? 1 : dir == 4 ? -1 : 0),
           y + (dir == 2 ? 1 : dir == 8 ? -1 : 0)
  end
  #============================================================================
  # * Passable from tile
  #============================================================================
  def passable?(x, y, dir)
    other_x = x + (dir == 6 ? 1 : dir == 4 ? -1 : 0)
    other_y = y + (dir == 2 ? 1 : dir == 8 ? -1 : 0)
    return ($game_map.valid?(other_x, other_y) and
            $game_map.passable?( x, y, dir, *@details ) and
            $game_map.passable?( other_x, other_y, 10-dir, *@details ))
  end
  #============================================================================
  # * Open tile for checking
  #   Assumption is that this tile is unexplored and not all ready open
  #============================================================================
  def open(x, y, steps)
    @steps[x, y] = steps
    dist = distance(x, y)
    unless distance_set = @live_nodes[dist]
      distance_set = []
      @live_nodes[dist] = distance_set
    end
    distance_set.push( [x, y] ) unless distance_set.find{ |node| node == [x, y]}
  end
  #============================================================================
  # * Close tile
  #   Assumption is that the tile is validly open
  #============================================================================
  def close(x, y)
    # Remove the node from the distance set.
    dist = distance(x, y)
    distance_set = @live_nodes[dist]
    distance_set.delete( distance_set.find { |node| node == [x, y] } )
    # Remove the set if it's empty
    @live_nodes.delete(dist) if distance_set.empty?
  end
  #============================================================================
  # * All nodes
  #============================================================================
  def all_nodes
    set = []
    @live_nodes.values.each { |value| set += value }
    set
  end
  #============================================================================
  # * Find path
  #   Explore the environment and determine if a path is available, programming
  #   the @steps table with the number of steps required to reach each position
  #============================================================================
  def program_path
    # Run until there are no more live nodes.
    # Running out of live nodes means there was no path.
    until @live_nodes.empty?
      # If the goal has been opened (distance of 1)
      if (minimum_distance = @live_nodes.keys.min) == 1
        return true
      end
      # For all open tiles with the smallest distance to the target ...
      case @constraint[:type]
      when :minimum_expected_distance
        check_set = @live_nodes[ minimum_distance ].dup
      when :known_maximum
        check_set = all_nodes
      end
      check_set.each { |node|
        # Open the tiles in all four directions, if it is possible to pass
        # in that direction
        DIRS.each { |dir|
          if passable?( node[0], node[1], dir )
            x, y = *coords_at( node[0], node[1], dir )
            # If there is a max distance constraint
            if @constraint[:type] == :known_maximum
              # Thanks to applying +1 to distance and steps (in order to use
              # 0 to represent an unvisited position) there are a bunch of
              # +1 corrections in this comparison, which combine into the +3
              # adjustment.
              next if distance(x, y) >= @constraint[:value] - @steps[ *node ] + 3
            end
            # If the tile has not all ready been opened, open it now
            if @steps[x, y] == 0 or @steps[x, y] > @steps[ *node ] + 1
              open( x, y, @steps[ *node ] + 1 )
            end
          end
        }
        close *node
      }
    end
    return false
  end
  #============================================================================
  # * Set path_coords
  #   With @steps programmed, start at the goal and work backwards to find
  #   a valid path.  Assumes that there is such a path.
  #============================================================================
  def set_path_coords
    # Set the coord-based path
    @path_coords = []
    x, y = @goal_x, @goal_y
    while ( [x, y] != [@start_x, @start_y] ) do
      # Add this point to the path
      @path_coords.push( [x, y] )
      choices = []
      min_dist = nil
      DIRS.each { |dir|
        # Possible to step in this direction?
        next unless passable?( x, y, dir )
        # Get the coords
        check_x, check_y = *coords_at(x, y, dir)
        # Unexplored tile?
        next if @steps[check_x, check_y] == 0
        # Not a backtrack?
        next unless @steps[check_x, check_y] < @steps[x, y]
        # Process choice
        if min_dist.nil? or @steps[check_x, check_y] <= min_dist
          choices.clear
          min_dist = @steps[check_x, check_y]
        end
        if @steps[check_x, check_y] == min_dist
          choices.push( [check_x, check_y ] )
        end
      }
      x, y = *choices[rand( choices.size )]
    end
    @path_coords.push( [@start_x, @start_y] )
    @path_coords.reverse!
  end
  #============================================================================
  # * Set path_dirs
  #   With @path_coords programmed, create a path consisting of directions.
  #============================================================================
  def set_path_dirs
    @path_dirs = []
    if @path_coords.size > 1
      0.upto(@path_coords.size - 2) { |i|
        here, there = @path_coords[i], @path_coords[i + 1]
        if here[0] == there[0]
          @path_dirs.push( here[1] > there[1] ? 8 : 2 )
        else
          @path_dirs.push( here[0] > there[0] ? 4 : 6 )
        end
      }
    end
  end
  #============================================================================
  # * The length of the path
  #============================================================================
  def length
    @path_coords.length - 1
  end
  #============================================================================
  # * The first direction of passage
  #============================================================================
  def first_direction
    @path_dirs[0]
  end
  #============================================================================
  # * Move route
  #============================================================================
  def move_route
    route = RPG::MoveRoute.new
    route.list.clear
    @path_dirs.each { |dir|
      command = RPG::MoveCommand.new
      command.code = dir / 2
      route.list.push command
    }
    route
  end
end