レストランアプリ試作#4 経路探索

http://m.2chradio.com/avatar3.swf

レストランアプリ試作中ですが
障害物を避けて着席できるように、探索を追加してみました
これが、詰将棋探索にちょっと似ています。
ゴールは、誰も座ってない椅子を見つけることなのですが、
どっちから進めばいいかは、障害物がある場合、
1マスづつ空き地を調べていかないと分かりません。
いったん逆方向に行かないとゴールに行けない場合もありますし
また、最短経路を探すために
反復進化をやってみました。
そのせいか、場合によってかなり重いです。
特に、部屋が広くて何も無いような「裸王問題」の場合に重くなりますw



探索時の残り深さをハッシュに残して比較して探索マスを枝刈りするように
改造したら十分早くなりました
(将棋で普通にやってることをやってなかった)
やねうらおさんからダイクストラ法を紹介されましたが、
オライリーの「ゲームAIプログラミング」でも紹介されている)
ゴールと途中ノードの距離などが分かってる場合の手法のようで、
それらを用意するコードを書くのが面倒そうなので、
とりあえず詰将棋的な手法でやってみます。
実装が簡単ですので


ただ、移動中に突然、進路変更して逆方向の椅子に向かうことがありますね

上からスキャンして見つかった椅子に向かっているから。
現在は、ターゲットの椅子への最短距離は調べているけど
一番近い椅子を探す作業はしていない。
細かく見ていくと、色々とたいへんです(^^;
レストランアプリ、一見単純に見えて
AI好きにはなかなか楽しい題材です。