Alternativas de partición espacial 2D a hashes espaciales y cuadrúpedos

11

He estado tratando de implementar un algoritmo de partición espacial en mi juego, pero tanto los hashes espaciales como los quadtrees no son lo que estoy buscando.

Se supone que el tamaño de mi nivel no tiene un límite (solo límites Int32). Necesito un algoritmo de partición espacial que no necesite un "Nivel de ancho" y un "Nivel de altura".

Tengo muchos objetos físicos en movimiento. Necesito que el algoritmo sea lo suficientemente rápido como para admitir más de 500 objetos.

Alguna alternativa?

c# collision-detection physics tree Vittorio Romeo
fuente

Respuestas:

13

Árbol dinámico

Box2D es un motor bien optimizado diseñado por un programador experimentado de física / juegos . Originalmente, Box2D utilizaba una cuadrícula hash que requería una altura y un ancho fijos.

Cuando Erin actualizó a un mejor algoritmo de fase ancha, eligió el btDbvt de Nathanael Presson. Esta es la fase ancha utilizada por Bullet Physics. Erin modificó y optimizó el algoritmo para 2d.

Puede leer una descripción general de nivel súper alto en el manual de Box2D (§4.11, o buscar Dynamic Tree).

Aquí hay una excepción de la documentación del código (que es muy bueno considerando que no es parte de la API pública).

Un árbol dinámico AABB de fase amplia, inspirado en el btDbvt de Nathanael Presson. Un árbol dinámico organiza los datos en un árbol binario para acelerar las consultas, como las consultas de volumen y las emisiones de rayos. Las hojas son representantes con un AABB. En el árbol, expandimos el proxy AABB por b2_fatAABBFactor para que el proxy AABB sea más grande que el objeto del cliente. Esto permite que el objeto del cliente se mueva en pequeñas cantidades sin activar una actualización de árbol.

Los nodos se agrupan y se pueden reubicar, por lo que utilizamos índices de nodos en lugar de punteros.

Mi comprensión del algoritmo del árbol dinámico es esto. El árbol dinámico es el cruce entre un árbol binario avl clásico y un árbol cuádruple . El efecto final es un árbol cuádruple que solo divide cada nodo por la mitad, y la línea de división no es fija (las dos mitades no tienen el mismo tamaño que un árbol cuádruple). AVL entra porque el cuadrante con divisiones dinámicas puede degenerar esencialmente a una lista (O (n) velocidad de búsqueda). El AVL se utiliza para reequilibrar los subárboles para garantizar la velocidad de búsqueda de O lg (N).

Lo mejor de todo es que el código es MIT, así que siéntase libre de copiar / derivado / robar descaradamente / etc.

código_deft
fuente
¡Parece ... complejo! Sin embargo, lo echaré un vistazo. Alguien me sugirió usar la técnica "barrer y podar" o "ordenar y barrer", pero no pude encontrar nada sobre una implementación de C # o .NET. Encontré un ejemplo de c ++ pero es confuso y no funcionó (intenté implementarlo de todos modos). ¿Crees que SAP sería más fácil de implementar? ¿Hay implementación de .NET?
Vittorio Romeo
8

Esto está muy cerca de una pregunta similar que se hace aquí en Gamedev, pero dado que le preocupa el rendimiento y no el almacenamiento de archivos, tal vez mi respuesta allí sea más útil para usted. Incluiré la mayor parte aquí para completar, pero la respuesta original proporciona un poco más de profundidad si desea analizarlo.

Me encontré con un problema similar y decidí crear mi propia estructura para manejar los datos. Se basa libremente en un quadtree, pero tiene una capacidad de expansión infinita (al menos tan grande como una Int) en todas las direcciones. Fue diseñado para manejar datos basados ​​en cuadrículas que se expandieron desde un punto central, al igual que Minecraft ahora. Es espacio eficiente en memoria, y muy rápido.

Mi código se puede encontrar aquí . El código está completo, probado (pruebas de unidad y carga) y bastante optimizado. Sin embargo, el funcionamiento interno aún no está muy bien documentado, pero todos los métodos públicos sí lo están, por lo que deberían ser utilizables. Si alguien decide probarlo, no dude en ponerse en contacto conmigo si tiene preguntas o comentarios.

dlras2
fuente
1

Cuando trabajo con un número relativamente pequeño (<varios miles) de objetos pequeños (la mayoría de los objetos no son lo suficientemente grandes como para colisionar potencialmente con muchos otros objetos), encuentro que una simple lista ordenada en x de cajas de delimitación axialmente alineadas (AABB) funciona muy bien. Simplemente pongo los objetos en una lista, luego cada cuadro después de mover los objetos, clasifico rápidamente la lista por valor de x, luego hago una pasada a través de la lista para verificar la proximidad de AABB. Para cada objeto, lo comparo con los objetos que están delante de él en la lista hasta que llegue al final de la lista o un objeto que está fuera del rango x; es decir, el valor x del borde izquierdo es> valor x del borde derecho del objeto que se está probando. Básicamente, divide dinámicamente el espacio en cortes a veces superpuestos, de tamaño AABB-x de ancho. Eso'

Shavais
fuente
0

Quizás el algoritmo r-tree es lo que estás buscando.

Funciono realmente bien para la geometría estática, pero también puedes usarla para mover objetos eliminando y agregando objetos en sus nuevas posiciones.

Holgazanear
fuente
Intenté una implementación de C #, y el rendimiento fue demasiado malo al "quitar y agregar objetos en su nueva posición".
Vittorio Romeo