A*アルゴリズムをTDDで作成してみる(1)
TDDの肝は、
まず最初に使い方から書き始めるので、
一番曖昧になりやすいAPIを早い段階で決められるところかな～って思います。
実際コードを書くとき、なんとなくな感覚で始めることが多いんですが、
「なんとなく」書いたコードは十中八九、メンテナンスがしにくくなる。
使い捨てや書いた後に必ず破棄するプロトタイプならそれでもいいんですが、
大規模になればなるほど「なんとなく」なコードは徐々に限界が見えてきます。
そこで設計の手法が大事になってきます。
これは擬似コードだったり、DDDだったりとあるらしいんですが、
それは今後の課題。
今回は、TDDのマスターに努めます。
最初は、解法が定まってるアルゴリズムに関してTDDを書くのが
入り口としては楽なんじゃないかと。
というわけで、経路探索でおなじみのA*アルゴリズムを試してみることに。
問題は、「ゲーム開発者のためのAI入門」P127の図7.2を拝借しました。
■■□□□□□□□□
■□□□□□G□□□
□□□□□□□□□□
□□□■■■■■□□
□□□□□□□■□□
□□□□S□□■□□
□□□□□□□■□□
■■■□□□□□□□
■□□□□□□□□□
□□□□□□■■□□
■：障害物、□：ルート、S：スタート、G：ゴール
ここからS->Gへ向かうルートを見つけるプログラムを組みます（Java）。
さて、こんな感じでかいてみました。
@Test
public void testSearch()
{
int width = 10;
int height = 10;
SearchMap map = SearchMap.newInstance(width, height);
for (int i = 0; i < width; i++)
{
for (int j = 0; j < height; j++)
{
if ((i == 0 && j == 0)
|| (i == 0 && j == 1)
|| (i == 1 && j == 0)
|| (i == 3 && j == 3)
|| (i == 3 && j == 4)
|| (i == 3 && j == 5)
|| (i == 3 && j == 6)
|| (i == 3 && j == 7)
|| (i == 4 && j == 7)
|| (i == 5 && j == 7)
|| (i == 6 && j == 7)
|| (i == 7 && j == 0)
|| (i == 7 && j == 1)
|| (i == 7 && j == 2)
|| (i == 8 && j == 0)
|| (i == 9 && j == 6)
|| (i == 9 && j == 7))
{
map.setNode(i, j, Wall.newInstance(i, j));
}
else
{
map.setNode(i, j, Road.newInstance(i, j));
}
}
}
ResultPath result = Astar.search(Position.newInstance(5, 4),
Position.newInstance(1, 6));
assertEquals("The start position is (5, 4).",
Position.newInstance(5, 4), result.next().getPosition());
assertEquals("The 2nd position is (4, 3).",
Position.newInstance(4, 3), result.next().getPosition());
assertEquals("The 3rd position is (3, 2).",
Position.newInstance(3, 2), result.next().getPosition());
assertEquals("The 4th position is (2, 3).",
Position.newInstance(2, 3), result.next().getPosition());
assertEquals("The 5th position is (1, 4).",
Position.newInstance(1, 4), result.next().getPosition());
assertEquals("The 6th position is (1, 5).",
Position.newInstance(1, 5), result.next().getPosition());
assertEquals("The last position is (1, 6).",
Position.newInstance(1, 6), result.next().getPosition());
assertEquals("Its point should be at the end.",
false, result.hasNext());
}まず、
SearchMap map = SearchMap.newInstance(width, height);
は、探索フィールドを作成します。最大の幅、高さを指定できるようにしました。
その後の、for文で障害物と道とを設定しています。
本来はファイルから読み込むべきですが、
テストなので直書きでもいいんじゃないかと思ってます。
WallとRoadはNodeを実装したクラスです。
SearchMap#setNode()は指定した位置にノードを設置していくことをイメージしています。
map.setNode(i, j, node);
テスト本体は、
ResultPath result = Astar.search(Position.newInstance(5, 4),
Position.newInstance(1, 6));
assertEquals("The start position is (5, 4).",
Position.newInstance(5, 4), result.next().getPosition());
...の部分で、スタート地点とゴール地点を指定した結果をresultに格納し、
result.next()でノードを順に引き出す（イテレータ）ようにしてみました。
最後に、最終地点に到達したかどうかを確認するためにhasNext()をテストします。
深いところを突き詰めれば、
Astar.search()はスタティックじゃないほうがいいんじゃないかとか、
result.next().getPosition()...っていう書き方がスマートじゃないなとか
いろいろありますが、あんまり深く考えすぎても次に進まないので
とりあえずこれを基に徐々に修正しながらやってみることにします。
