Glenelg開発メモ/迂回動作。

2006-08-26 (土) 17:19:56

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

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

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

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

・Ｓ・ｘ・・・・・    Ｓ：スタート地点（ホムがいる場所）
・・・ｘ・Ｇ・・・    Ｇ：ゴール地点（ユーザ指定した移動先点）
・・・ｘｘｘｘ・・    ×：進入不能セル
・・・・・・・・・    ・：進入可能セル
・・・・・・・・・

以下、順に処理。

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

TrackBack(0)

Glenelg開発メモ/迂回動作。

検索

編集操作

ある名言。†

折りたたみ†

シェアする†

メニュー†

クイックリンク†

最新の20件

管理†