一度に多くの敵を指揮する

Question

私は単純な2dゲームに取り組んでいます。多くの敵が引き続きプレイヤーやプレイヤーをpython + pygameで追いかけています。私が遭遇した問題と、この種のゲームをプログラムした多くの人々が遭遇したのは、敵が非常に迅速に収束するということです。私は、互いに近づけすぎると2つの敵をランダムに押し離す機能を使ってこの問題を一時的に解決しました。これは正常に機能しますが、すべてのフレームで実行されるO（n^2）アルゴリズムと、プログラムが遅くなり始める高い敵についてです。

私のプログラムがこの機能で動作するとき、敵は丸いオブジェクトを形成しているように見えます。塊は通常は黄道のように見えるが、プレイヤーが移動するにつれて敵が異なる方向に引っ張られるため、実際にはより複雑（対称ではない）である可能性がある。私は、このクランプが動作する方法が好きですが、それを計算するより効率的な方法があるかどうか疑問に思っています。現在、塊（しばしば> 100）内のすべての敵は、最初にプレイヤーの方向に移動され、次に離されます。代わりに、クランプが作成する図形を計算する方法があった場合、それがどのように動くかによって多くの計算量が節約されます。

私はこの問題にどのように接近するのか正確にはわかりません。図形の境界線がどこに移動するかを計算し、展開して領域が同じであることを確認することができます。

また、現在の敵を移動するために使用されている私の二つの機能：

def moveEnemy(enemy, player, speed): 
    a = player.left-enemy.left 
    b = player.top-enemy.top 
    r = speed/math.hypot(a,b) 
    return enemy.move(r*a, r*b) 

def clump(enemys): 
    for p in range(len(enemys)): 
     for q in range(len(enemys)-p-1): 
      a = enemys[p] 
      b = enemys[p+q+1] 
      if abs(a.left-b.left)+abs(a.top-b.top)<CLUMP: 
       xChange = (random.random()-.5)*CLUMP 
       yChange = ((CLUMP/2)**2-xChange**2)**.5 
       enemys[p] = enemys[p].move(int(xChange+.5), int(yChange + .5)) 
       enemys[p+q+1] = enemys[p+q+1].move(-int(xChange+.5),-int(yChange+.5)) 
    return enemys 

編集：塊がどのように見えるかのいくつかのスクリーンショット： http://imageshack.us/photo/my-images/651/elip.png/ http://imageshack.us/photo/my-images/ 832/newfni.png/

http://imageshack.us/photo/my-images/836/gamewk.png/

塊は（Eclipseのようなしかし、複数の方向に延伸してもよい）大部分だけ延伸丸い物体であると思われる、しかし、それは、電流増幅率長方形の敵のためにまっすぐなエッジがありません。

Answer 1

ゲームに応じて、これについてはいくつかの方法があります。掲載結果を改善するためのアイデアをいくつか紹介します。

1. 重複を許します。
2. 一定数のフレームの後に距離のチェックを減らします。
3. 距離チェック式を改善しました。標準距離式を使用している場合、これはさまざまな方法で最適化できます。 1つは、平方根を取り除く。精度は重要ではなく、相対距離だけです。
4. 各ユニットは、近くのユニットのリストを追跡することができます。そのリスト内のユニット間でのみ計算を実行します。頻繁に、すべてのユニットをチェックしてそのリストを更新します。
5. ゲームの設定に応じて、フィールドを象限やセルなどの領域に分割できます。ユニットは、そのセル内の他のユニットに対してのみテストされます。

EDIT：ユニットがターゲットに近づくと、正しく動作しない可能性があります。私は遠くからの正確なターゲットを自宅に持っていらっしゃるのではなく、実際に無作為に近いターゲットを探すことをお勧めします。彼らの本当の目標からのオフセットのように。

私はこれを改善するために他にも多くの方法があると確信しています。私はまた、興味のあるかもしれないBoidsとflockingを指摘する必要があります。

Answer 2

クランプは、塊の中の敵ユニットごとに固定数の空間的な「スロット」を持つ別個のオブジェクトとして定義できます。各スロットは、クランプ中心に対する座標のセットを有し、空であるか、または1つのユニットへの参照を保持する。

塊に参加しようとする新しいユニットは、最も内側の空いているスロットに向かって移動し、そこに着くと、その位置は常に占領していたスロットの位置になります。塊は、単一のユニットよりもはるかに大きな半径を持ち、他の塊や、塊などに結合しようとしていないユニットが重ならないように位置を調整します。

しかし、ある時点では、塊の中の個々のユニットの相互作用を扱うので、それは価値があるかどうかはわかりません。オースティン・ヘンリーは、フィールドをセル/リージョンに分割し、近くのセルのユニットに対してのみテストすることが最も実用的なアプローチであると考えています。

Answer 3

私はあなたがflockingを探していると思います。

Answer 4

フロッキング/ステアリング動作の動きのための最良のイントロ：http://www.red3d.com/cwr/steer/。添付書類red3d paperを参照してください。そして関連するものOpenSteer