#==============================================================================
# ■ Game_Character_tansaku
#------------------------------------------------------------------------------
# 　経路探索
# 
#==============================================================================

class Game_Character
  #--------------------------------------------------------------------------
  # ● 障害物がなければ直進し、あればランダムに向きを変える 2004/9/16
  #--------------------------------------------------------------------------
  def search_front
    unless moving?                         #移動中でなければ
      if passable?(@x, @y, @direction)      #前方が通行可能なら
        case @direction                      #向きが
        when 2                               #下向きの時
          move_down                           #下へ移動
        when 4                               #左向きの時
          move_left                           #左へ移動
        when 6                               #右向きの時
          move_right                          #右へ移動
        when 8                               #上向きの時
          move_up                             #上へ移動
        end
      else                                   #前方が通行不可なら
        turn_random                           #ランダムに向きを変える
      end
    end
  end
  
  #--------------------------------------------------------------------------
  # ● 双方向幅優先探索で目的地までの最短経路を作成する 2005/7/24
  #--------------------------------------------------------------------------
  def search_route(target_x, target_y)  
    #target_x=目的地のx座標, target_y=目的地のy座標
    if target_x == @x and target_y == @y  #現在地と目的地が同じなら
      return false                        #中断
    end                                   #分岐終了
    openlist = [@x * 1000 + @y, target_x * 1000 + target_y]  #探索予定座標を格納
    closelist = {@x * 1000 + @y=>0, target_x * 1000 + target_y=>1}
    #探索済み座標を格納。座標検索の高速化を狙いハッシュを使用する。
    #valueには探索方向が分かる値を代入(0:イベント側,1:目的地側)
    lootlist = [[],[]]     #openlistの対となってその座標に至るルートを格納する
    pointer = 0            #openlistから座標を順番に取り出すためのポインタ変数
    while pointer < openlist.length #openlistに未探索の座標がある間繰り返す
      for i in 1..4                           #4方向を順番に調べる
        case i                                  #調べる方向が
        when 1                                  #下なら
          way = openlist[pointer] + 1             #座標を下に移動
        when 2                                  #左なら
          way = openlist[pointer] - 1000          #座標を左に移動
        when 3                                  #右なら
          way = openlist[pointer] + 1000          #座標を右に移動
        when 4                                  #上なら
          way = openlist[pointer] - 1             #座標を上に移動
        end                                     #分岐終了
        if closelist.include?(way)              #探索済み座標ならば
          if closelist[way] != closelist[openlist[pointer]] 
          #その座標が相手側のものなら
            if closelist[way] == 0    #探索方向がイベント側か目的地側かで分岐
              half_route = lootlist[pointer]  #目的地側のルートをコピー
              half_route.push 5 - i           #新しいルートを追加
              perfect_route = lootlist[openlist.index(way)] 
              #イベント側のルートをコピー
            else
              half_route = lootlist[openlist.index(way)]
              #目的地側のルートをコピー
              perfect_route = lootlist[pointer]  #新しいルートを追加
              perfect_route.push i               #イベント側のルートをコピー
            end
            half_route.reverse!          #目的地側のルートを逆順に並び替える
            perfect_route += half_route  #2つのルートを統合
            move_route = RPG::MoveRoute.new
            #ルート指定の組み込みモジュールを呼び出す
            for i in 0...perfect_route.length #ルートの要素数だけ繰り返す
              move_route.list[i] = RPG::MoveCommand.new #動作指定コマンドを作成
              move_route.list[i].code = perfect_route[i] #動作指定
            end
            force_move_route(move_route) #イベント強制
            return  #終了
          end
        elsif passable?(openlist[pointer]/1000, openlist[pointer]%1000, i*2)
          #指定方向に移動可能なら
          openlist.push way #未探索リストに座標を追加
          closelist[way] = closelist[openlist[pointer]]
           #探索済みリストに座標を追加
          newloot = lootlist[pointer].dup #ルートをコピー
          if closelist[way] == 0  #探索方向がイベント側か目的地側かで分岐
            newloot.push i      #イベント側の新しいルートを追加
          else
            newloot.push 5 - i  #目的地側の新しいルートを追加
          end
          lootlist.push newloot #ルートリストに格納
        end
      end
      pointer += 1              #探索を1つ進める
    end
  end
end