QuadTree per rilevamento collisione 2D

Question

Attualmente sto lavorando a un tipo di gioco 2D di ripresa e sto utilizzando un albero quad per i rilevamenti delle collisioni. Ho scritto un quad tree funzionante che spinge correttamente i miei attori nei nodi/foglie a cui appartengono nell'albero. Tuttavia, ho alcuni problemi.

In primo luogo, in che modo utilizzo il mio quadrifoglio per selezionare contro quali altri oggetti un oggetto deve verificare le collisioni? Non sono sicuro di come sia fatto.

Che fa sorgere una seconda domanda. Diciamo che ho un oggetto nel nodo che non è un vicino di un altro nodo, ma che l'oggetto è abbastanza grande da occupare un numero limitato di nodi, come posso verificare una collisione effettiva, dal momento che immagino che l'albero potrebbe considerare che non è abbastanza vicino da scontrarsi con oggetti in un nodo "lontano"? Gli oggetti che non si adattano completamente a un nodo dovrebbero essere mantenuti nel nodo genitore?

Nel mio gioco, la maggior parte degli oggetti sono di dimensioni diverse e si spostano.

Ho letto un buon numero di blog/articoli su quadtrees ma la maggior parte spiega solo come costruire un albero che non è proprio quello che sto cercando.

Qualsiasi aiuto/informazione è benvenuto.

Answer 1

È possibile stabilire una convenzione per cui ogni elemento è contenuto nel nodo quadtree più piccolo che lo contiene completamente.

Poi, quando si controlla le collisioni per il nodo A, si procede in questo modo:

1. nodo corrente = radice nodo
2. collisioni controlla di A con ciascun elemento direttamente nel nodo corrente
3. se A lattina essere contenuto interamente in uno dei sotto-nodi del nodo corrente, impostare il nodo corrente su quel sub-nodo e passare nuovamente a 2
4. infine, controllare le collisioni di A con tutti gli elementi nei nodi figli del nodo corrente, in modo ricorsivo .

Si noti che più piccoli sono gli oggetti, più profondi saranno situati nel quad, quindi saranno confrontati meno spesso.