Esta semana foi curta, na segunda e na terça-feira continuei a trabalhar em um sistema de iluminação 2D . Passei o resto do tempo na implementação de árvores quadtree.

Neste artigo, compartilharei minha implementação e pensamentos que surgiram no processo de seu design.

Primeiro, preciso dizer por que decidi implementar uma árvore quadrante.

Quadtree é uma estrutura de dados de partição espacial . Sua principal vantagem sobre outras estruturas de dados é sua adaptabilidade. Ele fornece bom desempenho ao inserir, excluir e pesquisar. Ou seja, podemos usar essa árvore em um contexto dinâmico em que os dados geralmente mudam. Além disso, essa estrutura é bastante fácil de entender e implementar.

Se o particionamento de espaço for um novo tópico para você, recomendo a leitura deste artigo de Robert Nistrom. Se você quiser aprender mais sobre árvores de quadrante, leia este ou este artigo.

Existem áreas no meu jogo nas quais o uso do quadtree compensa instantaneamente:

• Ao reconhecer colisões, a árvore do quadrante é muito mais eficiente que o método da força bruta (testando todos os pares). Mas essa não é a abordagem mais eficaz, uma visão geral de várias técnicas e referências pode ser estudada neste artigo . No entanto, para a primeira versão do meu mecanismo de física, eu o uso. Talvez mais tarde, se necessário, escolha um algoritmo mais especializado.
• No gráfico da cena, ao executar o recorte, posso usar o quadtree para procurar todos os nós visíveis.
• Em um sistema de iluminação, você pode usar o quadtree para encontrar paredes que cruzam o polígono de visibilidade da fonte de luz.
• No sistema de IA, você pode usar o quadtree para procurar todos os objetos ou inimigos que estão próximos da essência.
• E assim por diante ...

Como você pode ver, as árvores de quadrante são bastante versáteis. Eles serão uma boa reposição no seu kit de ferramentas.

Todo o código mostrado no artigo pode ser encontrado no GitHub .

Preparação preliminar

Antes de detalhar o código quadtree, precisamos de pequenas classes para primitivas geométricas: a classe Vector2 para definir pontos e a classe Box para definir retângulos. Ambos serão padronizados.

Vector2

A classe Vector2 minimalista. Ele contém apenas construtores, bem como operadores + e / . É tudo o que precisamos:

 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; } 

Box

A classe Box não é muito mais 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); } }; 

Ele contém alguns getters úteis.

O mais interessante é que ele contém o método contains, que verifica se o retângulo está dentro de outro, e o método de intersects , que verifica se o retângulo se cruza com o outro.

Usaremos os contains ao inserir e excluir e intersects ao reconhecer cruzamentos.

Quadtree

Aqui está o Quadtree classe 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 você pode ver, Quadtree é uma classe de modelo. Isso nos permitirá usar a classe para vários propósitos, dos quais falei no começo.

Opções de modelo:

• T : o tipo de valores que estarão contidos em quadtree. T deve ser uma classe fácil, porque será armazenada dentro de um quadtree. Idealmente, isso deve ser um ponteiro ou uma pequena estrutura de dados simples (POD).
• GetBox : o tipo do objeto chamado que receberá o valor na entrada e retornará um retângulo.
• Equal : o tipo do objeto chamado para verificar se dois valores são iguais. Por padrão, usamos o operador de igualdade padrão.
• Float : O tipo aritmético usado nos cálculos. Por padrão, usamos float .

No início da definição de classe, há três asserções estáticas para verificar a validade dos parâmetros do modelo.

Vamos dar uma olhada na definição de um nó. Um nó simplesmente armazena ponteiros para seus quatro nós filhos e uma lista dos valores contidos nele. Não armazenamos nela sua caixa delimitadora ou profundidade, elas serão calculadas em tempo real.

Conduzi benchmarks de ambas as abordagens (preservando um retângulo com profundidade e sem preservar) e não encontrei nenhuma degradação de desempenho ao calculá-las em tempo real. Além disso, economiza um pouco de memória.

Para poder distinguir um nó interno de uma planilha, o método isLeaf . Apenas verifica se o primeiro filho não é nulo. Como nulo são todos os nós filhos, ou nenhum deles, basta verificar apenas o primeiro.

Agora podemos ver as Quadtree membro Quadtree :

• mBox é uma caixa delimitadora global. Todos os valores inseridos no quadtree devem estar contidos nele.
• mRoot é a raiz do quadtree.
• mGetBox é o objeto chamado, que usaremos para obter o retângulo do valor.
• mEqual é o objeto chamado, que usaremos para verificar a igualdade dos dois valores.

O construtor simplesmente define mBox , mGetBox e mEqual e também cria um nó raiz.

Os dois últimos parâmetros sobre os quais ainda não falamos são Threshold e MaxDepth . Threshold é o número máximo de valores que um nó pode conter antes de dividi-lo. MaxDepth é a profundidade máxima de um nó, paramos de tentar dividir os nós que estão no MaxDepth , porque se você dividir demais, poderá prejudicar o desempenho. Eu dei a essas constantes valores razoáveis ​​adequados para a maioria dos casos. Você pode tentar otimizá-los para sua configuração.

Agora estamos prontos para iniciar operações mais interessantes.

Inserir e excluir

Antes de mostrar o código de inserção, precisamos discutir quais nós conterão os valores. Existem duas estratégias:

• Os valores são armazenados apenas em folhas. Como a caixa delimitadora de um valor pode interagir com várias folhas, o valor será armazenado em todas essas folhas.
• Os valores podem ser armazenados em todos os nós. Armazenamos o valor no menor nó que contém completamente sua caixa delimitadora.

Se os retângulos delimitadores forem pequenos e aproximadamente do mesmo tamanho, a primeira estratégia será mais eficaz ao procurar cruzamentos. No entanto, se existirem retângulos grandes, poderão ocorrer casos degenerados nos quais o desempenho será muito baixo. Por exemplo, se inserirmos um valor cujo retângulo esteja na caixa delimitadora global, ele será adicionado a todas as folhas. E se inserirmos um Threshold para esses valores, todos os nós serão divididos até que MaxDepth atingido e os valores não estejam em todas as folhas. Portanto, quadtree conterá $$$\ texttt {Threshold} \ times 4 ^ {\ texttt {MaxDepth}}$significados, e isso é ... muito.

Além disso, com a primeira estratégia, inserir e excluir será um pouco mais lento, porque temos que inserir (ou excluir) todos os nós que cruzam o valor.

Portanto, usarei a segunda estratégia, na qual não há casos degenerados. Como pretendo usar o quadtree em vários contextos, será mais conveniente. Além disso, essa estratégia é mais adequada para contextos dinâmicos nos quais muitas inserções e exclusões são realizadas para atualizar valores, por exemplo, em um mecanismo físico para o qual as entidades são movidas.

Para descobrir em qual nó inseriremos ou excluiremos um valor, usaremos duas funções auxiliares.

O primeiro, computeBox , calcula o retângulo do nó filho pelo retângulo do nó pai e o índice do seu quadrante.

 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>(); } } 

O segundo, getQuadrant , retorna o quadrante em que o valor está localizado:

 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; } 

Retorna -1 se não estiver contido em nenhum dos quadrantes.

Agora estamos prontos para considerar os métodos de inserção e exclusão.

Inserir

O método add simplesmente chama um método auxiliar privado:

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

Aqui está o código do 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); } } 

No início, existem algumas suposições que confirmam que não estamos fazendo nada ilógico, por exemplo, não estamos inserindo um valor em um nó que não contém sua caixa delimitadora.

Então, se o nó for uma planilha, e podemos inserir um novo valor nele, ou seja, não atingimos MaxDepth ou Threshold , execute a inserção. Caso contrário, compartilhamos esse nó e tentamos novamente.

Se o nó for interno, calcularemos o quadrante que contém a caixa delimitadora do valor. Se estiver completamente contido no nó filho, fazemos uma chamada recursiva. Caso contrário, insira neste nó.

Aqui está o procedimento de separação:

 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); } 

Criamos quatro nós filhos e, para cada valor do nó pai, decidimos em qual nó (filho ou pai) o valor deve ser armazenado.

Excluir

O método remove também simplesmente chama um método auxiliar:

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

Aqui está o código do método auxiliar, é muito semelhante ao código de inserção:

 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); } } 

Se o nó atual for uma planilha, removeremos o valor da lista de valores do nó atual
e tente mesclar esse nó com os nós irmãos e seu pai. Caso contrário, determinamos em qual quadrante a caixa delimitadora do valor está localizada. Se estiver completamente contido no nó filho, faremos uma chamada recursiva. Caso contrário, exclua dos valores do nó atual.

Como não nos importamos com a ordem dos valores armazenados no nó, quando apago, uso um pouco de otimização: apenas altero o valor apagado pelo último e o apago:

 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(); } 

Também precisamos dar uma olhada no 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 se todos os nós filhos são abandonados e se o número total de seus valores e os valores dos nós filhos é menor que o limite. Nesse caso, copiamos todos os valores dos nós filhos para o nó atual e excluímos os nós filhos.

Pesquisa de interseção

Interseção com retângulo

Finalmente, chegamos ao mais interessante: a busca de cruzamentos. A primeira maneira de usá-lo é obter todos os valores que cruzam um determinado retângulo. Por exemplo, isso é necessário para executar o recorte.

Isso será query :

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

Nesse método, simplesmente selecionamos std::vector , que conterá os valores que cruzam a caixa delimitadora e chamamos o 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); } } } 

Primeiro, adicionamos todos os valores armazenados no nó atual que se cruzam com o retângulo solicitado. Então, se o nó atual for interno, fazemos uma chamada recursiva para cada nó filho cujo retângulo delimitador se cruza com o retângulo solicitado.

Todas as interseções aos pares

O segundo caso de uso suportado é procurar todos os pares de valores armazenados na árvore do quadrante que se cruzam. Isso é especialmente útil ao criar um mecanismo físico. Esse problema pode ser resolvido usando o método de query . E, de fato, podemos chamar query na caixa delimitadora de todos os valores. No entanto, isso pode ser feito de forma mais eficiente, adicionando apenas uma interseção para um par (com a query , vamos encontrá-los duas vezes).

Para perceber isso, precisamos considerar que a interseção só pode ocorrer

• entre dois valores armazenados em um nó

ou

• entre o valor armazenado no nó e outro valor armazenado no descendente desse nó.

Por esse motivo, devemos verificar apenas a interseção entre:

• valor e os seguintes valores armazenados no mesmo nó

e

• valor e valores armazenados no descendente.

Portanto, definitivamente não reportaremos a mesma interseção duas vezes.

Aqui está o 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; } 

Novamente, simplesmente alocamos std::vector para armazenar as interseções e chamar a função helper:

 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); } } 

No primeiro estágio, as interseções entre os valores armazenados no nó atual são verificadas. Em seguida, se o nó atual for interno, findIntersectionInDescendants verificará as interseções entre os valores armazenados nesse nó e os valores armazenados em seus descendentes. Finalmente, fazemos chamadas recursivas.

findIntersectionsInDescendants localiza recursivamente interseções entre o valor fornecido e todos os valores armazenados na subárvore:

 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); } } 

Isso é tudo! Repito, todo o código é publicado no GitHub .

Recursos úteis

Se você quiser saber mais sobre o reconhecimento de colisões e estruturas de dados de particionamento, recomendo a leitura do livro de Christer Erickson Detecção de colisões em tempo real . Muitos tópicos são profundamente revelados e, ao mesmo tempo, o livro é escrito em uma linguagem muito compreensível. Além disso, os capítulos podem ser lidos separadamente. Esta é uma ótima fonte de referência.

Conclusão

Isso conclui o trabalho com reconhecimento de colisão. No entanto, é apenas metade do mecanismo físico. A segunda metade é a resolução de colisões .