Metodi di rilevamento delle collisioni in fase larga?

Question

Sto costruendo un motore fisico 2D e voglio aggiungere il rilevamento di collisioni a fase larga, anche se conosco solo 2 o 3 tipi:

• Controlla tutto contro tutto il resto (O (n ^ 2) complessità)
• Sweep and Prune (ordina e sweep)
• qualcosa sulla partizione spaziale binaria (non so come fare)

Ma sicuramente ci sono più opzioni, giusto? quali sono? E può essere fornita una descrizione di base di ciascuna o collegamenti a descrizioni?

Ho visto questo ma sto chiedendo un elenco di algoritmi disponibili, non il migliore per le mie esigenze.

In questo caso, "rilevamento di collisioni a fase larga" è un metodo utilizzato dai motori fisici per determinare quali corpi nella loro simulazione sono abbastanza vicini da giustificare ulteriori indagini e possibilmente la risoluzione delle collisioni.

Answer 1

L'approccio migliore dipende dall'uso specifico, ma la linea di fondo è che vuoi suddividere il tuo spazio mondiale in modo tale che (a) ogni corpo sia esattamente in una suddivisione, (b) ogni suddivisione sia abbastanza grande da contenere un corpo una particolare suddivisione può scontrarsi solo con corpi in quella stessa suddivisione o suddivisione adiacente, e (c) il numero di corpi in una particolare suddivisione è il più piccolo possibile.

Il modo in cui lo fai dipende da quanti corpi hai, come si muovono, quali sono i tuoi requisiti di prestazione e quanto tempo vuoi spendere sul tuo motore. Se stai parlando di corpi che si muovono in uno spazio ampiamente aperto, la tecnica più semplice sarebbe quella di dividere il mondo in una griglia in cui ogni cella è più grande del tuo oggetto più grande e tracciare l'elenco di oggetti in ogni cella. Se stai costruendo qualcosa sulla scala di un classico gioco arcade, questa soluzione potrebbe essere sufficiente.

Se hai a che fare con corpi che si muovono in un mondo aperto più ampio, una semplice griglia diventerà travolgente abbastanza rapidamente e probabilmente vorrai una sorta di struttura ad albero come i quadrifogli, come suggerisce Arriu.

Se stai parlando di muovere corpi all'interno di spazi limitati anziché spazi aperti, allora potresti considerare un Albero BSP ; l'albero divide il mondo in "spazio in cui puoi camminare" e "muri", e tagliare un corpo nell'albero determina se è in una posizione legale. A seconda della geometria del mondo, puoi anche utilizzare un BSP per il rilevamento a larga fase delle collisioni tra corpi nel mondo.

Un'altra opzione per i corpi che si muovono nello spazio limitato sarebbe un motore portale; se il tuo mondo può essere costituito da regioni poligonali convesse in cui ciascun lato del poligono è una parete solida o un "portale" verso un altro spazio concavo, puoi facilmente determinare se un corpo si trova all'interno di una regione con un test point-in-poligono e semplifica il rilevamento delle collisioni osservando solo corpi nella stessa regione o regioni connesse.

Answer 2

Un'alternativa a QuadTrees o BSPTrees sono SphereTrees (CircleTrees in 2D, l'implementazione sarebbe più o meno la stessa). Il vantaggio di SphereTrees è che gestiscono molto bene grandi carichi di oggetti dinamici. Se i tuoi oggetti sono in costante movimento, BSPTrees e QuadTrees sono molto più lenti nei loro aggiornamenti di quanto non sarebbe un Albero Sfera / Cerchio.

Se hai un buon mix di oggetti dinamici e , una soluzione ragionevolmente buona è usare un QuadTree / BSPTree per la statica e un Sphere / Cicle Tree per gli oggetti dinamici. Ricorda solo che per ogni dato oggetto, dovresti controllarlo contro entrambi alberi.

Answer 3

Consiglio quadtree il partizionamento. È piuttosto semplice e funziona davvero bene. Ecco un Flash demo di rilevamento di collisioni a forza bruta vs. rilevamento delle collisioni quadrifoglio. (Puoi dirlo per mostrare la struttura a quattro alberi.) Hai notato come il rilevamento delle collisioni a quattro alberi sia solo il 3% della forza bruta in quella demo?

Inoltre, se sei serio sul tuo motore, ti consiglio vivamente di prendere real -time rilevazione delle collisioni . Non è costoso ed è davvero un ottimo libro che copre tutto ciò che vorresti sapere. (Incluso il rilevamento delle collisioni basato su GPU.)

Answer 4

Tutti gli algoritmi di accelerazione dipendono dall'uso di un test economico per escludere rapidamente oggetti (o gruppi di oggetti) e quindi ridurre il numero di test costosi che devi fare. Vedo gli algoritmi in categorie, ognuna delle quali ha molte varianti.

1. Partizionamento spaziale. Scava spazio ed escludi a buon mercato candidati che si trovano in diverse regioni. Ad esempio, BSP, griglie, ocre, ecc.

2. Partizionamento oggetti. Simile al n. 1, ma il clustering è focalizzato sugli oggetti stessi più dello spazio in cui risiedono. Ad esempio, gerarchie di volumi limitanti.

3. Metodi di ordinamento e sweep. Metti gli oggetti in ordine spazialmente ed escludi le collisioni tra quelli che non sono adiacenti.

1 e 2 sono spesso gerarchici, ricorrendo in ciascuna partizione secondo necessità. Con 3, puoi facoltativamente scorrere diverse dimensioni.

I compromessi dipendono molto dalla geometria della scena. Gli oggetti si raggruppano o sono distribuiti uniformemente o scarsamente? Hanno tutte le stesse dimensioni o ci sono enormi variazioni nelle dimensioni? La scena è dinamica? Potete permettervi molto tempo di preelaborazione?

Il " poco costoso " i test sono in realtà lungo uno spettro da molto economico a un po 'costoso. Scegliere l'algoritmo migliore significa ridurre al minimo il rapporto tra il costo dei test economici e la riduzione del numero di test costosi. Oltre alle preoccupazioni algoritmiche, ti metti in sintonia, come preoccuparti della località della cache.

Answer 5

Un'alternativa sono le semplici griglie, diciamo 20x20 o 100x100 (dipende dal tuo mondo e dalle dimensioni della memoria). L'implementazione è più semplice di una struttura ricorsiva come quad / bsp-alberi (o alberi a sfera per quella materia).

Gli oggetti che attraversano i bordi delle celle sono un po 'più semplici in questo caso e non degenerano tanto quanto potrebbe fare un'implementazione ingenua di un bsp / quad / oct-tree.

Usando quello (o altre tecniche), dovresti essere in grado di abbattere rapidamente molte coppie e ottenere una serie di potenziali collisioni che richiedono ulteriori indagini.

Answer 6

Ho appena trovato una soluzione che non dipende dalla dimensione della griglia ed è probabilmente O (nlogn) (che è ottimale quando non ci sono collisioni) anche se peggio in O (n n logn) (quando tutto si scontra).

L'ho anche implementato e testato, ecco il link alla source . Ma non l'ho confrontato con la soluzione della forza bruta.

Una descrizione di come funziona:     (Sto cercando collisioni di rettangoli)

• sull'asse x Ordino i rettangoli secondo il loro bordo destro (O (nlogn))

• per ogni rettangolo nella lista ordinata prendo il bordo sinistro e faccio una ricerca binaria fino a trovare il bordo più a destra a sinistra del bordo sinistro e inserisco questi rettangoli tra questi indici in un set possibile_Collision_On_X_Axis (quelli sono n rettangoli, logn per la ricerca binaria, n inserisce il set in O (log n) per insert)

• sull'asse y faccio lo stesso

• in ciascuno dei set ora ho possibili collisioni su x (in un set) e su y (int nell'altro), interseco questi set e ora ho le collisioni sia sull'asse x che sull'asse y (ciò significa che prendo gli elementi comuni) (O (n))

scusa per la scarsa descrizione, spero che tu capisca meglio dalla fonte, anche un esempio illustrato qui: immagine

Answer 7

Potresti voler controllare cosa ha fatto Scott in Chipmunk con hashing spaziale . La fonte è disponibile gratuitamente. Penso che abbia usato una tecnica simile a Box-2D se non per la collisione, sicuramente per la persistenza del contatto.

Answer 8

Se lo spazio all'interno del quale si muovono gli oggetti è limitato, è possibile utilizzare una griglia per suddividere gli oggetti. Inserisci ogni oggetto in ogni cella della griglia coperta dall'oggetto (in tutto o in parte). Per verificare se l'oggetto A si scontra con qualsiasi altro oggetto, determinare quali celle della griglia sono coperte dall'oggetto A, quindi ottenere l'elenco di oggetti univoci in quelle celle e infine testare l'oggetto A su ciascun oggetto univoco. Questo approccio funziona meglio se la maggior parte degli oggetti è generalmente contenuta in una singola cella della griglia.

Se il tuo spazio non è limitato, dovrai implementare una sorta di griglia dinamica che può crescere su richiesta in ciascuna delle quattro direzioni (in 2D).

Il vantaggio di questo approccio rispetto a un algoritmo più adattivo (cioè BSP, Quadtree, Circletree) è che è possibile accedere alle celle nel tempo O (1) (cioè tempo costante) anziché nel tempo O (log N) (cioè tempo logaritmico ). Tuttavia, questi ultimi algoritmi sono in grado di adattarsi alla grande variabilità della densità degli oggetti. L'approccio alla griglia funziona meglio quando la densità degli oggetti è abbastanza costante nello spazio.

Answer 9

Vorrei raccomandare il riferimento introduttivo alla fisica dei giochi di Ian Millington, Game Physics Sviluppo del motore . Ha una grande sezione sul rilevamento di collisioni a fase larga con codice di esempio.

Answer 10

Ho usato un quad-albero in un progetto più ampio, il che è buono per gli oggetti di gioco che non si muovono molto (meno rimozioni e re-inserimenti). Lo stesso principio vale per le ocre.

L'idea di base è che crei una struttura ad albero ricorsiva, che memorizza 4 (per quad) oggetti o 8 (ott) oggetti figlio dello stesso tipo della radice dell'albero. Ogni nodo nella struttura rappresenta una sezione dello spazio cartesiano, ad esempio -100 - > +100 su ciascun asse applicabile. ogni figlio rappresenta lo stesso spazio, ma suddiviso per metà (un figlio immediato dell'esempio rappresenterebbe, ad esempio, -100- > 0 sull'asse X e -100- > 0 sull'asse Y).

Immagina un quadrato, o piano, con un determinato insieme di dimensioni. Ora traccia una linea attraverso il centro su ciascun asse, dividendo quel piano in 4 piani più piccoli. Ora prendine uno e fallo di nuovo, e ancora, fino a quando non raggiungi un punto in cui la dimensione del segmento piano è all'incirca la dimensione di un oggetto di gioco. Ora hai il tuo albero. Solo gli oggetti che occupano lo stesso piano possono eventualmente scontrarsi. Dopo aver determinato quali oggetti possono scontrarsi, si generano coppie di possibili collisioni da essi. A questo punto, la fase larga è completa e puoi passare al rilevamento di collisioni a fase stretta, che è dove sono i tuoi calcoli più precisi e costosi.

Lo scopo di Broadphase, è quello di utilizzare calcoli economici per generare possibili collisioni e eliminare i contatti che non possono , riducendo così il lavoro che l'algoritmo in fase stretta deve svolgere, a sua volta, facendo intero algoritmo di rilevamento delle collisioni più efficiente.

Quindi, prima di andare avanti e provare a implementare un tale algoritmo, come te:

Quanti oggetti ci sono nel mio gioco? Se ce ne sono molti, probabilmente ho bisogno di una fase larga. In caso contrario, la fase Nnarrow dovrebbe essere sufficiente. Inoltre, ho a che fare con molti oggetti in movimento?

Le strutture ad albero sono generalmente rallentate da oggetti in movimento, in quanto possono cambiare la loro posizione nel tempo semplicemente spostandosi. Ciò richiede che gli oggetti vengano rimossi e reinseriti in ciascun fotogramma (potenzialmente), che è inferiore a Ideale.

In questo caso, staresti meglio con Sweep e Prune, che mantiene cumuli min / max delle estensioni delle forme nel tuo mondo. Non è necessario reinserire gli oggetti, ma è necessario ricorrere ai cumuli per ogni fotogramma, ritenendo che questo sia generalmente più veloce di un albero, attraversato con rimozioni e reinserzioni.

A seconda della tua esperienza di codifica, uno potrebbe essere più complicato codificare su un altro. Personalmente ho trovato gli alberi più intuitivi da codificare, ma meno efficienti e più inclini all'errore, dal momento che sollevano altri problemi, come cosa fare se si dispone di un oggetto che si trova direttamente sopra un asse o al centro del nodo radice. Questo può essere risolto usando alberi sciolti, che hanno una certa sovrapposizione spaziale, in modo che un nodo figlio abbia sempre la priorità sugli altri quando si verifica un caso del genere.