Share
Muchos juegos requieren el uso de algoritmos de detección de colisiones para determinar cuándo dos objetos han chocado, pero estos algoritmos son a menudo operaciones costosas y pueden ralentizar mucho un juego. En este artículo, aprenderemos sobre quadtrees y cómo podemos usarlos para acelerar la detección de colisiones saltando pares de objetos que están demasiado separados para colisionar.
Nota: Aunque este tutorial está escrito con Java, debería poder usar las mismas técnicas y conceptos en casi cualquier entorno de desarrollo de juegos.
La detección de colisiones es una parte esencial de la mayoría de los videojuegos. Tanto en juegos en 2D como en 3D, detectar cuando dos objetos han chocado es importante, ya que una mala detección de colisiones puede llevar a algunos resultados muy interesantes:
Sin embargo, la detección de colisiones es también una operación muy costosa. Digamos que hay 100 objetos que necesitan ser revisados por colisión. La comparación de cada par de objetos requiere 10.000 operaciones, que son muchos controles!
Una forma de acelerar el proceso es reducir la cantidad de controles que deben realizarse. Dos objetos que se encuentran en los extremos opuestos de la pantalla no pueden colisionar, por lo que no hay necesidad de verificar una colisión entre ellos. Aquí es donde entra en juego un quadtree..
Un quadtree es una estructura de datos que se usa para dividir una región 2D en partes más manejables. Es un árbol binario extendido, pero en lugar de dos nodos secundarios tiene cuatro.
En las siguientes imágenes, cada imagen es una representación visual del espacio 2D y los cuadrados rojos representan objetos. A los efectos de este artículo, los subnodos se etiquetarán en sentido contrario a las agujas del reloj de la siguiente manera:
Un quadtree se inicia como un solo nodo. Los objetos agregados al quadtree se agregan al nodo único.
Cuando se agregan más objetos al quadtree, eventualmente se dividirá en cuatro subnodos. Cada objeto se colocará en uno de estos subnodos de acuerdo con su ubicación en el espacio 2D. Cualquier objeto que no pueda caber completamente dentro del límite de un nodo se colocará en el nodo principal.
Cada subnodo puede continuar subdividiendo a medida que se agregan más objetos.
Como puede ver, cada nodo solo contiene algunos objetos. Entonces sabemos que, por ejemplo, los objetos en el nodo superior izquierdo no pueden colisionar con los objetos en el nodo inferior derecho, por lo que no necesitamos ejecutar un algoritmo costoso de detección de colisiones entre dichos pares..
Eche un vistazo a este ejemplo de JavaScript para ver un quadtree en acción.
Implementar un quadtree es bastante simple. El siguiente código está escrito en Java, pero se pueden usar las mismas técnicas para la mayoría de los otros lenguajes de programación. Voy a comentar después de cada fragmento de código.
Comenzaremos creando la clase principal de Quadtree. A continuación se muestra el código de Quadtree.java.
clase pública Quadtree private int MAX_OBJECTS = 10; int privado MAX_LEVELS = 5; nivel de int privado; Lista privada de objetos; limites rectangulares privados; nodos privados de Quadtree []; / * * Constructor * / public Quadtree (int pLevel, Rectangle pBounds) level = pLevel; objetos = nueva ArrayList (); límites = pBounds; nodos = nuevo Quadtree [4];
los Quadtree la clase es sencilla. MAX_OBJECTS define cuántos objetos puede contener un nodo antes de que se divida y MAX_LEVELS define el subnodo de nivel más profundo. Nivel es el nivel de nodo actual (0 es el nodo más alto), límites representa el espacio 2D que ocupa el nodo, y nodos son los cuatro subnodos.
En este ejemplo, los objetos que contendrá el quadtree son Rectángulos, pero para tu propio quadtree puede ser lo que quieras.
A continuación, implementaremos los cinco métodos de un quadtree: claro, división, getIndex, insertar, y recuperar.
/ * * Borra el quadtree * / public void clear () objects.clear (); para (int i = 0; i < nodes.length; i++) if (nodes[i] != null) nodes[i].clear(); nodes[i] = null;
los claro el método borra el quadtree borrando recursivamente todos los objetos de todos los nodos.
/ * * Divide el nodo en 4 subnodos * / private void split () int subWidth = (int) (lines.getWidth () / 2); int subHeight = (int) (lines.getHeight () / 2); int x = (int) lines.getX (); int y = (int) lines.getY (); nodos [0] = nuevo Quadtree (nivel + 1, nuevo Rectángulo (x + subWidth, y, subWidth, subHeight)); nodos [1] = nuevo Quadtree (nivel + 1, nuevo Rectángulo (x, y, subWidth, subHeight)); nodos [2] = nuevo Quadtree (nivel + 1, nuevo Rectángulo (x, y + subHeight, subWidth, subHeight)); nodos [3] = nuevo Quadtree (nivel + 1, nuevo Rectángulo (x + subWidth, y + subHeight, subWidth, subHeight));
los división El método divide el nodo en cuatro subnodos al dividir el nodo en cuatro partes iguales e inicializar los cuatro subnodos con los nuevos límites.
/ * * Determine a qué nodo pertenece el objeto. -1 significa que * el objeto no puede caber completamente dentro de un nodo secundario y es parte * del nodo principal * / private int getIndex (Rectangle pRect) int index = -1; double verticalMidpoint = lines.getX () + (lines.getWidth () / 2); double horizontalMidpoint = lines.getY () + (lines.getHeight () / 2); // El objeto puede caber completamente dentro de los cuadrantes superiores boolean topQuadrant = (pRect.getY () < horizontalMidpoint && pRect.getY() + pRect.getHeight() < horizontalMidpoint); // Object can completely fit within the bottom quadrants boolean bottomQuadrant = (pRect.getY() > horizontalMidpoint); // El objeto puede caber completamente dentro de los cuadrantes izquierdos si (pRect.getX () < verticalMidpoint && pRect.getX() + pRect.getWidth() < verticalMidpoint) if (topQuadrant) index = 1; else if (bottomQuadrant) index = 2; // Object can completely fit within the right quadrants else if (pRect.getX() > verticalMidpoint) if (topQuadrant) index = 0; else if (bottomQuadrant) index = 3; índice de retorno;
los getIndex El método es una función auxiliar del quadtree. Determina a dónde pertenece un objeto en el quadtree al determinar en qué nodo puede encajar el objeto.
/ * * Insertar el objeto en el quadtree. Si el nodo * excede la capacidad, se dividirá y agregará todos los * objetos a sus nodos correspondientes. * / public void insert (Rectangle pRect) if (nodes [0]! = null) int index = getIndex (pRect); if (index! = -1) nodes [index] .insert (pRect); regreso; objects.add (pRect); if (objects.size ()> MAX_OBJECTS && level < MAX_LEVELS) if (nodes[0] == null) split(); int i = 0; while (i < objects.size()) int index = getIndex(objects.get(i)); if (index != -1) nodes[index].insert(objects.remove(i)); else i++;
los insertar El método es donde todo se junta. El método primero determina si el nodo tiene nodos secundarios e intenta agregar el objeto allí. Si no hay nodos secundarios o el objeto no encaja en un nodo secundario, agrega el objeto al nodo principal.
Una vez que se agrega el objeto, determina si el nodo debe dividirse al verificar si el número actual de objetos supera el máximo permitido. La división hará que el nodo inserte cualquier objeto que pueda caber en un nodo secundario para agregarlo al nodo secundario; de lo contrario el objeto permanecerá en el nodo padre.
/ * * Devuelve todos los objetos que podrían colisionar con el objeto dado * / public Recuperación de lista (List returnObjects, Rectangle pRect) int index = getIndex (pRect); if (index! = -1 && nodes [0]! = null) nodes [index] .retrieve (returnObjects, pRect); returnObjects.addAll (objetos); return returnObjects;
El método final del quadtree es el recuperar método. Devuelve todos los objetos en todos los nodos con los que el objeto dado podría colisionar. Este método es lo que ayuda a reducir el número de pares para verificar la colisión..
Ahora que tenemos un quadtree totalmente funcional, es hora de usarlo para ayudar a reducir los controles necesarios para la detección de colisiones.
En un juego típico, comenzarás creando el quadtree y pasando los límites de la pantalla.
Quadtree quad = new Quadtree (0, nuevo rectángulo (0,0,600,600));
En cada fotograma, insertará todos los objetos en el quadtree, primero limpiando el quadtree y luego utilizando el insertar método para cada objeto.
quad.clear (); para (int i = 0; i < allObjects.size(); i++) quad.insert(allObjects.get(i));
Una vez que se hayan insertado todos los objetos, irá a través de cada objeto y recuperará una lista de objetos con los que podría colisionar. Luego, verificará las colisiones entre cada objeto en la lista y el objeto inicial, usando un algoritmo de detección de colisión.
List returnObjects = new ArrayList (); para (int i = 0; i < allObjects.size(); i++) returnObjects.clear(); quad.retrieve(returnObjects, objects.get(i)); for (int x = 0; x < returnObjects.size(); x++) // Run collision detection algorithm between objects
Nota: Los algoritmos de detección de colisiones están fuera del alcance de este tutorial. Vea este artículo para un ejemplo.
La detección de colisiones puede ser una operación costosa y puede ralentizar el rendimiento de su juego. Los quadtrees son una forma en que puedes ayudar a acelerar la detección de colisiones y mantener tu juego funcionando a la máxima velocidad.
Artículos Relacionados
Accentsconagua