Struttura dati spaziali per i giochi

Question

Ho bisogno di implementare una struttura di dati spaziali per archiviare i rettangoli e quindi essere in grado di trovare tutti i rettangoli che intersecano un determinato rettangolo. Questo sarà implementato in JavaScript.

Finora sto sviluppando un Quad Tree per abbattere lo spazio di ricerca ma poiché è per un gioco, tutti gli oggetti che si spostano dovranno aggiornare la sua posizione nell'albero. Torna al punto di partenza.

Esistono strutture dati o metodi per aiutare? Dovrà elaborare circa 10.000 oggetti, quindi la forza bruta non è abbastanza buona.

Answer 1

Una tabella hash funziona abbastanza bene come un test di intersezione approssimativo. Le tabelle hash vengono utilizzate come parte di un algoritmo più sofisticato per rilevare le collisioni in ODE.

Logicamente, questo test divide lo spazio in una griglia regolare. Ogni cella della griglia è etichettata con un elenco di oggetti che intersecano quella cella. La griglia viene inizializzata mediante la scansione di tutti gli oggetti. Non so javascript, quindi userò python-ish pseudocode.

for each ob in objects: 
    for each x in [floor(ob.x_min/grid_size) .. floor(ob.x_max/grid_size)]: 
    for each y in [floor(ob.y_min/grid_size) .. floor(ob.y_max/grid_size)]: 
     hashtable[hash(x, y)].append(ob) 

Per trovare collisione con un dato oggetto, guardare in alto vicino-collisioni nella tabella hash e poi applicare un test esatto di collisione a ciascuno.

near_collisions = [] 
for each x in [floor(ob.x_min/grid_size) .. floor(ob.x_max/grid_size)]: 
    for each y in [floor(ob.y_min/grid_size) .. floor(ob.y_max/grid_size)]: 
    near_collisions = near_collisions ++ hashtable[hash(x, y)] 

remove duplicates from near_collisions 

for each ob2 in near_collisions: 
    if exact_collision_test(ob, ob2): 
    do_something 

Answer 2

È comunque possibile utilizzare quadtree anche se avete oggetti in movimento - è sufficiente rimuovere e reinserire un oggetto ogni volta che si muove o ogni volta che attraversa regione di confine.

Ma i quadrifogli non sono molto buoni per la memorizzazione di rettangoli e suggerirei invece di utilizzare un R-tree.