Gioco 2D: veloce (est) modo di trovare x entità più vicine per un'altra entità - quantità enorme di entità, altamente dinamico

Question

Sto lavorando a un gioco 2D che ha una quantità enorme di entità dinamiche. Per il divertimento, chiamiamoli soldati, e diciamo che ce ne sono 50000 (che ho pensato solo casualmente, potrebbe essere molto più o molto meno :)).

Tutti questi soldati muovono ogni fotogramma secondo le regole - pensate al boid/al floccaggio/al comportamento dello sterzo. Per ogni soldato, per aggiornare il suo movimento ho bisogno dei soldati X che sono più vicini a quello che sto elaborando.

Quale sarebbe la migliore gerarchia spaziale per archiviarli per facilitare calcoli come questo senza troppe spese generali? (Tutte le entità vengono aggiornate/spostate ogni frame, quindi deve gestire molto bene le entità dinamiche)

Answer 1

L'approccio più semplice consiste nell'utilizzare una griglia. Ha diversi vantaggi:

• semplici
• veloci
• facile aggiungere e rimuovere gli oggetti
• facile cambiare la griglia per un dettaglio più fine, se si sta ancora facendo troppi controlli a distanza

Inoltre, assicurarsi di non eseguire uno squareroot per ogni controllo della distanza. Dal momento che stai solo confrontando le distanze, puoi anche confrontare la distanza al quadrato.

Answer 2

Per il rilevamento di collisione in fase ampia, un spatial index come un albero quadrangolare (poiché è 2D) o una griglia. Ho collegato a Metanet Software's tutorial prima; delinea uno schema basato sulla griglia. Naturalmente, il tuo gioco non ha nemmeno bisogno di usare le griglie in modo così approfondito. Basta archiviare ciascun attore in una griglia nascosta e scontrarlo con oggetti nelle stesse celle vicine.

Answer 3

L'intero punto di selezione di una buona gerarchia spaziale è di essere in grado di selezionare rapidamente solo gli oggetti che devono essere testati. (Una volta scoperto quel piccolo sottoinsieme, la radice quadrata probabilmente non farà più così male)

Mi interessa anche quale sia il metodo migliore/più ottimale per l'indicizzazione spaziale 2D oggetti dinamici.

Quadtree/kd-tree sembrano buoni, ma non sono troppo buoni con inserimenti dinamici. Gli alberi KD possono diventare sbilanciati.

Solo un pensiero casuale, se le tue entità sono punti una doppia struttura di inserimento-ordinamento (da X e Y) in combinazione con una ricerca binaria potrebbe essere qualcosa da provare ..?