2011 03.15 Tue AndroidでA*アルゴリズム ＣＡＴＥＧＯＲＹ ：ゲームAI

 1. A*アルゴリズムとは?
 A*アルゴリズムは開始地点から目標の地点までの経路を求める際に有効な手段です。
開始地点、目標地点間の中でそれぞれどのくらい離れているのかをスコアとして表記します。
スコアは以下のように求まります。

スコア = 開始地点から現在地までの距離 + 現在地からゴールまでの距離
開始地点から現在地までの距離をコスト(Cost)
現在地からゴールまでの距離をヒューリスティック(Heuristic)
と表記して説明されることが多いです。

このスコアを手がかりとし、よりスコアが低い方向を目指して進み、最後に通った道を
経路として出力することが出来ます。
今回は上下左右の4方向の経路を求めました。

2. A*の実装手順について
 前述したようにスコアの低い値を取るように経路を求めていくと問題にぶつかりました。

(1)ゴールまでの半分の距離を進むことはできるが後半の半分は、小さいスコアが見つからない
(2)通った道を繰り返し通ってしまい無限ループに陥る

それぞれの問題について見ていきます。
(1)そもそも、スコアが変化し続けているのはどこなのかについて考えてみると、
スタートまでの距離→増加
スコア→半分地点までは減少するが、それ以降は増加する
ゴールまでの距離→減る
つまり、ゴールまでの距離を取ることが解決策になりました。
ここで次の問題です。
Javaで実装するとリストはどのように実現するのか？
C言語などでは通った道を格納しポインタで辿れば良かったのですが、Javaでは出来ません。
そこで、あらかじめ用意されていたArrayListを使うことにしました。
結果的に言うとこの選択は間違いでした。
ArrayListではどの場所に格納されているのかインデックス値を取ることが出来ません。
そのため、最小値を求める方法がなかなか思いつきませんでした。
また、後述する値を取り出した後も順番は詰められずnullが入ったままになり、
デバッグが困難になりました。
また、多くの主要な関数を上書きして定義する必要が発生したため、
自前のリストクラスを作ったほうがミスを減らせたと思います。

(2)同じ経路を辿り無限ループに陥る問題は、あらかじめ通った経路を記録しておき、
新規に経路を作る際に比較することで、解決しました。

実装の流れを説明する前に3つのリストについて触れます。
A*を実装する上で、
・探索の候補リスト(オープンリスト)
・探索済のリスト(クローズリスト)
・経路リスト
この3つのリストが重要な役割を持っています。
それぞれの役割については流れの中で説明していきます。
処理の流れを以下に示します。

----------------------------------------------------------
あらかじめ、移動先がない場所を追加させないためのフラグを定義しておきます。
開始地点、ゴール地点のスコアを求め、スタート地点をオープンリストに登録します。
現在のヒューリスティックを開始地点のヒューリスティックとします。

最小のヒューリスティックを持った場所をオープンリストから探します。
最小の条件は、現在のヒューリスティック以下の値を持った場所です。
見つかった場所をオープンリストから取り出し、経路リストへ登録します。
登録した場所のヒューリスティックを現在のヒューリスティックに代入します。

今、経路リストへ登録した場所がゴールと一致したら経路を返して処理は終了します。
異なる場合は、探索の候補を追加する手順に入ります。

手順のはじめに、現在の場所をクローズリストに追加します。
また、移動先がない場所を追加することを防ぐためにここでフラグを無効化し、
隣接地が追加された時点でフラグを有効化させます。

続いて、登録した場所の上下左右の場所について見ていきます。
まず、移動できるのか(無効な配列にならないかどうか)について判定を行います。
次に、クローズリストに追加されている(既に通ったのかどうか)か判定します。
最後に移動先が障害物でないかを見ていきます。
この条件が全て満たされた時のみオープンリストの追加処理を行います。

再び、最小のヒューリスティックを持った場所を探す処理へ戻り、ゴールが見つかるまで
行います。
全て探索しても、ゴールが見つからなかった場合はnullを返す仕組みとなっています。
ゴールは絶対に存在するので、通常ならばnullは返らないはずです…。

3. A*実装内容について
 先程の手順で説明した内容を実装したコードを以下に示します。

private ArrayList astar() {
         // 目標地点のノードを作成
         Node goal = new Node(mX, mY, mGoalX, mGoalY, mGoalX, mGoalY);

         // パス探索
         ArrayList openList = new ArrayList();      // 探索候補
         ArrayList closeList = new ArrayList();      // 探索済ルート
         ArrayList pathList = new ArrayList();

         // 開始位置として目標地点を確定候補に追加
         // 初回なので、開始タイルと該当タイルは一致
         Node startPoint = new Node(mX, mY, mGoalX, mGoalY, mX, mY);
         openList.add(startPoint);                

         int curHeuristic = startPoint.getHeuristic();
         boolean flag = true;

         // 探索候補があればループ
         while(openList.isEmpty() == false) {
            // 現在のノード = 探索候補の最も安価なノード
            int index = SearchMin(openList, curHeuristic);
            Node current = openList.remove(index);
            if (flag)
               pathList.add(current);
            curHeuristic = current.getHeuristic();

            // 現在のノードが目標地点のノードと一致しているなら経路を配列として返す
            if (current.equals(goal))
               return pathList;
            else {
               // 現在のノードを探索済ルートに移動
               closeList.add(current);
               flag = false;
               // 現在のノードに隣接する各ノードを調査
               // オープンリストに隣接ノードを追加

               // 左との判定
               if (current.getX() - 1 >= 0) {
                  // クローズリストに既に追加されているか、
                  // 移動先が障害物でないか判定
                  Node left = new Node(mX, mY, mGoalX, mGoalY, current.getX() - 1, current.getY());
                  Log.d(TAG, "Left:(" + left.getX() + ", " + left.getY() + ")");
                  if ((!containNode(openList, left)) && (!containNode(closeList, left)) && (mField[left.getX()][left.getY()] != 1)) {
                     openList.add(left);
                     flag = true;
                  }
               }

               // 右との判定
               if (current.getX() + 1 < FLD_WIDTH) {
                  // クローズリストに既に追加されているか、
                  // 移動先が障害物でないか判定
                  Node right = new Node(mX, mY, mGoalX, mGoalY, current.getX() + 1, current.getY());
                  if ((!containNode(openList, right)) && (!containNode(closeList, right)) && (mField[right.getX()][right.getY()] != 1)) {
                     openList.add(right);
                     flag = true;
                  }
               }

               // 上との判定
               if (current.getY() - 1 >= 0) {
                  // クローズリストに既に追加されているか、
                  // 移動先が障害物でないか判定
                  Node up = new Node(mX, mY, mGoalX, mGoalY, current.getX(), current.getY() - 1);
                  if ((!containNode(openList, up)) && (!containNode(closeList, up)) && (mField[up.getX()][up.getY()] != 1)) {
                     openList.add(up);
                     flag = true;
                  }
               }

               // 下との判定
               if (current.getY() + 1 < FLD_HEIGHT) {
                  // クローズリストに既に追加されているか、
                  // 移動先が障害物でないか判定
                  Node down = new Node(mX, mY, mGoalX, mGoalY, current.getX(), current.getY() + 1);
                  if ((!containNode(openList, down)) && (!containNode(closeList, down)) && (mField[down.getX()][down.getY()] != 1)) {
                     openList.add(down);
                     flag = true;
                  }
               }

            }
         }
         // 到達不能
         return null;
      }

4.参考文献について
 今回の作成にあたり参考にさせていただいた書籍、サイトを紹介いたします。
「ゲーム開発者のためのAI入門」 pp.125～
PythonでA*(A-Star)アルゴリズム
http://d.hatena.ne.jp/pashango_p/20090713/1247455609
RE:自分ならこう書く - pythonでA*
http://d.hatena.ne.jp/pashango_p/20090729/1248882880
Path Finding on Tile based Maps
http://www.cokeandcode.com/pathfinding
A* アルゴリズム完全版
http://coders.g.hatena.ne.jp/bellbind/20070606/p1

5.おわりに
 今回のA*アルゴリズムにJavaで挑戦するにあたりいくつもの問題に
当たりつつもなんとか実装できました。
余力あれば他の言語でも実装してみたいと思いました。
最後にこれを使ったゲームのスクリーンショットでも…。
青い四角で表示されてるマスがA*で求めた経路となります。



ではでは。