Code:
#==============================================================================
# ** Path Finding V2
# PathFindingV2Beta.rb by Near Fantastica, DerVVulfman (11.09.2009)
#------------------------------------------------------------------------------
# http://www.rpg-studio.de/scriptdb/node/446
# http://www.rpg-studio.de/forum/index.php?page=Thread&threadID=32487
# http://www.hbgames.org/forums/viewtopic.php?f=156&t=26661&p=260346&hilit=path+finding#p260346
#==============================================================================
#==============================================================================
# ** Path Finding v2 beta
#------------------------------------------------------------------------------
# Original version by: Near Fantastica
# Original date: June 21, 2005
# Pathfinding Element by: Fuso
#
# Modifications/edit by: DerVVulfman
# Modification date: October 28, 2007
#
#==============================================================================
#
# INTRODUCTION:
# The original v2 pathfinding system allowed for more control over player and
# event motions than version 1. A more comprehensive 'event passable' system
# and a new interface system by Fuso added to the system's flexibility.
#
# Unfortunately, when version 2 was released (at least where I found it), the
# instructions for the system's use were only partially correct and a feature
# to enable movement 'to' a blocked destination was disabled.
#
# Though it was not my intention to tangle with any pathfinding system, luck
# (and a few friends) nudged me into experimenting with this system. And it
# is thanks to Fuso for informing me of the 'option_close' switch that origi-
# nally allows the scripter (you) to choose if a warning message pops up, or
# if the player/event can move to a blocked location.
#
# A newly added feature is the 'turn and face' feature. It adds the ability
# for the player/event to face a blocked location. Previous incarnations had
# not counted on the direction faced and merely ended the movement system if
# a location was not reachable.
#
# Another feature added is an editable 'depth' or 'limit' value. By increasing
# the depth of the pathfinding system, you can permit the pathfinding system
# to search through larger maps rather than not moving to the target location.
# Also, by reducing the depth, you can speed up the pathfinding system. The
# larger the value, the more time it takes to generate the path... but larger
# maps may need it.
#
#------------------------------------------------------------------------------
#
# FEATURES:
# * Use a 'pre-designed' movement systems similar to the Force Move Route call
# * Use a 'system generated' movement system (pathfinding) for final locations
# * Allows for 'pre-designed' or 'system generated' movement for players
# * Allows for 'pre-designed' or 'system generated' movement for events
# * Can generate a warning pop if 'pathfinding' target is blocked -OPTIONAL-
# * Can move to 'blocked' locations with 'pathfinding' systems -OPTIONAL-
# * Can 'turn and face' a desired location if blocked
# * Editable 'depth' system
#
#------------------------------------------------------------------------------
#
# INSTRUCTIONS:
# Performing a pathfinding routine with this system uses three steps. These
# steps are to:
# 1) Setup for the move
# 2) Set your pathfinding destination or custom move
# 3) Start the move.
#
# So the instructions given below will be fairly brief and in two sections...
# one section for the movement of the player and the other to move events.
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
# --PLAYER CALLS--
#
# $path_finding.setup_player(repeat, skippable = false)
# This routine call readies the player graphic for the input of pathfinding
# data or of a simple command movement call. It has to be called before
# any other call is made.
#
# repeat = If you set the repeat flag to true and the define movement
# will repeat. If set to false it will not repeat.
# skippable = If you set skippable flag to true, the event will continue
# through it's list of movement commands even when blocked.
#
# NOTE : These are not wanted in most cases that is why they
# are defaulted to false
#
#
# $path_finding.add_paths_player(trg_x, trg_y, option_close = false)
# This routine call attempts to chart a path for the player graphic so the
# player can be moved to said location. If a path is unobtainable, the
# system may either bring up a warning message or move to the closest
# possible location.
#
# trg_x = This is the X-coordinate on the map where the pathfinding
# system will chart for the player.
# trg_y = This is the y-coordinate on the map where the pathfinding
# system will chart for the player.
# option_close = This is a true/false switch. If you set this switch to
# true then the player will move to the closest possible
# location if the destination is blocked. If set to false,
# then the system will bring up a pop-up warning that the
# destination is unobtainable.
#
#
# $path_finding.add_command_player(code, parameters = [])
# This routine call attempts to move the player one step or movement command
# at a time. Passing (for example) a movement code of 'down' will move the
# character down. Very simple.
#
# code = The RGSS movement code (see below for a small list)
# parameters = Needed parameters for that movement code (such as for Jump)
# NOTE : Movement codes can be found in the Game_Character
# page 2 move_type_custom as well as there needed parameters
#
#
# $path_finding.start_player
# Once the paths or commands have been set, call this routine to move the
# player to the set location.
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
# --EVENT CALLS--
#
# $path_finding.setup_event(index, repeat, skippable = false)
# This routine call readies an event for the input of pathfinding data or of
# a simple command movement call. It has to be called before any other call
# is made. It can also be used to 'stop' an event's movement.
#
# index = the index or ID number of the map event to be moved
# repeat = If you set the repeat flag to true and the define movement
# will repeat. If set to false it will not repeat.
# skippable = If you set skippable flag to true, the event will continue
# through it's list of movement commands even when blocked.
#
# NOTE : These are not wanted in most cases that is why they
# are defaulted to false
#
#
# $path_finding.add_paths_event(index, trg_x, trg_y, option_close = false)
# This routine call attempts to chart a path for the map event so the
# event can be moved to said location. If a path is unobtainable, the
# system may either bring up a warning message or move to the closest
# possible location.
#
# index = the index or ID number of the map event to be moved
# trg_x = This is the X-coordinate on the map where the pathfinding
# system will chart for the event.
# trg_y = This is the y-coordinate on the map where the pathfinding
# system will chart for the event.
# option_close = This is a true/false switch. If you set this switch to
# true then the event will move to the closest possible lo-
# cation if the destination is blocked. If set to false,
# then the system will bring up a pop-up warning that the
# destination is unobtainable.
#
#
# $path_finding.add_command_event(index, code, parameters = [])
# This routine call attempts to move the event one step or movement command
# at a time. Passing (for example) a movement code of 'down' will move the
# event down. Very simple.
#
# index = the index or ID number of the map event to be moved
# code = The RGSS movement code (see below for a small list)
# parameters = Needed parameters for that movement code (such as for Jump)
# NOTE : Movement codes can be found in the Game_Character
# page 2 move_type_custom as well as there needed parameters
#
#
# $path_finding.start_event(index)
# Once the paths or commands have been set, call this routine to move the
# event to the set location.
#
# index = the index or ID number of the map event to be moved
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
# --DEPTH--
#
# $path_finding.set_depth(depth)
# This routine is the only call that can apply to both player and event
# movement, and directly affects the pathfinding system. It sets the max-
# imum number of steps taken to reach the destination or just how far the
# player or event will travel while trying to reach that goal.
#
# depth = the estimated number of tiles the character/event will move
# to the desired/targetted location.
#
# - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
#
# --MOVEMENT CODES--
#
# This is a selection of movement codes you can use in the add_command and
# the add_command_player routines. This is only a selection of the available
# commands... not all of them.
#
# 1) Move down 10) Move toward player 19) Turn up
# 2) Move left 11) Move away from player 20) Turn 90? right
# 3) Move right 12) 1 step forward 21) Turn 90? left
# 4) Move up 13) 1 step backward 22) Turn 180?
# 5) Move lower left 14) Jump* 23) Turn 90? right or left
# 6) Move lower right 15) Set wait count* 24) Turn at Random
# 7) Move upper left 16) Turn down 25) Turn toward player
# 8) Move upper right 17) Turn left 26) Turn away from player
# 9) Move at random 18) Turn right
#
# * These require additional parameters for use (x/y coordinates, time delay
# or other values).
#
#==============================================================================
#==============================================================================
# ** Path_Finding
#------------------------------------------------------------------------------
# This class sets and controls pathfinding movement routines. It is used
# within the Game_Character, Game_Event, Game_Player, and Game_Map classes.
#==============================================================================
class Path_Finding
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :pf_depth # pathfinding depth (limit)
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
def initialize
@player_path = nil
@player_points = []
@pf_depth = 100
end
#--------------------------------------------------------------------------
# * Setup Depth
# depth : Depth / Max number of pathfinding steps
#--------------------------------------------------------------------------
def setup_depth(depth)
@pf_depth = depth
end
#--------------------------------------------------------------------------
# * Setup Event
# index : event index / event ID number
# repeat : if path/movement is repeated
# skippable : if any blocked step can be skipped
#--------------------------------------------------------------------------
def setup_event(index, repeat = false, skippable = false)
event = $game_map.events[index]
event.points = []
event.path = RPG::MoveRoute.new
event.path.repeat = repeat
event.path.skippable = skippable
event.path.list.clear
key = [event.x,event.y]
event.points.push(key)
end
#--------------------------------------------------------------------------
# * Add Command Event
# index : event index / event ID number
# code : movement code
# parameters : movement parameters
#--------------------------------------------------------------------------
def add_command_event(index, code, parameters = [])
event = $game_map.events[index]
event.path.list.push RPG::MoveCommand.new(code, parameters)
end
#--------------------------------------------------------------------------
# * Add Paths Event
# index : event index / event ID number
# trg_x : target x-coordinate
# trg_y : target y-coordinate
# option_close : if blocked location is approachable
#--------------------------------------------------------------------------
def add_paths_event(index, trg_x, trg_y, option_close = false)
event = $game_map.events[index]
key = event.points.last
paths = $game_map.find_short_paths(key[0], key[1], trg_x, trg_y, option_close, event)
if paths == nil
print "Target " + trg_x.to_s + ","+ trg_y.to_s + " Is Unreachable for Event " + index.to_s
return
end
key = [trg_x, trg_y]
event.points.push(key)
for path in paths
event.path.list.push RPG::MoveCommand.new(4) if path == 2
event.path.list.push RPG::MoveCommand.new(2) if path == 4
event.path.list.push RPG::MoveCommand.new(3) if path == 6
event.path.list.push RPG::MoveCommand.new(1) if path == 8
# Facing direction
event.path.list.push RPG::MoveCommand.new(16) if path == 16
event.path.list.push RPG::MoveCommand.new(17) if path == 17
event.path.list.push RPG::MoveCommand.new(18) if path == 18
event.path.list.push RPG::MoveCommand.new(19) if path == 19
end
end
#--------------------------------------------------------------------------
# * Start Event
# index : event index / event ID number
#--------------------------------------------------------------------------
def start_event(index)
event = $game_map.events[index]
event.path.list.push RPG::MoveCommand.new(0)
event.force_move_route(event.path)
end
#--------------------------------------------------------------------------
# * Setup Player
# repeat : if path/movement is repeated
# skippable : if any blocked step can be skipped
#--------------------------------------------------------------------------
def setup_player(repeat = false, skippable = false)
@player_points = []
@player_path = RPG::MoveRoute.new
@player_path.repeat = repeat
@player_path.skippable = skippable
@player_path.list.clear
key = [$game_player.x, $game_player.y]
@player_points.push(key)
end
#--------------------------------------------------------------------------
# * Add Command Player
# code : movement code
# parameters : movement parameters
#--------------------------------------------------------------------------
def add_command_player(code, parameters = [])
@player_path.list.push RPG::MoveCommand.new(code, parameters)
end
#--------------------------------------------------------------------------
# * Add Paths Player
# trg_x : target x-coordinate
# trg_y : target y-coordinate
# option_close : if blocked location is approachable
#--------------------------------------------------------------------------
def add_paths_player(trg_x, trg_y, option_close = false)
key = @player_points.last
paths = $game_map.find_short_paths(key[0], key[1], trg_x, trg_y, option_close, $game_player, [$game_player])
if paths == nil
print "Target " + trg_x.to_s + "," + trg_y.to_s + " Is Unreachable for Player"
return
end
key = [trg_x, trg_y]
@player_points.push(key)
for path in paths
@player_path.list.push RPG::MoveCommand.new(4) if path == 2
@player_path.list.push RPG::MoveCommand.new(2) if path == 4
@player_path.list.push RPG::MoveCommand.new(3) if path == 6
@player_path.list.push RPG::MoveCommand.new(1) if path == 8
# Facing direction
@player_path.list.push RPG::MoveCommand.new(16) if path == 16
@player_path.list.push RPG::MoveCommand.new(17) if path == 17
@player_path.list.push RPG::MoveCommand.new(18) if path == 18
@player_path.list.push RPG::MoveCommand.new(19) if path == 19
end
end
#--------------------------------------------------------------------------
# * Start Player
#--------------------------------------------------------------------------
def start_player
@player_path.list.push RPG::MoveCommand.new(0)
$game_player.force_move_route(@player_path)
end
end
#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
# This class deals with characters. It's used as a superclass for the
# Game_Player and Game_Event classes.
#==============================================================================
class Game_Character
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :move_route
attr_accessor :move_route_index
#--------------------------------------------------------------------------
# * Pathfinding Passable?
# x : x-coordinate
# y : y-coordinat
# d : direction
# ignore_events : events to ignore
# check_player : player event to check (if event is being moved)
#--------------------------------------------------------------------------
def pf_passable?(x, y, d, ignore_events = [self], check_player = (self != $game_player))
ignore_event = [ignore_event] if not ignore_event.is_a?(Array)
new_x = x + (d == 6 ? 1 : d == 4 ? -1 : 0)
new_y = y + (d == 2 ? 1 : d == 8 ? -1 : 0)
unless $game_map.valid?(new_x, new_y)
return false
end
if @through
return true
end
unless $game_map.pf_passable?(x, y, d, ignore_events, check_player)
return false
end
unless $game_map.pf_passable?(new_x, new_y, 10 - d, ignore_events, check_player)
return false
end
for event in $game_map.events.values
if event.x == new_x and event.y == new_y
if not ignore_events.include?(event) and not event.through and not event == self
if self != $game_player
return false
end
if event.character_name != ""
return false
end
end
end
end
if $game_player.x == new_x and $game_player.y == new_y
unless $game_player.through or ignore_events.include?($game_player) or not check_player
if @character_name != ""
return false
end
end
end
return true
end
end
#==============================================================================
# ** Game_Event
#------------------------------------------------------------------------------
# This class deals with events. It handles functions including event page
# switching via condition determinants, and running parallel process events.
# It's used within the Game_Map class.
#==============================================================================
class Game_Event < Game_Character
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :path
attr_accessor :points
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
alias pf_game_event_initialize initialize
def initialize(map_id, event)
@path = []
@points = nil
pf_game_event_initialize(map_id, event)
end
end
#==============================================================================
# ** Game_Player
#------------------------------------------------------------------------------
# This class handles the player. Its functions include event starting
# determinants and map scrolling. Refer to "$game_player" for the one
# instance of this class.
#==============================================================================
class Game_Player < Game_Character
#--------------------------------------------------------------------------
# * Pathfinding Passable?
# x : x-coordinate
# y : y-coordinat
# d : direction
# ignore_events : events to ignore
# check_player : player event to check (if event is being moved)
#--------------------------------------------------------------------------
def pf_passable?(x, y, d, ignore_events = [self], check_player = false)
passable?(x,y,d)
end
end
#==============================================================================
# ** Game_Map
#------------------------------------------------------------------------------
# This class handles the map. It includes scrolling and passable determining
# functions. Refer to "$game_map" for the instance of this class.
#==============================================================================
class Game_Map
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :events
#--------------------------------------------------------------------------
# * Directional Constants
#--------------------------------------------------------------------------
UP = 2
LEFT = 4
RIGHT = 6
DOWN = 8
#--------------------------------------------------------------------------
# * Find Short Paths
# src_x : starting / source x-coordinate
# srx_y : starting / source y-coordinate
# trg_x : target x-coordinate
# trg_y : target y-coordinate
# option_close : if blocked location is approachable
# passable_owner : event being moved
# ignore_events : events to ignore
#--------------------------------------------------------------------------
def find_short_paths(src_x, src_y, trg_x, trg_y, option_close = false, passable_owner = self, ignore_events = [])
# Obtain currently selected depth/limit
depth = $path_finding.pf_depth
# Initialize final targetted coordinates (F Target x & F Target y)
ftrg_x, ftrg_y = trg_x, trg_y
# Initialize last steppable coordinates (L Target x & L Target y)
ltrg_x, ltrg_y = src_x, src_y
# Only return for impassable if 'get closest to' isn't enabled
unless option_close
return [] if not (passable_owner.pf_passable?(trg_x, trg_y, UP, ignore_events) or
passable_owner.pf_passable?(trg_x, trg_y, LEFT, ignore_events) or
passable_owner.pf_passable?(trg_x, trg_y, RIGHT, ignore_events) or
passable_owner.pf_passable?(trg_x, trg_y, DOWN, ignore_events))
end
# Paths will hold the succeeding paths.
paths = []
# Path_map will hold what paths has already been visited, to prevent that
# we attempt to walk on the same tile twice.
path_map = [src_x + src_y / 10000.0]
trackers = []
new_trackers = [[src_x, src_y, []]]
# Unless option to 'get closest to' target option enabled
unless option_close
depth.times {
break if new_trackers.empty?
trackers = new_trackers
new_trackers = []
for tracker in trackers
if tracker[0] == trg_x and tracker[1] == trg_y
paths.push tracker[2].compact
next
end
path_map.push tracker[0] + tracker[1] / 10000.0
if passable_owner.pf_passable?(tracker[0], tracker[1], DOWN, ignore_events, true) and
not path_map.include? tracker[0] + (tracker[1] - 1) / 10000.0
path_map.push tracker[0] + (tracker[1] - 1) / 10000.0
new_trackers.push [tracker[0], tracker[1] - 1, [tracker[2], UP].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], LEFT, ignore_events, true) and
not path_map.include? tracker[0] - 1 + tracker[1] / 10000.0
path_map.push tracker[0] - 1 + tracker[1] / 10000.0
new_trackers.push [tracker[0] - 1, tracker[1], [tracker[2], LEFT].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], RIGHT, ignore_events, true) and
not path_map.include? tracker[0] + 1 + tracker[1] / 10000.0
path_map.push tracker[0] + 1 + tracker[1] / 10000.0
new_trackers.push [tracker[0] + 1, tracker[1], [tracker[2], RIGHT].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], UP, ignore_events, true) and
not path_map.include? tracker[0] + (tracker[1] + 1) / 10000.0
path_map.push tracker[0] + (tracker[1] + 1) / 10000.0
new_trackers.push [tracker[0], tracker[1] + 1, [tracker[2], DOWN].flatten]
end
end
break if paths.size > 0
}
# Allow to 'get close to' if blocked
else
paths_distance = 10000 ** 2 * 2
depth.times {
trackers = new_trackers
new_trackers = []
for tracker in trackers
if tracker[0] == trg_x and tracker[1] == trg_y
if paths_distance > 0
paths_distance = 0
paths.clear
ftrg_x = tracker[0]
ftrg_y = tracker[1]
end
paths.push tracker[2].compact
next
end
distance = (tracker[0] - trg_x) ** 2 + (tracker[1] - trg_y) ** 2
if distance <= paths_distance
if distance < paths_distance
paths.clear
paths_distance = distance
ltrg_x = tracker[0]
ltrg_y = tracker[1]
end
paths.push tracker[2].compact
end
path_map.push tracker[0] + tracker[1] / 10000.0
if passable_owner.pf_passable?(tracker[0], tracker[1], DOWN, ignore_events, true) and
not path_map.include? tracker[0] + (tracker[1] - 1) / 10000.0
path_map.push tracker[0] + (tracker[1] - 1) / 10000.0
new_trackers.push [tracker[0], tracker[1] - 1, [tracker[2], UP].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], LEFT, ignore_events, true) and
not path_map.include? tracker[0] - 1 + tracker[1] / 10000.0
path_map.push tracker[0] - 1 + tracker[1] / 10000.0
new_trackers.push [tracker[0] - 1, tracker[1], [tracker[2], LEFT].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], RIGHT, ignore_events, true) and
not path_map.include? tracker[0] + 1 + tracker[1] / 10000.0
path_map.push tracker[0] + 1 + tracker[1] / 10000.0
new_trackers.push [tracker[0] + 1, tracker[1], [tracker[2], RIGHT].flatten]
end
if passable_owner.pf_passable?(tracker[0], tracker[1], UP, ignore_events, true) and
not path_map.include? tracker[0] + (tracker[1] + 1) / 10000.0
path_map.push tracker[0] + (tracker[1] + 1) / 10000.0
new_trackers.push [tracker[0], tracker[1] + 1, [tracker[2], DOWN].flatten]
end
end
break if distance == 0 and paths.size > 0
}
end
# turn to event (if applicable)
if option_close
# Calculate facing
facing = 0
facing = 17 if (ftrg_x - ltrg_x) <= -1
facing = 18 if (ftrg_x - ltrg_x) >= 1
facing = 19 if (ftrg_y - ltrg_y) <= -1
facing = 16 if (ftrg_y - ltrg_y) >= 1
paths[0].push facing if facing != 0
end
route = paths[0]
return route
end
#--------------------------------------------------------------------------
# * Pathfinding Passable?
# x : x-coordinate
# y : y-coordinat
# d : direction
# ignore_events : events to ignore
# check_player : player event to check (if event is being moved)
#--------------------------------------------------------------------------
def pf_passable?(x, y, d, ignore_events = [], check_player = false)
ignore_events = [ignore_events].compact if not ignore_events.is_a?(Array)
unless valid?(x, y)
return false
end
bit = (1 << (d / 2 - 1)) & 0x0f
checks = events.values
checks.push $game_player if check_player
for event in checks
if event.tile_id >= 0 and not ignore_events.include?(event) and
event.x == x and event.y == y and not event.through
return false if event == $game_player and check_player
if @passages[event.tile_id] & bit != 0
return false
elsif @passages[event.tile_id] & 0x0f == 0x0f
return false
elsif @priorities[event.tile_id] == 0
return true
end
end
end
for i in [2, 1, 0]
tile_id = data[x, y, i]
if tile_id == nil
return false
elsif @passages[tile_id] & bit != 0
return false
elsif @passages[tile_id] & 0x0f == 0x0f
return false
elsif @priorities[tile_id] == 0
return true
end
end
return true
end
end
#==============================================================================
# ** Scene_Title
#------------------------------------------------------------------------------
# This class performs title screen processing.
#==============================================================================
class Scene_Title
#--------------------------------------------------------------------------
# * Frame Update
#--------------------------------------------------------------------------
alias pf_scene_title_update update
def update
#set the pathfinding class as a callable class
$path_finding = Path_Finding.new
pf_scene_title_update
end
end