A*アルゴリズムをTDDで作成してみる(2)

前回記述したテストケースはそのままでは動かないので、肉付けをしていきます。

・・・の前に前回のテストケースに不十分な部分があったので、修正をば。

Astar astar = Astar.newInstance(map);
ResultPath result = astar.search(Position.newInstance(5, 4),
                                 Position.newInstance(1, 6));

作成したマップを渡してなかったので、結局動的クラスに変更しました。

List<Position> sixthAnswers = new ArrayList<Position>();
sixthAnswers.add(Position.newInstance(0, 5));
sixthAnswers.add(Position.newInstance(1, 5));
sixthAnswers.add(Position.newInstance(2, 5));
assertEquals("The 6th position is (0, 5), (1, 5), or (2, 5).",
             true, sixthAnswers.contains(result.next().getPosition()));

正解例が(1, 5)だけでなく(0, 5), (2, 5)も含まれていたため、
いずれかであれば成功としています。
この辺、まとまりがすっきりしないので上手にかける方法を模索中です。

作成していく順番は、個人的にはどこからでもいいと思ってるんですが、
コンパイルエラーを解消しながら、というのが
進行度がわかりやすくていいのかなと思ってます。
今回の場合は、SearchMap->Nodeと準備した後で、
Astar#search()を実装していくのが、わかりやすそうです。

まず、SearchMapから。
※インターフェースのみ。
ソースはgithub（https://github.com/mewtex/Algorithms）参照。

public class SearchMap
{
    private final int mWidth;
    private final int mHeight;
    private final Node[] mNodes;

    private SearchMap(int width, int height);
    public static SearchMap newInstance(int width, int height);
    public void setNode(int row, int column, Node node) throws SearchingFailedException

    void clear();       
    Node findNode(Position position) throws SearchingFailedException
    int getSize()
    AdjacencyList getAdjacencyList(Node node)   

基本的にnewInstance()というstaticファクトリー, equals(), hashCode(), toString()は
毎回作成しています。
パターンは毎回決まっていて、手入力だと結構面倒くさいので
コードジェネレータとか作って自動化するのがよさげです。
（equals, hashCode, toStringはApacheにそれ用のがあるのでそれを使うのが
楽で便利なんですが、一応外部ライブラリなので多少気を遣う必要はあります）

あとは、テスト側で見えているsetNode()以外のメソッドは
アクセス範囲をデフォルトもしくはprivateにしています。

mNodesは宣言は一次元ですが、扱いとしては二次元配列です。
setNodeで指定した位置に指定したノードを設定しています。

次に、Node（WallとRoad）について。

public interface Node extends Comparable<Node>
{
    public abstract Position getPosition();
    public abstract boolean hasParent();
    public abstract void setParent(Node node);
    public abstract Node getParent();
    public abstract boolean isAvailable();
    public abstract int getScore();   
    public abstract void setScore(int score);
}

getPosition()は、ノードの場所を返します。
parentというのは、そのノードの前の場所を指します。
isAvailable()は、WallとRoadで障害物かどうかを判定するために使用します。
scoreは、探索の際に用いるスコアです。
また、ノード同士でスコアの比較を行うのでComparableを実装しています。

実装してみて思ったんですが、
parentやisAvailable、scoreといった情報は
クライアントが知る必要のないものです。

これを解決するために、
getPosition()以外を別のインタフェースとして、
内部ではそのインタフェースを用いるような方法のほうが
もっとスマートかもしれません。
こういうのは、先に実装を済まして後のリファクタリングで修正していきます。

次に、Positionです。

public class Position
{
    private final int mRow;
    private final int mColumn;

    private Position(int row, int column);   
    public static Position newInstance(int row, int column);

    public int getRow();
    public int getColumn();

    @Override
    public boolean equals(Object o)
    {
        if (this == o)
        {
            return true;
        }
        if (!(o instanceof Position))
        {
            return false;
        }

        Position target = (Position) o;
        return mRow == target.mRow
                && mColumn == target.mColumn;
    }
}

テストで比較するものなので、equals()の実装が必須です。

最後に、Astar。

public class Astar
{
    private final SearchMap mMap;

    private final OpenList mOpenList;
    private final ClosedList mClosedList;

    private Node mCurrentNode;

    private Astar(SearchMap map);
    public static Astar newInstance(SearchMap map);
    public ResultPath search(Position start, Position goal) throws SearchingFailedException;

    void clear();
}

search()がA*アルゴリズムを解くメソッドです。
以下、これを繰り返して実装するのがTDDの特徴です。

今回のテストケースはひとつだけで試してますが、
例外的なケースに対応させる必要がある場合もあります。
その場合は適宜、テストを書いて、
前回の動作を保証しつつ、新しい機能を作成していきます。
今回で言えば、スタートからゴールに決してたどり着けない場合ような状況
（ゴールが壁に囲まれている）などを試す必要があるといえます。
次回は、このテストを作成してみることにします。