Glenelg開発メモ:迂回動作。

2006-08-26 (土) 17:19:56
お名前:

Glenelgの機能についてのメモ。
自分のための覚書でもあり、利用者のための豆知識でもあり、他AI開発者のための参考情報でもあり。

今回は、GlenelgというよりはAIライブラリ関連。
友瀬が公開しているライブラリに MoveLibというものがあります。
これの中に含まれている MoveEx() という関数には、地図情報を使って「移動できない場所を迂回」して移動する仕組みが入っています。
極端な話をいうと、ホムの現在位置と到着指定先との間に複雑な迷路のような壁があっても、その通れる場所を探して移動してしまう、というようなものです。
正直オーバースペックもいいところなのですが、技術的にそういうこともできるよ、という感じ。

で、ここではそのアルゴリズムについて記載しておきます。


前提条件:すでに「スタート地点」「行きたい場所」「各セルの進入可否」は判っている。

・S・x・・・・・    S:スタート地点(ホムがいる場所)
・・・x・G・・・    G:ゴール地点(ユーザ指定した移動先点)
・・・xxxx・・    ×:進入不能セル
・・・・・・・・・    ・:進入可能セル
・・・・・・・・・

以下、順に処理。

  1. 到達に必要な歩数算出:ゴール地点からスタート地点までの歩数を、逆算的に積んでいく。
    1. ゴール点を距離「0」として設定。
      ・S・x・・・・・
      ・・・x・0・・・
      ・・・xxxx・・
      ・・・・・・・・・
      ・・・・・・・・・
    2. 距離「0」のセル(ゴール)に隣接するセルを探し、それに「距離1」の情報を入れる。
      ・S・x・1・・・
      ・・・x101・・
      ・・・xxxx・・
      ・・・・・・・・・
      ・・・・・・・・・
    3. 距離「1」のセルに隣接するセルを探し、それに「距離2」の情報を入れる。
      ポイント:すでに距離が確定しているセルは、対象にしない。
      例えば距離「1」のセルには必ず「距離0」のセルが隣接しているが、ここは「0」のまま。
      ポイント:進入不能セルには書き込みしない。
      ・S・x212・・
      ・・・x1012・
      ・・・xxxx・・
      ・・・・・・・・・
      ・・・・・・・・・
    4. 以上、同様に実施していき、スタートセルに数字が書き込まれた瞬間に探索完了。
      ・1312x21234
      131211x10123
      121110xxxx34
      ・109876545
      ・・10987656
      ポイント:もしたどり着けないところにいる場合、全ての新しい数値書き込みができなくなっているはず。
      この時点で「たどり着けない」ことが判れば、「移動不能」を返す。
  2. ルート決定:上述の手順で作った「歩数のマップ」を用いて、最短のルートを探り出す。
    1. 自分のいるセル(スタートセル)を、開始位置にする。
      そして、その開始セルの優先度に比べて、「1ステップ小さな値」のセルを探し、それを仮移動先セルに決める。
      ・S12x21234
      13C11x10123    C:仮移動先セル
      121110xxxx34
      ・109876545
      ・・10987656
    2. そのセルまで「直線移動可能か」をチェックする。
      もし移動可能ならば、その「次に1ステップ小さな値」のセルを探し、それに直線移動可能かをチェック。
      これを繰り返すことで「開始セルからもっとも遠い、移動可能セル」を探す。
      これにより、「開始セルと仮移動セル」が決まる。
      ・S12x21234
      131211x10123    C1:最遠の仮移動先セル
      121110xxxx34
      ・10C1876545
      ・・10987656
    3. この仮移動セルを「キューに積む」。
      そして、仮移動先セルを新しい「開始セル」にして改めて上記の顱鬚魴り返しを実施していく。
    4. 上記を繰り返していくことで、いつかは必ず「仮移動先セル==ゴールセル」にできる。
      そして、キューには移動先に選ぶべき座標がいくつか突っ込まれた形になる:この複数の通過点(仮移動先セル)は互いに直線移動可能な位置関係にある。
  3. 実際の移動
    1. キューの先頭座標を取り出し、そこに向かって移動開始する。
      ・S12x21234
      131211x1C41C33    まずC1に向かって移動開始。
      121110xxxx34
      ・10C18765C25
      ・・10987656
    2. 移動中、キューにまだ次の目標地点が残っているなら、今の位置からその点が直線移動できるか調べる。
      もし直線移動可能ならば、その目標地点を新しい目標にする。
      ・S12x21234
      131211x1C41C33    M2からC3は直線移動可能。
      121110xxxx34    C2未到達だがC3を新目標に。
      ・10C1876M2C25
      ・・10987656
      (この手順は無くてもいいが、あったほうが滑らかに移動できる)
    3. 現在の目標地点まで次の目標地点をキューから取得して移動する。
      これを繰り返し、キューが空になるまで移動する→最後はゴール点に移動できる。