Pathfinding : "trouver un chemin vers"

#===============================================================================
# ■ Pathfinding
#-------------------------------------------------------------------------------
# Auteur  : Åvygeil
# Version : 1.2
# Date    : 20/04/2007
#-------------------------------------------------------------------------------
# Ce script contient une panoplie de fonctionnalités qui permettent au joueur
# et aux évènements de trouver automatiquement un chemin.
#-------------------------------------------------------------------------------
# Utilisation :
#
#
# Event Makers :
#
# - Inserer un commentaire dans un event et taper : trouver un chemin vers x
#
# - Remplacer x par
#    joueur si vous voulez que votre event se déplace vers le joueur
#      ou
#    le nom de l'event vers lequel vous voulez vous déplacer
#
#
# Scripteurs :
#
# - Game_Character#find_path_to(x,y) : permet au joueur et aux évènements
#  de se rendre si possible aux coordonnées (x,y) de la carte.
#
# - Game_Character#find_path_to_event("nom") : permet au joueur et aux
#  évènements de se rendre si possible auprès de l'évènement dont
#  le nom est "nom".
#
# - Game_Event#find_path_to_player : permet aux évènements de se rendre
#  si possible auprès du joueur.
#===============================================================================

#===============================================================================
# ▼ Interpreter
#===============================================================================
class Interpreter
 
  #=============================================================================
  # ● command_108
  #-----------------------------------------------------------------------------
  # Permet d'ajouter une fonction de pathfinding en commentaire dans un event.
  #=============================================================================
  alias pathfinding_command108 command_108
  def command_108
    # Commande non valide
    if not @parameters[0].split.size < 5
      # Commande valide
      if @parameters[0].upcase[/TROUVER UN CHEMIN VERS/]=="TROUVER UN CHEMIN VERS"
        #----------------------
        # Recupère le nom de l'event
        event_nom = @parameters[0].split[4]
        #----------------------
        # se diriger vers le joueur
        if event_nom.upcase == "JOUEUR"
          $game_map.events[@event_id].find_path_to_player
          return true
        end
        #----------------------
        # Cherche l'event vers qui se diriger
        $game_map.events[@event_id].find_path_to_event(event_nom)
        return true
      end
    end
    pathfinding_command108
  end

end

#===============================================================================
# ▼ Pathfinding
#-------------------------------------------------------------------------------
# Le module principal contenant les éléments de l'algorithme.
#===============================================================================
module Pathfinding
 
  @@x_to_go = 0 # l'abscisse de la destination
  @@y_to_go = 0 # l'ordonnée de la destination
 
  def Pathfinding.x_to_go
    return @@x_to_go
  end
 
  def Pathfinding.y_to_go
    return @@y_to_go
  end
 
  #=============================================================================
  # ▼ Square
  #-----------------------------------------------------------------------------
  # Une classe utilisée dans l'algorithme A* de recherche d'un chemin.
  #=============================================================================
  class Square
 
    attr_reader :x, :y  # coordonnées du carreau
    attr_reader :parent  # carreau parent
    attr_reader :g_score # coût de déplacement à partir du parent
    attr_reader :h_score # coût de la distance restante à parcourir
    attr_reader :f_score # coût total
   
    #===========================================================================
    # ● initialize
    #    x      : abscisse du carreau
    #    y      : ordonnée du carreau
    #    parent : carreau parent
    #---------------------------------------------------------------------------
    # Méthode d'initialisation du carreau.
    #===========================================================================
    def initialize(x, y, parent)
      @x = x
      @y = y
      @parent = parent
      calculate_scores(parent)
    end
   
    #===========================================================================
    # ● id
    #---------------------------------------------------------------------------
    # Méthode qui renvoie l'identifiant du carreau : "x-y".
    #===========================================================================
    def id
      return "#{@x}-#{@y}"
    end
   
    #===========================================================================
    # ● calculate_scores
    #    parent : Square parent
    #---------------------------------------------------------------------------
    # Méthode qui recalcule les divers coûts nécessaires à A*,
    # en fonction du noeud parent.
    #===========================================================================
    def calculate_scores(parent)
      if parent == nil
        @g_score = 0
      elsif @g_score == nil or @g_score > parent.g_score + 1
        @g_score = parent.g_score + 1
        @parent = parent
      end
      @h_score = remaining_distance
      @f_score = @g_score + @h_score
    end
   
    #===========================================================================
    # ● distance_to
    #    x : abscisse à atteindre
    #    y : ordonnée à atteindre
    #---------------------------------------------------------------------------
    # Méthode qui calcule la distance de Manhattan entre le carreau
    # et les coordonnées (x,y).
    #===========================================================================
    def remaining_distance
      return (@x - Pathfinding.x_to_go).abs + (@y - Pathfinding.y_to_go).abs
    end
   
    #===========================================================================
    # ● to_movecommand
    #---------------------------------------------------------------------------
    # Méthode qui renvoie un objet RPG::MoveCommand en fonction du mouvement
    # nécessaire vers le carreau, à partir de son parent.
    #===========================================================================
    def to_movecommand
      return nil if parent == nil
      mc = RPG::MoveCommand.new
      if self.x < parent.x
        mc.code = 2
      elsif self.x > parent.x
        mc.code = 3
      elsif self.y < parent.y
        mc.code = 4
      elsif self.y > parent.y
        mc.code = 1
      end
      return mc
    end
   
  end
 
  #=============================================================================
  # ● create_path_to
  #    x_end : abscisse à atteindre
  #    y_end : ordonnée à atteindre
  #-----------------------------------------------------------------------------
  # Méthode qui renvoie un objet MoveRoute, chemin vers les
  # coordonnées (x_end,y_end).
  #=============================================================================
  def create_path_to(x_end, y_end)
    @@x_to_go = x_end
    @@y_to_go = y_end
    open_list = {}
    closed_list = {}
    # On ajoute le carré du début à la liste ouverte.
    current_square = Square.new(@x,@y,nil)
    open_list[current_square.id] = current_square
    # Tant que le but n'est pas dans la liste fermée
    # et que la liste ouverte n'est pas vide
    while not closed_list.has_key?("#{x_end}-#{y_end}") and
          not open_list.empty?
      # on cherche dans la liste ouverte le carré dont le f est minimum
      current_square = open_list.values.min {|s1,s2| s1.f_score <=> s2.f_score}
      # on le supprime de la liste ouverte et on le met dans la liste fermée
      open_list.delete(current_square.id)
      closed_list[current_square.id] = current_square
      # Pour les 4 directions (down, left, right, up)
      # si le carré est infranchissable ou si il fait partie de la liste fermée,
      # il est ignoré.
      # Sinon si il ne fait pas partie de la liste ouverte, on l'y ajoute,
      # sinon on recalcule ses scores et son parent en fonction du carré courant
      current_x = current_square.x
      current_y = current_square.y
      # down
      id = "#{current_x}-#{current_y + 1}"
      if passable?(current_square.x, current_square.y, 2) and
        not closed_list.has_key?(id)
        if not open_list.has_key?(id)
          open_list[id] = Square.new(current_x, current_y + 1, current_square)
        else
          open_list[id].calculate_scores(current_square)
        end
      end
      # left
      id = "#{current_x - 1}-#{current_y}"
      if passable?(current_square.x, current_square.y, 4) and
        not closed_list.has_key?(id)
        if not open_list.has_key?(id)
          open_list[id] = Square.new(current_x - 1, current_y, current_square)
        else
          open_list[id].calculate_scores(current_square)
        end
      end
      # right
      id = "#{current_x + 1}-#{current_y}"
      if passable?(current_square.x, current_square.y, 6) and
        not closed_list.has_key?(id)
        if not open_list.has_key?(id)
          open_list[id] = Square.new(current_x + 1, current_y, current_square)
        else
          open_list[id].calculate_scores(current_square)
        end
      end
      # up
      id = "#{current_x}-#{current_y - 1}"
      if passable?(current_square.x, current_square.y, 8) and
        not closed_list.has_key?(id)
        if not open_list.has_key?(id)
          open_list[id] = Square.new(current_x, current_y - 1, current_square)
        else
          open_list[id].calculate_scores(current_square)
        end
      end
    end
    # On construit la route de déplacement en remontant
    # de parent en parent à partir du but.
    move_route = RPG::MoveRoute.new
    move_route.repeat = false
    move_route.skippable = true
    if closed_list.has_key?("#{x_end}-#{y_end}")
      current_square = closed_list["#{x_end}-#{y_end}"]
      while current_square != nil
        move_command = current_square.to_movecommand
        if move_command != nil
          move_route.list = [move_command] + move_route.list
        end
        current_square = current_square.parent
      end
    end
    return move_route
  end
 
end
 
#===============================================================================
# ▼ Game_Character
#-------------------------------------------------------------------------------
# On ajoute à la classe Game_Character les méthodes de recherche d'un chemin
# vers des coordonnées précises ou vers un évènement.
#===============================================================================
class Game_Character
 
  include Pathfinding
 
  attr_writer :through # traversable ou pas
 
  #=============================================================================
  # ● find_path_to
  #    x : abscisse à atteindre
  #    y : ordonnée à atteindre
  #-----------------------------------------------------------------------------
  # Méthode qui fait se déplacer vers les coordonnées (x,y).
  #=============================================================================
  def find_path_to(x,y)
    move_route = create_path_to(x,y)
    force_move_route(move_route)
  end
 
  #=============================================================================
  # ● find_path_to_event
  #    event_name : nom de l'évènement à atteindre
  #-----------------------------------------------------------------------------
  # Méthode qui fait se déplacer vers l'évènement dont le nom et event_name.
  #=============================================================================
  def find_path_to_event(event_name)
    event = $game_map.events.values.find{|e| e.name == event_name}
    event.through = true
    move_route = create_path_to(event.x, event.y)
    event.through = false
    force_move_route(move_route)
  end
 
end

#===============================================================================
# ▼ Game_Event
#-------------------------------------------------------------------------------
# On ajoute à la classe Game_Event la méthode de recherche d'un chemin
# vers le joueur.
#===============================================================================
class Game_Event < Game_Character
 
  #=============================================================================
  # ● find_path_to_player
  #-----------------------------------------------------------------------------
  # Méthode qui fait se déplacer vers le joueur.
  #=============================================================================
  def find_path_to_player
    $game_player.through = true
    move_route = create_path_to($game_player.x, $game_player.y)
    $game_player.through = false
    force_move_route(move_route)
  end
 
end