0

私はしばらくの間、2D のトップダウン シューティング ゲームに取り組んできました。ほとんどのゲームを実装し、エンジンを JOGL でゼロから作成しましたが、小さな問題に遭遇したので、他の人の意見を聞きたいと思います。問題にアプローチします。そのため、マップ内のランダムな場所にクリープがスポーンし、これらの各クリープは A* パス検索を使用し、不要なチェックを最小限に抑えるように最適化されていますが、マップは 10x10 から 200x200 タイルのいずれかになる可能性があり、速度が低下する唯一のものです。ゲームを大幅に下回っているのは AI です。距離ベースのソリューションも実装しようとしました。このソリューションでは、クリープが特定の範囲内に入るまでアイドル状態になりますが、多くのクリープが生成されるため、それでもゲームが大幅に遅くなります。アドバイスをいただければ幸いです。

4

1 に答える 1

1

コードを高速化する方法は多数あります。

まず、A* アルゴリズムには多くの変更があり、次のように使用できます。

クリープがプレーヤーへのパスを検索している場合 (すべてのクリープに1 つの目標があります)、次のアルゴリズムのいずれかに検索を変更できます。

  • Dijkstra アルゴリズムを使用してプレイヤーからマップ内の各ポイントまでの距離を計算します。200x200 の場合、非常に高速 (アルゴリズムを使用すると 40,000 頂点O(nlgn)) になり、現在のポイントよりもプレイヤーまでの距離が短い隣接ポイントにクリープを移動するだけです。
  • パスが見つかったら、プレーヤーから任意のクリープ (たとえば、最小の ID) まで A* 検索を実行します - 目標を次のクリープに変更しますが、アルゴリズム自体はリセットしません。プレーヤーからの最適なパス)、明らかに-実行中に別のクリープに遭遇した場合、目標は-それを記録するだけです(見つかったパスが最適です)。

マップが何らかの形で特定されている場合 (マップの一部へのドア/入り口が含まれている場合) に適用できる別の可能な変更は、クリープ AI を「有効にする」トリガーを配置することです。これはO(1)解決策ですが、特定のタイプのマップが必要です。

そして、最後のアイデアの 1 つは、次のようないくつかの準最適なソリューションを実装することです。

  • まず、各クリープの A* を計算します
  • プレーヤーまでの距離がしきい値よりも小さい場合はT、次の反復でパスを再計算して、遅延がないようにします。
  • それ以外の場合 - 別のパス検索の前に、少なくとも 10 ～ 50 回反復してパスをたどります。

数え切れないほどの最適化がありますが、ゲームに関する詳細と、それらの最適化に費やしたい時間についての詳細が必要です。

于 2013-08-20T16:01:47.260 に答える