|
Il problema purtroppo non è tra quelli banalmente ottimizzabili.
Come hai ben intuito, si tratta di un'operazione intrinsecamente quadratica.
Esiste però un modo per ottimizzare il calcolo basandosi su una suddivisione in due fasi:
- Broad phase: determino una sottoregione dello spazio contenente il mio oggetto
- Narrow phase: eseguo la collision detection solo nella regione corrente.
Come funziona?
Bisogna inventarsi un modo di suddividere lo spazio, per semplificare ti illustro il metodo con alberi binari.
Mettiamo che il tuo mondo si estende in 2 dimensioni, con X compresa tra 1 e 128 e Y compresa tra 1 e 128 (sono potenze di 2 per semplificare i prossimi calcoli, in realtà puoi avere una scala arbitraria). Un oggetto avrà coordinate (x,y).
Costruisco un albero binario in questo modo:
- La foglia dell'albero è una List di oggetti vuota
- L'albero ha profondità 3
- Ogni nodo intermedio ha esattamente 2 figli
- Ogni nodo ha un numero costante che chiamo "discriminante"
- La discriminante di ogni livello è calcolata come il la media di due valori Min e Max
- La discriminante della radice è la media tra 1 e 128, cioè 64
- La discriminante del figlio a sinistra è la media tra 1 e 64 (32), la discriminante del figlio a destra è la media tra 65 e 128 (96)
- Procedi allo stesso modo per i figli di secondo livello
Riempio l'albero così:
- Prendo un oggetto dall'insieme
- Se x < discriminante del nodo corrente scelgo il nodo a sinistra, altrimenti a destra
- Attraverso tutto l'albero fino alla foglia
- Inserisco l'oggetto corrente nella lista della foglia ottenuta
Procedi così per tutti gli oggetti.
Alla fine dell'inserimento, avrai un certo numero di liste, ad esempio una lista che contiene tutti gli oggetti la cui X è compresa tra 1 e 16, una lista che comprende da 17 a 32, una che va da 33 a 48 e così via…
Quando vai a fare il test delle collisioni, puoi farlo esclusivamente una lista per volta, o al massimo puoi confrontare gli oggetti con quelli della lista corrente e delle due liste di fianco. In questo modo elimini una buona parte degli oggetti che sono sicuramente troppo lontani per collidere.
Quanto pesa tutto questo casino?
La costruzione di un albero costa O(N) dove N è il numero di nodi. L'aggiornamento di un oggetto all'interno dell'albero puoi farla solo quando la sua X esce dal range della sua lista, quindi non è detto che tu debba reinserire gli oggetti ad ogni update, ma puoi limitarti a reinserire solo gli oggetti che si sono spostati oltre il proprio range (prima devi toglierli dalla lista corrente, altrimenti hai dei simpatici bug con oggetti che si moltiplicano per magia).
La ricerca delle collisioni, considerando una sola lista (o un numero costante di liste ragionevolmente piccolo) costa O(log2 N). Tutto il processo, nel caso peggiore, costa N * log2 N, che è un pochino meglio del precedente N^2.
In realtà invece di un albero puoi semplicemente stabilire a priori un numero fissato di liste e fare gli inserimenti semplicemente confrontando i range, ma in questo modo avresti un numero di confronti (per inserire gli oggetti) che è O(N), perciò non avresti una ottimizzazione sostanziale rispetto a quella invece ottenibile con l'albero binario.
Se il numero di liste è piccolo (diciamo poche decine), potresti fare un trick con la manipolazione di bit e ottenere un boost prestazionale notevole, pari a O(1) per l'inserimento, ma non sarebbe un algoritmo scalabile per N oggetti e per mondi di dimensioni arbitrarie.
Per ulteriori ottimizzazioni, potresti considerare un albero 4-ario, cioè invece di avere il solo discriminante per la X, puoi aggiungere il discriminante anche per la Y e i rami dell'albero coprirebbero così una griglia bidimensionale.
In questo modo invece di Log2N hai Log4N che è parecchio più conveniente se hai tanti oggetti.
| 
