Esta semana fue corta, los lunes y martes seguí trabajando en un sistema de iluminación 2D . El resto del tiempo lo pasé en la implementación de árboles quadtree.

En este artículo compartiré mi implementación y pensamientos que surgieron en el proceso de su diseño.

Primero, necesito decir por qué decidí implementar un árbol de cuadrante.

Quadtree es una estructura de datos de partición espacial . Su principal ventaja sobre otras estructuras de datos es su adaptabilidad. Proporciona un buen rendimiento al insertar, eliminar y buscar. Es decir, podemos usar este árbol en un contexto dinámico donde los datos a menudo cambian. Además, esta estructura es bastante fácil de entender e implementar.

Si la partición del espacio es un tema nuevo para usted, le recomiendo leer este artículo de Robert Nistrom. Si desea obtener más información sobre los árboles de cuadrantes, lea este o este artículo.

Hay áreas en mi juego en las que el uso de quadtree vale la pena al instante:

• Al reconocer las colisiones, el árbol del cuadrante es mucho más eficiente que el método de fuerza bruta (prueba de todos los pares). Pero este no es el enfoque más efectivo, en este artículo se puede estudiar una descripción general de varias técnicas y puntos de referencia. Sin embargo, para la primera versión de mi motor de física, lo uso. Quizás más tarde, si es necesario, elegiré un algoritmo más especializado.
• En el gráfico de escena, al realizar el recorte, puedo usar quadtree para buscar todos los nodos visibles.
• En un sistema de iluminación, puede usar quadtree para encontrar paredes que crucen el polígono de visibilidad de la fuente de luz.
• En el sistema de IA, puedes usar quadtree para buscar todos los objetos o enemigos que estén cerca de la esencia.
• Y así sucesivamente ...

Como puede ver, los árboles cuadrantes son bastante versátiles. Serán una buena reposición en su kit de herramientas.

Todo el código que se muestra en el artículo se puede encontrar en GitHub .

Preparación preliminar

Antes de detallar el código quadtree, necesitamos clases pequeñas para primitivas geométricas: la clase Vector2 para definir puntos y la clase Box para definir rectángulos. Ambos serán repetitivos.

Vector2

La clase Vector2 minimalista. Contiene solo constructores, así como operadores + y / . Eso es todo lo que necesitamos:

 template<typename T> class Vector2 { public: T x; T y; constexpr Vector2<T>(TX = 0, TY = 0) noexcept : x(X), y(Y) { } constexpr Vector2<T>& operator+=(const Vector2<T>& other) noexcept { x += other.x; y += other.y; return *this; } constexpr Vector2<T>& operator/=(T t) noexcept { x /= t; y /= t; return *this; } }; template<typename T> constexpr Vector2<T> operator+(Vector2<T> lhs, const Vector2<T>& rhs) noexcept { lhs += rhs; return lhs; } template<typename T> constexpr Vector2<T> operator/(Vector2<T> vec, T t) noexcept { vec /= t; return vec; } 

Caja

La clase Box no es mucho más complicada:

 template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : left(Left), top(Top), width(Width), height(Height) { } constexpr Box(const Vector2<T>& position, const Vector2<T>& size) noexcept : left(position.x), top(position.y), width(size.x), height(size.y) { } constexpr T getRight() const noexcept { return left + width; } constexpr T getBottom() const noexcept { return top + height; } constexpr Vector2<T> getTopLeft() const noexcept { return Vector2<T>(left, top); } constexpr Vector2<T> getCenter() const noexcept { return Vector2<T>(left + width / 2, top + height / 2); } constexpr Vector2<T> getSize() const noexcept { return Vector2<T>(width, height); } constexpr bool contains(const Box<T>& box) const noexcept { return left <= box.left && box.getRight() <= getRight() && top <= box.top && box.getBottom() <= getBottom(); } constexpr bool intersects(const Box<T>& box) const noexcept { return !(left >= box.getRight() || getRight() <= box.left || top >= box.getBottom() || getBottom() <= box.top); } }; 

Contiene algunos captadores útiles.

Lo que es más interesante es que contiene el método contiene, que verifica si el rectángulo está dentro de otro, y el método de intersects , que verifica si el rectángulo se cruza con otro.

Usaremos contains cuando inserte y elimine, e intersects al reconocer intersecciones.

Quadtree

Aquí está el Quadtree clase Quadtree :

 template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { static_assert(std::is_convertible_v<std::invoke_result_t<GetBox, const T&>, Box<Float>>, "GetBox must be a callable of signature Box<Float>(const T&)"); static_assert(std::is_convertible_v<std::invoke_result_t<Equal, const T&, const T&>, bool>, "Equal must be a callable of signature bool(const T&, const T&)"); static_assert(std::is_arithmetic_v<Float>); public: Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(), const Equal& equal = Equal()) : mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal) { } private: static constexpr auto Threshold = std::size_t(16); static constexpr auto MaxDepth = std::size_t(8); struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; }; Box<Float> mBox; std::unique_ptr<Node> mRoot; GetBox mGetBox; Equal mEqual; bool isLeaf(const Node* node) const { return !static_cast<bool>(node->children[0]); } }; 

Como puede ver, Quadtree es una clase de plantilla. Esto nos permitirá usar la clase para varios propósitos, de los que hablé al principio.

Opciones de plantilla:

• T : el tipo de valores que se incluirán en quadtree. T debería ser una clase fácil, ya que se almacenará dentro de un quadtree. Idealmente, esto debería ser un puntero o una pequeña estructura de datos simple (POD).
• GetBox : el tipo del objeto llamado que recibirá el valor en la entrada y devolverá un rectángulo.
• Equal : tipo del objeto llamado para verificar si dos valores son iguales. Por defecto, usamos el operador de igualdad estándar.
• Float : el tipo aritmético utilizado en los cálculos. Por defecto, usamos float .

Al comienzo de la definición de clase, hay tres aserciones estáticas para verificar la validez de los parámetros de la plantilla.

Echemos un vistazo a la definición de un nodo. Un nodo simplemente almacena punteros en sus cuatro nodos secundarios y una lista de los valores contenidos en él. No almacenamos en él su caja delimitadora o su profundidad, se calcularán sobre la marcha.

Realicé puntos de referencia de ambos enfoques (preservar un rectángulo con profundidad y sin preservar) y no encontré ninguna degradación del rendimiento al calcularlos sobre la marcha. Además, ahorra un poco de memoria.

Para poder distinguir un nodo interno de una hoja, isLeaf método isLeaf . Simplemente verifica que el primer hijo no sea nulo. Dado que nulo son todos los nodos secundarios, o ninguno de ellos, es suficiente verificar solo el primero.

Ahora podemos ver las Quadtree miembro de Quadtree :

• mBox es un cuadro delimitador global. Todos los valores insertados en quadtree deben estar contenidos dentro de él.
• mRoot es la raíz de quadtree.
• mGetBox es el objeto llamado, que usaremos para obtener el rectángulo del valor.
• mEqual es el objeto llamado, que usaremos para verificar la igualdad de los dos valores.

El constructor simplemente establece mBox , mGetBox y mEqual , y también crea un nodo raíz.

Los dos últimos parámetros de los que aún no hemos hablado son Threshold y MaxDepth . Threshold es el número máximo de valores que puede contener un nodo antes de dividirlo. MaxDepth es la profundidad máxima del nodo, dejamos de intentar dividir los nodos que están en MaxDepth , porque si divide demasiado, puede obstaculizar el rendimiento. Le di a estas constantes valores razonables adecuados para la mayoría de los casos. Puede intentar optimizarlos para su configuración.

Ahora estamos listos para comenzar operaciones más interesantes.

Insertar y eliminar

Antes de mostrar el código de inserción, debemos analizar qué nodos contendrán los valores. Hay dos estrategias:

• Los valores se almacenan solo en hojas. Como el cuadro delimitador de un valor puede interactuar con varias hojas, el valor se almacenará en todas estas hojas.
• Los valores se pueden almacenar en todos los nodos. Almacenamos el valor en el nodo más pequeño que contiene completamente su cuadro delimitador.

Si los rectángulos delimitadores son pequeños y aproximadamente del mismo tamaño, entonces la primera estrategia es más efectiva cuando se buscan intersecciones. Sin embargo, si existen rectángulos grandes, pueden ocurrir casos degenerados en los que el rendimiento será muy pobre. Por ejemplo, si insertamos un valor cuyo rectángulo está en el cuadro delimitador global, se agregará a todas las hojas. Y si insertamos un Threshold para tales valores, todos los nodos se dividirán hasta que MaxDepth alcance MaxDepth y los valores no estén en todas las hojas. Por lo tanto, quadtree contendrá $$$\ texttt {Umbral} \ veces 4 ^ {\ texttt {MaxDepth}}$significados, y eso es ... mucho.

Además, con la primera estrategia, la inserción y eliminación será un poco más lenta, ya que tenemos que insertar (o eliminar) todos los nodos que intersecan el valor.

Por lo tanto, usaré la segunda estrategia, en la que no hay casos degenerados. Como planeo usar quadtree en varios contextos, será más conveniente. Además, esta estrategia es más adecuada para contextos dinámicos en los que se realizan muchas inserciones y eliminaciones para actualizar valores, por ejemplo, en un motor físico donde se mueven las entidades.

Para averiguar en qué nodo insertaremos o eliminaremos un valor, utilizaremos dos funciones auxiliares.

El primero, computeBox , calcula el rectángulo del nodo secundario mediante el rectángulo del nodo primario y el índice de su cuadrante.

 Box<Float> computeBox(const Box<Float>& box, int i) const { auto origin = box.getTopLeft(); auto childSize = box.getSize() / static_cast<Float>(2); switch (i) { // North West case 0: return Box<Float>(origin, childSize); // Norst East case 1: return Box<Float>(Vector2<Float>(origin.x + childSize.x, origin.y), childSize); // South West case 2: return Box<Float>(Vector2<Float>(origin.x, origin.y + childSize.y), childSize); // South East case 3: return Box<Float>(origin + childSize, childSize); default: assert(false && "Invalid child index"); return Box<Float>(); } } 

El segundo, getQuadrant , devuelve el cuadrante en el que se encuentra el valor:

 int getQuadrant(const Box<Float>& nodeBox, const Box<Float>& valueBox) const { auto center = nodeBox.getCenter(); // West if (valueBox.getRight() < center.x) { // North West if (valueBox.getBottom() < center.y) return 0; // South West else if (valueBox.top >= center.y) return 2; // Not contained in any quadrant else return -1; } // East else if (valueBox.left >= center.x) { // North East if (valueBox.getBottom() < center.y) return 1; // South East else if (valueBox.top >= center.y) return 3; // Not contained in any quadrant else return -1; } // Not contained in any quadrant else return -1; } 

Devuelve -1 si no está contenido en ninguno de los cuadrantes.

Ahora estamos listos para considerar los métodos de inserción y eliminación.

Insertar

El método add simplemente llama a un método auxiliar privado:

 void add(const T& value) { add(mRoot.get(), 0, mBox, value); } 

Aquí está el código del método auxiliar:

 void add(Node* node, std::size_t depth, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Insert the value in this node if possible if (depth >= MaxDepth || node->values.size() < Threshold) node->values.push_back(value); // Otherwise, we split and we try again else { split(node, box); add(node, depth, box, value); } } else { auto i = getQuadrant(box, mGetBox(value)); // Add the value in a child if the value is entirely contained in it if (i != -1) add(node->children[static_cast<std::size_t>(i)].get(), depth + 1, computeBox(box, i), value); // Otherwise, we add the value in the current node else node->values.push_back(value); } } 

Al principio hay un par de suposiciones que verifican que no estamos haciendo nada ilógico, por ejemplo, no estamos insertando un valor en un nodo que no contiene su cuadro delimitador.

Luego, si el nodo es una hoja, y podemos insertar un nuevo valor en él, es decir no hemos alcanzado MaxDepth o Threshold , realice la inserción. De lo contrario, compartimos este nodo e intentamos nuevamente.

Si el nodo es interno, calculamos el cuadrante que contiene el cuadro delimitador del valor. Si está completamente contenido en el nodo hijo, hacemos una llamada recursiva. De lo contrario, inserte en este nodo.

Aquí está el procedimiento de separación:

 void split(Node* node, const Box<Float>& box) { assert(node != nullptr); assert(isLeaf(node) && "Only leaves can be split"); // Create children for (auto& child : node->children) child = std::make_unique<Node>(); // Assign values to children auto newValues = std::vector<T>(); // New values for this node for (const auto& value : node->values) { auto i = getQuadrant(box, mGetBox(value)); if (i != -1) node->children[static_cast<std::size_t>(i)]->values.push_back(value); else newValues.push_back(value); } node->values = std::move(newValues); } 

Creamos cuatro nodos secundarios, y luego para cada valor del nodo primario, decidimos en qué nodo (secundario o primario) se debe almacenar el valor.

Eliminar

El método remove también simplemente llama a un método auxiliar:

 void remove(const T& value) { remove(mRoot.get(), nullptr, mBox, value); } 

Aquí está el código del método auxiliar, es muy similar al código de inserción:

 void remove(Node* node, Node* parent, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Remove the value from node removeValue(node, value); // Try to merge the parent if (parent != nullptr) tryMerge(parent); } else { // Remove the value in a child if the value is entirely contained in it auto i = getQuadrant(box, mGetBox(value)); if (i != -1) remove(node->children[static_cast<std::size_t>(i)].get(), node, computeBox(box, i), value); // Otherwise, we remove the value from the current node else removeValue(node, value); } } 

Si el nodo actual es una hoja, entonces eliminamos el valor de la lista de valores del nodo actual
e intente fusionar este nodo con los nodos hermanos y su padre. De lo contrario, determinamos en qué cuadrante se ubica el cuadro delimitador del valor. Si está completamente contenido en el nodo hijo, entonces hacemos una llamada recursiva. De lo contrario, elimine de los valores del nodo actual.

Como no nos importa el orden de los valores almacenados en el nodo, cuando borro, uso una pequeña optimización: simplemente cambio el valor borrado con el último y lo borro:

 void removeValue(Node* node, const T& value) { // Find the value in node->values auto it = std::find_if(std::begin(node->values), std::end(node->values), [this, &value](const auto& rhs){ return mEqual(value, rhs); }); assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); // Swap with the last element and pop back *it = std::move(node->values.back()); node->values.pop_back(); } 

También tenemos que echar un vistazo a tryMerge :

 void tryMerge(Node* node) { assert(node != nullptr); assert(!isLeaf(node) && "Only interior nodes can be merged"); auto nbValues = node->values.size(); for (const auto& child : node->children) { if (!isLeaf(child.get())) return; nbValues += child->values.size(); } if (nbValues <= Threshold) { node->values.reserve(nbValues); // Merge the values of all the children for (const auto& child : node->children) { for (const auto& value : child->values) node->values.push_back(value); } // Remove the children for (auto& child : node->children) child.reset(); } } 

tryMerge verifica que todos los nodos secundarios son hojas y que el número total de sus valores y los valores de los nodos secundarios es inferior al umbral. Si es así, copiamos todos los valores de los nodos secundarios al nodo actual y eliminamos los nodos secundarios.

Búsqueda de intersección

Intersección con rectángulo

Finalmente, llegamos a lo más interesante: a la búsqueda de intersecciones. La primera forma de usarlo es hacer que todos los valores se crucen con un rectángulo dado. Por ejemplo, esto es necesario para realizar el recorte.

Esto se query :

 std::vector<T> query(const Box<Float>& box) const { auto values = std::vector<T>(); query(mRoot.get(), mBox, box, values); return values; } 

En este método, simplemente seleccionamos std::vector , que contendrá los valores que intersecan el cuadro delimitador, y llamaremos al método auxiliar:

 void query(Node* node, const Box<Float>& box, const Box<Float>& queryBox, std::vector<T>& values) const { assert(node != nullptr); assert(queryBox.intersects(box)); for (const auto& value : node->values) { if (queryBox.intersects(mGetBox(value))) values.push_back(value); } if (!isLeaf(node)) { for (auto i = std::size_t(0); i < node->children.size(); ++i) { auto childBox = computeBox(box, static_cast<int>(i)); if (queryBox.intersects(childBox)) query(node->children[i].get(), childBox, queryBox, values); } } } 

Primero, sumamos todos los valores almacenados en el nodo actual que se cruzan con el rectángulo solicitado. Luego, si el nodo actual es interno, hacemos una llamada recursiva para cada nodo secundario cuyo rectángulo delimitador se cruza con el rectángulo solicitado.

Todas las intersecciones por pares

El segundo caso de uso admitido es buscar todos los pares de valores almacenados en el árbol de cuadrante que se cruzan. Esto es especialmente útil al crear un motor físico. Este problema se puede resolver utilizando el método de query . Y, de hecho, podemos llamar a la query en el cuadro delimitador de todos los valores. Sin embargo, esto se puede hacer de manera más eficiente agregando solo una intersección para un par (con la query los encontraremos dos veces).

Para darnos cuenta de esto, debemos considerar que la intersección solo puede ocurrir

• entre dos valores almacenados en un nodo

o

• entre el valor almacenado en el nodo y otro valor almacenado en el descendiente de este nodo.

Debido a esto, necesitamos verificar solo la intersección entre:

• valor y los siguientes valores almacenados en el mismo nodo

y

• valor y valores almacenados en el descendiente.

Por lo tanto, definitivamente no informaremos la misma intersección dos veces.

Aquí está el código findAllIntersections :

 std::vector<std::pair<T, T>> findAllIntersections() const { auto intersections = std::vector<std::pair<T, T>>(); findAllIntersections(mRoot.get(), intersections); return intersections; } 

Nuevamente, simplemente asignamos std::vector para almacenar las intersecciones y llamar a la función auxiliar:

 void findAllIntersections(Node* node, std::vector<std::pair<T, T>>& intersections) const { // Find intersections between values stored in this node // Make sure to not report the same intersection twice for (auto i = std::size_t(0); i < node->values.size(); ++i) { for (auto j = std::size_t(0); j < i; ++j) { if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) intersections.emplace_back(node->values[i], node->values[j]); } } if (!isLeaf(node)) { // Values in this node can intersect values in descendants for (const auto& child : node->children) { for (const auto& value : node->values) findIntersectionsInDescendants(child.get(), value, intersections); } // Find intersections in children for (const auto& child : node->children) findAllIntersections(child.get(), intersections); } } 

En la primera etapa, se verifican las intersecciones entre los valores almacenados en el nodo actual. Luego, si el nodo actual es interno, findIntersectionInDescendants busca intersecciones entre los valores almacenados en este nodo y los valores almacenados en sus descendientes. Finalmente, hacemos llamadas recursivas.

findIntersectionsInDescendants busca recursivamente intersecciones entre el valor dado y todos los valores almacenados en el subárbol:

 void findIntersectionsInDescendants(Node* node, const T& value, std::vector<std::pair<T, T>>& intersections) const { // Test against the values stored in this node for (const auto& other : node->values) { if (mGetBox(value).intersects(mGetBox(other))) intersections.emplace_back(value, other); } // Test against values stored into descendants of this node if (!isLeaf(node)) { for (const auto& child : node->children) findIntersectionsInDescendants(child.get(), value, intersections); } } 

Eso es todo! Repito, todo el código está publicado en GitHub .

Recursos utiles

Si desea obtener más información sobre el reconocimiento de colisiones y las estructuras de datos de partición, le recomiendo leer el libro de Christer Erickson Real-Time Collision Detection . Muchos temas se revelan profundamente y al mismo tiempo el libro está escrito en un lenguaje muy comprensible. Además, los capítulos se pueden leer por separado. Esta es una gran fuente de referencia.

Conclusión

Esto completa el trabajo con reconocimiento de colisión. Sin embargo, es solo la mitad del motor físico. La segunda mitad es la resolución de colisiones .