dirigere una massa di nemici alla volta

Question

Sto lavorando ad un semplice gioco 2D in cui molti nemici continuano a generare e inseguire il giocatore oi giocatori in python + pygame. Un problema che ho incontrato e che molte persone che hanno programmato questo tipo di gioco hanno incontrato è che i nemici convergono molto rapidamente. Ho fatto una soluzione temporanea a questo problema con una funzione che allontana a caso due nemici a caso se sono troppo vicini l'uno all'altro. Funziona bene ma riguarda un algoritmo O (n^2) che viene eseguito ogni fotogramma e nei nemici alti il ​​programma inizia a rallentare.

Quando il mio programma viene eseguito con questa funzione, i nemici sembrano formare un oggetto rotondo che ho soprannominato un "grumo". Il grumo sembra di solito in eclittica, ma può essere in realtà più complesso (non simmetrico) perché quando il giocatore si muove i nemici vengono tirati in direzioni diverse. Mi piace il modo in cui si comporta questo grumo, tuttavia mi chiedo se esiste un modo più efficiente per calcolarlo. Attualmente ogni nemico nel gruppo (spesso> 100) viene prima mosso nella direzione del giocatore, e poi spinto a parte. Se invece ci fosse un modo per calcolare la figura creata dal gruppo, e come si muove, si risparmia un sacco di calcoli.

Non sono esattamente sicuro di come affrontare il problema. Potrebbe essere possibile calcolare il punto in cui si sposta il bordo della figura, quindi espanderlo per accertarsi che l'area rimanga invariata.

Anche i miei due funzioni attualmente utilizzate per spostare i nemici:

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 

Edit: alcuni colpi di schermo di come il ciuffo sembra: 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/

Il ciuffo sembra essere principalmente un oggetto rotondo appena allungato (come un'eclissi ma può essere allungato in più direzioni), tuttavia curre ha i bordi dritti a causa dei nemici rettangolari.

Answer 1

Ci sono diversi modi per farlo, a seconda del gioco. Ecco alcune idee per migliorare le prestazioni:

1. Consentire una certa sovrapposizione.
2. Riduce il controllo della distanza da eseguire dopo un numero fisso di frame.
3. Migliora la tua formula di controllo della distanza. Se si utilizza la formula della distanza standard, questa può essere ottimizzata in molti modi. Per uno, sbarazzarsi della radice quadrata. La precisione non ha importanza, solo la distanza relativa.
4. Ogni unità può tenere traccia di un elenco di unità vicine. Esegui i tuoi calcoli solo tra le unità di quell'elenco. Ogni tanto aggiorna quella lista controllando tutte le unità.
5. A seconda della configurazione del gioco, è possibile dividere il campo in aree, come quadranti o celle. Le unità vengono testate solo contro altre unità in quella cella.

EDIT: Quando le unità si avvicinano al loro obiettivo, non potrebbe comportarsi in modo corretto. Suggerirei piuttosto che farli rientrare direttamente sul bersaglio esatto da molto lontano, che in realtà cercano un bersaglio vicino casuale. Come un offset dal loro vero obiettivo.

Sono sicuro che ci sono molti altri modi per migliorare questo, dopo tutto è piuttosto aperto. Dovrei anche indicare Boids e flocking che potrebbero essere di interesse.

Answer 2

È possibile definire un gruppo come un oggetto separato con un numero fisso di "spazi" spaziali per ogni unità nemica nel gruppo. Ogni slot avrebbe un insieme di coordinate relative al centro del clump e sarebbe vuoto o terrebbe un riferimento a una unità.

Una nuova unità che tenta di unirsi al gruppo si muoverà verso lo slot libero più interno, e una volta arrivato lì "rimarrebbe in formazione", la sua posizione è sempre la posizione dello slot occupato. I ciuffi avrebbero un raggio molto più grande di una singola unità, regolerebbero la posizione per evitare sovrapposizioni di altri gruppi o unità allentate che non cercavano di unirsi al gruppo, ecc.

Ad un certo punto, però, avresti bisogno di tuttavia, gestisco le interazioni per le singole unità nel gruppo, quindi non sono sicuro che valga la pena. Penso che il suggerimento di Austin Henley di suddividere il campo in celle/regioni e solo di testare le unità nelle celle vicine sia l'approccio più pratico.

Answer 3

Penso che stiate cercando flocking.

Answer 4

La migliore introduzione al movimento di floccaggio/comportamento dello sterzo: http://www.red3d.com/cwr/steer/. Vedere il documento allegato red3d paper. E il relativo OpenSteer