[XP] Listra Pathfinder Module

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker XP
# Version 1.3
#==============================================================================
#
#                                    PART 1
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  LiTTleDRAgo
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's, A*, or Floyd–Warshall Algorithm).
#
#  To learn about pathfinding algorithms, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rmid.forumotion.net
#  - http://prodig.forumotion.net
#  - http://vixep.forumotion.com
#==============================================================================

module LPM
  #--------------------------------------------------------------------------
  # * Listra Pathfinder Module Configuration
  #--------------------------------------------------------------------------
 
  # Config 1 -- Pathfinding algorithm to be used:
  #  1. Dijkstra's algorithm, always accurate but lacks its performance.
  #    Use this only for small maps.
  #  2. A* algorithm, accurate but not as well as Dijkstra's algorithm.
  #    However, A* works much faster than Dijkstra's do. Recommended to
  #    use this, even for large maps.
  ALGO_USED = 2
 
  #==============================================================================
  # ** PQueue
  #------------------------------------------------------------------------------
  #  This class, as derivation of Array, provides additional operations, such
  #  as insert and remove element such that the array behaves like a priority
  #  queue, and also search value in the array. This will be used on
  #  pathfinding algorithms in MGraph class.
  #==============================================================================
 
  class PQueue < Array
    #--------------------------------------------------------------------------
    # * Add Element, values of elements priority will be always sorted
    #  descendingly
    #    ii : element to be added into the array
    #    PT : priority table to which array elements index
    #--------------------------------------------------------------------------
    def enqueue(ii,pt)
      iii = 0
      while iii < self.length && pt[self[iii]] > pt[ii]
        iii += 1
      end
      self.insert(iii,ii)
    end
  end
 
  #==============================================================================
  # ** MGraph
  #------------------------------------------------------------------------------
  #  This class generates a passage graph of given 2-dimensional map and uses it
  #  for pathfinding analysis with Dijkstra's algorithm and A*. Refer to
  #  "$mgraph" for the instance of this class.
  #==============================================================================
 
  class MGraph
    #--------------------------------------------------------------------------
    # * Public Instance Variables
    #--------------------------------------------------------------------------
    attr_accessor :w, :h
    attr_accessor :algo
    attr_accessor :neighbors
    attr_accessor :passage_table
    attr_accessor :floydpath, :floydnext
    #--------------------------------------------------------------------------
    # * Invariables
    #--------------------------------------------------------------------------
    INFINITY = 9999
    #--------------------------------------------------------------------------
    # * Graph Initialization
    #    nh : number of neighbors or allowed directions
    #    inalgo : pathfinding algorithm to be used
    #--------------------------------------------------------------------------
    def initialize(nh,inalgo)
      @w = $game_map.width
      @h = $game_map.height
      @algo = inalgo
      @neighbors = nh
      # Passage table for each map nodes
      @passage_table = Table.new(@w,@h,nh)
      for i in 0..@w
        for j in 0..@h
          for k in 1..nh
            @passage_table[i,j,k-1] = $game_map.passable2?(i,j,k*2) ? 1 : 0
            if not neighborExist?(nodeOf(i,j),k)
              @passage_table[i,j,k-1] = 0
            end
          end
        end
      end
    end
    #--------------------------------------------------------------------------
    # * Node/Vertex Of
    #    x : x-position
    #    y : y-position
    #--------------------------------------------------------------------------
    def nodeOf(x,y)
      return y*@w+x+1
    end
    #--------------------------------------------------------------------------
    # * xNode, yNode
    #    idxNode : index of node
    #--------------------------------------------------------------------------
    def xNode(idxNode)
      return (idxNode-1)%@w
    end
    def yNode(idxNode)
      return (idxNode-1)/@w
    end
    #--------------------------------------------------------------------------
    # * Neighbor Of
    #    idxNode : index of node
    #    dir : down(1), left(2), right(3), or up(4)
    #  Returns index of adjacent node idxNode
    #--------------------------------------------------------------------------
    def neighborOf(idxNode,dir)
      case dir
        when 1
          return (idxNode+@w)
        when 2
          return (idxNode-1)
        when 3
          return (idxNode+1)
        when 4
          return (idxNode-@w)
      end
    end
    #--------------------------------------------------------------------------
    # * Is Neighbor Exist?
    #    idxNode : index of node
    #    dir : down(1), left(2), right(3), or up(4)
    #  Returns if adjacent node of idxNode exists
    #--------------------------------------------------------------------------
    def neighborExist?(idxNode,dir)
      case dir
        when 1
          return (yNode(idxNode)<@h-1)
        when 2
          return (xNode(idxNode)>0)
        when 3
          return (xNode(idxNode)<@w-1)
        when 4
          return (yNode(idxNode)>0)
      end
    end
    #--------------------------------------------------------------------------
    # * Reconstruct Path
    #    s : source node
    #    t : target node
    #    vertices_prev : map of navigated nodes
    #  Returns movement direction 1(down), 2(left), 3(right), or 4(up)
    #--------------------------------------------------------------------------
    def reconstruct_path(s,t,vertices_prev)
      u=t
      while vertices_prev[u] != s && vertices_prev[u] != 0
        u = vertices_prev[u]
      end
      case u
        when s+@w
          return 1
        when s-1
          return 2
        when s+1
          return 3
        when s-@w
          return 4
      end
      return 0
    end
    #--------------------------------------------------------------------------
    # * Heuristic Distance
    #    u : node 1
    #    v : node 2
    #--------------------------------------------------------------------------
    def heuristic_dist(u,v)
      dx = xNode(v)-xNode(u)
      dy = yNode(v)-yNode(u)
      # Manhattan distance heuristic
      return (dx.abs+dy.abs)
    end
    #--------------------------------------------------------------------------
    # * Dijkstra's Algorithm
    #    x1, y1 : source coordinate
    #    x2, y2 : target coordinate
    #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
    #--------------------------------------------------------------------------
    def Dijkstra(x1, y1, x2, y2)
      # Initializations
      s = nodeOf(x1,y1)
      t = nodeOf(x2,y2)
      # Create open list q (as priority queue)
      q = PQueue.new(1,s)
      # Unknown distance function from source to v
      vertices_dist = Array.new(@w*@h+1,INFINITY)
      # Previous node in optimal path from source
      vertices_prev = Array.new(@w*@h+1,0)
      # Distance from source to source
      vertices_dist[s] = 0
      # The main loop
      while q.length > 0
        # Removes vertex u with least vertices_dist from open list and set it as
        # current node
        u = q.pop
        # Search completed
        if u == t
          return reconstruct_path(s,t,vertices_prev)
        end
        for i in 1..@neighbors
          if @passage_table[xNode(u),yNode(u),i-1] == 1
            v = neighborOf(u,i)
            alt = vertices_dist[u]+1
            if alt < vertices_dist[v]
              # Relax (u,v)
              q.enqueue(v,vertices_dist)
              vertices_dist[v]=alt
              vertices_prev[v]=u
            end
          end
        end
      end
      return 0
    end
    #--------------------------------------------------------------------------
    # * A* Algorithm
    #    x1, y1 : source coordinate
    #    x2, y2 : target coordinate
    #  Returns movement towards target 1(down), 2(left), 3(right), or 4(up)
    #--------------------------------------------------------------------------
    def AStar(x1, y1, x2, y2)
      # Initializations
      s = nodeOf(x1,y1)
      t = nodeOf(x2,y2)
      # Create open list q (as priority queue)
      q = PQueue.new(1,s)
      # Create closed list q1, The list of nodes already evaluated.
      q1 = Array.new(@w*@h+1,false)
      # The map of navigated nodes.
      vertices_prev = Array.new(@w*@h+1,0)
      # Unknown distance function from source to v
      vertices_dist = Array.new(@w*@h+1,INFINITY)
      h_score = Array.new(@w*@h+1,0)
      f_score = Array.new(@w*@h+1,INFINITY)
      # Distance from source to source
      vertices_dist[s] = 0
      h_score[s] = heuristic_dist(s,t)
      f_score[s] = h_score[s]
      # The main loop
      while q.length > 0
        # Removes vertex u with least f_score from open list and set it as
        # current node
        u = q.pop
        # Search completed
        if u == t
          return reconstruct_path(s,t,vertices_prev)
        end
        # Move current node from open list to the closed list
        q1[u] = true
        for i in 1..@neighbors
          if @passage_table[xNode(u),yNode(u),i-1] == 1
            v = neighborOf(u,i)
            tentative_g_score = vertices_dist[u]+1
            if !q1[v] && q.index(v) == nil
              q.enqueue(v,f_score)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
              if q1[v]
                q1[v] = 0
              end
            else
              tentative_is_better = false
            end
            if tentative_is_better
              vertices_prev[v] = u
              vertices_dist[v] = tentative_g_score
              h_score[v] = heuristic_dist(v,t)
              f_score[v] = vertices_dist[v]+h_score[v]
            end
          end
        end
      end
      return 0
    end
  end

end

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker XP
# Version 1.3
#==============================================================================
#
#                                    PART 2
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  LiTTleDRAgo
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rmid.forumotion.net
#  - http://prodig.forumotion.net
#  - http://vixep.forumotion.com
#==============================================================================

#==============================================================================
# ** Game_Map (part 2 - overriden)
#------------------------------------------------------------------------------
#  This class handles the map. It includes scrolling and passable determining
#  functions. Refer to "$game_map" for the instance of this class.
#  This part overrides setup to use MGraph initialization and adds passable2?
#  method to detect obstacles (excluding events).
#==============================================================================

class Game_Map
  #--------------------------------------------------------------------------
  # * Setup
  #    map_id : map ID
  #--------------------------------------------------------------------------
  alias setup_earlier setup
  def setup(map_id)
    setup_earlier(map_id)
    # Initializes MGraph instance
    $mgraph = LPM::MGraph.new(4,LPM::ALGO_USED)
  end
  #--------------------------------------------------------------------------
  # * Determine if Passable (ignoring events)
  #    x          : x-coordinate
  #    y          : y-coordinate
  #    d          : direction (0,2,4,6,8,10)
  #                  *  0,10 = determine if all directions are impassable
  #--------------------------------------------------------------------------
  def passable2?(x, y, d)
    # If coordinates given are outside of the map
    unless valid?(x, y)
      # impassable
      return false
    end
    # Change direction (0,2,4,6,8,10) to obstacle bit (0,1,2,4,8,0)
    bit = (1 << (d / 2 - 1)) & 0x0f
    # Loop searches in order from top of layer
    for i in [2, 1, 0]
      # Get tile ID
      tile_id = data[x, y, i]
      # Tile ID acquistion failure
      return false if tile_id == nil || @passages[tile_id] & bit != 0 ||
          @passages[tile_id] & 0x0f == 0x0f
      return true if @priorities[tile_id] == 0
    end
    # passable
    return true
  end
end

#==============================================================================
# ** Game_Character (part 4 - overriden)
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#  This part overrides move_type_toward_player and move_toward_player method to
#  perform pathfinding with either Dijkstra's algorithm or A*.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Move Type : Approach (modified)
  #--------------------------------------------------------------------------
  def move_type_toward_player
    # Approach player
    move_keplayer
  end
  #--------------------------------------------------------------------------
  # * Move toward Player (modified)
  #--------------------------------------------------------------------------
  def move_keplayer
    # Get difference in player coordinates
    sx, sy = @x - $game_player.x, @y - $game_player.y
    # If coordinates are equal
    return if sx == 0 && sy == 0
    # Determines the movement towards player with pathfinding algorithm
    case $mgraph.algo
    when 1
      dir = $mgraph.Dijkstra(@x,@y,$game_player.x,$game_player.y)
    when 2
      dir = $mgraph.AStar(@x,@y,$game_player.x,$game_player.y)
    end
    case dir
    when 1 then move_down
    when 2 then move_left
    when 3 then move_right
    when 4 then move_up
    else  # If no path is found
      # Get absolute value of difference
      abs_sx, abs_sy = sx.abs, sy.abs
      # If horizontal and vertical distances are equal
      if abs_sx == abs_sy
        # Increase one of them randomly by 1
        rand(2) == 0 ? abs_sx += 1 : abs_sy += 1
      # If horizontal distance is longer
      elsif abs_sx > abs_sy
        # Move towards player, prioritize left and right directions
        sx > 0 ? move_left : move_right
        if not moving? && sy != 0
          sy > 0 ? move_up : move_down
        end
      # If vertical distance is longer
      else
        # Move towards player, prioritize up and down directions
        sy > 0 ? move_up : move_down
        if not moving? && sx != 0
          sx > 0 ? move_left : move_right
        end
      end
    end
  end
end

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker XP
# Version 1.0                                                          (edited)
#==============================================================================
#
#                                    PART 2
#
#==============================================================================
# Copyrighted by Bunga Tepi Jalan.
#  * Don't forget to credit me if you want to use this work
#  * You are free to Share - to copy, distribute and transmit the work
#  * You are free to Remix - to adapt the work
#  * You may not use this work for commercial purposes
#
# Credits
#  Wikipedia
#  Amit's A* Pages
#
#==============================================================================
# Information:
#  This script improves events' Autonomous Movement of type Approach
#  such that they will perform smart pathfinding to move towards the player,
#  by overriding predefined move_type_toward_player and
#  move_toward_player methods in class Game_Character with pathfinding
#  algorithm (either Dijkstra's or A*).
#
#  To learn about A* and Dijkstra's algorithm, visit the following articles:
#    - http://en.wikipedia.org/wiki/Dijkstra's_algorithm
#    - http://en.wikipedia.org/wiki/A*_search_algorithm
#    - http://www-cs-students.stanford.edu/~amitp/gameprog.html
#
# If you find any bugs or you have any suggestions, please report them via
# e-mail (listra92@gmail.com), or either my blog or these forums:
#  - http://bungatepijalan.wordpress.com
#  - http://rpgmakerid.com
#  - http://prodig.forumotion.net
#  - http://vixep.forumotion.com
#==============================================================================

#==============================================================================
# ** Game_Map (part 2 - overriden)
#------------------------------------------------------------------------------
#  This class handles the map. It includes scrolling and passable determining
#  functions. Refer to "$game_map" for the instance of this class.
#  This part overrides setup to use MGraph initialization and adds passable2?
#  method to detect obstacles (excluding events).
#==============================================================================

class Game_Map
  #--------------------------------------------------------------------------
  # * Setup
  #    map_id : map ID
  #--------------------------------------------------------------------------
  alias setup_earlier setup
  def setup(map_id)
    setup_earlier(map_id)
    $mgraph = MGraph.new(4)
  end
  #--------------------------------------------------------------------------
  # * Determine if Passable (ignoring events)
  #    x          : x-coordinate
  #    y          : y-coordinate
  #    d          : direction (0,2,4,6,8,10)
  #                  *  0,10 = determine if all directions are impassable
  #--------------------------------------------------------------------------
  def passable2?(x, y, d)
    # If coordinates given are outside of the map
    unless valid?(x, y)
      # impassable
      return false
    end
    # Change direction (0,2,4,6,8,10) to obstacle bit (0,1,2,4,8,0)
    bit = (1 << (d / 2 - 1)) & 0x0f
    # Loop searches in order from top of layer
    for i in [2, 1, 0]
      # Get tile ID
      tile_id = data[x, y, i]
      # Tile ID acquistion failure
      return false if tile_id == nil || @passages[tile_id] & bit != 0 ||
          @passages[tile_id] & 0x0f == 0x0f
      return true if @priorities[tile_id] == 0
    end
    # passable
    return true
  end
end

#==============================================================================
# ** Game_Character (part 4 - overriden)
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass for the
#  Game_Player and Game_Event classes.
#  This part overrides move_type_toward_player and move_toward_player method to
#  perform pathfinding with either Dijkstra's algorithm or A*.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Move Type : Approach (modified)
  #--------------------------------------------------------------------------
  def move_type_toward_player
    # Approach player
    move_keplayer
  end
  #--------------------------------------------------------------------------
  # * Move toward Player (modified)
  #--------------------------------------------------------------------------
  def move_keplayer
    # Get difference in player coordinates
    sx, sy = @x - $game_player.x, @y - $game_player.y
    # If coordinates are equal
    return if sx == 0 && sy == 0
    # Determines the movement towards player with pathfinding algorithm
    # Uncomment one of these statements to use either A* or Dijkstra's
    # algorithm.
    # Note that:
    #  - Dijkstra's algorithm is always accurate but lacks its performance.
    #    You should only use this algorithm for small maps.
    #  - A* algorithm is accurate but not as well as Dijkstra's algorithm.
    #    However, A* works much faster than Dijkstra's do. Recommended to
    #    use this, even for large maps.
    dir = $mgraph.AStar(@x,@y,$game_player.x,$game_player.y)
    #dir = $mgraph.Dijkstra(@x,@y,$game_player.x,$game_player.y)
    case dir
    when 1 then move_down
    when 2 then move_left
    when 3 then move_right
    when 4 then move_up
    else  # If no path is found
      # Get absolute value of difference
      abs_sx, abs_sy = sx.abs, sy.abs
      # If horizontal and vertical distances are equal
      if abs_sx == abs_sy
        # Increase one of them randomly by 1
        rand(2) == 0 ? abs_sx += 1 : abs_sy += 1
      # If horizontal distance is longer
      elsif abs_sx > abs_sy
        # Move towards player, prioritize left and right directions
        sx > 0 ? move_left : move_right
        if not moving? && sy != 0
          sy > 0 ? move_up : move_down
        end
      # If vertical distance is longer
      else
        # Move towards player, prioritize up and down directions
        sy > 0 ? move_up : move_down
        if not moving? && sx != 0
          sx > 0 ? move_left : move_right
        end
      end
    end
  end
end