3

したがって、基本的には、障害物を通り抜けてパスを見つけ、診断的に移動できる A* パスファインダーをコーディングしました。私は基本的に、http: //www.policyalmanac.org/games/aStarTutorial.htm の疑似コードを実際のコードに実装し、バイナリ ヒープ メソッドを使用してオープンリストからアイテムを追加および削除しました。

バイナリ ヒープを使用すると、パフォーマンスが大幅に向上し、以前に使用した挿入ソート アルゴリズムよりも約 500 倍高速になりました。

問題は、平均で約 150 万ナノ秒かかることです。これは約 .0015 秒です。

問題は、マップにタワーを追加するたびに各モブのパスファインディングを更新する必要があるタワー ディフェンス ゲームを作成することです。マップ上に最大で約 50 体の Mob がある場合、Mob 全体のすべてのパスを更新するのに約 .0015 * 50 = .075 秒かかることを意味します。ゲームは基本的に 0.016 秒である 1/60 秒ごとに刻みます (すべてのゲーム内のものの更新)。したがって、問題は、刻みにかかる時間よりもパスの更新に時間がかかることです。これにより、大幅な遅延が発生します。では、これについてどうすればよいですか？オープンリストをソートするためのより良いアルゴリズムを見つけるか、パスファインディングタスクを分割して、各ティックがすべてではなくX個のパスファインディングタスクのみを実行するようにする必要があります。

4

3 に答える 3

4

各敵からチェックポイントまで探索するのではなく、チェックポイントから外側に向かって一度にすべての敵を探索します。この方法では、50 回の検索を行うのではなく、1 回だけで済みます。

より具体的には、すべての敵に到達するまで、プレーヤーから外側に向かって幅優先検索(グラフが重み付けされている場合はdjikstra の) を実行します。

EstimatedDistanceToEnd ヒューリスティック(aka h(x))を任意の敵に対する最小推定値に変更することで、この戦略を A* で機能するように変更できますが、多くの敵では、単純なオプションよりも遅くなる可能性があります。これが機能するには、ヒューリスティックが一貫している必要があります。

さらに、正しいタイブレーク基準を使用していることを確認してください。

また、最も重要なことは、ほとんどのゲームでパスファインダーをすべてのフレームで実行する必要がないことを覚えておいてください。多くの場合、ゲームによっては 1 秒に 1 回か 2 回、またはそれ以下で済みます。

それでも遅すぎる場合は、 D* liteを使用して、後続の検索間で情報を再利用することを検討できます。しかし、幅優先探索を 1 回実行するだけで十分な速度が得られることは間違いありません。

( gamedevの同様の質問に対する私の回答からコピー)

于 2013-02-27T19:05:00.023 に答える
1

Floyd-Warshall アルゴリズムを検討したことがありますか?

基本的に、A* は単一のソースから 1 つ以上の宛先へのパス検索用です。ただし、タワー ディフェンス (もちろんルールによって異なります) では、マップ内を移動する複数のソースが重要です。

したがって、このためには、フロイドのアルゴリズムがより最適であるように思われます。ただし、A* アルゴリズムで、個々のユニットではなくユニットグループのパスを見つけることができます。これにより、計算時間が最適化されます。

于 2013-02-27T14:54:46.953 に答える
0

おそらく、出口からすべてのクリープに向かって逆検索できるため、迷路を探索する必要があるのは 1 回だけです。

于 2013-02-27T16:06:41.137 に答える