Estructura de datos espaciales para juegos

Question

Necesito implementar una estructura de datos espaciales para almacenar rectángulos y luego poder encontrar todos los rectángulos que se cruzan con un rectángulo dado. Esto se implementará en JavaScript.

Hasta ahora estoy desarrollando un Quad Tree para reducir el espacio de búsqueda, pero como es para un juego, todos los objetos que se muevan necesitarán actualizar su posición en el árbol. Volver al punto de partida.

¿Hay alguna estructura de datos o métodos para ayudar? Necesitará procesar alrededor de 10,000 objetos para que la fuerza bruta no sea lo suficientemente buena.

Answer 1

Una tabla hash funciona bastante bien como una prueba aproximada de intersección. Las tablas hash se utilizan como parte de un algoritmo más sofisticado para detectar colisiones en ODE.

Lógicamente, esta prueba divide el espacio en una cuadrícula regular. Cada celda de la grilla está etiquetada con una lista de objetos que se cruzan con esa celda. La grilla se inicializa al escanear todos los objetos. No sé javascript, entonces usaré el pseudocódigo python-ish.

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) 

Para encontrar colisiones con un objeto dado, mira hacia arriba cerca de colisiones en la tabla hash y luego aplicar una prueba de colisión exacta a cada uno.

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

Puede seguir utilizando árbol cuádruple aunque haya objetos en movimiento - acaba de quitar y volver a insertar un objeto cada vez que se mueve o cada vez que se cruza límite de región.

Pero los quadtrees no son muy buenos para almacenar rectángulos y yo recomendaría usar un R-tree en su lugar.