Ruby Quellcode

####################################
# Pathfinding by Reborn            |
# v.2.1                            |
####################################
 
################################################################################
# Pathfinding
# Features:
# - when no way was found the closest node will be used
# - very intiligent
# - blocks away dynamic, a new way is calculated (optional)
# - if no new way to calculate, he is waiting for
# - and random pathes (optional) (this features slows the computationally)
# - very very fast by using the A*-Algo in combination with a binary heap
#        a way in a grid with 500x500 nodes is, without random, in ~0.117 sec 
#        calculated with random in ~0.118 sec
#
# Instructions:
# to send one of events to a way, call:
# charachter.find_path(x, y[, flags])
#
# 
# you can get a character like this:
# character = $game_map.events[id]
# or:
# character = $game_player
# or you call it in a event call script:
# character = event # (for self character)
#
#
# flags are the switches for using the new_calculate and the random - feature
# to use the random feature:
# character.find_path(x, y, Pathfinder::RANDOM)
#
# to use the new_calculate feature:
# character.find_path(x, y, Pathfinder::NEW_CALC)
#
# to use both of them:
# character.find_path(x, y, Pathfinder::RANDOM | Pathfinder::NEW_CALC)
#
# to stop fallowing a path invoke:
# character.clear_path()
#
################################################################################
# thanks goes to =Kai=
################################################################################
 
################################################################################
# Changelog |
################################################################################
# v.2.0
# - revised a star algorithm
# - revised closed list
# - revised passable? - method
# - revised binary heap
# - a grid with 350 * 350 nodes and random now takes time less then 0.08 sec.
################################################################################
class Time
  def get_total_time()
    return hour * 60 * 60 * 1000000 + min * 60 * 1000000 + sec * 1000000 + usec
  end
end
 
module Graphics
  class << self
    alias_method(:old_update_28_11_12, :update)
  end
  def self.update()
    old_update_28_11_12
    @last_frame = Time.now
  end
  def self.last_frame()
    return 0.0 unless @last_frame
    return Time.now() - @last_frame
  end
end
 
module Pathfinder
  class BinaryHeap < Array
    def initialize()
      super()
    end
 
    def replace(index, newObject)
      self[index] = newObject
      sort(index)
    end
 
    def push(*args)
      result = super(*args)
      quick_sort()
      return result
    end
 
    def <<(*args)
      push(*args)
    end
 
    def remove(index=0)
      temp = self[index]
      if size() > 1
        self[index] = pop()
        sort(index)
      elsif size() == 1
        clear()
      end
      return temp
    end
 
    def sort(y)
      x = y
      keyc = self[x][0]
      if size() > x * 2 + 2
        keyl = self[x * 2 + 1][0]
        keyr = self[x * 2 + 2][0]
        if keyl >= keyr
          if keyc > keyr
            y = x * 2 + 2
          end
        elsif keyc > keyl
          y = x * 2 + 1
        end
      elsif size() > x * 2 + 1
        keyl = self[x * 2 + 1][0]
        if keyc > keyl
          y = x * 1 + 1
        end
      end
      return if x == y
      self[x], self[y] = self[y], self[x]
      sort(y)
    end
 
    def quick_sort()
      return if size() < 2
      index = size() - 1
      while index > 0
        temp = self[index / 2]
        break if self[index][0] > temp[0]
        self[index / 2] = self[index]
        self[index] = temp
        index /= 2
      end
    end
    private :sort, :quick_sort, :[]
  end
 
  RANDOM   = 1  
  NEW_CALC = 2
 
  class Pathfinder    
    attr_reader :new_calculation, :random
    def initialize(character, target_node, flags=0)
      unless target_node[2].between?(0, $game_map.width) || target_node[3].between?(0, $game_map.height)
        raise "X or Y bigger than the mapsize!"
      end
      @character       = character
      @target          = target_node
      @passable_target = @character.passable?(@target[2], @target[3], 0)
      @random          = flags & RANDOM == RANDOM
      @new_calculation = flags & NEW_CALC == NEW_CALC
      @closed_list     = Table.new($game_map.width, $game_map.height)
      @open_list       = BinaryHeap.new()
      @move_route      = Array.new()
    end
 
    def init_closed_list()
      @closed_list = Table.new(@closed_list.xsize, @closed_list.ysize)
      unless $game_player.through
        @closed_list[$game_player.x, $game_player.y] = -1
      end
      $game_map.events.values.each do |i|
        unless i.through
          @closed_list[i.x, i.y] = -1 
        end
      end
    end
 
    def calculate_path()
      init_closed_list()
      @start   = [0, 0, @character.x, @character.y]
      @current = @start
      @open_list.clear()
      @move_route.clear()
      @open_list.push(@current)
      @nearest = [99999999999, 0, 0, 0]
      until @open_list.empty?
        Graphics.update() if Graphics.last_frame > 1
        @current = get_current()
        if @passable_target
          if @current[2, 3] == @target[2, 3]
            create_move_route()
            return
          end
        else
          delta_x = (@current[2] - @target[2]).abs()
          delta_y = (@current[3] - @target[3]).abs()
          if (delta_x + delta_y) == 1
            @target = @current
            create_move_route()
            return
          end
        end
        expand_node()
        if @current[1] > 0
          @nearest = @current if @current[0] - @current[1] <= @nearest[0] - @nearest[1]
        end
      end
      @target = @nearest
      create_move_route()
    end
 
    def get_current()
      return @open_list.remove()
    end
 
    def expand_node()
      get_possible_moves.each do |i|
        if passable?(i[2], i[3]) && @closed_list[i[2], i[3]].zero?
          @open_list.push(i)
          @closed_list[i[2], i[3]] = i[1]
        end
      end
    end
 
    def get_possible_moves()
      node        = @current
      nodes       = Array.new()
      x, y        = Array.new(), Array.new()
      cost        = node[1] + 1
      x[0], y[0]  = node[2], node[3] - 1
      x[1], y[1]  = node[2] - 1, node[3]
      x[2], y[2]  = node[2] + 1, node[3]
      x[3], y[3]  = node[2], node[3] + 1
      score       = Array.new(4) {|i| get_heuristic(x[i], y[i]) + cost}
      nodes_col   = Array.new(4) {|i| [score[i], cost, x[i], y[i]]}
      passables   = Array.new(4) {|i|  passable?(x[i], y[i])}
      if @random
        case rand(2)
        when 0 then
          0.upto(3) {|i| nodes << nodes_col[i] if passables[i]}
        when 1 then
          3.downto(0) {|i| nodes << nodes_col[i] if passables[i]}
        end
      else
        0.upto(3)  {|i| nodes << nodes_col[i] if passables[i]}
      end
      return nodes
    end
 
    def passable?(x, y)
      d = get_direction(@current[2], @current[3], x, y)
      return $game_map.map_passable?(x, y, d) && @closed_list[x, y].zero?
    end
 
    def get_direction(x1, y1, x2, y2)
      return 2 if y1 > y2
      return 4 if x1 < x2
      return 6 if x1 > x2
      return 8 if y1 < y2
      return 0
    end
 
    def get_heuristic(x, y)
      return (x - @target[2]).abs() + (y - @target[3]).abs()
    end
 
    def target?(x, y)
      return @target[2] == x && @target[3] == y
    end
 
    def get_next_dir()
      return @move_route[-1]
    end
 
    def pop_last_dir()
      return @move_route.pop()
    end
 
    def create_move_route()
      x, y  = @target[2], @target[3]
      old_x = old_y = -1
      while (a = @start[2] - x).abs() + (b = @start[3] - y).abs() >  1
        break if x == old_x && y == old_y
        old_x, old_y = x, y
        cost          = @closed_list[x, y]
        cmr_cl_col    = Hash.new()
        cmr_cl_col[2] = cmr_cl(x, y - 1, cost)
        cmr_cl_col[4] = cmr_cl(x + 1, y, cost)
        cmr_cl_col[6] = cmr_cl(x - 1, y, cost)
        cmr_cl_col[8] = cmr_cl(x, y + 1, cost)
        if @random
          case rand(2)
          when 0 then
            [2, 4, 6, 8].each do |i|
              if cmr_cl_col[i]
                @move_route << i
                x, y = in_dekrement_xy(i, x, y)
              end
            end
          when 1 then
            [8, 6, 4, 2].each do |i|
              if cmr_cl_col[i]
                @move_route << i
                x, y = in_dekrement_xy(i, x, y)
              end
            end
          end
        else
          [2, 4, 6, 8].each do |i|
            if cmr_cl_col[i]
              @move_route << i
              x, y = in_dekrement_xy(i, x, y)
            end
          end
        end
      end
      @move_route << 2 if b == -1
      @move_route << 4 if a == 1
      @move_route << 6 if a == -1
      @move_route << 8 if b == 1
    end
 
    def in_dekrement_xy(i, x, y)
      case i
      when 2 then return x, y - 1
      when 4 then return x + 1, y
      when 6 then return x - 1, y
      when 8 then return x, y + 1
      end
    end
 
    def cmr_cl(x, y, cost)
      return false unless x.between?(0, @closed_list.xsize - 1)
      return false unless y.between?(0, @closed_list.ysize - 1)
      @closed_list[x, y] > 0 && @closed_list[x, y] == cost - 1
    end
  end
end
 
class Game_Map  
  def map_passable?(x, y, d)
    unless valid?(x, y)
      return false
    end
    bit = (1 << (d / 2 - 1)) & 0x0f
    for i in [2, 1, 0]
      tile_id = data[x, y, i]
      if tile_id.nil?
        return false
      elsif @passages[tile_id] & bit != 0
        return false
      elsif @passages[tile_id] & 0x0f == 0x0f
        return false
      elsif @priorities[tile_id].zero?
        return true
      end
    end
    return true
  end
end
 
class Game_Character
 
  alias nf_pf_game_character_initialize initialize
  alias nf_pf_game_character_update update
 
  def initialize()
    nf_pf_game_character_initialize
    @runpath = false
    @pathfinder = []
  end
 
  def update()
    run_path if @runpath
    nf_pf_game_character_update
  end
 
  def run_path
    return if moving?
    if @pathfinder.target?(@x, @y)
      @runpath = false
      delta_x = @x - @pf_last_x
      delta_y = @y - @pf_last_y
      if delta_x.zero? && delta_y.zero?
        return
      end
      if delta_x.abs() > delta_y.abs()
        delta_x > 0 ? turn_left : turn_right
      else
        delta_y > 0 ? turn_up : turn_down
      end
      return
    end
    dir = @pathfinder.get_next_dir()
    case dir
    when 2 then 
      unless passable?(@x, @y + 1, 0)
        if @pathfinder.new_calculation && !@pathfinder.target?(@x, @y + 1)
          @pathfinder.calculate_path()
        end
        return
      end
      move_down
    when 4 then
      unless passable?(@x - 1, @y, 0)
        if @pathfinder.new_calculation && !@pathfinder.target?(@x - 1, @y)
          @pathfinder.calculate_path()
        end
        return
      end
      move_left()
    when 6 then
      unless passable?(@x + 1, @y, 0)
        if @pathfinder.new_calculation && !@pathfinder.target?(@x + 1, @y)
          @pathfinder.calculate_path()
        end
        return
      end
      move_right()
    when 8 then
      unless passable?(@x, @y - 1, 0)
        if @pathfinder.new_calculation && !@pathfinder.target?(@x, @y - 1)
          @pathfinder.calculate_path()
        end
        return
      end
      move_up()
    end
    @pathfinder.pop_last_dir()
  end
 
  def find_path(x, y, flags=0)
    @pf_last_x, @pf_last_y = x, y
    @pathfinder = Pathfinder::Pathfinder.new(self, [0, 0, x, y], flags)
    @pathfinder.calculate_path()
    @runpath    = true
  end
 
  def clear_path()
    @runpath = false
    @pathfinder = nil
  end
end
 
class Game_Player
  alias pf_game_player_update update
  def update
    $game_player.clear_path() if Input.dir4 != 0
    pf_game_player_update
  end
end
 
class Interpreter
  def event
    return $game_map.events[@event_id]
  end
end