---

Introdução

Este
é um avançado e altamente inteligente sistema de pathfinding. Ele
permite que o usuário faça com que eventos ou o game player - seja pelo
script ou chamar script - automaticamente andem por um caminho, de
acordo com determinadas coordenadas, de maneira simples e rápida. O
sistema é esperto o bastante pra rapidamente achar o caminho através de
áreas relativamente complexas e espontaneamente desviar de qualquer
obstáculo que entre em sua rota. Foi usado o algoritmo A*, que é um
algoritmo de busca básico normalmente usado na robótica. Leia mais sobre
ele aqui.

---

Características

• Pathfinding rápido e inteligente.
  
• Comando "chamar script" de fácil uso.
  
• Pelo parâmetro opcional de "range", um character pode ir até outros lugares com alcance igual, caso o desejado esteja bloqueado.
  
• Pode-se programar callbacks opcionais para que algo se execute quando o character consegue ou não chegar em seu destino.
  

---

Screenshots

É possível navegar sem problemas por mapas como estes, sem lag algum:


Spoiler :

Clique para Expandir.

Spoiler :

---

Demo

Em anexo no tópico.

---

Script


Código: [Tens de ter uma conta e sessão iniciada para poderes visualizar este link]#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# Advanced Pathfinding
# Autor: ForeverZer0
# Versão: 1.0
# Data: 5.30.2011
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
#
# Introdução
# Este é um sistema de pathfinding avançado e altamente inteligente.
# Ele permite que o usuário faça com que eventos ou o game player -
# seja pelo script ou chamar script - automaticamente andem por um caminho,
# de acordo com determinadas coordenadas, de maneira simples e rápida.
# O sistema é esperto o bastante pra rapidamente achar o caminho através
# de áreas relativamente complexas e espontaneamente desviar de qualquer
# obstáculo que entre em sua rota. Foi usado o algoritmo A*, que é um
# algoritmo de busca básico normalmente usado na robótica.
#
# Leia mais sobre ele:
#
# [Tens de ter uma conta e sessão iniciada para poderes visualizar este link]
#
# Características:
# - Pathfinding rápido e inteligente.
# - Comando "chamar script" de fácil uso.
# - Pelo parâmetro opcional de "range", um character pode ir até outros
# lugares com alcance igual, caso o desejado esteja bloqueado.
# - Pode-se programar callbacks opcionais para que algo se execute quando
# o character consegue ou não chegar em seu destino.
#
# Instruções
# - Coloque o script acima do Main
# - Use o seguinte comando usando da opção "Chamar Script"
#
# pathfind(X, Y, CHARACTER, RANGE, SUCCESS_PROC, FAIL_PROC)
#
# X e Y são os únicos argumentos indispensáveis. Os outros podem sem omitidos.
#
# X - Coordenada X de destino
# Y - Coordenada Y de destino
#
# CHARACTER - Poder ser indicada usando-se a instância do character ($game_player,
# $game_map.events[ID], etc) ou então o ID do mesmo.
# Use o ID do evento ou então "-1" (sem aspas) para o personagem
#
# SUCCESS_PROC - Um objeto Proc que será executado quando o character
# chegar a coordenada definida
# FAILURE_PROC - Um objeto Proc que será executado quando o character
# não puder chegar a coordenada definida
#
# - Por padrão, o pathfinder fará 35 tentativas de recalcular a rota quando bloqueada
# Este valor pode ser alterado durante o jogo chamando o seguinte comando usando o "Chamar Script"
#
# $game_map.collision_retry = NUMBER
#
# Você pode alterar o valor padrão dando uma olhada no começo da primeira classe do script
# - Para rotas maiores, às vezes é necessário resetar o search limiter
# Isso pode aumentar o lag quando um objeto bloquear o character ao tentar se mover
# mas isso fará com que o alcance do sistema seja maior do que o sistema conseguiria lidar.
# Use o seguinte comando para isso:
#
# $game_map.search_limiter = NUMBER (Padrão = 1000)
#
# - Se você estiver tendo problemas com compatibilidade, vá até a classe
# Game_Map e mude @recalculate_paths para false. Isso irá diminuir um pouco
# a eficiência dos cálculos de colisões, mas pode resolver seu problema.
#
# Compatibilidade
# Altamente compatível. Você poderá ter problemas com scripts de movimento
# customizado, caso contrário não é provável que tenha problemas com o sistema.
#
# Créditos/Agradecimentos
# - ForeverZer0, pelo script
# - Agradecimento especial ao Jragyn pela ajuda em fazer o grande labirinto da demo
# e por contribuir nos testes.
# - Crédito a Peter Hart, Nils Nilsson e Bertram Raphael pelo algorítmo original
# de busca que foi implementado
# - Black Mage e Megalukes pela tradução.
#
#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+

#===============================================================================
# ** Game_Map
#===============================================================================

class Game_Map

attr_accessor :collision_retry
attr_accessor :recalculate_paths
attr_accessor :search_limiter

alias zer0_pathfinding_init initialize
def initialize
# Initialize instance variables used for pathfinding.
@collision_retry = 35
@recalculate_paths = true
@search_limiter = 1000
# Original method
zer0_pathfinding_init
end
end

#===============================================================================
# ** Interpreter
#===============================================================================

class Interpreter

def pathfind(x, y, *args)
args[0] = @event_id if args[0] == nil
args[1] = 0 if args[1] == nil
# Add a simpler call for using as a script call
Pathfind.new(Node.new(x, y), *args)
end
end

#==============================================================================
# ** Pathfind
#==============================================================================

class Pathfind

attr_reader :route
attr_accessor :range
attr_reader :goal
attr_reader :found
attr_reader :character
attr_accessor :success_proc
attr_accessor :failure_proc
attr_accessor :target
attr_accessor :collisions

def initialize(node, char = -1, range = 0, *callbacks)
# Set the character. Can either us an ID or an instance of a Game_Character.
# A value of -1, which is default, is the Game_Player.
if char.is_a?(Integer)
@character = (char == -1) ? $game_player : $game_map.events[char]
elsif char.is_a?(Game_Character)
@character = char
end
# Set forcing flag. Will be disabled for recalculating on the fly.
@forcing = true
# Call a public method, since this method may need to be used again,
# and "initialize" is private.
setup(node, range, *callbacks)
end

def setup(node, range = 0, *callbacks)
# Initialize the node we are trying to get to.
@target = Node.new(node.x, node.y)
@goal = @target.clone
# Set beginning nodes and required variables.
@start_node = Node.new(@character.x, @character.y)
@nearest = Node.new(0, 0, 0, -1)
@range, @found, @collisions = range, false, 0
# Set callbacks for success and failure if included, else nil.
@success_proc = callbacks[0]
@failure_proc= callbacks[1]
# Initialize sets to track open and closed nodes
@open_set, @close_set = [@start_node], {}
# Find the optimal path
calculate_path
end

def calculate_path
# Only do calculation if goal is actually passable, unless we only
# need to get close or within range
if @character.passable?(@goal.x, @goal.y, 0) || @range > 0
# Initialize counter
counter, wait = 0, 0
until @open_set.empty?

counter += 1
# Give up if pathfinding is taking more than 500 iterations
if counter >= $game_map.search_limiter
@found = false
break
end
# Get the node with lowest cost and add it to the closed list
@current_node = get_current
@close_set[[@current_node.x, @current_node.y]] = @current_node
if @current_node == @goal ||
(@range > 0 && @goal.in_range?(@current_node, @range))
# We reached goal, exit the loop!
@target = @goal
@goal, @found = @current_node, true
break
else # if not goal
# Keep track of the node with the lowest cost so far
if @current_node.heuristic < @nearest.heuristic ||
@nearest.heuristic < 1
@nearest = @current_node
end
# Get adjacent nodes and check if they can be added to the open list
neighbor_nodes(@current_node).each {|neighbor|
# Skip Node if it already exists in one of the lists.
next if can_skip?(neighbor)
# Add node to open list following the binary heap conventions
@open_set.push(neighbor)
arrange(@open_set.size - 1)
}
end
end
end
# If no path was found, see if we can get close to goal
unless @found
if @range > 0 && @nearest.heuristic > 0
# Create an alternate path.
setup(@nearest, @range, @success_proc, @failure_proc)
elsif @failure_proc != nil && (($game_map.collision_retry == 0) ||
(@collisions > $game_map.collision_retry))
# If out of retries, call the Proc for failure if defined
@failure_proc.call
end
end
# Create the move route using the generated path
create_move_route
end

def create_move_route
# There's no path to generate if no path was found
return if !@found
# Create a new move route that isn't repeatable
@route = RPG::MoveRoute.new
@route.repeat = false
# Generate path by starting from goal and following parents
node = @goal
while node.parent
# Get direction from parent to node as RPG::MoveCommand
code = case direction(node.parent.x, node.parent.y, node.x, node.y)
when 2 then 4 # Up
when 4 then 3 # Left
when 6 then 2 # Right
when 8 then 1 # Down
else; 0
end
# Add movement code to the start of the array
@route.list.unshift(RPG::MoveCommand.new(code)) if code != 0
node = node.parent
end
# If the path should be assigned to the character
if (@forcing && !@route.list.empty?)
@collisions = 0
@character.paths.push(self)
@character.force_move_route(@route) if @character.paths.size == 1
end
# Reset forcing flag if needed
@forcing = true
# Return the constructed RPG::MoveRoute
return @route
end

def arrange(index)
# Rearrange nodes in the open_set
while index > 0
# Break loop unless current item's cost is less than parent's
break if @open_set[index].score > @open_set[index / 2].score
# Bring lowest value to the top.
temp = @open_set[index / 2]
@open_set[index / 2] = @open_set[index]
@open_set[index] = temp
index /= 2
end
end

def get_current
return if @open_set.empty?
return @open_set[0] if @open_set.size == 1
# Set current node to local variable and replace it with the last
current = @open_set[0]
@open_set[0] = @open_set.pop
# Loop and rearrange array according to the A* algorithm until done.
y = 0
loop {
x = y
# If two children exist
if 2 * x + 1 < @open_set.size
if @open_set[2 * x].score <= @open_set[x].score
y = 2 * x
if @open_set[2 * x + 1].score <= @open_set[y].score
y = 2 * x + 1
end
end
# If only one child exists
elsif 2 * x < @open_set.size &&
@open_set[2 * x].score <= @open_set[x].score
y = 2 * x
end
# Swap a child if it is less than the parent.
break if x == y
temp = @open_set[x]
@open_set[x] = @open_set[y]
@open_set[y] = temp
}
# Return the original first node (which was removed)
return current
end

def direction(x1, y1, x2, y2)
# Return the numerical direction between coordinates.
return 6 if x1 > x2 # Right
return 4 if x1 < x2 # Left
return 2 if y1 > y2 # Bottom
return 8 if y1 < y2 # Top
return 0
end

def neighbor_nodes(node)
# Create array to hold the nodes, then check each direction.
nodes = []
nodes.push(get_neighbor(node.x + 1, node.y, node)) # Right
nodes.push(get_neighbor(node.x - 1, node.y, node)) # Left
nodes.push(get_neighbor(node.x, node.y + 1, node)) # Down
nodes.push(get_neighbor(node.x, node.y - 1, node)) # Up
# Remove any nil elements, then return results.
return nodes.compact
end

def get_neighbor(x, y, parent)
# Calculate direction, return new node if passable.
direction = direction(x, y, parent.x, parent.y)
if @character.passable?(parent.x, parent.y, direction)
# The heuristic is simply the distance
heuristics = ((x - @goal.x).abs + (y - @goal.y).abs)
return Node.new(x, y, parent, parent.cost + 1, heuristics)
end
end

def can_skip?(node)
# Branch by if node is in either the open or closed set.
if @open_set.include?(node)
index = @open_set.index(node)
return true if @open_set[index].score <= node.score
# Swap them and update list order
@open_set[index] = node
arrange(index)
return true
elsif @close_set[[node.x, node.y]] != nil
# If the existing passed node has a lower score than this one.
return true if @close_set[[node.x, node.y]].score <= node.score
# Update the existing node
@close_set[[node.x, node.y]] = node
end
# Return false if no criteria was met.
return false
end
end

#==============================================================================
# ** Game_Character
#==============================================================================

class Game_Character

attr_accessor :paths
attr_accessor :move_route_forcing
attr_accessor :move_route

alias zer0_pathfinding_init initialize
def initialize
# Add public instance variable for paths
@paths = []
# Original method
zer0_pathfinding_init
end

def next_route
# Stop any custom move route that may be occuring.
if @move_route != nil
# Set index and disable forcing of current route
@move_route_index = @move_route.list.size
@move_route_forcing = false
# Reset to what it was originally
@move_route = @original_move_route
@move_route_index = @original_move_route_index
@original_move_route = nil
end
# Remove first path from the paths array.
@paths.shift
# If there is another path to follow...
if @paths[0] != nil
# Setup path again to reflect any changes since original creation
@forcing = false
@paths[0].setup(@paths[0].target, @paths[0].range,
@paths[0].success_proc, @paths[0].failure_proc)
force_move_route(@paths[0].route) if @paths[0].found
end
end

alias zer0_recalculate_paths_move move_type_custom
def move_type_custom
if $game_map.recalculate_paths
# Interrupt if not stopping
return if jumping? || moving?
# Loop until finally arriving at move command list
while @move_route_index < @move_route.list.size
# Get the move command at index
command = @move_route.list[@move_route_index]
# If command code is 0 (end of list)
if command.code == 0
# If [repeat action] option is ON
if @move_route.repeat
# Reset move route index to the top of the list
@move_route_index = 0
end
# If [repeat action] option is OFF
unless @move_route.repeat
# If move route is forced and not repeating
if @move_route_forcing and not @move_route.repeat
# The move route is no longer forced (moving ended)
@move_route_forcing = false
# Restore original move route
@move_route = @original_move_route
@move_route_index = @original_move_route_index
@original_move_route = nil
# If there was a path to follow and we reached goal
if @paths[0] != nil
if self.x == @paths[0].goal.x &&
y == @paths[0].goal.y && @paths[0].success_proc
# Call success Proc if goal is reached and it is defined.
@paths[0].success_proc.call
end
next_route
end
end
# Clear stop count
@stop_count = 0
end
return
end # if command.code == 0
# For move commands (from move down to jump)
if command.code <= 14
# Branch by command code
case command.code
when 1 then move_down # Move down
when 2 then move_left # Move left
when 3 then move_right # Move right
when 4 then move_up # Move up
when 5 then move_lower_left # Move lower left
when 6 then move_lower_right # Move lower right
when 7 then move_upper_left # Move upper left
when 8 then move_upper_right # Move upper right
when 9 then move_random # Move random
when 10 then move_toward_player # Move toward player
when 11 then move_away_from_player # Move away from player
when 12 then move_forward # Step forward
when 13 then move_backward # Step backward
when 14 then jump(command.parameters[0], command.parameters[1]) # Jump
end
# If movement failure occurs when "Ignore If Can't Move" is unchecked.
if !@move_route.skippable && !moving? && !jumping?
# If path is current and collision limit is not reached
if @paths[0] != nil &&
@paths[0].collisions < $game_map.collision_retry
# Setup path again to update starting location.
# original goal node is used because pathfinding changes
# the goal node to current node
goal, range = @paths[0].target, @paths[0].range
reach = @paths[0].success_proc
fail = @paths[0].failure_proc
counter = @paths[0].collisions + 1
# Find another path to goal
@paths[0] = Pathfind.new(goal, self, range, reach, fail)
@paths[0].collisions = counter
force_move_route(@paths[0].route) if @paths[0].found
# Wait a bit before starting to follow the new path
@wait_count = 6
return
else
# Call failure Proc if defined and set move index.
@move_route_index = @move_route.list.size
@paths[0].failure_proc.call if @paths[0].failure_proc != nil
next_route
end
# End method
return
end
# Advance index
@move_route_index += 1
return
end # if command.code <= 14
# If waiting
if command.code == 15
# Set wait count (from provided parameter)
@wait_count = command.parameters[0] * 2 - 1
@move_route_index += 1
return
end # if command.code == 15
# If direction change (turning) command
if command.code >= 16 and command.code <= 26
# Branch by command code
case command.code
when 16 then turn_down # Turn down
when 17 then turn_left # Turn left
when 18 then turn_right # Turn right
when 19 then turn_up # Turn up
when 20 then turn_right_90 # Turn 90° right
when 21 then turn_left_90 # Turn 90° left
when 22 then turn_180 # Turn 180°
when 23 then turn_right_or_left_90 # Turn 90° right or left
when 24 then turn_random # Turn at Random
when 25 then turn_toward_player # Turn toward player
when 26 then turn_away_from_player # Turn away from player
end
@move_route_index += 1
return
end
# If other command (commands that don't 'return')
if command.code >= 27
# Branch by command code
case command.code
when 27 # Switch ON
$game_switches[command.parameters[0]] = true
$game_map.need_refresh = true
when 28 # Switch OFF
$game_switches[command.parameters[0]] = false
$game_map.need_refresh = true
when 29 then @move_speed = command.parameters[0] # Change speed
when 30 then @move_frequency = command.parameters[0] # Change freq
when 31 then @walk_anime = true # Move ON
when 32 then @walk_anime = false # Move OFF
when 33 then @step_anime = true # Stop ON
when 34 then @step_anime = false # Stop OFF
when 35 then @direction_fix = true # Direction ON
when 36 then @direction_fix = false # Direction OFF
when 37 then @through = true # Through ON
when 38 then @through = false # Through OFF
when 39 then @always_on_top = true # On top ON
when 40 then @always_on_top = false # On top OFF
when 41 # Change Graphic
# Can't change into a tile
@tile_id = 0
@character_name = command.parameters[0]
@character_hue = command.parameters[1]
# Update direction
if @original_direction != command.parameters[2]
@direction = command.parameters[2]
@original_direction = @direction
@prelock_direction = 0
end
# Update frame
if @original_pattern != command.parameters[3]
@pattern = command.parameters[3]
@original_pattern = @pattern
end
when 42 then @opacity = command.parameters[0] # Change Opacity
when 43 then @blend_type = command.parameters[0] # Change Blending
when 44 then $game_system.se_play(command.parameters[0]) # Play SE
when 45 then result = eval(command.parameters[0]) # Script
end
# Increment move index.
@move_route_index += 1
end
end
else
# Original method
zer0_recalculate_paths_move
end
end
end

#==============================================================================
# ** Node
#==============================================================================

class Node

attr_accessor
attr_accessor :y
attr_accessor :parent
attr_accessor :cost
attr_accessor :heuristic

def initialize(x, y, parent = nil, cost = 0, heuristic = 0)
# Set public instance variables.
@x, @y, @parent, @cost, @heuristic = x, y, parent, cost, heuristic
end

def score
# Return the current "score" of this node
return @cost + @heuristic
end

def in_range?(node, range)
# Return true/false if Nodes are within RANGE of each other.
return (@x - node.x).abs + (@y - node.y).abs <= range
end

def ==(node)
# Returns true/false of whether self and other are equal.
return ((node.is_a?(Node)) && (node.x == @x) && (node.y == @y))
end
end

---

Instruções

Coloque abaixo dos scripts padrão e acima de Main. Demais instruções estão no próprio script e na demo.

---

Compatibilidade

Altamente compatível, tendo problemas apenas com outros scripts de movimento customizado.

---

Créditos e Agradecimentos

Agradecimentos
especiais para Jragyn pela ajuda na criação do labirinto da demo e nos
testes. Créditos vão para Peter Hart, Nils Nilsson e Bertram Raphael
pelo algoritmo de busca original que foi usado.

---

Notas do Autor

Favor reportar qualquer bug ou problema para que possam ser resolvidos. Aproveite!