[VX] Listra Pathfinder Module

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.2
#==============================================================================
#
#                                    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
#  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?(xNode(neighborOf(nodeOf(i,j),k)),yNode(neighborOf(nodeOf(i,j),k)),0x01) ? 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 VX
# Version 1.2
#==============================================================================
#
#                                    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, 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
#==============================================================================

#==============================================================================
# ** Game_Map (part 2 - overriden)
#------------------------------------------------------------------------------
#  This class handles maps. It includes scrolling and passage determination
#  functions. The instance of this class is referenced by $game_map.
#  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
  #--------------------------------------------------------------------------
  def setup(map_id)
    @map_id = map_id
    @map = load_data(sprintf("Data/Map%03d.rvdata", @map_id))
    @display_x = 0
    @display_y = 0
    @passages = $data_system.passages
    referesh_vehicles
    setup_events
    setup_scroll
    setup_parallax
    @need_refresh = false
    # Initializes MGraph instance
    $mgraph = LPM::MGraph.new(4,LPM::ALGO_USED)
  end
  #--------------------------------------------------------------------------
  # * Determine if Passable (ignoring events)
  #    x    : x coordinate
  #    y    : y coordinate
  #    flag : The impassable bit to be looked up
  #            (normally 0x01, only changed for vehicles)
  #--------------------------------------------------------------------------
  def passable2?(x, y, flag = 0x01)
    for i in [2, 1, 0]                      # in order from on top of layer
      tile_id = @map.data[x, y, i]          # get tile ID
      return false if tile_id == nil        # failed to get tile: Impassable
      pass = @passages[tile_id]            # get passable attribute
      next if pass & 0x10 == 0x10          # *: Does not affect passage
      return true if pass & flag == 0x00    # o: Passable
      return false if pass & flag == flag  # x: Impassable
    end
    return false                            # Impassable
  end
end

#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
#  This class deals with characters. It's used as a superclass of the
# Game_Player and Game_Event classes.
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # * Move Type : Approach
  #--------------------------------------------------------------------------
  def move_type_toward_player
    # Approach player
    move_toward_player
  end
  #--------------------------------------------------------------------------
  # * Move toward Player
  #--------------------------------------------------------------------------
  def move_toward_player
    sx = distance_x_from_player
    sy = distance_y_from_player
    if sx != 0 or 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
        move_down
      when 2
        move_left
      when 3
        move_right
      when 4
        move_up
      else  # If no path is found
        if sx.abs > sy.abs                  # Horizontal distance is longer
          sx > 0 ? move_left : move_right  # Prioritize left-right
          if @move_failed and sy != 0
            sy > 0 ? move_up : move_down
          end
        else                                # Vertical distance is longer
          sy > 0 ? move_up : move_down      # Prioritize up-down
          if @move_failed and sx != 0
            sx > 0 ? move_left : move_right
          end
        end
      end
    end
  end
end