#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
# Lagless Path Finder by Blizzard
# Version: 1.0
# Type: Pathfinding System
# Date: 9.2.2013
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
#   
#  This work is protected by the following license:
# #----------------------------------------------------------------------------
# #  
# #  Creative Commons - Attribution-NonCommercial-ShareAlike 3.0 Unported
# #  ( http://creativecommons.org/licenses/by-nc-sa/3.0/ )
# #  
# #  You are free:
# #  
# #  to Share - to copy, distribute and transmit the work
# #  to Remix - to adapt the work
# #  
# #  Under the following conditions:
# #  
# #  Attribution. You must attribute the work in the manner specified by the
# #  author or licensor (but not in any way that suggests that they endorse you
# #  or your use of the work).
# #  
# #  Noncommercial. You may not use this work for commercial purposes.
# #  
# #  Share alike. If you alter, transform, or build upon this work, you may
# #  distribute the resulting work only under the same or similar license to
# #  this one.
# #  
# #  - For any reuse or distribution, you must make clear to others the license
# #    terms of this work. The best way to do this is with a link to this web
# #    page.
# #  
# #  - Any of the above conditions can be waived if you get permission from the
# #    copyright holder.
# #  
# #  - Nothing in this license impairs or restricts the author's moral rights.
# #  
# #----------------------------------------------------------------------------
# 
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
# 
# IMPORTANT NOTE:
# 
#   This Path Finder is a derived version of Blizz-ABS's original Path Finder.
#   If you are using Blizz-ABS, please remove this script. Blizz-ABS has a
#   Path Finder already built-in.
# 
# 
# Compatibility:
# 
#   99% compatible with SDK v1.x. 90% compatible with SDK v2.x. May cause
#   incompatibility issues with exotic map systems.
# 
# 
# Features:
# 
#   - calculates path from point A to point B on the map
#   - allows immediate calculation as well as path calculation requests that
#     are done over the course of a few frames in order to reduce lag
#   - supports dynamic calculation that is done every step to ensure the
#     character reaches its targets
#   - can assign other characters as targets so dynamic calculation with a
#     moving will cause the character to find the target regardless of his
#     changed position
# 
# 
# Instructions:
#   
# - Explanation:
#   
#   This script will allow your characters to walk from point A to point B,
#   navigating by themselves, finding the shortest path and all that without
#   you having to manually specify their moving route. They can also navigate
#   through dynamically changing environments or track a dynamically moving
#   target.
# 
# - Configuration:
# 
#   MAX_NODES_PER_FRAME - maximum number of node calculation per frame when
#                         using path requests instead of immediate calculations
#   DIRECTIONS_8_WAY    - if set to true, it will smooth out corner movement
#                         and use a diagonal movement step wherever possible
#                         (this does NOT mean that the path finder will do
#                         8-directional path finding!)
# 
# - Script calls:
# 
#   This path finder offers you several script calls in order to designate path
#   finding to characters on the map. Following script calls are at your
#   disposal:
#   
#     PathFinder.find(C_ID, X, Y)
#     PathFinder.find(C_ID, X, Y, RANGE)
#     PathFinder.find(C_ID, TARGET)
#     PathFinder.find(C_ID, TARGET, RANGE)
#     PathFinder.request(C_ID, X, Y)
#     PathFinder.request(C_ID, X, Y, RANGE)
#     PathFinder.request(C_ID, TARGET)
#     PathFinder.request(C_ID, TARGET, RANGE)
#     PathFinder.dyn_find(C_ID, X, Y)
#     PathFinder.dyn_find(C_ID, X, Y, RANGE)
#     PathFinder.dyn_find(C_ID, TARGET)
#     PathFinder.dyn_find(C_ID, TARGET, RANGE)
#     PathFinder.dyn_request(C_ID, X, Y)
#     PathFinder.dyn_request(C_ID, X, Y, RANGE)
#     PathFinder.dyn_request(C_ID, TARGET)
#     PathFinder.dyn_request(C_ID, TARGET, RANGE)
# 
#   C_ID   - either an event ID, 0 for the player character or an actual
#            character (e.g. $game_map.events[ID])
#   X      - X target coordinate
#   Y      - Y target coordinate
#   RANGE  - range within which the target should be located (greater than 0)
#   TARGET - an actual target character
#   
#   This is how the 4 different script calls behave:
#   
#   - The "find" variants always calculate the path immediately.
#   - The "request" variants always request a path calculation to be done over
#     the course of several frames in order to avoid lag. Requesting paths for
#     multiple characters will cause the calculation to take longer as each
#     frame only a certain number of nodes is calculated (can be configured).
#     So if there are more characters requesting a path, naturally each one
#     will consume a part of the allowed node calculations every frame.
#   - The "dyn" variants (dynamic) will recalculate/request a calculation every
#     step in order to keep a path up to date with an ever-changing
#     environment. You won't need to use these calls if there are no moving
#     events on the map or if there are no environmental passability changes.
#   - When using a "dyn" variant, if actual coordinates (X, Y) are used, the
#     character will find its path to these fixed coordinates. If an actual
#     target character is being used, the path finder will track the character
#     instead of fixed coordinates. If the character changes its position, the
#     path calculation will attempt to find a path to the new position of the
#     target.
#   - Using "dyn_find" a lot, with many characters at the same time and/or for
#     long paths may cause performance issue and lag. Use it wisely.
#   - Using "dyn_request" is much more performance-friendly, but it will also
#     cause characters to "stop and think". This can also cause problems in a
#     constantly changing environment as the environment may change during the
#     few frames while the calculation is being done. Use it wisely.
#   
#   In order to cancel dynamic path calculation for a character, use following
#   script call:
#   
#     character.clear_path_target
#   
#   Example:
#     
#     $game_map.events[23].clear_path_target
#   
#   In order to check if a character has a dynamic path calculation for a
#   target, use following script call:
#   
#     character.has_path_target?
#   
#   Example:
#     
#     if $game_map.events[23].has_path_target?
#   
# 
# Notes:
# 
#   - This path finder is an implementation fo the A* Search Algorithm.
#   - The PathFinder module is being updated during the call of $game_system.update.
#     Keep this in mind if you are using specific exotic scripts.
# 
# 
# If you find any bugs, please report them here:
# http://forum.chaos-project.com
#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# START Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

module BlizzCFG
  
  MAX_NODES_PER_FRAME = 100
  DIRECTIONS_8_WAY = false
  
end

#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
# END Configuration
#::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::

$lagless_path_finder = 1.0

#==============================================================================
# module PathFinder
#==============================================================================

module Math
  
  def self.hypot_squared(x, y)
    return (x * x + y * y)
  end
  
end

#==============================================================================
# module PathFinder
#==============================================================================

module PathFinder
  
  PATH_DIRS = [[0, 1, 2], [-1, 0, 4], [1, 0, 6], [0, -1, 8]]
  DIR_DOWN_LEFT = [2, 4]
  DIR_LEFT_DOWN = [4, 2]
  DIR_DOWN_RIGHT = [2, 6]
  DIR_RIGHT_DOWN = [6, 2]
  DIR_LEFT_UP = [4, 8]
  DIR_UP_LEFT = [8, 4]
  DIR_RIGHT_UP = [6, 8]
  DIR_UP_RIGHT = [8, 6]
  DIR_OFFSETS = [[0, 0], [-1, 1], [0, 1], [1, 1], [-1, 0], [0, 0], [1, 0],
                [-1, -1], [0, -1], [1, -1]]
  
  @requests = {}
  
  def self.clear
    @requests = {}
  end
  
  def self.find(char, x, y = nil, range = 0)
    char, x, y, range = self.check_args(char, x, y, range)
    self._find(char, x, y, range, false)
    return true
  end
  
  def self.dyn_find(char, x, y = nil, range = 0)
    tx, ty = x, y
    char, x, y, range = self.check_args(char, x, y, range)
    self._find(char, x, y, range, true)
    char.set_path_target(tx, ty, range, true)
    return true
  end
  
  def self.request(char, x, y = nil, range = 0)
    char, x, y, range = self.check_args(char, x, y, range)
    self._request(char, x, y, range, false)
    return true
  end
  
  def self.dyn_request(char, x, y = nil, range = 0)
    tx, ty = x, y
    char, x, y, range = self.check_args(char, x, y, range)
    self._request(char, x, y, range, true)
    char.set_path_target(tx, ty, range, false)
    return true
  end
  
  def self.check_args(char, x, y, range)
    if x.is_a?(Game_Character)
      range = (y != nil ? y : 0)
      y = x.y
      x = x.x
    end
    range = 0 if range < 0
    if char.is_a?(Numeric)
      char = (char > 0 ? $game_map.events[char] : $game_player)
    end
    p "Warning! Character to move does not exist!" if $DEBUG && char == nil
    return [char, x, y, range]
  end
  
  def self._find(char, x, y, range, dynamic)
    @requests[char] = PathRequest.new(char.x, char.y, x, y, range, dynamic)
    result = nil
    result = self.calc_node(char) while result == nil
    @requests.delete(char)
    if $DEBUG && result == []
      p "Warning! Path Finder could not find path for character at (#{x},#{y})!"
    end
    char.set_found_path(result)
  end
  
  def self._request(char, x, y, range, dynamic)
    if @requests[char] == nil
      @requests[char] = PathRequest.new(char.x, char.y, x, y, range, dynamic)
    end
  end
  
  def self.update
    @requests = {} if @requests == nil
    characters = @requests.keys
    count = BlizzCFG::MAX_NODES_PER_FRAME
    while characters.size > 0 && count > 0
      char = characters.shift
      result = self.calc_node(char)
      result != nil ? char.set_found_path(result) : characters.push(char)
      count -= 1
    end
  end

  def self.calc_node(char)
    request = @requests[char]
    if request.open.size == 0
      @requests.delete(char)
      return []
    end
    found = false
    key = request.open.keys.min {|a, b|
        a[2] > b[2] ? 1 : (a[2] < b[2] ? -1 :
        (Math.hypot_squared(a[0] - request.tx, a[1] - request.ty) <=>
        Math.hypot_squared(b[0] - request.tx, b[1] - request.ty)))}
    request.closed[key[0], key[1]] = request.open[key]
    request.open.delete(key)
    kx, ky = 0, 0
    passable = false
    passable_checked = false
    PATH_DIRS.each {|dir|
        kx, ky = key[0] + dir[0], key[1] + dir[1]
        if request.range == 0 && kx == request.tx && ky == request.ty
          request.closed[kx, ky] = dir[2]
          found = true
          break
        end
        passable = false
        passable_checked = false
        if request.range > 0 &&
            (kx - request.tx).abs + (ky - request.ty).abs <= request.range
          passable = char.passable?(key[0], key[1], dir[2])
          passable_checked = true
          if passable
            request.closed[kx, ky] = dir[2]
            found = true
            break
          end
        end
        if request.closed[kx, ky] == 0
          passable = char.passable?(key[0], key[1], dir[2]) if !passable_checked
          if passable
            request.open[[kx, ky, key[2] + 1]] = dir[2]
          end
        end}
    return nil if !found
    result = request.backtrack(kx, ky)
    @requests.delete(char)
    return result
  end
  
end

#==============================================================================
# PathRequest
#==============================================================================

class PathRequest
  
  attr_reader :open
  attr_reader :closed
  attr_reader :sx
  attr_reader :sy
  attr_reader :tx
  attr_reader :ty
  attr_reader :range
  attr_reader :dynamic
  
  def initialize(ox, oy, tx, ty, range, dynamic = false)
    @sx, @sy, @tx, @ty, @range, @dynamic = ox, oy, tx, ty, range, dynamic
    @open = {[@sx, @sy, 0] => -1}
    @closed = Table.new($game_map.width, $game_map.height)
  end
  
  def backtrack(tx, ty)
    cx, cy, x, y, result = tx, ty, 0, 0, []
    loop do
      cx, cy = cx - x, cy - y
      break if cx == @sx && cy == @sy
      result.unshift(@closed[cx, cy])
      x, y = PathFinder::DIR_OFFSETS[@closed[cx, cy]]
    end
    return self.modify_8_way(result)
  end
  
  def modify_8_way(result)
    if BlizzCFG::DIRECTIONS_8_WAY
      result.each_index {|i|
          if result[i] != nil && result[i + 1] != nil
            case [result[i], result[i + 1]]
            when PathFinder::DIR_DOWN_LEFT, PathFinder::DIR_LEFT_DOWN
              result[i], result[i + 1] = 1, nil
            when PathFinder::DIR_DOWN_RIGHT, PathFinder::DIR_RIGHT_DOWN
              result[i], result[i + 1] = 3, nil
            when PathFinder::DIR_LEFT_UP, PathFinder::DIR_UP_LEFT
              result[i], result[i + 1] = 7, nil
            when PathFinder::DIR_RIGHT_UP, PathFinder::DIR_UP_RIGHT
              result[i], result[i + 1] = 9, nil
            end
          end}
      result.compact!
    end
    return result
  end
  
end

#==============================================================================
# Game_System
#==============================================================================

class Game_System
  
  alias update_lagless_path_finder_later update
  def update
    PathFinder.update
    update_lagless_path_finder_later
  end
  
end

#==============================================================================
# Game_Map
#==============================================================================

class Game_Map
  
  alias setup_lagless_path_finder_later setup
  def setup(map_id)
    PathFinder.clear
    setup_lagless_path_finder_later(map_id)
  end
  
end

#==============================================================================
# Game_Character
#==============================================================================

class Game_Character
  
  def set_path_target(x, y, range, immediate)
    @path_x, @path_y, @path_range, @path_immediate = x, y, range, immediate
  end
  
  def clear_path_target
    @path_x, @path_y, @path_range, @path_immediate = nil, nil, nil, nil
  end
  
  def has_path_target?
    return (@path_x != nil)
  end
  
  def set_found_path(path)
    return if path.size == 0
    route = RPG::MoveRoute.new
    route.repeat = false
    # each move command code equals direction / 2
    path.reverse.each {|dir| route.list.unshift(RPG::MoveCommand.new(dir / 2))}
    self.force_move_route(route)
  end
  
  alias update_move_lagless_path_finder_later update_move
  def update_move
    update_move_lagless_path_finder_later
    return if self.moving? || !self.has_path_target?
    x, y = @path_x, @path_y
    x, y = @path_x.x, @path_x.y if @path_x.is_a?(Game_Character)
    if @x == x && @y == y
      #p @x, x, @y, y
      #p @path_x
      self.clear_path_target
    elsif @path_immediate
      PathFinder.dyn_find(self, @path_x, @path_y, @path_range)
    else
      PathFinder.dyn_request(self, @path_x, @path_y, @path_range)
    end
  end
  
end
