# GIBMAKER'S PROFILE

"College is fun as long as you don't die."

- L,

- L,

*Death Note*## Search

## kentona

## [SCRIPTING] Pathfinding script

Just give credit if you use :)

#==============================================================================

# ** Pathfinder

# by Gibmaker

# just give credit if you use this

#------------------------------------------------------------------------------

# Efficiently finds a route to a target in the least number of steps

# Will return an empty move list if no route exists, but it will exhaust

# the entire map if no route exists which is time-consuming so it's best

# used in cases where a route is guaranteed to exist.

#

# Initialization:

# Pathfinder.new( start_x, start_y, goal_x, goal_y, details[] )

# "details" contains additional arguments that would be

# passed to a $game_map.passable? check. Typically a reference to the

# event if a route is being devised for an event.

#

# Public members:

# move_route : Path formatted as an RPG::MoveRoute

# first_direction : First direction of movement in the route (2/4/6/8)

# path_coords : List of coordinates of all tiles stepped through

# path_dirs : List of all directions moved (2/4/6/8)

#

# Simple step-toward-player implementation:

#

# event.force_move_route( Pathfinder.new(

# event.x, event.y, $game_player.x, $game_player.y, event ).move_route )

#==============================================================================

class Pathfinder

#============================================================================

# * Invariants

#============================================================================

DIRS = [2, 4, 6, 8]

#============================================================================

# * Publics

#============================================================================

attr_reader :path_coords

attr_reader :path_dirs

#============================================================================

# * Initialize

# The path is filled out immediately

#============================================================================

def initialize(start_x, start_y, goal_x, goal_y, details = [], known_max = nil)

@start_x = start_x

@start_y = start_y

@goal_y = goal_y

@goal_x = goal_x

@details = [details].flatten

# Initialize working variables

# @steps plots the number of actual steps that were taken to reach a spot

@steps = Table.new($game_map.width, $game_map.height)

# Holds all nodes that are open but not visited yet

@live_nodes = {}

# Set constraint

if known_max

# Explore every possible route within the given maximum distance

@constraint = { :type => :known_maximum, :value => known_max }

else

# No known route length yet, so prefer stepping toward the target

@constraint = { :type => :minimum_expected_distance }

end

# Set the starting position

open(start_x, start_y, 1)

# Find a path!

if program_path

set_path_coords

# Check for a path using the known_max paradigm; compare

if @constraint[:type] == :minimum_expected_distance

alt_path = Pathfinder.new(@start_x, @start_y, @goal_x, @goal_y,

@details, length )

if alt_path.length < length

@path_coords = alt_path.path_coords

end

end

set_path_dirs

else

@path_coords = []

@path_dirs = []

end

# Clean up temp variables

@steps = @live_nodes = nil

end

#============================================================================

# * Distance to goal

# The minimum possible steps to reach the goal + 1, assuming there are no

# obstacles in the way.

# +1 because the default starting value for the table is 0 in all positions

# so the goal tile itself will receive a value of 1

#============================================================================

def distance(x, y)

(x - @goal_x).abs + (y - @goal_y).abs + 1

end

#============================================================================

# * Coords at

#============================================================================

def coords_at(x, y, dir)

return x + (dir == 6 ? 1 : dir == 4 ? -1 : 0),

y + (dir == 2 ? 1 : dir == 8 ? -1 : 0)

end

#============================================================================

# * Passable from tile

#============================================================================

def passable?(x, y, dir)

other_x = x + (dir == 6 ? 1 : dir == 4 ? -1 : 0)

other_y = y + (dir == 2 ? 1 : dir == 8 ? -1 : 0)

return ($game_map.valid?(other_x, other_y) and

$game_map.passable?( x, y, dir, *@details ) and

$game_map.passable?( other_x, other_y, 10-dir, *@details ))

end

#============================================================================

# * Open tile for checking

# Assumption is that this tile is unexplored and not all ready open

#============================================================================

def open(x, y, steps)

@steps[x, y] = steps

dist = distance(x, y)

unless distance_set = @live_nodes[dist]

distance_set = []

@live_nodes[dist] = distance_set

end

distance_set.push( [x, y] ) unless distance_set.find{ |node| node == [x, y]}

end

#============================================================================

# * Close tile

# Assumption is that the tile is validly open

#============================================================================

def close(x, y)

# Remove the node from the distance set.

dist = distance(x, y)

distance_set = @live_nodes[dist]

distance_set.delete( distance_set.find { |node| node == [x, y] } )

# Remove the set if it's empty

@live_nodes.delete(dist) if distance_set.empty?

end

#============================================================================

# * All nodes

#============================================================================

def all_nodes

set = []

@live_nodes.values.each { |value| set += value }

set

end

#============================================================================

# * Find path

# Explore the environment and determine if a path is available, programming

# the @steps table with the number of steps required to reach each position

#============================================================================

def program_path

# Run until there are no more live nodes.

# Running out of live nodes means there was no path.

until @live_nodes.empty?

# If the goal has been opened (distance of 1)

if (minimum_distance = @live_nodes.keys.min) == 1

return true

end

# For all open tiles with the smallest distance to the target ...

case @constraint[:type]

when :minimum_expected_distance

check_set = @live_nodes[ minimum_distance ].dup

when :known_maximum

check_set = all_nodes

end

check_set.each { |node|

# Open the tiles in all four directions, if it is possible to pass

# in that direction

DIRS.each { |dir|

if passable?( node[0], node[1], dir )

x, y = *coords_at( node[0], node[1], dir )

# If there is a max distance constraint

if @constraint[:type] == :known_maximum

# Thanks to applying +1 to distance and steps (in order to use

# 0 to represent an unvisited position) there are a bunch of

# +1 corrections in this comparison, which combine into the +3

# adjustment.

next if distance(x, y) >= @constraint[:value] - @steps[ *node ] + 3

end

# If the tile has not all ready been opened, open it now

if @steps[x, y] == 0 or @steps[x, y] > @steps[ *node ] + 1

open( x, y, @steps[ *node ] + 1 )

end

end

}

close *node

}

end

return false

end

#============================================================================

# * Set path_coords

# With @steps programmed, start at the goal and work backwards to find

# a valid path. Assumes that there is such a path.

#============================================================================

def set_path_coords

# Set the coord-based path

@path_coords = []

x, y = @goal_x, @goal_y

while ( [x, y] != [@start_x, @start_y] ) do

# Add this point to the path

@path_coords.push( [x, y] )

choices = []

min_dist = nil

DIRS.each { |dir|

# Possible to step in this direction?

next unless passable?( x, y, dir )

# Get the coords

check_x, check_y = *coords_at(x, y, dir)

# Unexplored tile?

next if @steps[check_x, check_y] == 0

# Not a backtrack?

next unless @steps[check_x, check_y] < @steps[x, y]

# Process choice

if min_dist.nil? or @steps[check_x, check_y] <= min_dist

choices.clear

min_dist = @steps[check_x, check_y]

end

if @steps[check_x, check_y] == min_dist

choices.push( [check_x, check_y ] )

end

}

x, y = *choices[rand( choices.size )]

end

@path_coords.push( [@start_x, @start_y] )

@path_coords.reverse!

end

#============================================================================

# * Set path_dirs

# With @path_coords programmed, create a path consisting of directions.

#============================================================================

def set_path_dirs

@path_dirs = []

if @path_coords.size > 1

0.upto(@path_coords.size - 2) { |i|

here, there = @path_coords[i], @path_coords[i + 1]

if here[0] == there[0]

@path_dirs.push( here[1] > there[1] ? 8 : 2 )

else

@path_dirs.push( here[0] > there[0] ? 4 : 6 )

end

}

end

end

#============================================================================

# * The length of the path

#============================================================================

def length

@path_coords.length - 1

end

#============================================================================

# * The first direction of passage

#============================================================================

def first_direction

@path_dirs[0]

end

#============================================================================

# * Move route

#============================================================================

def move_route

route = RPG::MoveRoute.new

route.list.clear

@path_dirs.each { |dir|

command = RPG::MoveCommand.new

command.code = dir / 2

route.list.push command

}

route

end

end

## A good mp3 encoder?

## Too many games! ;_;

Pages:
1