#:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=:=
# 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)
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
