Game Development #20 経路検索

tank_20150122195053

冬休みにつくっていたドイツ軍の避弾経始な戦車が大体出来ました。駆逐戦車ヘッツァーと、パンター戦車、そしてパンター戦車からのヤークトパンターです。ドイツ戦車はソ連軍に対抗するために中盤から傾斜装甲ばかりになっていきます。戦況が悪化し始め、なりふり構わなくなっていく様がデザインに表れてますね。涙

 

route_20150122193717

今年はアルゴリズムを強化していく方向なので、手始めに経路検索に取り組んでみました。ダイクストラの最短経路問題。二点間の最短経路を求めるアルゴリズムです。こういった検索アルゴリズムは身近なところでは電車の路線検索なんかに使われていますよね。

ルートの作成はいちいち数値入力していくのが面倒なのと、今後の拡張性を考えてツールを作りました。ポイントを打ち、ポイント同士をつなげるシンプルなツールです。

 

route_20150122193738

ルートを編集しつつ、その場で最短経路を求めることも出来ます。こういったリアルタイム性って大事ですよね。

 

tank_20150122200332

これをマップに利用します。戦車ユニットはこれを利用して目標への経路を求めることになります。

 

tank_20150122203036

どの敵が一番近いかを経路検索で求めていきます。一番近い距離ではなく、経路というところが今回ちょっと進歩したところです。経路が見つかったら順にたどっていきます。最終的に敵に遭遇して砲撃戦になります。

 

tank_20150122203352

敵を探して常に動き回るようになりましたが、すべての戦車が味方を意識せずに一本の経路を通ろうとするので渋滞が起こってしまっています。次回はこの辺の問題を解決していこうと思います。

 

参考資料

ダイクストラの経路検索については「実例で学ぶゲームAIプログラミング」の第五章「グラフの不思議な世界」を参考にしました。

http://www.amazon.co.jp/gp/product/4873113393

広告

Game Development #20 経路検索」への2件のフィードバック

  1. 「一番近い距離ではなく、経路で」至近の敵を求める方法にすると、直線距離は一番近いが接近には迂回が必要な敵よりも、直線距離は少し離れているが迂回の必要がない敵を優先する、という事で良いしょうか。敵に意志を感じられますね!
    私は敵の巡回・追尾アルゴリズムを作っていると、非合理的な移動をしたり、すぐにパターンが読めてしまったりで、いつも悩まされています。
    プレイヤーが思わず感心してしまうような、合理的でいやらしい移動をしてくるアルゴリズムが作れるようになりたいです。
    それから、私も傾斜装甲を取り入れたドイツ戦車は初めの頃はあまり好きじゃなかったのですが、小林源文先生の黒騎士物語でパンターの格好良さに気付かされました。実は今でも、あのペンと薄墨のモノクロ画のまま3Dで動かせないものかと考えています。

    • そうです。これまではマップが平原みたいなものだったので一番近い敵に向かって走っていくような簡単なものでよかったのですが、障害物の多い複雑なマップでは都合が悪いので経路探索を取り入れることにしました。ゲームAIの本(実例で学ぶゲームAIプログラミング)を読んで勉強中ですが、面白そうだと思ったものは一通りやってみるつもりです。最終的に集団行動が取れたらいいですね。

      前の職場に戦車好きの方がいて、黒騎士物語を貸してくれました。なつかしいですね・・・。三号戦車や三号突撃砲がきっかけで戦車好きになったので、パンターはスマートすぎてドイツらしくない!といまだにひっかかってます。そのわりになぜかヤークトパンターは格好いいと思ってたり・・・。

      p.s
      ご存知かもしれませんがパンターの試作戦車でベンツ案というものがあるのですが、これがそのまんまT-34なので本当にこれにならなくてよかったと思います。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中