ささブログ

この人は心が少年ジャンプなんだ、と言われた。そうだよ。いいじゃん。これからもずっとな!!

経路探索アルゴリズム

time 2010/01/15

タワーディフェンスの製作をしているとき、敵の動かし方に迷いました。(私は、だいたい迷ってばかりなのですが) どういうことかと言うと、タワーディフェンスは、プレイヤーが砲台(ユニット)をフィールドに配置して敵を撃破するゲームです。敵は砲台を通り抜けることが出来ない(飛行ユニットは例外)ので、砲台を避けてゴールに向かって移動します。 そのため、プレイヤーは砲台を迷路のように多数配置することが多いです。 ここで、私が困ったのは、「どうやってリアルタイムで構築される迷路の道順を調べるのか?」 でした。 迷路が固定(通路侵入型タワーディフェンスは、これに当てはまります)なら道順は予めわかるので問題ありません。プログラム時に該当迷路に対するスタート地点からゴールまでの道順を、配列かリストにでも設定しておけば良いです。その値に従い敵を動かすだけです。 ただ、これが(砲台の)自由配置型タワーディフェンスの場合、砲台をプレイヤーが配置(または削除)するたびに迷路の形状がリアルタイムに変わってしまいます。 また、敵も随時移動しているため、砲台を配置(または、削除)した時点で道順を計算し直す必要があります。(スタート地点からゴールまでの道順ではなく、今現在、敵がいる位置からゴールまでの道順を計算し直す必要があります。) 計算しなくても、次の方法でも出来そうかな、浅はかな素人である私は思いました。 1)敵が移動するとき、移動先に砲台があったら別の道を行く 2)その際の行き先はランダム 3)移動先がゴールになるまで1)2)を繰り返す これでも、処理を何回も繰り返す内に、寄り道や遠回りをしそうですが、いつかはゴールにたどり着けそうです。(実際作ったら、同じところを永遠に回りゴールに到達しませんでした。) 他の方の作ったタワーディフェンスを見ると、どんな迷路配置にしても、最短ルートを通ってゴールに向かっています。 か、かしこい。 仕方がないので、また途方にくれつつ、Googleで調べたところ「経路探索アルゴリズム」なるものにたどり着きました。駅スパートとかで、そういえば聞いたことあるかも。 「経路探索アルゴリズム」はいくつも種類があり、私が探しだせたのは下記になります。 1)ダイクストラ法 2)幅優先探索 3)深さ優先探索 4)A*アルゴリズム Wikipediaなどに詳しく載っているので興味ある方は覗いてみて頂きたいのですが、私的には4)が良さげに感じました。A*(エースター)と名前もとても素敵。(ちなみにA*はダイクストラ法の改良版とのことです) A* アルゴリズムは、各頂点nからゴールまでの距離の推定値 h* (n) を知っていた場合に対して最短経路問題を効率的に解くアルゴリズムである。 ただし、推定値は実際の距離と同じであるかないしそれより小さくなければならない。 例えば地図上を道路に沿って歩いたときの最短経路を求めたい場合、直線距離を h* (n) として用いる事ができる、とのこと。(Wikipediaより抜粋) 、、、、。 何のことやら初めて読んだときは、さっぱりでしたが「最短経路問題を効率的に解くアルゴリズムである」という部分に非常に引かれました。 で、このA*を調べて理解して実装することになるのですが、すごーーーーーーーく、しんどかったです。一応ささタワーディフェンスでは、なんとなく動いていますが、ちゃんと理論どおりに実装出来ているかは未だにわからず。他の皆さんも、これ使っているのかなぁ? 今また同じ実装を0からやれ、と言われても私には無理です。 A*の理屈、JAVAによる実装方法の概要は、そのうち(自分自身へのメモの意味が100%の理由で)書きたいと思います。
応援嬉しいです^^ にほんブログ村 IT技術ブログ iPhoneアプリ開発へ

この記事を読んだ方はこの記事も読まれています

sponsored link

down

コメントする




オレです!

やまだ33太郎あきら

やまだ33太郎あきら

名前:やまだ33太郎あきら レベル:33 職業:釣り堀屋店主 得意技:キン肉バスター33



sponsored link

人気記事