FX自動売買
禁断のケーキ
じゃらん♪
さくらのVPS

経路探索


メニュー

障害物で方向転換しつつ前進する (2004/9/16)
指定位置まで最短経路で移動する (2005/7/24)

動作サンプル (164kb)
ソースコード

● 障害物で方向転換しつつ前進する


最短経路探索を作ろうと思っていろいろとテストしていたら副産物としてこれができました。
使い方は、イベントの移動タイプを「カスタム」にして、スクリプトの中に

search_front

と書き込みます。
これで障害物にぶつかるまで前進し、ぶつかったらランダムに方向転換するようになります。
プレイヤーの場合は移動タイプがないので、イベントコマンドの「移動ルート設定」を使います。

class Game_Character
  #--------------------------------------------------------------------------
  # ● 障害物がなければ直進し、あればランダムに向きを変える
  #--------------------------------------------------------------------------
  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
end

Game_Characterクラスに「通行可能かどうか」とか「移動中かどうか」ということを
調べるメソッドがあるので、拝借することにします。
それでクラス定義がclass Game_Characterになっています。
moving?はキャラクターが移動中なら"true"を返すメソッド、
passable?(x, y, d)は指定座標から指定した方向に通行可能なら"true"を返すメソッド、
move_***はキャラを指定方向に移動するメソッド、
turn_***はキャラを指定方向に向き変更するメソッド、です。
…借り物ばかりなので特に難しい操作はありませんね。
というわけで以上!

メニューへ


● 指定位置まで最短経路で移動する

ツクールでの実現が難しかったものの1つ、最短経路探索です。
2000でも作っていますが、10歩の範囲を調べるのに1秒くらいかかり、
使いにくい代物でした。
このスクリプトもアルゴリズムはほとんど同じですが、かなり高速です。
スクリプト万歳!

さて、使い方です。
まずソースコードをMainより上の適当なところに貼り付けてください。
これで準備完了です。

イベントコマンドから移動ルート作成のスクリプトを実行します。

◆スクリプト:$game_map.events[1].search_route(10,20)

これでIDが1番のイベントが座標(10,20)に至るまでのルートを作成します。
ルートが作成されるとイベントは自動的に移動を開始します。


class Game_Character
  #--------------------------------------------------------------------------
  # ● 双方向幅優先探索で目的地までの最短経路を作成する
  #--------------------------------------------------------------------------
  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

このスクリプトでは幅優先探索というものを使っています。
まず座標は"X * 1000 + Y"という形で記録しています。
例えば(12,34)なら、12034となります。
最初に配列[12034]の0番目、12034を取り出し、上下左右を調べ、通行可能なら
その座標を配列の後ろに追加します。
4方向とも通行可能なら[12034,12035,11034,13034,12033]となります。
そしたら次に配列の1番目の12035を取り出して上下左右が通行可能ならさらに後ろに追加、
その次に配列の2番目を…という作業を調べられる座標がなくなるまで繰り返しています。

ルートの方は下に調べたなら1、左なら2という形で別の配列lootlistの同じ位置に記録します。
[12034,12035,11034,13034,12033]に対応するルートは[[],[1],[2],[3],[4]]です。
12035からさらに右に調べたなら、次は[[],[1],[2],[3],[4],[1,3]]となります。

検索中の座標がもう1方の配列にも入っていたら、道が繋がったとみなして検索を中断します。
このときopenlist.include?(way)で調べてももちろんできますが、
なぜか同じ座標をハッシュに登録してそこから検索しています。
これは調査済み座標の要素数が多くなった時に高速で検索する工夫です。
もし配列からお目当ての要素を探そうと思ったら要素の最初から
順番に探していくしかありません。
この方法では要素数に比例して検索が遅くなります。
ハッシュではキーの値から保管位置を計算しています。
つまりキーが存在するかしないかの判断は要素数に関係なく一瞬でできてしまうわけです。
といってもスクリプトを使う側にしてみればどんな計算をしてるのか分かりませんけどね…

ところで、目的地側からの検索ではルートが逆向きになっているので補正が必要です。
それがこの部分。

            half_route.reverse!          #目的地側のルートを逆順に並び替える
            perfect_route += half_route  #2つのルートを統合
片方のルートを逆順に並び替えて、もう片方のルートに統合する作業です。
これで逆向きだったルートが同じ向きで繋がります。

こうやってできたルートはperfect_routeに記録されています。
この値を使って組み込みモジュールのRPG::MoveRouteに動作指定コマンドを送り込んでいます。
最後にforce_move_route(move_route)を使うことでキャラクターが移動を開始します。

「双方向」とあるようにこのスクリプトではスタートとゴールの両方から同時に
検索しています。こうすることで検索の無駄を削ることができます。
例えば障害物のないマップで5マス先の目的地まで調べるとします。
この2つを最短経路で結ぶ時、片方向からの検索では5歩の範囲で61個の座標を
調べることになります。双方向ならそれぞれ3歩の範囲で合わせて50個の座標で済みます。
探索方向を調べるための値を、せっかくなのでハッシュの登録内容にしました。

以上の処理の流れを図にすると次のような感じです。
script

メニューへ


一覧へ戻る
トップページへ戻る



更新日時:2005 7/24 18:00
管理人:すっぴぃ ◆ADGYPSYxII