ТЕМА: Поиск пути

#-------------------------------------------------------------------------------
# * [ACE] Khas Pathfinder
#-------------------------------------------------------------------------------
# * Автор - Khas Arcthunder - arcthunder.site40.net
# * Переведен - strelokhalfer
# * Специально для http://rpg-maker.info
# * Версия: 1.0 RU
# * Релиз: 28/02/2012
#
#-------------------------------------------------------------------------------
# * Условия использования
#-------------------------------------------------------------------------------
# При использовании данного скрипта вы автоматически соглашаетесь с тем, что:
# 1. Вы должны упомянуть в титрах автора, т.е Khas;
# 2. Все скрипты Khas находятся под защитой (CCL) Creative Commons license;
# 3. Все скрипты Khas только для некоммерческого использования. 
#    Если вы хотите использовать скритпы для вашего коммерческого проекта,
#    пришлите письмо на [email protected] с заявкой, и Великий, быть может
#    одобрит ваш проект.
# 4. Все скрипты Кхаса только для личного использования, вы можете использовать
#    и редактировать их для под свои нужды, но вам нельзя публиковать
#    модифицированные версии скрипта.
#    {А русификация считается модификацией?}
# 5. Если вы постите скрипт Khas, вы не должны 
#    приписывать его себе{Очень хотелось};
# 6. Все ссылки на загрузку указывать как arcthunder.site40.net
 
# 
# Больше правил(если кто то захочет) http://arcthunder.site40.net/terms/
#
#-------------------------------------------------------------------------------
# * Полезности
#-------------------------------------------------------------------------------
# Умный поиск пути
# Быстрый алгоритм
# Легко использовать
# Plug'n'Play(Подключи и играй)
# Совместимо с игровыми персонажами!
# Так же есть лог!
#
#-------------------------------------------------------------------------------
# * Инструкции
#-------------------------------------------------------------------------------
# Просто вызовите нужный скрипт в событии через опцию "Скрипт..."
# 
# find_path(id,fx,fy)
# Запускает поиск пути.
# id => Значение -1 для игрока, 0 для события, в котором вызывается скрипт.
# Или укажите нужный id события.
# fx => X координата нужной клетки. 
# fy => Y координата нужной клетки.
#
# find_path_var(id,varx_id,vary_id)
# Запускает поиск пути, но по значениям переменных.
# id => Значение -1 для игрока, 0 для события, в котором вызывается скрипт.
# Или укажите нужный id события.
# varx_id => ID переменной, отвечающей за X координату нужной клетки.
# vary_id => ID переменной, отвечающей за Y координату нужной клетки.
# НЕ СТАВИТЬ ОТРИЦАТЕЛЬНЫЕ ЗНАЧЕНИЯ, т.к. проявятся баги.
#
# find_path(id,fx,fy,true)
# Используйте, если хотите что бы игра подождала, пока персонаж двигается.
# (Починена Caveman, спасибо!)
#
# Если хотите включить логи, установите константу Log в true
# в модуле Path_Core 
#
#-------------------------------------------------------------------------------
# * Register
#-------------------------------------------------------------------------------
$khas_awesome = [] if $khas_awesome.nil?
$khas_awesome << ["Pathfinder",1.0]
#-------------------------------------------------------------------------------
# * Script
#-------------------------------------------------------------------------------
class Game_Interpreter
  def find_path(char,fx,fy,wait=false)
    $game_map.refresh if $game_map.need_refresh
    character = get_character(char)
    return if character.nil?
    return unless Path_Core.runnable?(character,fx,fy)
    path = Path_Core.run(character,fx,fy)
    return if path.nil?
    route = RPG::MoveRoute.new
    route.repeat = false
    route.wait = wait
    route.skippable = true
    route.list = []
    path << 0x00
    path.each { |code| route.list << RPG::MoveCommand.new(code)}
    character.force_move_route(route)
    Fiber.yield while character.move_route_forcing if wait # поправка от caveman
  end
  def find_path_var(char,var_x,var_y,wait=false)
    find_path(char,$game_variables[var_x],$game_variables[var_y],wait)
  end
end
class Path
  attr_accessor :axis
  attr_accessor :from
  attr_accessor :cost
  attr_accessor :dir
  def initialize(x,y,f,c,d)
    @axis = [x,y]
    @from = f
    @cost = c
    @dir = d
  end
end
module Path_Core
  Log = false
  Directions = {[1,0] => 3,[-1,0] => 2,[0,-1] => 4,[0,1] => 1}
  def self.runnable?(char,x,y)
    return false unless $game_map.valid?(x,y)
    return false if char.collide_with_characters?(x,y)
    $game_map.all_tiles(x,y).each { |id|
    flag = $game_map.tileset.flags[id]
    next if flag & 0x10 != 0
    return flag & 0x0f != 0x0f}
    return false
  end
  def self.run(char,fx,fy)
    return nil if char.x == fx && char.y == fy
    st = Time.now
    @char = char
    @start = Path.new(@char.x,@char.y,nil,0,nil)
    @finish = Path.new(fx,fy,nil,0,nil)
    @list = []
    @queue = []
    @preference = ((@char.x-fx).abs > (@char.y-fy).abs ? 0x0186aa : 0x01d)
    class << @list
      def new_path?(path_class)
        for path in self
          return false if path.axis == path_class.axis
        end
        return true
      end
    end
    class << @queue
      def new_path?(path_class)
        for path in self
          return false if path.axis == path_class.axis
        end
        return true
      end
    end
    if @preference & 0x02 == 0x02
      @queue << Path.new(@char.x,@char.y+1,@start,1,[0,1]) if @char.passable?(@char.x,@char.y,2)
      @queue << Path.new(@char.x,@char.y-1,@start,1,[0,-1]) if @char.passable?(@char.x,@char.y,8)
      @queue << Path.new(@char.x+1,@char.y,@start,1,[1,0]) if @char.passable?(@char.x,@char.y,6)
      @queue << Path.new(@char.x-1,@char.y,@start,1,[-1,0]) if @char.passable?(@char.x,@char.y,4)
      @list << @start
      loop do
        break if @queue.empty?
        @cpath = @queue[0]
        if @cpath.axis == @finish.axis
          @finish.cost = @cpath.cost
          @finish.from = @cpath
          break
        end
        @list << @cpath
        @path_array = []
        p1 = Path.new(@cpath.axis[0]+1,@cpath.axis[1],@cpath,@cpath.cost+1,[1,0])
        p2 = Path.new(@cpath.axis[0]-1,@cpath.axis[1],@cpath,@cpath.cost+1,[-1,0])
        p3 = Path.new(@cpath.axis[0],@cpath.axis[1]+1,@cpath,@cpath.cost+1,[0,1])
        p4 = Path.new(@cpath.axis[0],@cpath.axis[1]-1,@cpath,@cpath.cost+1,[0,-1])
        @path_array << p3 if @char.passable?(@cpath.axis[0],@cpath.axis[1],2) && @list.new_path?(p3) && @queue.new_path?(p3)
        @path_array << p4 if @char.passable?(@cpath.axis[0],@cpath.axis[1],8) && @list.new_path?(p4) && @queue.new_path?(p4)
        @path_array << p1 if @char.passable?(@cpath.axis[0],@cpath.axis[1],6) && @list.new_path?(p1) && @queue.new_path?(p1)
        @path_array << p2 if @char.passable?(@cpath.axis[0],@cpath.axis[1],4) && @list.new_path?(p2) && @queue.new_path?(p2)
        @path_array.each { |path| @queue << path }
        @queue.delete(@cpath)
      end
    else
      @queue << Path.new(@char.x+1,@char.y,@start,1,[1,0]) if @char.passable?(@char.x,@char.y,6)
      @queue << Path.new(@char.x-1,@char.y,@start,1,[-1,0]) if @char.passable?(@char.x,@char.y,4)
      @queue << Path.new(@char.x,@char.y+1,@start,1,[0,1]) if @char.passable?(@char.x,@char.y,2)
      @queue << Path.new(@char.x,@char.y-1,@start,1,[0,-1]) if @char.passable?(@char.x,@char.y,8)
      @list << @start
      loop do
        break if @queue.empty?
        @cpath = @queue[0]
        if @cpath.axis == @finish.axis
          @finish.cost = @cpath.cost
          @finish.from = @cpath
          break
        end
        @list << @cpath
        @path_array = []
        p1 = Path.new(@cpath.axis[0]+1,@cpath.axis[1],@cpath,@cpath.cost+1,[1,0])
        p2 = Path.new(@cpath.axis[0]-1,@cpath.axis[1],@cpath,@cpath.cost+1,[-1,0])
        p3 = Path.new(@cpath.axis[0],@cpath.axis[1]+1,@cpath,@cpath.cost+1,[0,1])
        p4 = Path.new(@cpath.axis[0],@cpath.axis[1]-1,@cpath,@cpath.cost+1,[0,-1])
        @path_array << p1 if @char.passable?(@cpath.axis[0],@cpath.axis[1],6) && @list.new_path?(p1) && @queue.new_path?(p1)
        @path_array << p2 if @char.passable?(@cpath.axis[0],@cpath.axis[1],4) && @list.new_path?(p2) && @queue.new_path?(p2)
        @path_array << p3 if @char.passable?(@cpath.axis[0],@cpath.axis[1],2) && @list.new_path?(p3) && @queue.new_path?(p3)
        @path_array << p4 if @char.passable?(@cpath.axis[0],@cpath.axis[1],8) && @list.new_path?(p4) && @queue.new_path?(p4)
        @path_array.each { |path| @queue << path }
        @queue.delete(@cpath)
      end
    end
    if @finish.from.nil?
      return nil
    else
      steps = [@finish.from]
      loop do
        cr = steps[-1]
        if cr.cost == 1
          @result = []
          steps.each { |s| @result << Directions[s.dir]}
          break
        else
          steps << cr.from
        end
      end
      self.print_log(Time.now-st) if Log
      return @result.reverse
    end
  end
  def self.print_log(time)
    print "\n--------------------\n"
    print "Khas Pathfinder\n"
    print "Time: #{time}\n"
    print "Size: #{@result.size}\n"
    print "--------------------\n"
  end
end

#-------------------------------------------------------------------------------
# * [XP] Khas Pathfinder
#-------------------------------------------------------------------------------
# * Автор - Khas Arcthunder - arcthunder.site40.net
# * Переведен - strelokhalfer
# * Адаптирован под RPG Maker XP - caveman
# * Специально для http://rpg-maker.info
# * Версия: 1.0 RU
# * Релиз: 28/02/2012
#
#-------------------------------------------------------------------------------
# * Условия использования
#-------------------------------------------------------------------------------
# При использовании данного скрипта вы автоматически соглашаетесь с тем, что:
# 1. Вы должны упомянуть в титрах автора, т.е Khas;
# 2. Все скрипты Khas находятся под защитой (CCL) Creative Commons license;
# 3. Все скрипты Khas только для некоммерческого использования. 
#    Если вы хотите использовать скритпы для вашего коммерческого проекта,
#    пришлите письмо на [email protected] с заявкой, и Великий, быть может
#    одобрит ваш проект.
# 4. Все скрипты Кхаса только для личного использования, вы можете использовать
#    и редактировать их для под свои нужды, но вам нельзя публиковать
#    модифицированные версии скрипта.
#    {А русификация считается модификацией?}
# 5. Если вы постите скрипт Khas, вы не должны 
#    приписывать его себе{Очень хотелось};
# 6. Все ссылки на загрузку указывать как arcthunder.site40.net
 
# 
# Больше правил(если кто то захочет) http://arcthunder.site40.net/terms/
#
#-------------------------------------------------------------------------------
# * Полезности
#-------------------------------------------------------------------------------
# Умный поиск пути
# Быстрый алгоритм
# Легко использовать
# Plug'n'Play(Подключи и играй)
# Совместимо с игровыми персонажами!
# Так же есть лог!
#
#-------------------------------------------------------------------------------
# * Инструкции
#-------------------------------------------------------------------------------
# Просто вызовите нужный скрипт в событии через опцию "Скрипт..."
# 
# find_path(id,fx,fy)
# Запускает поиск пути.
# id => Значение -1 для игрока, 0 для события, в котором вызывается скрипт.
# Или укажите нужный id события.
# fx => X координата нужной клетки.
# fy => Y координата нужной клетки.
#
# find_path(id,fx,fy,true)
# Используйте, если хотите что бы игра подождала, пока персонаж двигается.
# В версии для XP настроил и усе работает!!! (caveman)
#
# Если хотите включить логи, установите константу Log в true
# в модуле Path_Core 
#
#-------------------------------------------------------------------------------
# * Register
#-------------------------------------------------------------------------------
$khas_awesome = [] if $khas_awesome.nil?
$khas_awesome << ["Pathfinder",1.0]
#-------------------------------------------------------------------------------
# * Script
#-------------------------------------------------------------------------------
class Interpreter
  def find_path_var(char,var_x,var_y,wait=false)
    find_path(char,$game_variables[var_x],$game_variables[var_y],wait)
  end
 
  def find_path(char,fx,fy,wait=false)
    $game_map.refresh if $game_map.need_refresh
    character = get_character(char)
    return if character.nil?
    return unless Path_Core.runnable?(character,fx,fy)
    path = Path_Core.run(character,fx,fy)
    return if path.nil?
    route = RPG::MoveRoute.new
    route.repeat = false
    route.skippable = true
    route.list = []
    path << 0x00
 
    path.each { |code| route.list << RPG::MoveCommand.new(code)}
    character.force_move_route(route)
    @move_route_waiting = true if wait
  end 
end
 
class Path
  attr_accessor :axis
  attr_accessor :from
  attr_accessor :cost
  attr_accessor :dir
  def initialize(x,y,f,c,d)
    @axis = [x,y]
    @from = f
    @cost = c
    @dir = d
  end
end
 
module Path_Core
  Log = false
  Directions = {[1,0] => 3,[-1,0] => 2,[0,-1] => 4,[0,1] => 1}
 
  def self.runnable?(char,x,y)
    return false unless $game_map.valid?(x,y)
    return false if !char.passable?(x,y,0)
    return true
  end
 
  def self.run(char,fx,fy)
    return nil if char.x == fx && char.y == fy
    st = Time.now
    @char = char
    @start = Path.new(@char.x,@char.y,nil,0,nil)
    @finish = Path.new(fx,fy,nil,0,nil)
    @list = []
    @queue = []
    @preference = ((@char.x-fx).abs > (@char.y-fy).abs ? 0x0186aa : 0x01d)
    class << @list
      def new_path?(path_class)
        for path in self
          return false if path.axis == path_class.axis
        end
        return true
      end
    end
    class << @queue
      def new_path?(path_class)
        for path in self
          return false if path.axis == path_class.axis
        end
        return true
      end
    end
    if @preference & 0x02 == 0x02
      @queue << Path.new(@char.x,@char.y+1,@start,1,[0,1]) if @char.passable?(@char.x,@char.y,2)
      @queue << Path.new(@char.x,@char.y-1,@start,1,[0,-1]) if @char.passable?(@char.x,@char.y,8)
      @queue << Path.new(@char.x+1,@char.y,@start,1,[1,0]) if @char.passable?(@char.x,@char.y,6)
      @queue << Path.new(@char.x-1,@char.y,@start,1,[-1,0]) if @char.passable?(@char.x,@char.y,4)
      @list << @start
      loop do
        break if @queue.empty?
        @cpath = @queue[0]
        if @cpath.axis == @finish.axis
          @finish.cost = @cpath.cost
          @finish.from = @cpath
          break
        end
        @list << @cpath
        @path_array = []
        p1 = Path.new(@cpath.axis[0]+1,@cpath.axis[1],@cpath,@cpath.cost+1,[1,0])
        p2 = Path.new(@cpath.axis[0]-1,@cpath.axis[1],@cpath,@cpath.cost+1,[-1,0])
        p3 = Path.new(@cpath.axis[0],@cpath.axis[1]+1,@cpath,@cpath.cost+1,[0,1])
        p4 = Path.new(@cpath.axis[0],@cpath.axis[1]-1,@cpath,@cpath.cost+1,[0,-1])
        @path_array << p3 if @char.passable?(@cpath.axis[0],@cpath.axis[1],2) && @list.new_path?(p3) && @queue.new_path?(p3)
        @path_array << p4 if @char.passable?(@cpath.axis[0],@cpath.axis[1],8) && @list.new_path?(p4) && @queue.new_path?(p4)
        @path_array << p1 if @char.passable?(@cpath.axis[0],@cpath.axis[1],6) && @list.new_path?(p1) && @queue.new_path?(p1)
        @path_array << p2 if @char.passable?(@cpath.axis[0],@cpath.axis[1],4) && @list.new_path?(p2) && @queue.new_path?(p2)
        @path_array.each { |path| @queue << path }
        @queue.delete(@cpath)
      end
    else
      @queue << Path.new(@char.x+1,@char.y,@start,1,[1,0]) if @char.passable?(@char.x,@char.y,6)
      @queue << Path.new(@char.x-1,@char.y,@start,1,[-1,0]) if @char.passable?(@char.x,@char.y,4)
      @queue << Path.new(@char.x,@char.y+1,@start,1,[0,1]) if @char.passable?(@char.x,@char.y,2)
      @queue << Path.new(@char.x,@char.y-1,@start,1,[0,-1]) if @char.passable?(@char.x,@char.y,8)
      @list << @start
      loop do
        break if @queue.empty?
        @cpath = @queue[0]
        if @cpath.axis == @finish.axis
          @finish.cost = @cpath.cost
          @finish.from = @cpath
          break
        end
        @list << @cpath
        @path_array = []
        p1 = Path.new(@cpath.axis[0]+1,@cpath.axis[1],@cpath,@cpath.cost+1,[1,0])
        p2 = Path.new(@cpath.axis[0]-1,@cpath.axis[1],@cpath,@cpath.cost+1,[-1,0])
        p3 = Path.new(@cpath.axis[0],@cpath.axis[1]+1,@cpath,@cpath.cost+1,[0,1])
        p4 = Path.new(@cpath.axis[0],@cpath.axis[1]-1,@cpath,@cpath.cost+1,[0,-1])
        @path_array << p1 if @char.passable?(@cpath.axis[0],@cpath.axis[1],6) && @list.new_path?(p1) && @queue.new_path?(p1)
        @path_array << p2 if @char.passable?(@cpath.axis[0],@cpath.axis[1],4) && @list.new_path?(p2) && @queue.new_path?(p2)
        @path_array << p3 if @char.passable?(@cpath.axis[0],@cpath.axis[1],2) && @list.new_path?(p3) && @queue.new_path?(p3)
        @path_array << p4 if @char.passable?(@cpath.axis[0],@cpath.axis[1],8) && @list.new_path?(p4) && @queue.new_path?(p4)
        @path_array.each { |path| @queue << path }
        @queue.delete(@cpath)
      end
    end
    if @finish.from.nil?
      return nil
    else
      steps = [@finish.from]
      loop do
        cr = steps[-1]
        if cr.cost == 1
          @result = []
          steps.each { |s| @result << Directions[s.dir]}
          break
        else
          steps << cr.from
        end
      end
      self.print_log(Time.now-st) if Log
      return @result.reverse
    end
  end
 
  def self.print_log(time)
    print "\n--------------------\n"
    print "Khas Pathfinder\n"
    print "Time: #{time}\n"
    print "Size: #{@result.size}\n"
    print "--------------------\n"
  end
end