移動するオブジェクトの周りのパスを計算する方法

Question

小さなゲームエンジンを書きました。タイルベースのマップと経路探索のためのA *アルゴリズムが特徴です。しかし、2つのオブジェクトが衝突してウェイポイントをブロックすると、問題が発生します。彼らは反対方向から来ているので、もう移動することはできず、次のウェイポイントには到達しません。 は私が可動して、すべてのタイルにフラグを立てる、

はちょうど次の空きウェイポイントへのパスを計算ブロックされたタイルにフラグを立てるパスを再計算し、他の可動物体と衝突することはできません

• 可動オブジェクトのように、いくつかの可能な解決策を考えましたブロックされたオブジェクト

私は本当に最初の可能性を望んでいない、それはエンジンのようなアクションではないゲームのためのちょっとしたものです。マップ上に多くの移動可能なオブジェクトがある場合、最後の2つの可能性は非常に遅くなる可能性があります。 どうすればいいですか？ところで、最初の可能性は "Stronghold"で実装され、他の2つは新しい戦略ゲームで見つけることができます。

Answer 1

あり、もちろんの単一の正解はないのですが、私は同様の問題で何をやったかを共有することができます

私が通過すると、この時点では、古い学校のように見えることに同意します。ただし、オブジェクトがナビゲーションメッシュよりも小さい場合は、実際にパスを無効にすることなく、境界ボックスを使用して衝突回避を行うことができます。より大きな経路に対して、衝突回避を小さく、局所的にする。

ゲームでうまくいかない場合は、通常はブロックを追加することをおすすめします。経路探索のコストが気になる場合は、衝突が発生するまで待つことができ、一時的に「ブロック」を追加して、再経路を設定することができます。もう1つの方法は、ブロックと再パスを定期的に挿入することです。これは、自然に見えるパスを与えることができ、奇妙に見ることができる "移動する前にお互いに実行"を避ける。

コストはA *アルゴリズムに大きく依存します。アルゴリズムが結果をキャッシュしない場合、ブロックには増分コストがなく、A *はできるだけ頻繁に実行することができます。たとえば、フレームを1回実行し、A *タスクのキューを保持します。

アルゴリズムが結果をキャッシュする場合は、ブロックを移動する前に複数の解決を行うようにA *計算をグループ化してみてください。