Evita la complessità O (n^2) per il rilevamento delle collisioni

Question

Sto sviluppando un semplice gioco 2D basato su tile. Ho un livello, popolato da oggetti che possono interagire con le tessere e tra loro. Controllare la collisione con la tilemap è piuttosto semplice e può essere fatto per tutti gli oggetti con una complessità lineare. Ma ora devo rilevare la collisione tra gli oggetti e ora devo controllare ogni oggetto contro ogni altro oggetto, il che risulta in una complessità quadrata.

Vorrei evitare la complessità quadrata. Esistono metodi noti per ridurre le chiamate di rilevamento delle collisioni tra gli oggetti. Ci sono strutture dati (come ad esempio albero BSP), che sono facilmente mantenute e permettono di rifiutare molte collisioni alla volta.

Ad esempio, il numero totale di oggetti nel livello è di circa 500, circa 50 di loro sono visti sullo schermo alla volta ...

Grazie!

Answer 1

Perché non lasciare che le tessere memorizzino informazioni sugli oggetti che le occupano. Quindi le collisioni possono essere rilevate ogni volta che un oggetto viene spostato in una nuova tessera, osservando se tale tessera contiene già un altro oggetto.

Questo non costerebbe praticamente nulla.

Answer 2

È possibile utilizzare quadrilatero per dividere lo spazio e ridurre il numero di oggetti che è necessario controllare per la collisione.

See this article - Quadtree demonstration.

And perhaps this - Collision Detection in Two Dimensions.

Or this - Quadtree (source included)

Può sembrare - a prima vista - che ci vuole un sacco di potenza della CPU per mantenere l'albero, ma riduce anche il numero di controlli in modo significativo (vedere la dimostrazione nel primo link).

Answer 3

Il tuo gioco ha già il concetto di una mappa del gioco correlata al gameplay. È possibile cooptare questa mappa del til per il rilevamento delle collisioni o sovrapporre una griglia secondaria sul campo di gioco utilizzata specificamente per il rilevamento dello sprite e il rilevamento delle collisioni.

All'interno della griglia, ogni sprite occupa una o più tessere. Lo sprite sa quali tessere occupa e le tessere sanno quali folletti lo occupano. Quando uno sprite si muove, devi solo controllare le collisioni all'interno delle tessere che occupa lo sprite. Ciò significa che non è necessario alcun rilevamento di collisione, a meno che gli sprites non siano abbastanza vicini da occupare le stesse tessere, e anche in questo caso, è sufficiente controllare le collisioni tra gli sprite che sono vicini tra loro.

Se il tuo gameplay è tale che gli sprite si raggruppano spesso, potresti voler implementare la tua griglia come un quadruplo per consentire a ogni tessera di essere suddivisa ed evitare che troppi sprite occupino la stessa tessera della griglia.

Inoltre, a seconda dell'implementazione, potrebbe essere necessario utilizzare un riquadro di delimitazione leggermente più grande per determinare l'occupazione della piastrella rispetto a quella utilizzata per determinare le collisioni. In questo modo ti verrà garantito che gli sprite si sovrappongano e occupino la stessa tessera prima che i loro limiti di collisione tocchino.