Quad árboles / colisión basada en cuadrícula: poner la lógica en acción

En primer lugar, solo he estado escribiendo mi propia lógica de juego por un corto tiempo, así que me disculpo si esto puede parecer sencillo.

He estado leyendo mucho sobre los árboles cuádruples y la detección de colisiones basada en cuadrículas. Entiendo la lógica: básicamente, no verifique la colisión a menos que los objetos estén cerca básicamente. Pero nunca se menciona cómo realmente ejecutan esto.

Tengo un par de métodos posibles en mi cabeza pero no estoy seguro de cuál es el mejor

Prueba de colisión general: sin optimización

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

almacenar vecinos (método 1) Pero, ¿qué pasa si queremos optimizar las colisiones para verificar solo los objetos que están cerca? ¿Todavía corremos a través de todos los objetos, o creamos una matriz con objetos cercanos para verificar?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

recorrer todos los objetos pero solo verificar la colisión de los vecinos (método 3) La otra posibilidad es que todavía recorremos todo pero verificamos si los objetos están cerca antes de probar la colisión.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Almacenar objetos en datos de mosaico (método 3) Usar un sistema basado en mosaico permite otra opción; Almacene los objetos que están en un mosaico específico en los datos del mosaico en sí. Verifique en qué mosaico está el objeto. Los mosaicos circundantes contienen objetos con los que podría chocar:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Siempre trato de ver el mundo real como un ejemplo. Si quisiera comparar artículos con el mismo color, parecería ilógico verificar cada artículo completo, incluso si no coinciden con el color (Método 2, verifique cada artículo). Probablemente recolectaría los artículos con el mismo color (objetos que están cerca uno del otro) y los vería (método 1), en lugar de verificar todo.

Esta no es una comparación adecuada ya que los elementos en la verificación de colisión se mueven constantemente, por lo que el orden se confunde. Eso es lo que me confunde.

¿Sería más eficiente verificar cada elemento, eliminando así la tensión de seguir generando una serie de vecinos?

¿O es más eficiente encontrar vecinos para no tener que recorrer tantos objetos para verificar la colisión?

Seguir cambiando los datos en cada mosaico también parece muy intensivo, así que no estoy seguro de si es una buena idea.

He estado pensando en un juego de defensa de la torre donde la torre necesita detectar objetos si los objetos están dentro del alcance antes de dispararle. Y parece una tontería comprobar todos los elementos, mientras que en ocasiones no habrá ningún objeto cerca.

Pido disculpas por la larga publicación, siempre tengo problemas para explicarme.

Debe reducir el recuento de comprobaciones de colisión reales. Sí obvio, lo sé. Así que vamos a explicar esto:

Su primer algoritmo de comprobación de colisión sin ninguna optimización: ¿cuántas comprobaciones hará en una ejecución? Si n es el recuento de objetos, esto será alrededor de n * (n-1) comprobaciones. Para muchos objetos (> 100) esto será terriblemente lento.

Su método de verificación de vecinos no será mucho más rápido. Si sus objetos no son estáticos y se mueven mucho, necesitará crear esta lista de vecinos para cada objeto cada vez en su ciclo de juego. Esto es realmente peor que el primer algoritmo ya que está haciendo n * (n-1) para construir la lista de vecinos y luego verifica si cada objeto colisiona con uno de sus vecinos.

Necesitas particionar tu espacio de juego. Digamos que su espacio de juego es de 400x400 píxeles de ancho. Puede dividir esto en 4 subespacios cada uno de 200x200 de tamaño y verificar para cada objeto a cuál de los subespacios pertenece (un objeto puede estar dentro de más de un subespacio). Entonces solo necesitará verificar si los objetos en cada subespacio chocan con otro objeto en el mismo subespacio.

Por lo tanto, el costo de tiempo de ejecución será: n para construir la lista de 4 subespacios + (n / 4) * ((n-1) / 4) que es mucho mejor que el costo de tiempo de ejecución anterior. Esto se puede reducir aún más haciendo que los subespacios sean más pequeños (por ejemplo, 50x50).

Entonces nuestro algoritmo ahora se ve así:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Esto es algo similar a su idea de datos de mosaico. Pero los subespacios no necesitan ser del mismo tamaño que los mosaicos.

Podemos hacer un último paso para optimizar esto aún más usando un quadtree. Sea k el recuento de subespacios. Para construir las listas de objetos de espacios, estamos haciendo k * n verificaciones, lo que lleva a muchas verificaciones si su mundo de juego se hace grande.

Para reducir este costo, usamos un quadtree. Un quadtree es otra forma de particionar nuestro espacio de juego. En lugar de dividir nuestro espacio de 400x400 en 64 subespacios de 50x50 y verificar para cada objeto en cuál de los 64 subespacios que es actualmente, el espacio del juego se divide en 4 subespacios la mitad del tamaño del espacio del juego (200x200), que a su vez se dividen en subespacios más pequeños (100x100), que a su vez se dividen nuevamente en subespacios de 50x50. Este es nuestro quadtree.

Ahora, si queremos saber a qué subespacio de 50x50 pertenece un objeto, comprobamos a cuál de los subespacios de 200x200 pertenece. Luego vamos un nivel más profundo en nuestro quadtree y verificamos los 4 subespacios de 100x100 que están dentro del subespacio de 200x200 que acabamos de encontrar. Esto se repite hasta que sepamos a qué subespacio 50x50 pertenece el objeto. Entonces, ¿cuántos controles eran necesarios ahora? 4 para cada nivel del quadtree (recuerde que un objeto puede estar en el borde de dos subespacios). Por lo tanto, necesitamos verificaciones 4 * 3 para asignar un objeto al subespacio 50x50 correcto. Mucho mejor que 64 cheques.

Entonces, nuestro algoritmo quadtree necesita 4 * 3 * n verificaciones para construir las listas de subespacios y luego algo así como k * (n / k) verificaciones para verificar las colisiones de cada objeto.