前回の経路探索ではナビゲーションメッシュの各ポリゴンをノードとしたダイクストラ法に
よる手法でしたが、今回はスタート、ゴール、凸壁頂点をノードとしたA*による手法で
実装してみました。
以前はラビが妙な方向に進みながら対象方向に向かっていましたが、今回はちゃんと
最短経路を進むようになっています。…ただ、動画では経路探索でよく用いられる迷路
のような地形ではないため実際に最短経路を進んでる様子が分かりにくいですね苦笑。
他には高さを考慮した手法等が残っていますが、経路探索はこれで一旦終了にしようと
思います。それと前回記事を書いた時点では「他のキャラクターによって経路が遮られて
いる場合はどうするんだろ？」と疑問に思っていたのですがこの場合、キャラクターの
コリジョンサイズと同じかそれより大きいサイズのバウンディングボックスやConvex
Hullを考え、そのコリジョンの凸角を経路探索のノードとして追加することで解決できるな、
と思いました。…結局まだ試していないのであやしいですが。
ところで、GTAやMMO系のようなワールドサイズが広大なゲームの場合、経路探索の
コストがとんでもないことになりそうですが、どうやって最適化してるんだろう。。
ネットで調べてみると、エリアを「AABBで分割してうまく最適化してるぜ！」みたいな
ことが書かれていますが、うーむ分かりそうで…分からない苦笑。
そもそも離れすぎている対象に対しての正確な最短経路の移動は逆に不自然になるので
2ブロック以上離れたAABBエリアへの経路探索は行わないようにする、とかそういう
ことなのかなあ。
追記：
凸角をノードとして経路探索を行う手法はどうやら一般的にはJump Point Searchと
呼ぶようです。自分で思いついた手法なのですが、やはり先人がいました笑。