■
Mavericksに更新すると、
$ sudo port selfupdate ... Error: /opt/local/bin/port: port selfupdate failed: Error installing new MacPorts base: command execution failed
でエラッた。
$ sudo xcode-select --install
で解決した。完。
/tmp/mysql.sock
mysql.sockがないと怒られたので、
cp /private/.../mysql.sock /tmp/mysql.sock
なんてやってみたけど、
cp: /private/.../mysql.sock: Operation not supported on socket
ってエラった。正しくは、
ln -s /private/.../mysql.sock /tmp/mysql.sock
でした。久々にやると、いろいろ忘れてて困る。
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の特徴です。
今回のテストケースはひとつだけで試してますが、
例外的なケースに対応させる必要がある場合もあります。
その場合は適宜、テストを書いて、
前回の動作を保証しつつ、新しい機能を作成していきます。
今回で言えば、スタートからゴールに決してたどり着けない場合ような状況
（ゴールが壁に囲まれている）などを試す必要があるといえます。
次回は、このテストを作成してみることにします。
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()...っていう書き方がスマートじゃないなとか
いろいろありますが、あんまり深く考えすぎても次に進まないので
とりあえずこれを基に徐々に修正しながらやってみることにします。
TDDにおける接合部の基準
最近はもっぱら、テストファーストでコーディングすることを意識するようになりました。
そのときに問題となるのが、
他のクラスやデータに依存しすぎてメソッドをそのまま呼ぶことができない、
あるいは、そのメソッドを呼ぶのに必要な準備が多すぎて
テストコード自体が複雑になってしまったりということが多々あります。
こういう状況に陥るということは、設計が不十分だからに他ならないのですが、
じゃあどうやって上の状況を避けるかと言えば、
メソッドを複雑にしてしまっている原因を分離する必要があります。
これについて、「レガシーコード改善ガイド」という本では、
接合部という言葉を使って、解決策を示しています。
接合部というのは、ポリモーフィズムによってあるメソッドの振る舞いを
テストの時と本番の時で変えることのできるポイントのことです。
たとえば、以下のdoSomething()メソッドをテストしたいときに
class Something
{
public void doSomething()
{
...
job.work();
...
}
}
class Job
{
public void work()
{
// ものすごく時間がかかる処理
...
}
}そのままテストをすると、job.work()が邪魔して、
テストをするのに支障があるときに、何か別のものに置き換えてしまえば
その影響を排除できると言うことです。
（ただし、内部でグローバル変数を使ってるとか戻り値が必要だとかっていう
副作用がある場合はまた別にそれも考慮に入れなければなりません。）
interface Job
{
public abstract void work();
}
class HeavyJob implements Job
{
@Override
public void work()
{
// 重い処理
...
}
}
class MockJob implements Job
{
@Override
public void work()
{
// 何もしない
}
}単体テストでは、そのメソッドの責任のみを確かめるのが目的なので、
このように、邪魔な部分を一時的に上書きするのはとても都合がいいです。
個人的に、接合部に適してるな～って思う部分をまとめると、
- その言語のシンタックスシュガー
- 重い処理
- 外部のアプリケーションやハードが必要になる部分（データベース、ソケットなど）
- ライブラリ
- OSによって挙動が変わる部分（システムコールとか）
- スレッド、GUI
- 毎回値が変わる部分（乱数、現在時刻など）
- グローバル変数（シングルトンも含む）
現時点ではこんなところでしょうか。
試行錯誤の段階なので、今後いろいろと変わるかもしれないですが。
たぶん、序文。
達人プログラマ－の2Pにこんな一説があります。
達人プログラマーは自分自身の経歴を管理し、無知や誤りを認めることを恐れません。
自分はというと、有意無意にかかわらず、どうも背伸びをしてしまう傾向があるみたいです。
すなわち、世の中のすごい人たちに追いつこうと必死で、
無知にたいして異常な劣等感を抱いてしまうということです。
もちろん、無知は仕事や時に趣味においても大きなハンデとしてのしかかることが多々あります。
当然、それが目の前の課題に大きく関係するならば乗り越えなければならないことです。
が、なんでもかんでもを吸収するというのは、時間が限られる中、非常に困難を極めます。
全知全能というのは到底不可能なことでしょう。
まずは、自分が今立たされている状況を知り、そしてどうありたいかを今一度見つめ直す。
そして少しずつその目的に対して、見聞を深めていくことを意識していこうと思います。
わからないことは、わからない。
必要になれば、それを理解する。
理解できたことを、ちょっとずつ記していければ。
