テレワークならECナビ Yahoo 楽天 LINEがデータ消費ゼロで月額500円〜!
無料ホームページ 無料のクレジットカード 海外格安航空券 海外旅行保険が無料! 海外ホテル


log

2014.04.20 C++:経路探索その2


前回の経路探索ではナビゲーションメッシュの各ポリゴンをノードとしたダイクストラ法に
よる手法でしたが、今回はスタート、ゴール、凸壁頂点をノードとしたA*による手法で
実装してみました。

以前はラビが妙な方向に進みながら対象方向に向かっていましたが、今回はちゃんと
最短経路を進むようになっています。…ただ、動画では経路探索でよく用いられる迷路
のような地形ではないため実際に最短経路を進んでる様子が分かりにくいですね苦笑。

他には高さを考慮した手法等が残っていますが、経路探索はこれで一旦終了にしようと
思います。それと前回記事を書いた時点では「他のキャラクターによって経路が遮られて
いる場合はどうするんだろ?」と疑問に思っていたのですがこの場合、キャラクターの
コリジョンサイズと同じかそれより大きいサイズのバウンディングボックスやConvex
Hullを考え、そのコリジョンの凸角を経路探索のノードとして追加することで解決できるな、
と思いました。…結局まだ試していないのであやしいですが。

ところで、GTAやMMO系のようなワールドサイズが広大なゲームの場合、経路探索の
コストがとんでもないことになりそうですが、どうやって最適化してるんだろう。。
ネットで調べてみると、エリアを「AABBで分割してうまく最適化してるぜ!」みたいな
ことが書かれていますが、うーむ分かりそうで…分からない苦笑。
そもそも離れすぎている対象に対しての正確な最短経路の移動は逆に不自然になるので
2ブロック以上離れたAABBエリアへの経路探索は行わないようにする、とかそういう
ことなのかなあ。

追記:
凸角をノードとして経路探索を行う手法はどうやら一般的にはJump Point Searchと
呼ぶようです。自分で思いついた手法なのですが、やはり先人がいました笑。

comment

たけなか 2014.04.23-03:18 Edit

DirectXによる自前プロファイリングの方法
ttp://msdn.microsoft.com/ja-jp/library/bb172234(v=vs.85).aspx

余所様のサイトでDrawCallやSetRenderStateのボトルネックの
調査をしているところがありますが、今まではどうやってやってるのか
分からないでいました。が、上のページを見て「なるほど!Queryを
使えばできるのか!」って思いました。

今までオクルージョンクエリしか使っていなかったので、目から鱗です。
というか大半の人からしたら今更って感じかもしれませんが苦笑。

たけなか 2014.04.24-09:40 Edit

ダイクストラやA*のような経路探索手法は任意点から任意点までの
最短ノードリンクを辿る手法ですが。例えば床に落ちているアイテムを
一番多く取った方が勝ちといったゲームの場合は話が複雑になる。

一番単純な方法は自身から最も近いアイテムから順に取得していく
方法ですが、アイテムごとに獲得できるポイント数が異なる場合は
近くて安いアイテムより遠くて高いアイテムをゲットする方が効率が
いい可能性があります。ただし遠ければ遠いほど敵にアイテムを
とられるリスクも高くなる、、等など。
ゲームデザインが変われば単純にA*を利用するだけでは解決
できなくなる場合があるなと思いました。

たけなか 2014.04.30-22:29 Edit

割といまさらですが、中国はこれくらい過激な手段をとるほど
沖縄がほしいらしい。
ttp://hosyusokuhou.jp/archives/37851992.html

独立を宣言して沖縄が戦場になるのを避けるのが目的、らしいが
独立した瞬間に日中間で戦争が始まるだろ、どう考えても。
まぁ中国からするとそれが狙いなんだと思うが、割と本気で
怖いなと思った。

たけなか 2014.05.11-01:55 Edit

海外の技術論文ではまるでおきまりかのようにとあるキャラの
画像が載せられていたりするのですが。その画像の元ネタは
どうやらこのサイトのようですね。

ttp://hyperboleandahalf.blogspot.jp/

今までずっと疑問に思っていたので、もやもやが晴れてスッキリしました。