あたまがうにになる

今のマイブームは防衛ゲームです。

防衛ゲームとは、シミュレーションとかアクションとかアドベンチャーとかRTSと同じく、ゲームのジャンルとして使ってます。
Desktop Tower Defense とか Defender とか TURRET WARS みたいなゲーム。

この手のゲームには大体組み込まれている迷路を最短経路で移動する機能。
この部分をどうやって作ってるのかきになったので、試しにFlashで作って見ました。
  青い■がスタート、赤い四角が目的地、●が敵キャラ、■が通り抜け出来ない壁のつもりです。
1秒に1回ぐらいのタイミングでランダムに■と●が増えます。

アルゴリズムは基本的にはオリジナルのつもりだったのですが、調べて見るとA＊(エースター)という有名なアルゴリズムみたいですね。
作ってみたものの、どうしても最短経路計算時に処理落ちしますね。

webで出回ってるゲームで処理落ちしてるのを余り見かけないので、もっと効率の良い計算方法があるのかな…
どうやって計算してるんだろ。