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 [Tens de ter uma conta e sessão iniciada para poderes visualizar este link]


Características


Pathfinding rápido e inteligente.[/li]
Comando "chamar script" de fácil uso.[/li]
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:

Spoiler:

Demo

Em anexo no tópico.


Script

Código:

#+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
# 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:
#
#              http://en.wikipedia.org/wiki/A*_search_algorithm
#
# 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 :x                     
  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!