Here's a Pathfinding system I made for the MACL (still working on the node pathfinding bug before that "mode" is complete) and haven't released yet. The idea for this system is to allow multiple "modes" (aka algorithms) for finding the best path.
[rgss]#==============================================================================
# ** Systems.Pathfinding (V1.0)
#------------------------------------------------------------------------------
# SephirothSpawn
# Version 1.0
# 2008-08-17
#------------------------------------------------------------------------------
# Description:
# ------------
# This system allows the player and events draw a path from one point to
# another in the shortest route possible.
#
# This also can serve as a base for other pathfinding algorithms.
#
# Method List:
# ------------
#
# Pathfinding
# -----------
# find_path
# retry_path
#
# Pathfinding::Node
# -----------------
# clear_nodes
# x, x=
# y, y=
# g, g=
# h, h=
# parent_id, parent_id=
# parent
# cost
# ==
#
# Pathfinding::Seph_A_Star
# ------------------------
# find_path
# retry_path
# find_next_node (private)
# adjacent_nodes (private)
# add_node (private)
# update_node (private)
# passable? (private)
# skip_node? (private)
#
# Game_Character
# --------------
# find_path
# clear_pathfinding
# update_pathfinding
# pathfinding
# pathfinding_c_proc
# pathfinding_c_frames
#------------------------------------------------------------------------------
# * Syntax :
#
# Make Player find path
# - $game_player.find_path(x, y, special = {}, mode = Pathfinding::Mode)
#==============================================================================
MACL::Loaded << 'Systems.Pathfinding'
#==============================================================================
# ** Pathfinding
#==============================================================================
module Pathfinding
#--------------------------------------------------------------------------
# * Constant
#
# Limit: Number of steps a path will tried to be found before quitting
# (-1 for infinity)
# - Used in: Seph-A*
#
# Fail Proc: Proc called when path cannot be found
# - Used in: Seph-A*
#
# Complete Proc: Proc called when path finished
# - Used in: Seph-A*
#
# Collision Frames: Number of frames to wait to retry when failure
#--------------------------------------------------------------------------
Defaults = {}
Defaults['limit'] = -1 # Limit
Defaults['f_proc'] = nil # Fail Proc
Defaults['c_proc'] = nil # Complete Proc
Defaults['c_frames'] = 20 # Collision Frames
Mode = 'Seph-A*'
Prevent_Script_Hang = 200
#--------------------------------------------------------------------------
# * Find Path
#--------------------------------------------------------------------------
def self.find_path(character, end_x, end_y, special = {}, mode = Mode)
# Setup Default Specials
Defaults.each {|k, v| special[k] = v unless special.has_key?(k)}
# Save Mode
@mode = mode
# Branch By Mode
if mode == 'Seph-A*'
# Seph-A*
Seph_A_Star.find_path(character, end_x, end_y, special)
end
end
#--------------------------------------------------------------------------
# * Retry Path
#--------------------------------------------------------------------------
def self.retry_path
# Branch By Mode
if @mode == 'Seph-A*'
# Seph-A*
Seph_A_Star.retry_path
end
end
end
#==============================================================================
# ** Pathfinding::Node
#==============================================================================
class Pathfinding::Node
#--------------------------------------------------------------------------
# * Saved Nodes
#--------------------------------------------------------------------------
@@saved_nodes = {}
#--------------------------------------------------------------------------
# * Clear Nodes
#--------------------------------------------------------------------------
def self.clear_nodes
@@saved_nodes = {}
end
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :x
attr_accessor :y
attr_accessor :g
attr_accessor :h
attr_accessor :parent_id
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
def initialize(x, y, g = 0, h = 0, parent_id = nil)
# Set Instances
@x, @y, @g, @h, @parent_id = x, y, g, h, parent_id
# Save By Object
@@saved_nodes[object_id] = self
end
#--------------------------------------------------------------------------
# * Parent
#--------------------------------------------------------------------------
def parent
return @@saved_nodes[@parent_id]
end
#--------------------------------------------------------------------------
# * Node Cost
#--------------------------------------------------------------------------
def cost
return @g + @h
end
#--------------------------------------------------------------------------
# * ==
#--------------------------------------------------------------------------
def ==(other)
return other.is_a?(Pathfinding::Node) && other.x == x && other.y == y
end
end
#==============================================================================
# ** Pathfinding::Seph_A_Star
#==============================================================================
module Pathfinding::Seph_A_Star
#--------------------------------------------------------------------------
# * Retry Path
#--------------------------------------------------------------------------
def self.retry_path
self.find_path(@character, @end_node.x, @end_node.y, @special)
end
#--------------------------------------------------------------------------
# * Find Path
#--------------------------------------------------------------------------
def self.find_path(character, end_x, end_y, special = {})
# Clear Nodes List
Pathfinding::Node.clear_nodes
# Setup default specials
Pathfinding::Defaults.each {|k, v| special[k] = v unless special.has_key?(k)}
# Saves character
@character = character
# Creates nodes
start_node = Pathfinding::Node.new(character.x, character.y)
@end_node = Pathfinding::Node.new(end_x, end_y)
# Saves specials
@special = special
limit = special['limit']
f_proc = special['f_proc']
c_proc = special['c_proc']
c_frames = special['c_frames']
# Create lists
@open_list = [start_node]
@closed_list = {}
# Clear found flag
found = false
# Start count
count = 1
# If target can be reached
if self.passable?(@end_node.x, @end_node.y)
# As long as list has a node to check
until @open_list.empty?
# Add to count
count += 1
# Update Graphics (Prevents scripting hanging error)
Graphics.update if count % Pathfinding::Prevent_Script_Hang == 0
# Break pathfinding if limit reached
break if limit != -1 && count > limit
# Get next node
next_node = self.find_next_node
# Add node to closed list
@closed_list[[next_node.x, next_node.y]] = next_node
# If next node has same position as end node
if next_node == @end_node
# Replace start node
@end_node = next_node
# Set found flag
found = true
# Break pathfinding
break
end
# Get adjacent nodes
adj_nodes = self.adjacent_nodes(next_node)
# Pass through adjacent nodes
for node in adj_nodes
# Skip node if node in list
next if self.skip_node?(node)
# Add Node to Open List
@open_list << node
# Update Node
self.update_node(@open_list.size - 1)
end
end
end
# If path cannot be found, call fail proc
f_proc.call if found == false && f_proc != nil
# If path found
if found
# Create movement list
mvt_list = []
# Start from end node
node = @end_node
# Keep checking parent node
while node.parent != nil
# Get Direction
if node.parent.x > node.x
dir = 4
elsif node.parent.x < node.x
dir = 6
elsif node.parent.y > node.y
dir = 8
elsif node.parent.y < node.y
dir = 2
end
# Add direction to front of list
mvt_list.unshift(dir) if dir != nil
# Switch current node to parent node
node = node.parent
end
# Set pathfinding
@character.pathfinding = mvt_list
@character.pathfinding_c_proc = c_proc
@character.pathfinding_c_frames = c_frames
# If no path found
else
# Clear Pathfinding
@character.clear_pathfinding
end
end
#--------------------------------------------------------------------------
# * Find Next Node
#--------------------------------------------------------------------------
private
def self.find_next_node
# Return nil if no nodes
return nil if @open_list.empty?
# Remove Last Element
last = @open_list.pop
# Return Last if List Empty
return last if @open_list.empty?
# Get original first element
first = @open_list.first
# Replace first element with last
@open_list[0] = last
# V Counter
v = 0
# Loop
loop do
u = v
# If both children exist
if 2 * u + 1 < @open_list.size
v = 2 * u if @open_list[2 * u].cost <= @open_list.cost
v = 2 * u + 1 if @open_list[2 * u + 1].cost <= @open_list[v].cost
# If only one child exists
elsif 2 * u < @open_list.size
v = 2 * u if @open_list[2 * u].cost <= @open_list.cost
end
# Break if same
break if u == v
# Swap
@open_list, @open_list[v] = @open_list[v], @open_list
end
# Return first node
return first
end
#--------------------------------------------------------------------------
# * Get a List of Adjacent Nodes
#--------------------------------------------------------------------------
private
def self.adjacent_nodes(node)
# Creates list of nodes
nodes = []
nodes << self.add_node(node.x, node.y + 1, node)
nodes << self.add_node(node.x - 1, node.y, node)
nodes << self.add_node(node.x + 1, node.y, node)
nodes << self.add_node(node.x, node.y - 1, node)
# Return Nodes - nil elements
return nodes.compact
end
#--------------------------------------------------------------------------
# * Add Node
#--------------------------------------------------------------------------
private
def self.add_node(x, y, parent)
# If passable
if self.passable?(x, y)
# Add 1 to Part Cost
g = parent.g + 1
# Get heuristic distance (Manhattan distance)
h = (x - @end_node.x).abs + (y - @end_node.y).abs
# Create New Node
return Pathfinding::Node.new(x, y, g, h, parent.object_id)
end
# Return nil
return nil
end
#--------------------------------------------------------------------------
# * Update Node (heap_update)
#--------------------------------------------------------------------------
private
def self.update_node(i)
# Loop
while i > 0
# Break if parents cost is greater than parents
break if @open_list[i / 2].cost > @open_list.cost
# Swap node and parent
@open_list[i / 2], @open_list = @open_list, @open_list[i / 2]
# Switch index to parent
i /= 2
end
end
#--------------------------------------------------------------------------
# * Passable?
#--------------------------------------------------------------------------
private
def self.passable?(x, y)
return @character.passable?(x, y, 0)
end
#--------------------------------------------------------------------------
# * Skip Node?
#--------------------------------------------------------------------------
private
def self.skip_node?(node)
# Clear skip flag
skip_node = false
# Gets node index
index = @open_list.index(node)
# If Node Found
if index != nil
# If current node cost less than node being tested
if @open_list[index].cost <= node.cost
# Set skip flag
skip_node = true
else
# Replace node
@open_list[index] = node
# Update node
self.update_node(index)
# Set skip flag
skip_node = true
end
end
# If closed list has a node
if @closed_list[[node.x, node.y]] != nil
# If current node cost less than node being tested
if @closed_list[[node.x, node.y]].cost <= node.cost
# Set skip flag
skip_node = true
else
# Replace Node
@closed_list[[node.x, node.y]] = node
end
end
# Return the result
return skip_node
end
end
#==============================================================================
# ** Game_Character
#==============================================================================
class Game_Character
#--------------------------------------------------------------------------
# * Public Instance Variables
#--------------------------------------------------------------------------
attr_accessor :pathfinding
attr_accessor :pathfinding_c_proc
attr_accessor :pathfinding_c_frames
#--------------------------------------------------------------------------
# * Alias Listings
#--------------------------------------------------------------------------
alias_method :seph_pathfinding_gmchr_init, :initialize
alias_method :seph_pathfinding_gmchr_update, :update
#--------------------------------------------------------------------------
# * Object Initialization
#--------------------------------------------------------------------------
def initialize
# Clear pathfinding
clear_pathfinding
# Original Initialization
seph_pathfinding_gmchr_init
end
#--------------------------------------------------------------------------
# * Clear Pathfinding
#--------------------------------------------------------------------------
def clear_pathfinding
@pathfinding = nil
@pathfinding_c_proc = nil
@pathfinding_c_frames = nil
end
#--------------------------------------------------------------------------
# * Find Pathing
#--------------------------------------------------------------------------
def find_path(x, y, special = {}, mode = Pathfinding::Mode)
# Run Pathfinding
Pathfinding.find_path(self, x, y, special)
end
#--------------------------------------------------------------------------
# * Frame Update
#--------------------------------------------------------------------------
def update
# Run pathfinding if path defined
update_pathfinding if @pathfinding != nil
# Original Update
seph_pathfinding_gmchr_update
end
#--------------------------------------------------------------------------
# * Frame Update : Pathfinding
#--------------------------------------------------------------------------
def update_pathfinding
# Return If Moving
return if self.moving?
# If Empty Pathfinding
if @pathfinding.empty?
# Call Complete Proc
@pathfinding_c_proc.call unless @pathfinding_c_proc == nil
# Clear Pathfinding
clear_pathfinding
return
end
# Get Next Direction
dir = @pathfinding.shift
# If Passable
if passable?(x, y, dir)
# Get Method Name
m = 'move_'
m += dir == 2 ? 'down' : dir == 4 ? 'left' : dir == 6 ? 'right' : 'up'
# Call Next Move
self.send(m.to_sym)
return
end
# If retry
if @pathfinding_c_frames != nil && @pathfinding_c_frames > 0
# Set Wait Count
@wait_count = @pathfinding_c_frames
# Retry Path
Pathfinding.retry_path
# If don't retry
else
# Clear Pathfinding
clear_pathfinding
end
end
end
#==============================================================================
# ** Game_Map
#==============================================================================
class Game_Map
#--------------------------------------------------------------------------
# * Alias Listings
#--------------------------------------------------------------------------
alias_method :seph_pathfinding_gmmap_setup, :setup
#--------------------------------------------------------------------------
# * Setup
#--------------------------------------------------------------------------
def setup(map_id)
# Orignal Setup
seph_pathfinding_gmmap_setup(map_id)
# Clear Player Pathfinding
$game_player.clear_pathfinding
end
end
#==============================================================================
# ** Game_Player
#==============================================================================
class Game_Player
#--------------------------------------------------------------------------
# * Alias Listings
#--------------------------------------------------------------------------
alias_method :seph_pathfinding_gmplyr_update, :update
#--------------------------------------------------------------------------
# * Frame Update
#--------------------------------------------------------------------------
def update
# Clear Path if Direciton Pressed
clear_pathfinding if Input.dir4 != 0
# Original Update
seph_pathfinding_gmplyr_update
end
end
[/rgss]
Just insert below above Main. Check the heading for instructions on make the event move to a position. Let me know how it preforms.
