Theo - BFS Pathfinding

# =============================================================================
# TheoAllen - Breadth-First Search Pathfinding
# Version : 1.0
# Contact : www.rpgmakerid.com (or) http://theolized.blogspot.com
# (This script documentation is written in informal indonesian language)
# =============================================================================
($imported ||= {})[:Theo_BFSPathfind] = true
# =============================================================================
# Change Logs:
# -----------------------------------------------------------------------------
# 2014.05.08 - Finished script
# =============================================================================
=begin

  Perkenalan :
  Script ini adalah untuk menemukan jalan terpendek dari sebuah karakter/event
  ke koordinat tujuan

  Cara penggunaan :
  Pasang di bawah material namun diatas main.

  Gunakan script call pada set move route
  find_path(x,y)

  Dimana x,y adalah koordinat tujuan.
  Apabila jalan tidak ditemukan, maka karakter/event tidak akan bergerak

  Terms of use :
  Credit gw, TheoAllen. Kalo semisal u bisa ngedit2 script gw trus jadi lebih
  keren, terserah. Ane bebasin. Asal ngga ngeklaim aja. Kalo semisal mau
  dipake buat komersil, jangan lupa, gw dibagi gratisannya.

=end
#==============================================================================
# Tidak ada konfigurasi
#==============================================================================
# ** MapNode
#------------------------------------------------------------------------------
#  A node that represent tilemap passability
#==============================================================================
class MapNode
  attr_accessor :parent   # Parent node
  attr_accessor :visited  # Visited flag
  attr_reader :nodes      # Child node
  attr_reader :x          # X Coordinate
  attr_reader :y          # Y Coordinate
  # ---------------------------------------------------------------------------
  # *) Initialize
  # ---------------------------------------------------------------------------
  def initialize(x,y)
    @x = x
    @y = y
    @nodes = {}
    @visited = false
  end
  # ---------------------------------------------------------------------------
  # *) Make child node
  # ---------------------------------------------------------------------------
  def make_nodes(mapnodes, char)
    dir = [2,4,6,8]
    # Check all direction
    dir.each do |d|
      next unless char.passable?(x,y,d)
      xpos = x
      ypos = y
      case d
      when 2 # DOWN
        ypos += 1
      when 4 # LEFT
        xpos -= 1
      when 6 # RIGHT
        xpos += 1
      when 8 # UP
        ypos -= 1
      end
      key = [xpos,ypos]
      # Get the next noce
      next_node = mapnodes[key]
      if next_node.nil?
        next_node = MapNode.new(xpos,ypos)
        mapnodes[key] = next_node
      end
      # Set child node
      self.nodes[d] = next_node
    end
  end

end
#==============================================================================
# ** Game_Character
#------------------------------------------------------------------------------
#  A character class with mainly movement route and other such processing
# added. It is used as a super class of Game_Player, Game_Follower,
# GameVehicle, and Game_Event.
#==============================================================================
class Game_Character
  # ---------------------------------------------------------------------------
  # *) Alias force move route
  # ---------------------------------------------------------------------------
  alias theo_pathfind_force_move force_move_route
  def force_move_route(move_route)
    route = Marshal.load(Marshal.dump(move_route))
    theo_pathfind_force_move(route)
  end
  # ---------------------------------------------------------------------------
  # *) Create entire map node
  # ---------------------------------------------------------------------------
  def create_mapnodes
    @mapnodes = {}
    # Scan entire map ~
    for i in 0..$game_map.width
      for j in 0..$game_map.height
        key = [i,j]
        node = @mapnodes[key]
        if node
          node.make_nodes(@mapnodes, self)
        else
          new_node = MapNode.new(i,j)
          new_node.make_nodes(@mapnodes, self)
          @mapnodes[key] = new_node
        end
      end
    end
  end
  # ---------------------------------------------------------------------------
  # *) Find Path
  # ---------------------------------------------------------------------------
  def find_path(tx,ty)
    create_mapnodes
    @target_findx = tx
    @target_findy = ty
    @queue = []
    @queue.push(@mapnodes[[self.x,self.y]])
    until @queue.empty?
      bfsearch(@queue.shift)
    end
    @mapnodes.clear
  end
  # ---------------------------------------------------------------------------
  # *) Breadth-First Seach algorithm
  # ---------------------------------------------------------------------------
  def bfsearch(node)
    node.visited = true
    dir = [2,4,8,6]
    dir.each do |d|
      next unless node.nodes[d]
      next_node = node.nodes[d]
      if next_node.x == @target_findx && next_node.y == @target_findy
        next_node.parent = node
        generate_route(next_node)
        @queue.clear
        return
      end
      next if next_node.visited
      next_node.parent = node
      next_node.visited = true
      @queue.push(next_node)
    end
  end
  # ---------------------------------------------------------------------------
  # *) Generate move route
  # ---------------------------------------------------------------------------
  def generate_route(node)
    list = []
    loop do
      break if node.parent.nil?
      dir = get_dir(node, node.parent)
      command = RPG::MoveCommand.new
      command.code = dir/2
      list.unshift(command)
      node = node.parent
    end
    list.push(RPG::MoveCommand.new)
    if !@move_route
      route = RPG::MoveRoute.new
      route.list = list
      force_move_route(route)
    else
      @move_route.list.insert(@move_route_index+1, *list)
    end
  end
  # ---------------------------------------------------------------------------
  # *) Get direction
  # ---------------------------------------------------------------------------
  def get_dir(node, parent)
    if node.y > parent.y
      return 2
    elsif node.x < parent.x
      return 4
    elsif node.x > parent.x
      return 6
    elsif node.y < parent.y
      return 8
    end
  end

end