Controllare se due oggetti si toccano è veloce. Il problema nasce quando gli oggetti sono tanti. Con 10 oggetti le coppie possibili sono 45; con 100 diventano 4.950; con 1.000 quasi mezzo milione. In uno sparatutto pieno di proiettili o in una simulazione con molte particelle, confrontare tutto con tutto a ogni fotogramma diventa rapidamente insostenibile. La soluzione è dividere il lavoro in due fasi.
Broad phase e narrow phase
- La broad phase (fase ampia) scarta in modo economico le coppie che non possono collidere perché troppo lontane, producendo un elenco ridotto di coppie candidate.
- La narrow phase (fase stretta) applica il test preciso, per esempio AABB contro AABB o cerchio contro cerchio, solo a queste candidate.
Il numero di coppie cresce con il quadrato del numero di oggetti: n × (n − 1) / 2. Una buona broad phase riduce questo costo a qualcosa di molto più vicino a una crescita lineare, a patto che gli oggetti siano distribuiti nello spazio e non tutti ammassati nello stesso punto.
La griglia spaziale uniforme
È la tecnica più semplice ed è sorprendentemente efficace. Si divide il mondo in celle quadrate di dimensione fissa e si registra ogni oggetto nelle celle che occupa. Due oggetti possono collidere solo se condividono almeno una cella.
dimensione_cella = 64
per ogni oggetto o:
cx0 = floor(o.x / dimensione_cella)
cx1 = floor((o.x + o.larghezza) / dimensione_cella)
cy0 = floor(o.y / dimensione_cella)
cy1 = floor((o.y + o.altezza) / dimensione_cella)
per cx da cx0 a cx1, cy da cy0 a cy1:
griglia[cx, cy].aggiungi(o)
per ogni cella non vuota:
confronta tra loro gli oggetti nella cella
Scegliere la dimensione delle celle
La dimensione della cella è il parametro decisivo:
- celle troppo piccole: ogni oggetto occupa molte celle, aumentano inserimenti e duplicati;
- celle troppo grandi: troppi oggetti per cella, e si torna al confronto quasi completo.
Una regola pratica è usare celle grandi circa quanto l'oggetto tipico o un po' di più, per esempio una o due volte la dimensione dei nemici più comuni.
Evitare i controlli doppi
Un oggetto a cavallo di quattro celle verrebbe confrontato con lo stesso vicino fino a quattro volte. Si può memorizzare un insieme delle coppie già controllate in questo fotogramma, oppure confrontare una coppia solo nella cella che contiene, per esempio, l'angolo in alto a sinistra della loro intersezione.
Il quadtree
Il quadtree divide lo spazio in modo adattivo. Si parte da un nodo che copre tutto il mondo; quando contiene più di un certo numero di oggetti, viene suddiviso in quattro quadranti, e così via ricorsivamente fino a una profondità massima.
Il vantaggio rispetto alla griglia uniforme è l'adattamento alla densità: zone affollate vengono suddivise finemente, zone vuote restano un unico nodo grande. È utile quando gli oggetti hanno dimensioni molto diverse o si concentrano in poche aree della mappa.
Gli svantaggi sono la maggiore complessità e il costo di aggiornamento quando gli oggetti si muovono molto: spesso conviene ricostruire l'albero da zero a ogni fotogramma, cosa che con strutture ben scritte resta abbastanza rapida. Gli oggetti che stanno a cavallo dei confini tra quadranti vanno gestiti con attenzione, per esempio conservandoli nel nodo padre.
Sweep and prune
Questa tecnica sfrutta un'osservazione: due AABB possono sovrapporsi solo se si sovrappongono le loro proiezioni sull'asse x. Si ordinano gli oggetti in base al bordo sinistro e si scorre la lista mantenendo un insieme di oggetti «attivi»:
- si ordinano gli oggetti per
xminimo; - per ogni oggetto, si rimuovono dagli attivi quelli il cui
xmassimo è minore del suoxminimo; - i rimanenti attivi sono candidati e vanno verificati con il test completo;
- si aggiunge l'oggetto corrente agli attivi.
Poiché tra un fotogramma e l'altro gli oggetti si spostano poco, la lista è quasi già ordinata, e un ordinamento per inserimento la sistema in tempo molto breve. Funziona bene quando gli oggetti sono sparsi lungo l'asse scelto, come in uno sparatutto a scorrimento orizzontale.
Quale scegliere
| Tecnica | Ideale per | Punti deboli |
|---|---|---|
| Griglia uniforme | Oggetti di dimensioni simili, mappa limitata | Oggetti molto grandi o di taglie diverse |
| Quadtree | Densità molto variabile | Complessità, aggiornamento degli oggetti in movimento |
| Sweep and prune | Oggetti sparsi lungo un asse | Molti oggetti allineati sulla stessa x |
Per la maggior parte dei giochi 2D indipendenti una griglia uniforme ben dimensionata è la scelta migliore: semplice da scrivere, facile da verificare e veloce. I motori fisici professionali usano spesso strutture più raffinate, come alberi di volumi di contenimento dinamici, ma il principio è lo stesso.
Ulteriori ottimizzazioni utili
- Gruppi di collisione: i proiettili del giocatore non devono essere confrontati tra loro né con il giocatore stesso. Filtrare per categoria elimina molte coppie prima ancora della broad phase.
- Oggetti statici separati: muri e piattaforme non si muovono; si possono inserire in una struttura costruita una sola volta.
In sintesi
- Confrontare tutte le coppie ha un costo che cresce con il quadrato del numero di oggetti.
- La broad phase scarta rapidamente le coppie lontane, la narrow phase verifica quelle rimaste.
- La griglia uniforme è semplice ed efficace se le celle hanno la dimensione giusta.
- Quadtree e sweep and prune si adattano a distribuzioni particolari degli oggetti.
- Gruppi di collisione e strutture statiche riducono ancora il lavoro.
