#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker
# Version 1.0
#==============================================================================
#
#                                    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 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
#==============================================================================

#==============================================================================
# ** 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, the result array will be always ordered ascendingly
  #    ii : element to be added into the array
  #--------------------------------------------------------------------------
  def addEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.insert(iii,ii)
  end
  #--------------------------------------------------------------------------
  # * Remove Element
  #    ii : element to be removed from the array, the result remains if
  #          ii isn't found in the array
  #--------------------------------------------------------------------------
  def remEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.delete_at(iii)
  end
  #--------------------------------------------------------------------------
  # * Is Element Found?
  #    ii : element to be searched in the array (using binary search)
  #  Returns true if ii found in the array
  #--------------------------------------------------------------------------
  def found?(ii)
    i = 0
    j = self.length-1
    ff = false
    while (not ff) && i <= j
      mid = (i+j)/2
      if self[mid] == ii
        ff = true
      else
        if self[mid] < ii
          i = mid+1
        else
          j = mid-1
        end
      end
    end
    return ff
  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 :neighbors
  attr_accessor :passage_table
  #--------------------------------------------------------------------------
  # * Map Graph Initialization
  #--------------------------------------------------------------------------
  def initialize(nh)
    @w = $game_map.width
    @h = $game_map.height
    @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,0)
    # Add s into open list q
    q.addEl(s)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    # 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 > 1
      # Finds vertex u with least value of path distance
      d = vertices_dist[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if vertices_dist[q[ii]]<d
                  d = vertices_dist[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Remove u from open list q
      q.remEl(u)
      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.addEl(v)
            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,0)
    # Add s into open list q
    q.addEl(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,9999)
    h_score = Array.new(@w*@h+1,0)
    f_score = Array.new(@w*@h+1,9999)
    # 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 > 1
      # Finds vertex u with least value of f_score
      d = f_score[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if f_score[q[ii]]<d
                  d = f_score[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Move current node from open list to the closed list
      q.remEl(u)
      q1[u] = true
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          if !q1[v]
            tentative_g_score = vertices_dist[u]+1
            if !q.found?(v)
              q.addEl(v)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
            else
              tentative_is_better = false
            end
            if tentative_is_better
              if vertices_prev[v] != 0
                if f_score[u] < f_score[vertices_prev[v]]
                  vertices_prev[v] = u
                end
              else
                vertices_prev[v] = u
              end
              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
    end
    return 0
  end
end

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker
# Version 1.0
#==============================================================================
#
#                                    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
  #--------------------------------------------------------------------------
  def setup(map_id)
    # Put map ID in @map_id memory
    @map_id = map_id
    # Load map from file and set @map
    @map = load_data(sprintf("Data/Map%03d.rxdata", @map_id))
    # set tile set information in opening instance variables
    tileset = $data_tilesets[@map.tileset_id]
    @tileset_name = tileset.tileset_name
    @autotile_names = tileset.autotile_names
    @panorama_name = tileset.panorama_name
    @panorama_hue = tileset.panorama_hue
    @fog_name = tileset.fog_name
    @fog_hue = tileset.fog_hue
    @fog_opacity = tileset.fog_opacity
    @fog_blend_type = tileset.fog_blend_type
    @fog_zoom = tileset.fog_zoom
    @fog_sx = tileset.fog_sx
    @fog_sy = tileset.fog_sy
    @battleback_name = tileset.battleback_name
    @passages = tileset.passages
    @priorities = tileset.priorities
    @terrain_tags = tileset.terrain_tags
    # Initialize displayed coordinates
    @display_x = 0
    @display_y = 0
    # Clear refresh request flag
    @need_refresh = false
    # Set map event data
    @events = {}
    for i in @map.events.keys
      @events[i] = Game_Event.new(@map_id, @map.events[i])
    end
    # Set common event data
    @common_events = {}
    for i in 1...$data_common_events.size
      @common_events[i] = Game_CommonEvent.new(i)
    end
    # Initialize all fog information
    @fog_ox = 0
    @fog_oy = 0
    @fog_tone = Tone.new(0, 0, 0, 0)
    @fog_tone_target = Tone.new(0, 0, 0, 0)
    @fog_tone_duration = 0
    @fog_opacity_duration = 0
    @fog_opacity_target = 0
    # Initialize scroll information
    @scroll_direction = 2
    @scroll_rest = 0
    @scroll_speed = 4
    # Make MGraph
    $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
      if tile_id == nil
        # impassable
        return false
      # If obstacle bit is set
      elsif @passages[tile_id] & bit != 0
        # impassable
        return false
      # If obstacle bit is set in all directions
      elsif @passages[tile_id] & 0x0f == 0x0f
        # impassable
        return false
      # If priorities other than that are 0
      elsif @priorities[tile_id] == 0
        # passable
        return true
      end
    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_toward_player
  end
  #--------------------------------------------------------------------------
  # * Move toward Player (modified)
  #--------------------------------------------------------------------------
  def move_toward_player
    # Get difference in player coordinates
    sx = @x - $game_player.x
    sy = @y - $game_player.y
    # If coordinates are equal
    if sx == 0 and sy == 0
      return
    end
    # 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
      move_down
    when 2
      move_left
    when 3
      move_right
    when 4
      move_up
    else  # If no path is found
      # Get absolute value of difference
      abs_sx = sx.abs
      abs_sy = 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
      end
      # If horizontal distance is longer
      if abs_sx > abs_sy
        # Move towards player, prioritize left and right directions
        sx > 0 ? move_left : move_right
        if not moving? and 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? and sx != 0
          sx > 0 ? move_left : move_right
        end
      end
    end
  end
end

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.0
#==============================================================================
#
#                                    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 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
#==============================================================================

#==============================================================================
# ** 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, the result array will be always ordered ascendingly
  #    ii : element to be added into the array
  #--------------------------------------------------------------------------
  def addEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.insert(iii,ii)
  end
  #--------------------------------------------------------------------------
  # * Remove Element
  #    ii : element to be removed from the array, the result remains if
  #          ii isn't found in the array
  #--------------------------------------------------------------------------
  def remEl(ii)
    iii = 0
    while iii < self.length && self[iii] < ii
      iii += 1
    end
    self.delete_at(iii)
  end
  #--------------------------------------------------------------------------
  # * Is Element Found?
  #    ii : element to be searched in the array (using binary search)
  #  Returns true if ii found in the array
  #--------------------------------------------------------------------------
  def found?(ii)
    i = 0
    j = self.length-1
    ff = false
    while (not ff) && i <= j
      mid = (i+j)/2
      if self[mid] == ii
        ff = true
      else
        if self[mid] < ii
          i = mid+1
        else
          j = mid-1
        end
      end
    end
    return ff
  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 :neighbors
  attr_accessor :passage_table
  #--------------------------------------------------------------------------
  # * Map Graph Initialization
  #--------------------------------------------------------------------------
  def initialize(nh)
    @w = $game_map.width
    @h = $game_map.height
    @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,0)
    # Add s into open list q
    q.addEl(s)
    # Unknown distance function from source to v
    vertices_dist = Array.new(@w*@h+1,9999)
    # 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 > 1
      # Finds vertex u with least value of path distance
      d = vertices_dist[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if vertices_dist[q[ii]]<d
                  d = vertices_dist[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Remove u from open list q
      q.remEl(u)
      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.addEl(v)
            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,0)
    # Add s into open list q
    q.addEl(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,9999)
    h_score = Array.new(@w*@h+1,0)
    f_score = Array.new(@w*@h+1,9999)
    # 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 > 1
      # Finds vertex u with least value of f_score
      d = f_score[q[1]]
         u = q[1]
         if q.length>2
        for ii in 2..q.length-1
               if f_score[q[ii]]<d
                  d = f_score[q[ii]]
                  u = q[ii]
               end
        end
         end
      # Search completed
      if u == t
        return reconstruct_path(s,t,vertices_prev)
      end
      # Move current node from open list to the closed list
      q.remEl(u)
      q1[u] = true
      for i in 1..@neighbors
        if @passage_table[xNode(u),yNode(u),i-1] == 1
          v = neighborOf(u,i)
          if !q1[v]
            tentative_g_score = vertices_dist[u]+1
            if !q.found?(v)
              q.addEl(v)
              tentative_is_better = true
            elsif tentative_g_score < vertices_dist[v]
              tentative_is_better = true
            else
              tentative_is_better = false
            end
            if tentative_is_better
              if vertices_prev[v] != 0
                if f_score[u] < f_score[vertices_prev[v]]
                  vertices_prev[v] = u
                end
              else
                vertices_prev[v] = u
              end
              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
    end
    return 0
  end
end

#==============================================================================
# Listra Pathfinder Module by Bunga Tepi Jalan
# for RPG Maker VX
# Version 1.0
#==============================================================================
#
#                                    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 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
    # Make MGraph
    $mgraph = MGraph.new(4)
  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
      # 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
        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