Repository navigation
Core Quadtree
Il Quadtree è una struttura di partizionamento spaziale. Serve a ridurre il numero di oggetti da esaminare quando si cerca ciò che si trova in una zona della scena.
Senza una struttura spaziale, una ricerca deve spesso controllare tutti gli oggetti. Con il quadtree si visitano principalmente i quadranti che intersecano l'area richiesta.
L'indice non è il contenitore principale degli oggetti: Scene mantiene il vettore usato per l'update, mentre GameScene consulta opzionalmente il quadtree per alcune query. Questo spiega perché objects() senza parametri restituisce comunque tutti gli oggetti, anche quando _useQuadtree è attivo.
Un quadtree organizza lo spazio in una gerarchia di regioni: la radice rappresenta l'intera area indicizzata e ogni nodo suddiviso ha quattro figli. La suddivisione può proseguire ricorsivamente, creando regioni più piccole solo dove serve. Una foglia è un nodo che non ha figli.
Nel core, il costruttore riceve il rettangolo della radice. Ogni suddivisione dimezza larghezza e altezza, producendo quattro rettangoli uguali: con l'asse y verso il basso, gli indici 0, 1, 2, 3 corrispondono a NO, NE, SO, SE. GameScene usa una radice più grande del rettangolo della scena, così da lasciare un margine attorno alla mappa.
Non tutti i quadtrees collocano gli oggetti allo stesso modo: alcuni indicizzano punti, altri regioni; gli oggetti possono essere conservati nelle foglie, anche nei nodi interni oppure replicati in più regioni. Le regole che seguono descrivono l'implementazione di questo repository.
La regola è: si scende in un figlio soltanto se contiene interamente il rettangolo dell'oggetto. Se nessun figlio lo contiene, l'oggetto resta nel nodo corrente. Questa politica condivide il principio di collocazione degli MX-CIF quadtrees; qui è abbinata a una soglia di suddivisione e a una profondità massima. Nel commento del codice è indicata come strict.
Figura 1 — A sinistra lo spazio, a destra l'albero corrispondente. Le lettere dentro i nodi indicano gli oggetti conservati in quei nodi.
Nell'esempio, A entra interamente nel quadrante NO e viene conservato nel relativo figlio. B attraversa il confine tra SO e SE: nessuno dei due figli lo contiene interamente, quindi rimane nel padre. Non viene duplicato nei quadranti che interseca.
Di conseguenza, anche i nodi interni possono contenere oggetti. Il nodo assegnato è il più profondo raggiungibile nella struttura esistente che contiene l'intero rettangolo: non si creano nuovi livelli per ogni oggetto piccolo, ma soltanto quando scatta la suddivisione.
add(obj) parte dalla radice e applica queste regole:
- Se il rettangolo dell'oggetto non è interamente contenuto nella radice, l'inserimento viene rifiutato.
- In una foglia, l'oggetto viene aggiunto se ci sono meno di 16 oggetti oppure se è già stata raggiunta la profondità massima.
- Se la foglia contiene già 16 oggetti e la profondità è inferiore a 8,
split()crea quattro figli e ridistribuisce gli oggetti esistenti secondo la regola del contenimento. Poi riprende l'inserimento del nuovo oggetto. - In un nodo interno, si scende nel figlio che contiene l'intero oggetto; altrimenti lo si conserva nel nodo corrente.
Figura 2 — È l'arrivo del 17° oggetto a far scattare lo split. In questo esempio i 16 oggetti precedenti entrano nei figli, mentre B attraversa più quadranti e resta nel padre.
I parametri correnti sono MAX_OBJECTS_PER_NODE = 16 e MAX_DEPTH = 8, con la radice a profondità 0. 16 è una soglia di suddivisione, non un limite assoluto di capienza: una foglia alla profondità massima può contenerne di più; anche un nodo interno può accumulare molti oggetti che attraversano i confini dei figli.
queryObjects(area) parte dalla radice. Per ogni nodo visitato:
- scarta l'intero ramo se la regione del nodo non interseca l'area;
- controlla gli oggetti conservati nel nodo corrente e aggiunge al risultato quelli il cui
rect()interseca l'area; - ripete la ricerca nei soli figli le cui regioni intersecano l'area.
Figura 3 — Il rettangolo tratteggiato è l'area richiesta; i rami sbiaditi sono esclusi dalla visita. Il risultato è B, anche se B è memorizzato nel padre e non nel figlio SO.
Questo esempio spiega perché non basta cercare nelle foglie: la query interseca una porzione di B, che va controllato mentre si visita il padre. A, invece, appartiene a un ramo escluso e non viene esaminato. Se l'area attraversa più quadranti, la ricerca prosegue in più rami.
La query restituisce intersezioni tra rettangoli di ingombro, non verifica la forma precisa degli oggetti. Ogni oggetto compare una sola volta, perché è memorizzato in un solo nodo. Il semplice contatto tra bordi non conta come intersezione per Rect::intersects().
queryIntersections() cerca le coppie di rettangoli che si intersecano. Confronta gli oggetti conservati nello stesso nodo, poi quelli del nodo con gli oggetti nei suoi discendenti, e ripete il procedimento nei figli.
Non occorre confrontare oggetti conservati in due rami fratelli: sono interamente contenuti in quadranti con interni disgiunti. Un oggetto che attraversa quei quadranti è invece rimasto in un antenato ed è incluso nei confronti con i discendenti. Anche questa proprietà deriva dalla regola del contenimento.
La GameScene mantiene sincronizzato il quadtree con la scena:
- quando nasce un oggetto, lo aggiunge;
- quando cambia rettangolo, lo aggiorna;
- quando viene eliminato, lo rimuove.
GameScene::newObject() inoltra l'oggetto alla scena e lo inserisce nell'indice se _useQuadtree è attivo. objectMoved() aggiorna l'indice, salvo per un oggetto già marcato killed; killObject() lo rimuove. L'indice viene costruito nel costruttore di GameScene con rect.scaleOnCenter(10): la radice è più grande della mappa nominale, ma non illimitata.
Per questo un oggetto deve cambiare posizione tramite setPos() o sostituire la geometria tramite setRect(): entrambi notificano la scena. Il setSize() della classe base modifica invece soltanto la dimensione; se una sottoclasse lo usa con il quadtree attivo deve anche garantire l'aggiornamento dell'indice, per esempio passando da setRect().
Il quadtree conserva riferimenti agli stessi oggetti della scena. Quando un oggetto si sposta, il suo rettangolo cambia già in memoria, ma la sua collocazione nell'albero deve essere aggiornata: lasciarlo nel vecchio ramo potrebbe renderlo invisibile alle query nella nuova posizione.
update(obj) usa una procedura semplice:
- trova il vecchio nodo tramite
_objectToNode, che associa l'ID dell'oggetto al nodo; - rimuove il riferimento dall'elenco del vecchio nodo e dalla mappa;
- richiama
add(obj)dalla radice, usando il nuovo rettangolo.
Per esempio, se A si sposta da NO a NE, viene rimosso da NO e reinserito in NE; se durante lo spostamento attraversa il confine, può essere reinserito nel padre. Se l'oggetto non era indicizzato, update() tenta direttamente di aggiungerlo.
Questa scelta riusa le regole di inserimento e non richiede di risalire dal vecchio nodo per cercare un antenato adatto. Non significa che risalire e scendere sia sempre meno efficiente: è una possibile ottimizzazione alternativa. L'implementazione corrente rimuove e reinserisce anche quando il nuovo rettangolo potrebbe restare nello stesso nodo.
La mappa evita di cercare il vecchio nodo visitando tutto il quadtree, ma è una std::map, non una tabella hash: la ricerca per ID è logaritmica; inoltre la rimozione cerca l'oggetto nel vettore del nodo. Il codice contiene anche tryMerge(), ma il percorso corrente di rimozione non la chiama: i nodi vuoti non vengono automaticamente riuniti.
queryObjects(rect) restituisce gli oggetti che intersecano un rettangolo. queryIntersections() produce invece le coppie di oggetti i cui rettangoli si intersecano.
Chiamata dalla GameScene
|
Con quadtree attivo | Senza quadtree |
|---|---|---|
objects(rect) |
queryObjects(rect) |
scansione del vettore |
objects(point) |
piccola query rettangolare, poi contains(point)
|
scansione con contains(point)
|
isEmpty(rect) |
query rettangolare vuota/non vuota | test sui singoli oggetti |
objects() |
vettore completo | vettore completo |
Il core usa queste operazioni per restringere il lavoro di:
- culling della vista;
- ricerca di oggetti in un punto o in un'area;
- generazione delle coppie candidate per le collisioni, se il progetto usa l'API relativa;
- logiche di gioco che devono interrogare una regione.
Il quadtree può svolgere la broad phase: seleziona candidati usando i rettangoli di ingombro. La narrow phase applica i test di collisione precisi alle forme dei candidati e resta responsabilità del gioco; anche la percorribilità delle celle è una regola del progetto.
queryIntersections() è disponibile sull'oggetto Quadtree, ma il core non la chiama automaticamente per risolvere le collisioni. Le sottoclassi di gioco possono usare objects(rect) per recuperare candidati e poi applicare i propri collider. In ActionRPG, per esempio, CollidableObject usa la query spaziale, mentre RPGGameScene::isEmpty() considera solo gli oggetti statici per la percorribilità.
Un oggetto viene indicizzato solo se il rettangolo della radice lo contiene interamente. Questa regola è importante per mappe con portali, stanze esterne o oggetti che possono uscire temporaneamente dai confini nominali.
La soluzione è definire il rettangolo del quadtree in modo che comprenda tutte le posizioni raggiungibili, eventualmente aggiungendo un margine. Un oggetto fuori dall'indice non può essere trovato dalle sue query; inoltre GameScene può eliminare automaticamente gli oggetti che escono dal rettangolo della scena, secondo autoKillWhenOutsideScene.
La regola di auto-eliminazione viene controllata quando un oggetto notifica uno spostamento ed esclude _player. Sono quindi due confini distinti: quello della scena, usato dall'opzione autoKillWhenOutsideScene, e quello più ampio della radice del quadtree, usato per l'indicizzazione. Un portale può portare il player fuori dalla mappa nominale senza eliminarlo, ma se lo porta fuori anche dalla radice l'indice non lo restituirà alle query, incluso il culling della View.
Il quadtree è utile quando la scena contiene molti oggetti distribuiti nello spazio e le ricerche sono locali. Per scene piccole o molto dense, il costo di manutenzione può superare il vantaggio.
Immaginiamo un albero equilibrato con 1.024 regioni finali e una ricerca che debba raggiungerne una sola. A ogni livello scegliamo un quadrante e scartiamo gli altri tre rami:
1.024 → 256 → 64 → 16 → 4 → 1: bastano 5 scelte.
Quadruplicando le regioni finali, da 1.024 a 4.096, aggiungiamo una sola scelta. È questa la crescita logaritmica: il numero di livelli cresce molto più lentamente del numero di regioni. Se anche gli oggetti sono distribuiti in modo equilibrato e ogni nodo richiede pochi controlli, una ricerca lungo un solo ramo può avere costo logaritmico nel numero di oggetti.
Una query rettangolare non ha però un costo logaritmico garantito: può attraversare molti rami, incontrare molti oggetti conservati nei padri oppure restituire gran parte della scena. Il lavoro dipende dai nodi visitati e dagli oggetti controllati; restituire k risultati richiede comunque di raccoglierli tutti. Nel caso sfavorevole si possono esaminare tutti gli oggetti. La profondità massima di 8 limita i livelli di questo core, ma non il numero di oggetti da controllare nei nodi.
L'opzione _useQuadtree di GameScene consente di confrontare facilmente i due comportamenti senza cambiare le logiche di gioco. Va attivata prima di creare gli oggetti: abilitarla quando la scena è già popolata non inserisce retroattivamente gli oggetti esistenti.
Il costo di una query dipende dalla distribuzione degli oggetti e dall'area interrogata; aggiornare molti oggetti mobili richiede invece rimozioni e reinserimenti. Per misurare il beneficio, confronta query e frame nelle stesse condizioni, includendo il costo degli update dell'indice. Il quadtree non rende ogni algoritmo più veloce per il solo fatto di essere acceso.
Il BFS non è implementato nel core: si trova in ActionRPG/Pathfinding.cpp. L'inizializzazione di quella griglia legge scene()->objects() senza filtro, quindi parte da tutti gli oggetti; le verifiche successive delle celle chiamano scene()->isEmpty(rect), che RPGGameScene implementa tramite il quadtree e un test sugli oggetti statici. L'indice può dunque aiutare le query di occupazione, non la visita BFS delle celle in sé. Tenere distinti questi passaggi evita di attribuire al quadtree un'accelerazione che non fornisce.
- Quadtree and Collision Detection — pvigier, con repository C++: descrive passo passo una strategia di contenimento con suddivisione a soglia, molto vicina a quella del core.
- MX-CIF quadtree — JTS: un'implementazione Java esplicitamente identificata come MX-CIF. Condivide il principio del contenimento, ma non tutti i dettagli dell'implementazione del core.
Prosegui con Servizi e risorse.