Эффективная (и хорошо объясненная) реализация Quadtree для обнаружения 2D-столкновений

1. Эффективные деревья квадрантов

Ладно, я попробую. Сначала тизер, чтобы показать результаты того, что я предложу с участием 20 000 агентов (просто то, что я очень быстро придумал для этого конкретного вопроса):

GIF имеет чрезвычайно низкую частоту кадров и значительно более низкое разрешение, чтобы соответствовать максимальному размеру 2 МБ для этого сайта. Вот видео, если вы хотите увидеть это на полной скорости: https://streamable.com/3pgmn .

И GIF со 100 КБ, хотя мне пришлось так много возиться с ним, и мне пришлось отключить линии quadtree (похоже, не хотел так сильно сжимать с ними), а также изменить способ, которым агенты выглядели, чтобы получить его помещается в 2 мегабайта (хотелось бы, чтобы создание GIF было таким же простым, как кодирование дерева квадрантов):

Симуляция с 20 000 агентов занимает ~3 мегабайта оперативной памяти. Я также могу легко обрабатывать 100 000 агентов меньшего размера, не жертвуя частотой кадров, хотя это приводит к некоторому беспорядку на экране до такой степени, что вы едва можете видеть, что происходит, как на GIF выше. Все это выполняется в одном потоке на моем i7, и я трачу почти половину времени, согласно VTune, просто рисуя эти вещи на экране (просто используя некоторые базовые скалярные инструкции для построения объектов по одному пикселю за раз в ЦП).

А вот видео со 100 000 агентов, хотя трудно понять, что происходит. Это довольно большое видео, и я не смог найти приличного способа сжать его, чтобы все видео не превратилось в кашу (возможно, сначала потребуется загрузить или кэшировать его, чтобы увидеть, как оно транслируется с разумной частотой кадров). С 100 тыс. агентов симуляция занимает около 4,5 мегабайт ОЗУ, и использование памяти очень стабильно после запуска симуляции в течение примерно 5 секунд (перестает увеличиваться или уменьшаться, поскольку перестает выделяться куча). То же самое в замедленной съемке.

Эффективное дерево квадрантов для обнаружения столкновений

Итак, на самом деле деревья квадрантов не являются моей любимой структурой данных для этой цели. Я предпочитаю иерархическую сетку, например грубую сетку для мира, более мелкую сетку для региона и еще более тонкую сетку для субрегиона (3 фиксированных уровня плотных сеток и без участия деревьев), со строками. на основе оптимизации, так что строка, в которой нет сущностей, будет освобождена и превращена в нулевой указатель, а также полностью пустые области или подобласти превращены в нули. Хотя эта простая реализация дерева квадрантов, работающего в одном потоке, может обрабатывать 100 000 агентов на моем i7 со скоростью 60+ кадров в секунду, я реализовал сети, которые могут обрабатывать пару миллионов агентов, отскакивающих друг от друга в каждом кадре, на более старом оборудовании (i3). Также мне всегда нравилось, как с помощью сеток очень легко предсказать, сколько памяти им потребуется, поскольку они не подразделяют ячейки. Но я попытаюсь рассказать, как реализовать достаточно эффективное дерево квадрантов.

Обратите внимание, что я не буду вдаваться в полную теорию структуры данных. Я предполагаю, что вы уже это знаете и заинтересованы в повышении производительности. Я также просто расскажу о своем личном способе решения этой проблемы, который, кажется, превосходит большинство решений, которые я нахожу в Интернете для своих случаев, но есть много достойных способов, и эти решения адаптированы к моим случаям использования (очень большие входные данные со всем, что движется в каждом кадре для визуальных эффектов в фильмах и на телевидении). Другие люди, вероятно, оптимизируют для других вариантов использования. Когда речь идет, в частности, о структурах пространственного индексирования, я действительно думаю, что эффективность решения говорит вам больше о разработчике, чем о структуре данных. Кроме того, те же стратегии, которые я предлагаю для ускорения работы, также применимы в трехмерном пространстве с октодеревьями.

Представление узла

Итак, прежде всего, давайте рассмотрим представление узла:

// Represents a node in the quadtree.
struct QuadNode
{
    // Points to the first child if this node is a branch or the first
    // element if this node is a leaf.
    int32_t first_child;

    // Stores the number of elements in the leaf or -1 if it this node is
    // not a leaf.
    int32_t count;
};

Всего 8 байт, и это очень важно, так как это ключевая часть скорости. На самом деле я использую меньший (6 байт на узел), но я оставлю это читателю в качестве упражнения.

Вы, вероятно, можете обойтись без count. Я включаю это для патологических случаев, чтобы избежать линейного обхода элементов и подсчета их каждый раз, когда конечный узел может разделиться. В большинстве случаев узел не должен хранить столько элементов. Тем не менее, я работаю с визуальными эффектами, и патологические случаи не обязательно редки. Вы можете столкнуться с художниками, создающими контент с кучей совпадающих точек, массивными полигонами, охватывающими всю сцену, и т. д., поэтому в итоге я сохраняю файл count.

Где AABB?

Таким образом, одна из первых вещей, которые могут возникнуть у людей, — это расположение ограничивающих рамок (прямоугольников) для узлов. Я их не храню. Я вычисляю их на лету. Я немного удивлен, что большинство людей не делают этого в коде, который я видел. Для меня они хранятся только с древовидной структурой (в основном только один AABB для корня).

Может показаться, что вычислять их на лету будет дороже, но сокращение использования памяти узлом может пропорционально уменьшить промахи кэша при обходе дерева, и эти сокращения промахов кэша, как правило, более значительны, чем необходимость сделать пару битовых сдвигов и некоторые добавления/вычитания во время обхода. Обход выглядит так:

static QuadNodeList find_leaves(const Quadtree& tree, const QuadNodeData& root, const int rect[4])
{
    QuadNodeList leaves, to_process;
    to_process.push_back(root);
    while (to_process.size() > 0)
    {
        const QuadNodeData nd = to_process.pop_back();

        // If this node is a leaf, insert it to the list.
        if (tree.nodes[nd.index].count != -1)
            leaves.push_back(nd);
        else
        {
            // Otherwise push the children that intersect the rectangle.
            const int mx = nd.crect[0], my = nd.crect[1];
            const int hx = nd.crect[2] >> 1, hy = nd.crect[3] >> 1;
            const int fc = tree.nodes[nd.index].first_child;
            const int l = mx-hx, t = my-hx, r = mx+hx, b = my+hy;

            if (rect[1] <= my)
            {
                if (rect[0] <= mx)
                    to_process.push_back(child_data(l,t, hx, hy, fc+0, nd.depth+1));
                if (rect[2] > mx)
                    to_process.push_back(child_data(r,t, hx, hy, fc+1, nd.depth+1));
            }
            if (rect[3] > my)
            {
                if (rect[0] <= mx)
                    to_process.push_back(child_data(l,b, hx, hy, fc+2, nd.depth+1));
                if (rect[2] > mx)
                    to_process.push_back(child_data(r,b, hx, hy, fc+3, nd.depth+1));
            }
        }
    }
    return leaves;
}

Исключение AABB — одна из самых необычных вещей, которые я делаю (я продолжаю искать других людей, которые делают это только для того, чтобы найти равного и потерпеть неудачу), но я измерил до и после, и это действительно значительно сократило время, по крайней мере, на очень большие входные данные, чтобы существенно сжать узел дерева квадрантов и просто вычислять AABB на лету во время обхода. Пространство и время не всегда диаметрально противоположны. Иногда сокращение пространства также означает сокращение времени, учитывая, насколько в наши дни производительность зависит от иерархии памяти. Я даже ускорил некоторые операции реального мира, применяемые к массивным входным данным, сжимая данные в четыре раза по сравнению с используемой памятью и распаковывая их на лету.

Я не знаю, почему многие люди предпочитают кэшировать AABB: будь то удобство программирования или действительно быстрее в их случаях. Тем не менее, для структур данных, которые равномерно разделены по центру, таких как обычные деревья квадрантов и октодеревьев, я бы предложил измерять влияние исключения AABB и вычислять их на лету. Вы можете быть весьма удивлены. Конечно, имеет смысл хранить AABB для структур, которые не разделяются равномерно, например Kd-деревья и BVH, а также свободные деревья квадрантов.

Плавающая точка

Я не использую числа с плавающей запятой для пространственных индексов, и, возможно, поэтому я вижу улучшенную производительность, просто вычисляя AABB на лету со сдвигом вправо для деления на 2 и так далее. Тем не менее, по крайней мере, SPFP кажется очень быстрым в наши дни. Не знаю, так как не измерял разницу. Я просто предпочитаю использовать целые числа, хотя обычно работаю с входными данными с плавающей запятой (вершины сетки, частицы и т. д.). Я просто конвертирую их в целочисленные координаты для разделения и выполнения пространственных запросов. Я не уверен, есть ли какое-то серьезное преимущество в скорости. Это просто привычка и предпочтение, так как мне легче рассуждать о целых числах, не думая о денормализованной FP и тому подобном.

Центрированные AABB

Хотя я сохраняю ограничивающую рамку только для корня, полезно использовать представление, в котором хранится центр и половинный размер для узлов, а для запросов используется представление слева/сверху/справа/снизу, чтобы свести к минимуму объем арифметических операций.

Смежные дочерние элементы

Это также ключ, и если мы вернемся к представлению узла:

struct QuadNode
{
    int32_t first_child;
    ...
};

Нам не нужно хранить массив дочерних элементов, потому что все 4 дочерних элемента непрерывны:

first_child+0 = index to 1st child (TL)
first_child+1 = index to 2nd child (TR)
first_child+2 = index to 3nd child (BL)
first_child+3 = index to 4th child (BR)

Это не только значительно уменьшает промахи в кеше при обходе, но также позволяет нам значительно уменьшить наши узлы, что еще больше уменьшает промахи в кеше, сохраняя только один 32-битный индекс (4 байта) вместо массива из 4 (16 байт).

Это означает, что если вам нужно передать элементы только в пару квадрантов родителя при его разделении, он все равно должен выделить все 4 дочерних листа для хранения элементов только в двух квадрантах, имея при этом два пустых листа в качестве дочерних. Тем не менее, компромисс более чем оправдан с точки зрения производительности, по крайней мере, в моих случаях использования, и помните, что узел занимает всего 8 байт, учитывая, насколько мы его сжали.

При освобождении потомков мы освобождаем все четыре одновременно. Я делаю это в постоянное время, используя индексированный свободный список, например:

За исключением того, что мы объединяем фрагменты памяти, содержащие 4 смежных элемента, а не по одному. Это делает так, что нам обычно не нужно задействовать какие-либо выделения или освобождения кучи во время моделирования. Группа из 4 узлов помечается как освобожденная неделимо только для того, чтобы затем быть неделимо возвращена в последующем разделении другого конечного узла.

Отложенная очистка

Я не обновляю структуру дерева квадрантов сразу после удаления элементов. Когда я удаляю элемент, я просто спускаюсь по дереву к дочернему узлу (узлам), который он занимает, а затем удаляю элемент, но я пока не беспокоюсь о том, чтобы делать что-то еще, даже если листья становятся пустыми.

Вместо этого я делаю отложенную очистку следующим образом:

void Quadtree::cleanup()
{
    // Only process the root if it's not a leaf.
    SmallList<int> to_process;
    if (nodes[0].count == -1)
        to_process.push_back(0);

    while (to_process.size() > 0)
    {
        const int node_index = to_process.pop_back();
        QuadNode& node = nodes[node_index];

        // Loop through the children.
        int num_empty_leaves = 0;
        for (int j=0; j < 4; ++j)
        {
            const int child_index = node.first_child + j;
            const QuadNode& child = nodes[child_index];

            // Increment empty leaf count if the child is an empty 
            // leaf. Otherwise if the child is a branch, add it to
            // the stack to be processed in the next iteration.
            if (child.count == 0)
                ++num_empty_leaves;
            else if (child.count == -1)
                to_process.push_back(child_index);
        }

        // If all the children were empty leaves, remove them and 
        // make this node the new empty leaf.
        if (num_empty_leaves == 4)
        {
            // Push all 4 children to the free list.
            nodes[node.first_child].first_child = free_node;
            free_node = node.first_child;

            // Make this node the new empty leaf.
            node.first_child = -1;
            node.count = 0;
        }
    }
}

Это вызывается в конце каждого кадра после перемещения всех агентов. Причина, по которой я выполняю такое отложенное удаление пустых листовых узлов в несколько итераций, а не сразу в процессе удаления одного элемента, заключается в том, что элемент A может переместиться в узел N2, сделав N1 пустым. Однако элемент B может в том же кадре переместиться в N1, снова сделав его занятым.

С отложенной очисткой мы можем справиться с такими случаями без ненужного удаления дочерних элементов только для того, чтобы добавить их обратно, когда другой элемент перемещается в этот квадрант.

Перемещение элементов в моем случае является простым: 1) удалить элемент, 2) переместить его, 3) повторно вставить его в дерево квадрантов. После того, как мы переместим все элементы и в конце кадра (не временного шага, может быть несколько временных шагов в каждом кадре), функция cleanup выше вызывается для удаления дочерних элементов из родителя, который имеет 4 пустых листа в качестве дочерних, которые эффективно превращает этот родитель в новый пустой лист, который затем может быть очищен в следующем кадре с последующим вызовом cleanup (или нет, если в него что-то вставлено или если братья и сестры пустого листа не пусты).

Давайте посмотрим на отложенную очистку визуально:

Начиная с этого, скажем, мы удаляем некоторые элементы из дерева, оставляя нам 4 пустых листа:

В этот момент, если мы вызовем cleanup, он удалит 4 листа, если найдет 4 пустых дочерних листа, и превратит родителя в пустой лист, например:

Допустим, мы удалим еще несколько элементов:

... а затем снова вызовите cleanup:

Если мы вызовем его еще раз, то получим следующее:

... в этот момент сам корень превращается в пустой лист. Однако метод очистки никогда не удаляет корень (он удаляет только дочерние элементы). Опять же, основной смысл делать это отложенным таким образом и в несколько шагов состоит в том, чтобы уменьшить количество потенциальной избыточной работы, которая может выполняться за один временной шаг (которых может быть много), если бы мы делали все это немедленно каждый раз, когда элемент удаляется из дерево. Это также помогает распределить работу по кадрам, чтобы избежать заиканий.

TBH, я изначально применил эту технику отложенной очистки в игре для DOS, которую написал на C из-за чистой лени! Я не хотел возиться со спуском вниз по дереву, удалением элементов, а затем удалением узлов снизу вверх, потому что изначально я написал дерево для обхода сверху вниз (а не сверху вниз и снова вверх) и действительно думал, что это ленивое решение было компромиссом производительности (жертвование оптимальной производительности для более быстрого внедрения). Однако, много лет спустя, я на самом деле дошел до реализации удаления дерева квадрантов таким образом, что сразу начал удалять узлы, и, к моему удивлению, я фактически значительно замедлил его с более непредсказуемой и прерывистой частотой кадров. Отложенная очистка, несмотря на то, что изначально была вдохновлена ​​моей программистской ленью, на самом деле (и случайно) оказалась очень эффективной оптимизацией для динамических сцен.

Односвязные индексные списки для элементов

Для элементов я использую это представление:

// Represents an element in the quadtree.
struct QuadElt
{
    // Stores the ID for the element (can be used to
    // refer to external data).
    int id;

    // Stores the rectangle for the element.
    int x1, y1, x2, y2;
};

// Represents an element node in the quadtree.
struct QuadEltNode
{
    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    int next;

    // Stores the element index.
    int element;
};

Я использую узел элемента, который отделен от элемента. Элемент вставляется в дерево квадрантов только один раз, независимо от того, сколько ячеек он занимает. Однако для каждой ячейки, которую он занимает, вставляется узел элемента, который индексирует этот элемент.

Узел элемента представляет собой односвязный узел списка индексов в массиве, а также использует метод свободного списка, описанный выше. Это влечет за собой еще несколько промахов кеша из-за непрерывного хранения всех элементов листа. Однако, учитывая, что это дерево квадрантов предназначено для очень динамичных данных, которые перемещаются и сталкиваются на каждом временном шаге, обычно требуется больше времени обработки, чем экономия, чтобы найти идеально непрерывное представление для листовых элементов (вам фактически пришлось бы реализовать переменную распределитель памяти размером с размер, который действительно быстр, и это далеко не просто). Поэтому я использую односвязный список индексов, который позволяет использовать постоянный подход свободного списка к выделению/освобождению. Когда вы используете это представление, вы можете перенести элементы из разделенных родителей в новые листья, просто изменив несколько целых чисел.

SmallList<T>

О, я должен упомянуть об этом. Естественно, это помогает, если вы не выделяете кучу только для хранения временного стека узлов для нерекурсивного обхода. SmallList<T> похож на vector<T>, за исключением того, что он не будет включать выделение кучи, пока вы не вставите в него более 128 элементов. Это похоже на оптимизацию строк SBO в стандартной библиотеке C++. Это то, что я реализовал и использовал целую вечность, и это очень помогает убедиться, что вы используете стек, когда это возможно.

Представление в виде дерева

Вот представление самого дерева квадрантов:

struct Quadtree
{
    // Stores all the elements in the quadtree.
    FreeList<QuadElt> elts;

    // Stores all the element nodes in the quadtree.
    FreeList<QuadEltNode> elt_nodes;

    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    std::vector<QuadNode> nodes;

    // Stores the quadtree extents.
    QuadCRect root_rect;

    // Stores the first free node in the quadtree to be reclaimed as 4
    // contiguous nodes at once. A value of -1 indicates that the free
    // list is empty, at which point we simply insert 4 nodes to the
    // back of the nodes array.
    int free_node;

    // Stores the maximum depth allowed for the quadtree.
    int max_depth;
};

Как указано выше, мы сохраняем один прямоугольник для корня (root_rect). Все суб-прямоугольники вычисляются на лету. Все узлы хранятся непрерывно в массиве (std::vector<QuadNode>) вместе с элементами и узлами элементов (в FreeList<T>).

FreeList<T>

Я использую структуру данных FreeList, которая в основном представляет собой массив (и последовательность с произвольным доступом), которая позволяет вам удалять элементы из любого места в постоянное время (оставляя дыры, за которыми восстанавливаются при последующих вставках в постоянное время). Вот упрощенная версия, которая не занимается обработкой нетривиальных типов данных (не использует вызовы размещения новых или ручного уничтожения):

/// Provides an indexed free list with constant-time removals from anywhere
/// in the list without invalidating indices. T must be trivially constructible 
/// and destructible.
template <class T>
class FreeList
{
public:
    /// Creates a new free list.
    FreeList();

    /// Inserts an element to the free list and returns an index to it.
    int insert(const T& element);

    // Removes the nth element from the free list.
    void erase(int n);

    // Removes all elements from the free list.
    void clear();

    // Returns the range of valid indices.
    int range() const;

    // Returns the nth element.
    T& operator[](int n);

    // Returns the nth element.
    const T& operator[](int n) const;

private:
    union FreeElement
    {
        T element;
        int next;
    };
    std::vector<FreeElement> data;
    int first_free;
};

template <class T>
FreeList<T>::FreeList(): first_free(-1)
{
}

template <class T>
int FreeList<T>::insert(const T& element)
{
    if (first_free != -1)
    {
        const int index = first_free;
        first_free = data[first_free].next;
        data[index].element = element;
        return index;
    }
    else
    {
        FreeElement fe;
        fe.element = element;
        data.push_back(fe);
        return static_cast<int>(data.size() - 1);
    }
}

template <class T>
void FreeList<T>::erase(int n)
{
    data[n].next = first_free;
    first_free = n;
}

template <class T>
void FreeList<T>::clear()
{
    data.clear();
    first_free = -1;
}

template <class T>
int FreeList<T>::range() const
{
    return static_cast<int>(data.size());
}

template <class T>
T& FreeList<T>::operator[](int n)
{
    return data[n].element;
}

template <class T>
const T& FreeList<T>::operator[](int n) const
{
    return data[n].element;
}

У меня есть один, который работает с нетривиальными типами и предоставляет итераторы и т. д., но гораздо сложнее. В наши дни я склонен больше работать с тривиально конструируемыми/разрушаемыми структурами в стиле C (используя только нетривиальные определяемые пользователем типы для высокоуровневых вещей).

Максимальная глубина дерева

Я предотвращаю слишком сильное разделение дерева, указав максимально допустимую глубину. Для быстрой симуляции, которую я набросал, я использовал 8. Для меня это имеет решающее значение, поскольку опять же, в визуальных эффектах я часто сталкиваюсь с патологическими случаями, включая контент, созданный художниками, с большим количеством совпадающих или перекрывающихся элементов, которые без ограничения максимальной глубины дерева могли бы хотят, чтобы он подразделяется на неопределенный срок.

Существует небольшая тонкая настройка, если вы хотите получить оптимальную производительность в отношении максимально допустимой глубины и количества элементов, которые вы разрешаете хранить в листе, прежде чем он разделится на 4 дочерних элемента. Я склоняюсь к тому, что оптимальные результаты достигаются при использовании максимум 8 элементов на узел до его разделения и максимальной глубины, установленной таким образом, чтобы наименьший размер ячейки немного превышал размер вашего среднего агента (в противном случае можно было бы вставить больше отдельных агентов). на несколько листьев).

Конфликт и запросы

Есть несколько способов обнаружения коллизий и запросов. Я часто вижу, как люди делают это так:

for each element in scene:
     use quad tree to check for collision against other elements

Это очень просто, но проблема с этим подходом заключается в том, что первый элемент сцены может находиться в совершенно другом месте в мире, чем второй. В результате пути, по которым мы спускаемся по дереву квадрантов, могут быть совершенно случайными. Мы можем пройти один путь к листу, а затем снова захотеть пройти по тому же пути для первого элемента, например, для 50 000-го элемента. К этому времени узлы, участвующие в этом пути, могут быть уже вытеснены из кэша ЦП. Поэтому я рекомендую делать это следующим образом:

traversed = {}
gather quadtree leaves
for each leaf in leaves:
{
     for each element in leaf:
     {
          if not traversed[element]:
          {
              use quad tree to check for collision against other elements
              traversed[element] = true                  
          }
     }
}

Хотя это немного больше кода и требует, чтобы мы сохраняли набор битов traversed или какой-то параллельный массив, чтобы избежать двойной обработки элементов (поскольку они могут быть вставлены более чем в один лист), это помогает убедиться, что мы спускаемся по одним и тем же путям вниз. дерево квадрантов по всему циклу. Это помогает сохранять вещи гораздо более удобными для кэширования. Кроме того, если после попытки переместить элемент на временном шаге он все еще полностью охвачен этим конечным узлом, нам даже не нужно снова возвращаться из корня (мы можем просто проверить только этот один лист).

Распространенные недостатки: чего следует избегать

Хотя существует множество способов ободрать кошку и найти эффективное решение, существует распространенный способ найти очень неэффективное решение. И я столкнулся со своей долей очень неэффективных деревьев квадрантов, kd-деревьев и октодеревьев за свою карьеру, работая в VFX. Мы говорим о гигабайте памяти, используемой только для разбиения сетки со 100 000 треугольников, при этом на сборку уходит 30 секунд, тогда как приличная реализация должна делать то же самое сотни раз в секунду и занимать всего несколько мегабайт. Есть много людей, разрабатывающих их для решения проблем, которые являются теоретическими волшебниками, но не уделяют особого внимания эффективности памяти.

Таким образом, самым распространенным запретом, который я вижу, является хранение одного или нескольких полноценных контейнеров с каждым узлом дерева. Под полноценным контейнером я подразумеваю что-то, что владеет, выделяет и освобождает свою собственную память, например:

struct Node
{
     ...

     // Stores the elements in the node.
     List<Element> elements;
};

И List<Element> может быть списком в Python, ArrayList в Java или C#, std::vector в C++ и т. д.: некоторая структура данных, которая управляет своей собственной памятью/ресурсами.

Проблема здесь в том, что, хотя такие контейнеры очень эффективно реализованы для хранения большого количества элементов, все на всех языках крайне неэффективны, если вы создаете множество их экземпляров только для хранения нескольких элементов в каждый. Одна из причин заключается в том, что метаданные контейнера имеют тенденцию к взрывоопасному использованию памяти на таком детальном уровне одного узла дерева. Контейнеру может потребоваться хранить размер, емкость, указатель/ссылку на данные, которые он выделяет, и т. д., и все это для общих целей, поэтому он может использовать 64-битные целые числа для размера и емкости. В результате метаданные только для пустого контейнера могут быть 24 байта, что уже в 3 раза больше, чем полнота предложенного мной представления узла, и это только для пустого контейнера, предназначенного для хранения элементов в листьях.

Кроме того, каждый контейнер часто хочет либо выделить кучу/GC-аллоцировать при вставке, либо заранее потребовать еще больше предварительно выделенной памяти (в этот момент может потребоваться 64 байта только для самого контейнера). Таким образом, это либо становится медленным из-за всех выделений памяти (обратите внимание, что выделения GC изначально действительно быстры в некоторых реализациях, таких как JVM, но это только для начального цикла взрыва Eden), либо из-за того, что мы подвергаемся куче промахов кеша, потому что узлы настолько огромен, что почти не помещается в нижние уровни кеша ЦП при обходе или в оба.

Тем не менее, это очень естественная склонность и имеет интуитивно понятный смысл, поскольку мы теоретически говорим об этих структурах, используя такой язык, как Элементы хранятся в листьях, что предполагает хранение контейнера элементов в конечных узлах. К сожалению, это имеет взрывную стоимость с точки зрения использования памяти и обработки. Так что избегайте этого, если хотите создать что-то достаточно эффективное. Сделайте общий ресурс Node и укажите (ссылайтесь) или индексируйте память, выделенную и сохраненную для всего дерева, а не для каждого отдельного узла. На самом деле элементы не должны храниться в листьях.

Элементы должны храниться в дереве, а конечные узлы должны индексировать или указывать на эти элементы.

Заключение

Уф, так что это основные вещи, которые я делаю, чтобы достичь того, что, надеюсь, считается достойным решением. Надеюсь, это поможет. Обратите внимание, что я нацелен на несколько продвинутый уровень для людей, которые уже реализовали деревья квадрантов хотя бы один или два раза. Если у вас есть какие-либо вопросы, не стесняйтесь стрелять.

Поскольку этот вопрос немного широк, я мог бы прийти и отредактировать его, а затем продолжать корректировать и расширять его с течением времени, если он не будет закрыт (мне нравятся вопросы такого типа, поскольку они дают нам повод написать о нашем опыте работы в поле, но сайту они не всегда нравятся). Я также надеюсь, что некоторые эксперты могут предложить альтернативные решения, из которых я могу извлечь уроки и, возможно, использовать для дальнейшего улучшения моего.

Опять же, деревья квадрантов на самом деле не являются моей любимой структурой данных для чрезвычайно динамичных сценариев столкновений, подобных этому. Так что, вероятно, мне есть чему поучиться у людей, которые предпочитают использовать деревья квадрантов для этой цели и много лет их настраивают и настраивают. В основном я использую quadtrees для статических данных, которые не перемещаются в каждом кадре, и для них я использую представление, сильно отличающееся от предложенного выше.

<сильный>2. Основы

В этом ответе (извините, я снова исчерпал лимит символов) я больше сосредоточусь на основах, предназначенных для тех, кто плохо знаком с этими структурами.

Итак, допустим, у нас есть куча таких элементов в пространстве:

И мы хотим узнать, какой элемент находится под курсором мыши, или какие элементы пересекаются/сталкиваются друг с другом, или какой элемент находится ближе всего к другому элементу, или что-то в этом роде.

В этом случае, если бы у нас были только данные о положениях и размерах/радиусах элементов в пространстве, нам пришлось бы перебирать все, чтобы выяснить, какой элемент находится в заданной области поиска. Для обнаружения столкновений нам пришлось бы перебирать каждый отдельный элемент, а затем для каждого элемента перебирать все остальные элементы, что делало бы его взрывоопасным алгоритмом квадратичной сложности. Это не выдержит нетривиальных входных размеров.

Разделить

Итак, что мы можем сделать с этой проблемой? Один из простых подходов состоит в том, чтобы разделить пространство поиска (например, экран) на фиксированное количество ячеек, например так:

Теперь предположим, что вы хотите найти элемент под курсором мыши в позиции (cx, cy). В этом случае все, что нам нужно сделать, это проверить элементы в ячейке под курсором мыши:

grid_x = floor(cx / cell_size);
grid_y = floor(cy / cell_size);
for each element in cell(grid_x, grid_y):
{
     if element is under cx,cy:
         do something with element (hover highlight it, e.g)
}

Аналогичная вещь для обнаружения столкновений. Если мы хотим увидеть, какие элементы пересекаются (сталкиваются) с данным элементом:

grid_x1 = floor(element.x1 / cell_size);
grid_y1 = floor(element.y1 / cell_size);
grid_x2 = floor(element.x2 / cell_size);
grid_y2 = floor(element.y2 / cell_size);

for grid_y = grid_y1, grid_y2:
{
     for grid_x = grid_x1, grid_x2:
     {
         for each other_element in cell(grid_x, grid_y):
         {
             if element != other_element and collide(element, other_element):
             {
                 // The two elements intersect. Do something in response
                 // to the collision.
             }
         }
     }
}

И я рекомендую людям начать таким образом, разделив пространство/экран на фиксированное количество ячеек сетки, например 10x10, или 100x100, или даже 1000x1000. Некоторые люди могут подумать, что 1000x1000 будет взрывоопасным в использовании памяти, но вы можете сделать так, чтобы каждая ячейка требовала только 4 байта с 32-битными целыми числами, например:

... в этот момент даже миллион ячеек занимает менее 4 мегабайт.

Недостаток сетки с фиксированным разрешением

Сетка с фиксированным разрешением — фантастическая структура данных для этой задачи, если вы спросите меня (мой личный фаворит для обнаружения столкновений), но у нее есть некоторые недостатки.

Представьте, что у вас есть видеоигра «Властелин колец». Допустим, многие из ваших юнитов — это маленькие юниты на карте, такие как люди, орки и эльфы. Однако у вас также есть некоторые гигантские юниты, такие как драконы и энты.

Здесь проблема с фиксированным разрешением сетки заключается в том, что, хотя размеры ваших ячеек могут быть оптимальными для хранения таких маленьких юнитов, как люди, эльфы и орки, которые большую часть времени занимают только 1 ячейку, огромные чуваки, такие как драконы и энты, могут захотеть занимают много ячеек, скажем, 400 ячеек (20х20). В результате нам приходится вставлять этих больших парней во многие ячейки и хранить много избыточных данных.

Также предположим, что вы хотите найти интересующие вас единицы в большой прямоугольной области карты. В этом случае вам, возможно, придется проверить гораздо больше ячеек, чем теоретически оптимально.

Это главный недостаток сетки с фиксированным разрешением*. В конечном итоге нам потенциально придется вставлять большие объекты и хранить их в гораздо большем количестве ячеек, чем в идеале, а для больших областей поиска нам, возможно, придется проверять гораздо больше ячеек, чем в идеале.

• Тем не менее, если оставить в стороне теорию, часто вы можете работать с сетками так, чтобы это было очень удобно для кэширования, аналогично обработке изображений. В результате, несмотря на эти теоретические недостатки, на практике простота и легкость реализации благоприятных для кэширования шаблонов обхода могут сделать сетку намного лучше, чем кажется.

Квадранты

Таким образом, деревья квадрантов являются одним из решений этой проблемы. Вместо того, чтобы использовать, так сказать, сетку с фиксированным разрешением, они адаптируют разрешение на основе некоторых критериев, при этом подразделяя/разбивая на 4 дочерние ячейки для увеличения разрешения. Например, мы могли бы сказать, что ячейка должна быть разделена, если в данной ячейке более 2 дочерних элементов. В таком случае это:

В итоге становится так:

И теперь у нас есть довольно красивое представление, в котором ни одна ячейка не хранит более двух элементов. А пока давайте посмотрим, что произойдет, если мы вставим огромного дракона:

Здесь, в отличие от сетки с фиксированным разрешением, дракона можно просто вставить в одну ячейку, поскольку ячейка, которую он занимает, содержит только один элемент. Точно так же, если мы будем искать большую область карты, нам не нужно будет проверять так много ячеек, если только ячейки не занимают много элементов.

Реализация

Итак, как нам реализовать одну из этих штуковин? Ну, в конце концов, это дерево, и к тому же 4-арное дерево. Итак, мы начнем с понятия корневого узла с 4 дочерними элементами, но в настоящее время они равны null/nil, а корень также является листом:

Вставка

Давайте начнем вставлять некоторые элементы, и снова для простоты допустим, что узел должен разделиться, когда он имеет более 2 элементов. Итак, мы будем вставлять элемент, и когда мы вставляем элемент, мы должны вставлять его в листья (ячейки), которым он принадлежит. В этом случае у нас есть только один, корневой узел/ячейка, поэтому мы вставим его туда:

... и давайте вставим еще:

... и еще:

И теперь у нас более 2 элементов в листовом узле. Теперь он должен разделиться. На этом этапе мы создаем 4 дочерних элемента для листового узла (в данном случае нашего корня), а затем переносим элементы из разделяемого листа (корень) в соответствующие квадранты в зависимости от области/ячейки, которую каждый элемент занимает в пространстве:

Давайте вставим еще один элемент, и снова в соответствующий лист, которому он принадлежит:

... и другой:

И теперь у нас снова более 2 элементов в листе, поэтому мы должны разделить его на 4 квадранта (дети):

И это основная идея. Одна из вещей, которую вы можете заметить, это то, что когда мы вставляем элементы, которые не являются бесконечно малыми точками, они могут легко перекрывать несколько ячеек/узлов.

В результате, если у нас есть много элементов, которые пересекаются со многими границами между ячейками, они могут в конечном итоге захотеть разделить все множество, возможно, бесконечно. Чтобы смягчить эту проблему, некоторые люди предпочитают разбивать элемент. Если все, что вы связываете с элементом, — это прямоугольник, довольно просто нарезать прямоугольники кубиками. Другие люди могут просто установить ограничение глубины/рекурсии на то, насколько дерево может быть разделено. Я склонен предпочитать последнее решение для сценариев обнаружения столкновений между этими двумя, поскольку я считаю, что его, по крайней мере, легче реализовать более эффективно. Однако есть и другая альтернатива: свободные представления, и она будет рассмотрена в другом разделе.

Кроме того, если у вас есть элементы прямо друг над другом, тогда ваше дерево может захотеть разбиться на неопределенный срок, даже если вы храните бесконечно малые точки. Например, если у вас есть 25 точек прямо друг над другом в пространстве (сценарий, с которым я довольно часто сталкиваюсь в визуальных эффектах), то ваше дерево захочет бесконечно разбиваться без ограничения рекурсии/глубины, несмотря ни на что. В результате для обработки патологических случаев вам может понадобиться ограничение глубины, даже если вы нарезаете элементы.

Удаление элементов

Удаление элементов описано в первом ответе вместе с удалением узлов для очистки дерева и удаления пустых листьев. Но в основном все, что мы делаем, чтобы удалить элемент, используя предложенный мной подход, — это просто спускаемся вниз по дереву туда, где находится лист/листья, в которых хранится элемент (что вы можете определить, например, с помощью его прямоугольника), и удаляем его из этих листьев.

Затем, чтобы начать удаление пустых листовых узлов, мы используем подход отложенной очистки, описанный в исходном ответе.

Заключение

У меня мало времени, но я постараюсь вернуться к этому и продолжать улучшать ответ. Если людям нужно упражнение, я бы предложил реализовать старую простую сетку с фиксированным разрешением и посмотреть, сможете ли вы свести ее к тому, где каждая ячейка представляет собой просто 32-битное целое число. Сначала разберитесь с сеткой и присущими ей проблемами, прежде чем рассматривать дерево квадрантов, и, возможно, вы будете в порядке с сеткой. Это может даже предоставить вам наиболее оптимальное решение в зависимости от того, насколько эффективно вы можете реализовать сетку по сравнению с деревом квадрантов.

Правка: мелкие/грубые сетки и оптимизация строк

У меня много вопросов по этому поводу, поэтому я кратко расскажу об этом. Это на самом деле невероятно глупо-просто и может разочаровать людей, которые думали, что это какая-то причудливая вещь. Итак, давайте начнем с простого представления сетки с фиксированным разрешением. Я буду использовать указатели здесь, чтобы сделать это как можно проще (хотя я рекомендую использовать массив и индексы позже, чтобы лучше контролировать использование памяти и шаблоны доступа).

// Stores a node in a grid cell.
struct Node
{
    // Stores a pointer to the next node or null if we're at the end of
    // the list.
    Node* next = nullptr;

    // Stores a pointer to the element in the cell.
    Element* element = nullptr;
};

// Stores a 1000x1000 grid. Hard-coded for simple illustration.
Node* grid[1000][1000] = {};

Как описано в других ответах, сетки с фиксированным разрешением на самом деле намного приличнее, чем кажутся, даже если они кажутся такими глупыми по сравнению с древовидными решениями с переменным разрешением. Однако у них есть недостаток: если мы хотим найти большой параметр (например, огромную круглую или прямоугольную область), им приходится проходить через множество ячеек сетки. Таким образом, мы можем уменьшить эту стоимость, сохранив более грубую сетку:

// Stores a lower-resolution 500x500 parent grid (can use bitsets instead
// of bools). Stores true if one or more elements occupies the cell or
// false if the cell is empty.
bool parent_grid[500][500] = {};

// Stores an even lower-resolution 100x100 grid. It functions similarly
// as the parent grid, storing true if ane element occupies the cell or
// false otherwise.
bool grandparent_grid[100][100] = {};

Мы можем продолжать, а вы можете настроить разрешение и количество используемых сеток по своему усмотрению. Делая это, когда мы хотим найти большой параметр, мы начинаем проверять сетку прародителя, прежде чем искать родительскую сетку, и родителя, прежде чем мы проверяем сетку с полным разрешением. Мы продолжаем только в том случае, если ячейки не полностью пусты. Это может помочь нам исключить целую кучу ячеек для проверки из сетки с самым высоким разрешением во многих случаях, связанных с большими параметрами поиска.

Вот и все. Это требует хранения всех ячеек с самым высоким разрешением в памяти, в отличие от дерева квадрантов, но я всегда находил его намного проще для оптимизации, поскольку нам не нужно гоняться за указателями/индексами, чтобы пройти дочерние элементы каждого узла дерева. Вместо этого мы просто выполняем поиск в массиве с шаблонами доступа, которые очень удобны для кэширования.

Оптимизация на основе строк

Таким образом, оптимизация на основе строк также проста (хотя она применима только тогда, когда мы используем массивы и индексы вместо указателей на узлы*).

• Или настраиваемые распределители памяти, но я действительно не рекомендую использовать их для большинства целей, поскольку довольно громоздко иметь дело с распределителем и структурой данных по отдельности. Связанным структурам намного проще эмулировать эффект массового выделения/освобождения и шаблонов непрерывного доступа, просто сохраняя/перераспределяя массивы (например, std::vector) и индексы в них. В частности, для связанных структур и учитывая, что теперь у нас есть 64-битная адресация, особенно полезно сократить размер ссылок до 32-бит или меньше, превратив их в индексы в определенный массив, если вам действительно не нужно хранить более 2 ^32-1 элементов в вашей структуре данных.

Если представить такую ​​сетку:

... поскольку мы храним все узлы в одной структуре списка для всей сетки, шаг памяти для перехода от одного элемента в ячейке к другому может быть довольно большим, что заставляет нас много пропускать в памяти и нести больше в результате промахи кеша (а также загрузка большего количества нерелевантных данных в строки кеша).

Мы могли бы полностью избавиться от этого, сохраняя целый отдельный список узлов для каждой отдельной ячейки (в этом случае все элементы в ячейке могли бы храниться совершенно непрерывно), но это может быть довольно взрывоопасным с точки зрения использования памяти и очень неэффективным в других отношениях. Таким образом, баланс заключается в том, чтобы просто хранить отдельный список узлов для каждой строки. Таким образом, мы улучшаем пространственную локальность, не имея взрывного количества отдельных списков, поскольку не так много строк по сравнению с общим количеством ячеек (rows * columns). Еще одна вещь, которую вы можете сделать, когда вы делаете это, это то, что когда строка полностью пуста, вы можете освободить память даже для ячеек сетки для всей строки и просто превратить всю строку в нулевой указатель.

Наконец, это дает больше возможностей для распараллеливания вставки/удаления/доступа, поскольку вы можете гарантировать безопасность при условии, что никакие два потока не изменяют/не обращаются к одной и той же строке одновременно (что часто довольно легко обеспечить).

5. Лузово-тайтовая двойная сетка с 500 тыс. агентов

Выше приведен небольшой GIF-файл, показывающий, как 500 000 агентов отскакивают друг от друга на каждом временном шаге, используя новую структуру данных со свободной/плотной сеткой, на создание которой меня вдохновил после написания ответа о свободных деревьях квадрантов. Я постараюсь рассказать, как это работает.

На данный момент это самая производительная структура данных среди всех тех, которые я реализовал (хотя это мог быть только я), обрабатывающая полмиллиона агентов лучше, чем первоначальное дерево квадрантов, обрабатывающее 100 000, и лучше, чем свободное Quadtree обработал 250 тыс. Он также требует наименьшего объема памяти и имеет наиболее стабильное использование памяти среди этих трех. Все это по-прежнему работает в одном потоке, без SIMD-кода, без причудливых микрооптимизаций, которые я обычно применяю для производственного кода — просто простая реализация за пару часов работы.

Я также устранил узкие места в рисовании без какого-либо улучшения кода растеризации. Это потому, что сетка позволяет мне легко перемещаться по ней таким образом, чтобы это было удобно для кэширования для обработки изображений (отрисовка элементов в ячейках сетки один за другим по совпадению приводит к очень удобным для кэширования шаблонам обработки изображений при растеризации).

Как ни странно, на его реализацию у меня также ушло самое короткое время (всего 2 часа, в то время как я потратил 5 или 6 часов на свободное дерево квадрантов), и он также требует наименьшего количества кода (и, возможно, имеет самый простой код). Хотя это может быть просто потому, что я накопил так много опыта реализации сеток.

Свободная/плотная двойная сетка

Итак, я рассказал, как работают сетки, в разделе «Основы» (см. часть 2), но это расплывчатая сетка. Каждая ячейка сетки хранит свою собственную ограничивающую рамку, которая может уменьшаться при удалении элементов и увеличиваться при добавлении элементов. В результате каждый элемент нужно вставить в сетку только один раз в зависимости от того, в какую ячейку попадает его центральная позиция, например:

// Ideally use multiplication here with inv_cell_w or inv_cell_h.
int cell_x = clamp(floor(elt_x / cell_w), 0, num_cols-1);
int cell_y = clamp(floor(ely_y / cell_h), 0, num_rows-1);
int cell_idx = cell_y*num_rows + cell_x;
// Insert element to cell at 'cell_idx' and expand the loose cell's AABB.

Ячейки хранят элементы и AABB следующим образом:

struct LGridLooseCell
{
    // Stores the index to the first element using an indexed SLL.
    int head;

    // Stores the extents of the grid cell relative to the upper-left corner
    // of the grid which expands and shrinks with the elements inserted and 
    // removed.
    float l, t, r, b;
};

Однако незакрепленные клетки представляют собой концептуальную проблему. Учитывая, что у них есть эти ограничивающие рамки переменного размера, которые могут стать огромными, если мы вставим огромный элемент, как нам избежать проверки каждой долбанной ячейки сетки, когда мы хотим узнать, какие свободные ячейки и соответствующие элементы пересекают прямоугольник поиска? Может быть случай, когда мы ищем верхний правый угол свободной сетки, но есть ячейка в нижнем левом углу на противоположной стороне, которая стала достаточно большой, чтобы пересечь эту область. Без решения этой проблемы мы вынуждены проверять все свободные ячейки за линейное время на совпадения.

... и решение состоит в том, что на самом деле это двойная сетка. Сами ячейки рыхлой сетки разбиты на плотную сетку. Когда мы выполняем аналогичный поиск выше, мы сначала просматриваем плотную сетку следующим образом:

tx1 = clamp(floor(search_x1 / cell_w), 0, num_cols-1);
tx2 = clamp(floor(search_x2 / cell_w), 0, num_cols-1);
ty1 = clamp(floor(search_y1 / cell_h), 0, num_rows-1);
ty2 = clamp(floor(search_y2 / cell_h), 0, num_rows-1);

for ty = ty1, ty2:
{
    trow = ty * num_cols
    for tx = tx1, tx2:
    {
        tight_cell = tight_cells[trow + tx];
        for each loose_cell in tight_cell:
        {
            if loose_cell intersects search area:
            {
                for each element in loose_cell:
                {
                    if element intersects search area:
                        add element to query results
                }
            }
        }
    }
}

Плотные ячейки хранят односвязный индексный список свободных ячеек, например:

struct LGridLooseCellNode
{
    // Points to the next loose cell node in the tight cell.
    int next;

    // Stores an index to the loose cell.
    int cell_idx;
};

struct LGridTightCell
{
    // Stores the index to the first loose cell node in the tight cell using 
    // an indexed SLL.
    int head;
};

И вуаля, это основная идея рыхлой двойной сетки. Когда мы вставляем элемент, мы расширяем AABB свободной ячейки так же, как и для свободного дерева квадрантов, только за постоянное время, а не за логарифмическое. Однако мы также вставляем свободную ячейку в плотную сетку за постоянное время на основе ее прямоугольника (и ее можно вставить в несколько ячеек).

Комбинация этих двух элементов (плотная сетка для быстрого поиска незакрепленных ячеек и незакрепленные ячейки для быстрого поиска элементов) дает очень красивую структуру данных, в которой каждый элемент вставляется в одну ячейку с постоянным поиском, вставкой и удалением во времени.

Единственным большим недостатком, который я вижу, является то, что нам нужно хранить все эти ячейки и, возможно, нам придется искать больше ячеек, чем нам нужно, но они все еще достаточно дешевы (в моем случае 20 байт на ячейку), и их легко пройти через ячейки при поиске в очень удобном для кэширования шаблоне доступа.

Я рекомендую попробовать эту идею свободных сеток. Возможно, его намного проще реализовать, чем деревья квадрантов и свободные деревья квадрантов, и, что более важно, оптимизировать, поскольку он сразу же поддается организации кэш-памяти. В качестве супер крутого бонуса, если вы можете заранее предвидеть количество агентов в вашем мире, он почти на 100% идеально стабилен и сразу в плане использования памяти, так как элемент всегда занимает ровно одну ячейку, а количество ячеек всего фиксирован (поскольку они не подразделяются/разделяются). Единственная незначительная нестабильность в использовании памяти заключается в том, что эти свободные ячейки могут время от времени расширяться и вставляться в дополнительные плотные ячейки в более грубой сетке, но это должно происходить довольно редко. В результате использование памяти очень стабильно/последовательно/предсказуемо, а также часто соответствует соответствующей частоте кадров. Это может быть огромным бонусом для определенного оборудования и программного обеспечения, где вы хотите заранее выделить всю память.

Кроме того, с помощью SIMD очень легко заставить работать несколько последовательных запросов одновременно с векторизованным кодом (в дополнение к многопоточности), поскольку обход, если мы вообще можем его так назвать, является плоским (это просто поиск с постоянным временем в массиве). индекс ячейки, который включает в себя некоторые арифметические действия). В результате довольно легко применять стратегии оптимизации, подобные пакетам лучей, которые Intel применяет к своему ядру трассировки лучей/BVH (Embree) для одновременного тестирования нескольких когерентных лучей (в нашем случае это будут агентские пакеты для коллизии), за исключением таких причудливых вещей. /сложный код, так как обход сетки намного проще.

Об использовании памяти и эффективности

Я немного рассказал об этом в части 1 об эффективных деревьях квадрантов, но сокращение использования памяти часто является ключом к скорости в наши дни, поскольку наши процессоры очень быстры, когда вы помещаете данные, скажем, в L1 или регистр, но доступ к DRAM относительно невелик. , так медленно. У нас так мало быстрой памяти, даже если у нас безумное количество медленной памяти.

Я думаю, что мне повезло начать в то время, когда мы должны были быть очень экономными с использованием памяти (хотя и не так сильно, как люди до меня), когда даже мегабайт DRAM считался потрясающим. Некоторые вещи, которые я узнал тогда, и привычки, которые я перенял (хотя я далеко не эксперт), по совпадению совпадают с производительностью. От некоторых из них мне пришлось отказаться как от вредных привычек, которые в наши дни контрпродуктивны, и я научился использовать расточительство там, где это не имеет значения. Сочетание профилировщика и сжатых сроков помогает мне оставаться продуктивным и не терять слишком много приоритетов.

Итак, один общий совет, который я бы дал по эффективности в целом, а не только по пространственным индексам, используемым для обнаружения столкновений, заключается в том, чтобы следить за использованием памяти. Если это взрывоопасно, есть вероятность, что решение не будет очень эффективным. Конечно, есть серая зона, где использование немного большего объема памяти для структуры данных может существенно сократить обработку до такой степени, что это выгодно только с точки зрения скорости, но во много раз уменьшает объем памяти, необходимой для структур данных, особенно горячую память, которая к которому обращаются повторно, может привести к вполне пропорциональному увеличению скорости. Все наименее эффективные пространственные индексы, с которыми я сталкивался в своей карьере, были самыми взрывоопасными в использовании памяти.

Полезно посмотреть на объем данных, которые вам нужно хранить, и рассчитать, хотя бы приблизительно, сколько памяти в идеале требуется. Затем сравните это с тем, сколько вам действительно нужно. Если они полностью разделены, то вы, скорее всего, получите приличный прирост, сократив использование памяти, потому что это часто приводит к меньшему времени загрузки фрагментов памяти из более медленных форм памяти в памяти. иерархия.

4. Свободное квадродерево

Хорошо, я хотел бы уделить некоторое время реализации и объяснению свободных деревьев квадрантов, так как я нахожу их очень интересными и, возможно, даже наиболее сбалансированными для самых разных вариантов использования, связанных с очень динамичными сценами.

Так что в итоге я реализовал один прошлой ночью и потратил некоторое время на настройку, настройку и профилирование. Вот тизер с четвертью миллиона динамических агентов, которые движутся и отскакивают друг от друга на каждом временном шаге:

Частота кадров начинает страдать, когда я уменьшаю масштаб, чтобы посмотреть на все четверть миллиона агентов вместе со всеми ограничивающими прямоугольниками свободного дерева квадрантов, но это в основном из-за узких мест в моих функциях рисования. Они начинают становиться горячими точками, если я уменьшаю масштаб, чтобы нарисовать все на экране сразу, и я вообще не удосужился их оптимизировать. Вот как это работает на базовом уровне с очень небольшим количеством агентов:

Свободное дерево квадрантов

Итак, что такое свободные квадранты? По сути, это деревья квадрантов, узлы которых не идеально разделены по центру на четыре четных квадранта. Вместо этого их AABB (ограничивающие прямоугольники) могут перекрываться и быть больше, а часто даже меньше, чем то, что вы получили бы, если бы вы разделили узел точно по центру на 4 квадранта.

Так что в этом случае нам абсолютно необходимо хранить ограничивающие рамки с каждым узлом, поэтому я представил это так:

struct LooseQuadNode
{
    // Stores the AABB of the node.
    float rect[4];

    // Stores the negative index to the first child for branches or the 
    // positive index to the element list for leaves.
    int children;
};

На этот раз я попытался использовать числа с плавающей запятой одинарной точности, чтобы увидеть, насколько хорошо они работают, и они справились с очень приличной задачей.

В чем смысл?

Хорошо, так в чем смысл? Главное, что вы можете использовать со свободным деревом квадрантов, это то, что вы можете рассматривать каждый элемент, который вы вставляете в дерево квадрантов, как одну точку для вставки и удаления. Поэтому элемент никогда не вставляется более чем в один конечный узел всего дерева, поскольку он рассматривается как бесконечно малая точка.

Однако, когда мы вставляем эти точки элемента в дерево, мы расширяем ограничивающие рамки каждого узла, в который мы вставляем, чтобы охватить границы элемента (например, прямоугольник элемента). Это позволяет нам надежно находить эти элементы при выполнении поискового запроса (например, при поиске всех элементов, пересекающих область прямоугольника или круга).

Плюсы:

• Даже самый гигантский агент нужно вставить только в один конечный узел, и он займет не больше памяти, чем самый маленький. В результате он хорошо подходит для сцен с элементами, размеры которых сильно различаются от одного к другому, и это то, что я проводил стресс-тестирование в демонстрационной версии агента 250k выше.
• Использует меньше памяти на элемент, особенно большие элементы.

Минусы:

• Хотя это ускоряет вставку и удаление, это неизбежно замедляет поиск в дереве. То, что раньше было несколькими базовыми сравнениями с центральной точкой узла, чтобы определить, в какие квадранты спуститься, превращается в цикл, в котором нужно проверять каждый прямоугольник каждого дочернего элемента, чтобы определить, какие из них пересекают область поиска.
• Использует больше памяти на узел (в моем случае в 5 раз больше).

Дорогие запросы

Эта первая афера была бы довольно ужасной для статических элементов, поскольку все, что мы делаем, это строим дерево и ищем его в этих случаях. И я обнаружил с этим свободным деревом квадрантов, что, несмотря на то, что я потратил несколько часов на его настройку и настройку, есть огромная точка доступа, связанная с запросом:

Тем не менее, на данный момент это моя лучшая личная реализация дерева квадрантов для динамических сцен (хотя имейте в виду, что я предпочитаю иерархические сетки для этой цели и не имею такого большого опыта использования деревьев квадрантов для динамических сцен), несмотря на это вопиющее против. И это потому, что, по крайней мере, для динамических сцен нам приходится постоянно перемещать элементы на каждом временном шаге, и поэтому с деревом нужно делать гораздо больше, чем просто запрашивать его. Его нужно постоянно обновлять, и это на самом деле делает довольно приличную работу.

Что мне нравится в свободном дереве квадрантов, так это то, что вы можете чувствовать себя в безопасности, даже если у вас есть куча массивных элементов в дополнение к куче самых маленьких элементов. Массивные элементы не займут больше памяти, чем маленькие. В результате, если бы я писал видеоигру с массивным миром и хотел бы просто поместить все в один центральный пространственный индекс, чтобы ускорить все, не заморачиваясь иерархией структур данных, как я обычно делаю, тогда свободные квадродеревья и свободные октодеревья могли бы быть идеальными. сбалансирована как одна центральная универсальная структура данных, если мы собираемся использовать только одну для всего динамического мира.

Использование памяти

С точки зрения использования памяти, в то время как элементы занимают меньше памяти (особенно массивные), узлы занимают немного больше по сравнению с моими реализациями, где узлам даже не нужно хранить AABB. В целом, в различных тестовых случаях, в том числе с большим количеством гигантских элементов, я обнаружил, что свободное дерево квадрантов имеет тенденцию занимать немного больше памяти с его мощными узлами (примерно на 33% больше). Тем не менее, он работает лучше, чем реализация quadtree в моем первоначальном ответе.

С положительной стороны, использование памяти более стабильно (что приводит к более стабильной и плавной частоте кадров). Дерево квадрантов моего первоначального ответа заняло около 5 с лишним секунд, прежде чем использование памяти стало совершенно стабильным. Это имеет тенденцию становиться стабильным всего через секунду или две после запуска, и, скорее всего, потому, что элементы никогда не нужно вставлять более одного раза (даже небольшие элементы могут быть вставлены дважды в исходное дерево квадрантов, если они перекрывают два или более узла). на границах). В результате структура данных быстро обнаруживает необходимый объем памяти для выделения, так сказать, на все случаи.

Теория

Итак, давайте рассмотрим основную теорию. Я рекомендую сначала реализовать обычное дерево квадрантов и понять его, прежде чем переходить к свободным версиям, поскольку их немного сложнее реализовать. Когда мы начинаем с пустого дерева, вы можете представить, что оно также имеет пустой прямоугольник.

Вставим один элемент:

Поскольку на данный момент у нас есть только корневой узел, который также является листом, мы просто вставляем его в него. После этого ранее пустой прямоугольник корневого узла теперь охватывает вставленный нами элемент (показан красными пунктирными линиями). Вставим еще:

Мы расширяем AABB узлов, которые мы пересекаем, когда мы вставляем (на этот раз только корень), на AABB элементов, которые мы вставляем. Давайте вставим еще один, и скажем, узлы должны разделяться, когда они содержат более 2 элементов:

В этом случае у нас есть более 2 элементов в листовом узле (наш корень), поэтому мы должны разделить его на 4 квадранта. Это почти то же самое, что и разбиение обычного дерева квадрантов на основе точек, за исключением того, что мы, опять же, расширяем ограничивающие рамки при переносе дочерних элементов. Начнем с рассмотрения центрального положения разделяемого узла:

Теперь у нас есть 4 дочерних элемента для нашего корневого узла, и каждый из них также хранит свою ограничивающую рамку (показана зеленым цветом). Вставим еще один элемент:

Здесь вы можете видеть, что вставка этого элемента расширила не только прямоугольник нижнего левого дочернего элемента, но и корень (мы расширяем все AABB вдоль вставляемого пути). Вставим еще:

В этом случае у нас снова есть 3 элемента в листовом узле, поэтому мы должны разделить:

Просто так. А как насчет того круга в левом нижнем углу? Кажется, что он пересекает 2 квадранта. Однако мы рассматриваем только одну точку элемента (например, его центр), чтобы определить квадрант, к которому он принадлежит. Так что этот круг на самом деле вставляется только в нижний левый квадрант.

Тем не менее, ограничивающая рамка нижнего левого квадранта расширена, чтобы охватить его пределы (показаны голубым цветом, и надеюсь, вы, ребята, не возражаете, но я изменил цвет фона, так как стало трудно видеть цвета), и поэтому AABB узлы на уровне 2 (показаны голубым цветом) фактически переходят в квадранты друг друга.

Тот факт, что каждый квадрант хранит свой собственный прямоугольник, который всегда гарантированно охватывает его элементы, позволяет нам вставлять элемент только в один конечный узел, даже если его площадь пересекает несколько узлов. Вместо этого мы расширяем ограничивающую рамку конечного узла вместо того, чтобы вставлять элемент в несколько узлов.

Обновление AABB

Таким образом, это может привести к вопросу, когда обновляются AABB? Если мы будем расширять AABB только при вставке элементов, они просто будут расти все больше и больше. Как мы сжимаем их, когда элементы удаляются? Есть много способов решить эту проблему, но я делаю это, обновляя ограничивающие рамки всей иерархии в том методе очистки, который описан в моем первоначальном ответе. Это кажется достаточно быстрым (даже не отображается как точка доступа).

Сравнение с сетками

Я все еще не могу реализовать это почти так же эффективно для обнаружения столкновений, как мои реализации иерархической сетки, но опять же, это может быть больше обо мне, чем о структуре данных. Основная трудность, с которой я сталкиваюсь при работе с древовидными структурами, заключается в том, чтобы легко контролировать, где все находится в памяти и как к ней осуществляется доступ. С сеткой вы можете убедиться, что все столбцы строки являются смежными и расположены последовательно, например, и убедиться, что вы обращаетесь к ним последовательно вместе с элементами, хранящимися в этой строке непрерывно. С деревом доступ к памяти имеет тенденцию быть немного спорадическим по своей природе, а также имеет тенденцию к быстрой деградации, поскольку деревья хотят передавать элементы намного чаще, поскольку узлы разбиваются на несколько дочерних элементов. Тем не менее, если бы я хотел использовать пространственный индекс, который был бы деревом, я действительно пока копал эти свободные варианты, и в моей голове появляются идеи для реализации свободной сетки.

Заключение

Таким образом, это свободные деревья квадрантов в двух словах, и они в основном имеют логику вставки/удаления обычного дерева квадрантов, которое просто хранит точки, за исключением того, что оно расширяет/обновляет AABB по пути. Для поиска мы обходим все дочерние узлы, прямоугольники которых пересекают нашу область поиска.

Я надеюсь, что люди не возражают против того, что я публикую так много длинных ответов. Я действительно получаю удовольствие от их написания, и это было полезное упражнение для меня при повторном посещении деревьев квадрантов, чтобы попытаться написать все эти ответы. Я также обдумываю книгу на эти темы в какой-то момент (хотя она будет на японском языке) и пишу некоторые ответы здесь, хотя и поспешно и на английском языке, это помогает мне собрать все воедино в моем мозгу. Теперь мне просто нужно, чтобы кто-то попросил объяснить, как писать эффективные октодеревья или сетки для обнаружения столкновений, чтобы дать мне повод сделать то же самое по этим предметам.

3. Портативная реализация C

Я надеюсь, что люди не возражают против другого ответа, но я исчерпал лимит в 30 тысяч. Сегодня я думал о том, что мой первый ответ не был очень языково-независимым. Я говорил о стратегиях распределения памяти, шаблонах классов и т. д., и не все языки допускают такие вещи.

Поэтому я потратил некоторое время на размышления об эффективной реализации, применимой почти повсеместно (исключение составляют функциональные языки). Так что в итоге я перенес свое дерево квадрантов на C таким образом, что все, что ему нужно, это массивы int для хранения всего.

Результат некрасивый, но он должен работать очень эффективно на любом языке, позволяющем хранить непрерывные массивы int. Для Python есть такие библиотеки, как ndarray в numpy. Для JS существуют типизированные массивы. Для Java и C# мы можем использовать массивы int (не Integer, они не гарантируют непрерывное хранение и используют гораздо больше памяти, чем старый добрый int).

Список IntList

Поэтому я использую одну вспомогательную структуру, построенную на int массивах для всего дерева квадрантов, чтобы максимально упростить перенос на другие языки. Он сочетает в себе стек/свободный список. Это все, что нам нужно, чтобы эффективно реализовать все, о чем говорилось в другом ответе.

#ifndef INT_LIST_H
#define INT_LIST_H

#ifdef __cplusplus
    #define IL_FUNC extern "C"
#else
    #define IL_FUNC
#endif

typedef struct IntList IntList;
enum {il_fixed_cap = 128};

struct IntList
{
    // Stores a fixed-size buffer in advance to avoid requiring
    // a heap allocation until we run out of space.
    int fixed[il_fixed_cap];

    // Points to the buffer used by the list. Initially this will
    // point to 'fixed'.
    int* data;

    // Stores how many integer fields each element has.
    int num_fields;

    // Stores the number of elements in the list.
    int num;

    // Stores the capacity of the array.
    int cap;

    // Stores an index to the free element or -1 if the free list
    // is empty.
    int free_element;
};

// ---------------------------------------------------------------------------------
// List Interface
// ---------------------------------------------------------------------------------
// Creates a new list of elements which each consist of integer fields.
// 'num_fields' specifies the number of integer fields each element has.
IL_FUNC void il_create(IntList* il, int num_fields);

// Destroys the specified list.
IL_FUNC void il_destroy(IntList* il);

// Returns the number of elements in the list.
IL_FUNC int il_size(const IntList* il);

// Returns the value of the specified field for the nth element.
IL_FUNC int il_get(const IntList* il, int n, int field);

// Sets the value of the specified field for the nth element.
IL_FUNC void il_set(IntList* il, int n, int field, int val);

// Clears the specified list, making it empty.
IL_FUNC void il_clear(IntList* il);

// ---------------------------------------------------------------------------------
// Stack Interface (do not mix with free list usage; use one or the other)
// ---------------------------------------------------------------------------------
// Inserts an element to the back of the list and returns an index to it.
IL_FUNC int il_push_back(IntList* il);

// Removes the element at the back of the list.
IL_FUNC void il_pop_back(IntList* il);

// ---------------------------------------------------------------------------------
// Free List Interface (do not mix with stack usage; use one or the other)
// ---------------------------------------------------------------------------------
// Inserts an element to a vacant position in the list and returns an index to it.
IL_FUNC int il_insert(IntList* il);

// Removes the nth element in the list.
IL_FUNC void il_erase(IntList* il, int n);

#endif

#include "IntList.h"
#include <stdlib.h>
#include <string.h>
#include <assert.h>

void il_create(IntList* il, int num_fields)
{
    il->data = il->fixed;
    il->num = 0;
    il->cap = il_fixed_cap;
    il->num_fields = num_fields;
    il->free_element = -1;
}

void il_destroy(IntList* il)
{
    // Free the buffer only if it was heap allocated.
    if (il->data != il->fixed)
        free(il->data);
}

void il_clear(IntList* il)
{
    il->num = 0;
    il->free_element = -1;
}

int il_size(const IntList* il)
{
    return il->num;
}

int il_get(const IntList* il, int n, int field)
{
    assert(n >= 0 && n < il->num);
    return il->data[n*il->num_fields + field];
}

void il_set(IntList* il, int n, int field, int val)
{
    assert(n >= 0 && n < il->num);
    il->data[n*il->num_fields + field] = val;
}

int il_push_back(IntList* il)
{
    const int new_pos = (il->num+1) * il->num_fields;

    // If the list is full, we need to reallocate the buffer to make room
    // for the new element.
    if (new_pos > il->cap)
    {
        // Use double the size for the new capacity.
        const int new_cap = new_pos * 2;

        // If we're pointing to the fixed buffer, allocate a new array on the
        // heap and copy the fixed buffer contents to it.
        if (il->cap == il_fixed_cap)
        {
            il->data = malloc(new_cap * sizeof(*il->data));
            memcpy(il->data, il->fixed, sizeof(il->fixed));
        }
        else
        {
            // Otherwise reallocate the heap buffer to the new size.
            il->data = realloc(il->data, new_cap * sizeof(*il->data));
        }
        // Set the old capacity to the new capacity.
        il->cap = new_cap;
    }
    return il->num++;
}

void il_pop_back(IntList* il)
{
    // Just decrement the list size.
    assert(il->num > 0);
    --il->num;
}

int il_insert(IntList* il)
{
    // If there's a free index in the free list, pop that and use it.
    if (il->free_element != -1)
    {
        const int index = il->free_element;
        const int pos = index * il->num_fields;

        // Set the free index to the next free index.
        il->free_element = il->data[pos];

        // Return the free index.
        return index;
    }
    // Otherwise insert to the back of the array.
    return il_push_back(il);
}

void il_erase(IntList* il, int n)
{
    // Push the element to the free list.
    const int pos = n * il->num_fields;
    il->data[pos] = il->free_element;
    il->free_element = n;
}

Использование IntList

Использование этой структуры данных для реализации всего не дает самого красивого кода. Вместо доступа к элементам и полям следующим образом:

elements[n].field = elements[n].field + 1;

... мы в конечном итоге делаем это так:

il_set(&elements, n, idx_field, il_get(&elements, n, idx_field) + 1);

... что отвратительно, я знаю, но смысл этого кода в том, чтобы быть максимально эффективным и переносимым, а не настолько простым в обслуживании, насколько это возможно. Есть надежда, что люди смогут просто использовать это дерево квадрантов в своих проектах, не изменяя и не поддерживая его.

Да, и не стесняйтесь использовать этот код, который я публикую, как хотите, даже для коммерческих проектов. Мне бы очень понравилось, если бы люди дали мне знать, если найдут это полезным, но делайте, как хотите.

Квадрант

Итак, используя приведенную выше структуру данных, вот дерево квадрантов в C:

#ifndef QUADTREE_H
#define QUADTREE_H

#include "IntList.h"

#ifdef __cplusplus
    #define QTREE_FUNC extern "C"
#else
    #define QTREE_FUNC
#endif

typedef struct Quadtree Quadtree;

struct Quadtree
{
    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    IntList nodes;

    // Stores all the elements in the quadtree.
    IntList elts;

    // Stores all the element nodes in the quadtree.
    IntList enodes;

    // Stores the quadtree extents.
    int root_mx, root_my, root_sx, root_sy;

    // Maximum allowed elements in a leaf before the leaf is subdivided/split unless
    // the leaf is at the maximum allowed tree depth.
    int max_elements;

    // Stores the maximum depth allowed for the quadtree.
    int max_depth;

    // Temporary buffer used for queries.
    char* temp;

    // Stores the size of the temporary buffer.
    int temp_size;
};

// Function signature used for traversing a tree node.
typedef void QtNodeFunc(Quadtree* qt, void* user_data, int node, int depth, int mx, int my, int sx, int sy);

// Creates a quadtree with the requested extents, maximum elements per leaf, and maximum tree depth.
QTREE_FUNC void qt_create(Quadtree* qt, int width, int height, int max_elements, int max_depth);

// Destroys the quadtree.
QTREE_FUNC void qt_destroy(Quadtree* qt);

// Inserts a new element to the tree.
// Returns an index to the new element.
QTREE_FUNC int qt_insert(Quadtree* qt, int id, float x1, float y1, float x2, float y2);

// Removes the specified element from the tree.
QTREE_FUNC void qt_remove(Quadtree* qt, int element);

// Cleans up the tree, removing empty leaves.
QTREE_FUNC void qt_cleanup(Quadtree* qt);

// Outputs a list of elements found in the specified rectangle.
QTREE_FUNC void qt_query(Quadtree* qt, IntList* out, float x1, float y1, float x2, float y2, int omit_element);

// Traverses all the nodes in the tree, calling 'branch' for branch nodes and 'leaf' 
// for leaf nodes.
QTREE_FUNC void qt_traverse(Quadtree* qt, void* user_data, QtNodeFunc* branch, QtNodeFunc* leaf);

#endif

#include "Quadtree.h"
#include <stdlib.h>

enum
{
    // ----------------------------------------------------------------------------------------
    // Element node fields:
    // ----------------------------------------------------------------------------------------
    enode_num = 2,

    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    enode_idx_next = 0,

    // Stores the element index.
    enode_idx_elt = 1,

    // ----------------------------------------------------------------------------------------
    // Element fields:
    // ----------------------------------------------------------------------------------------
    elt_num = 5,

    // Stores the rectangle encompassing the element.
    elt_idx_lft = 0, elt_idx_top = 1, elt_idx_rgt = 2, elt_idx_btm = 3,

    // Stores the ID of the element.
    elt_idx_id = 4,

    // ----------------------------------------------------------------------------------------
    // Node fields:
    // ----------------------------------------------------------------------------------------
    node_num = 2,

    // Points to the first child if this node is a branch or the first element
    // if this node is a leaf.
    node_idx_fc = 0,

    // Stores the number of elements in the node or -1 if it is not a leaf.
    node_idx_num = 1,

    // ----------------------------------------------------------------------------------------
    // Node data fields:
    // ----------------------------------------------------------------------------------------
    nd_num = 6,

    // Stores the extents of the node using a centered rectangle and half-size.
    nd_idx_mx = 0, nd_idx_my = 1, nd_idx_sx = 2, nd_idx_sy = 3,

    // Stores the index of the node.
    nd_idx_index = 4,

    // Stores the depth of the node.
    nd_idx_depth = 5,
};

static void node_insert(Quadtree* qt, int index, int depth, int mx, int my, int sx, int sy, int element);

static int floor_int(float val)
{
    return (int)val;
}

static int intersect(int l1, int t1, int r1, int b1,
                     int l2, int t2, int r2, int b2)
{
    return l2 <= r1 && r2 >= l1 && t2 <= b1 && b2 >= t1;
}

void leaf_insert(Quadtree* qt, int node, int depth, int mx, int my, int sx, int sy, int element)
{
    // Insert the element node to the leaf.
    const int nd_fc = il_get(&qt->nodes, node, node_idx_fc);
    il_set(&qt->nodes, node, node_idx_fc, il_insert(&qt->enodes));
    il_set(&qt->enodes, il_get(&qt->nodes, node, node_idx_fc), enode_idx_next, nd_fc);
    il_set(&qt->enodes, il_get(&qt->nodes, node, node_idx_fc), enode_idx_elt, element);

    // If the leaf is full, split it.
    if (il_get(&qt->nodes, node, node_idx_num) == qt->max_elements && depth < qt->max_depth)
    {
        int fc = 0, j = 0;
        IntList elts = {0};
        il_create(&elts, 1);

        // Transfer elements from the leaf node to a list of elements.
        while (il_get(&qt->nodes, node, node_idx_fc) != -1)
        {
            const int index = il_get(&qt->nodes, node, node_idx_fc);
            const int next_index = il_get(&qt->enodes, index, enode_idx_next);
            const int elt = il_get(&qt->enodes, index, enode_idx_elt);

            // Pop off the element node from the leaf and remove it from the qt.
            il_set(&qt->nodes, node, node_idx_fc, next_index);
            il_erase(&qt->enodes, index);

            // Insert element to the list.
            il_set(&elts, il_push_back(&elts), 0, elt);
        }

        // Start by allocating 4 child nodes.
        fc = il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_insert(&qt->nodes);
        il_set(&qt->nodes, node, node_idx_fc, fc);

        // Initialize the new child nodes.
        for (j=0; j < 4; ++j)
        {
            il_set(&qt->nodes, fc+j, node_idx_fc, -1);
            il_set(&qt->nodes, fc+j, node_idx_num, 0);
        }

        // Transfer the elements in the former leaf node to its new children.
        il_set(&qt->nodes, node, node_idx_num, -1);
        for (j=0; j < il_size(&elts); ++j)
            node_insert(qt, node, depth, mx, my, sx, sy, il_get(&elts, j, 0));
        il_destroy(&elts);
    }
    else
    {
        // Increment the leaf element count.
        il_set(&qt->nodes, node, node_idx_num, il_get(&qt->nodes, node, node_idx_num) + 1);
    }
}

static void push_node(IntList* nodes, int nd_index, int nd_depth, int nd_mx, int nd_my, int nd_sx, int nd_sy)
{
    const int back_idx = il_push_back(nodes);
    il_set(nodes, back_idx, nd_idx_mx, nd_mx);
    il_set(nodes, back_idx, nd_idx_my, nd_my);
    il_set(nodes, back_idx, nd_idx_sx, nd_sx);
    il_set(nodes, back_idx, nd_idx_sy, nd_sy);
    il_set(nodes, back_idx, nd_idx_index, nd_index);
    il_set(nodes, back_idx, nd_idx_depth, nd_depth);
}

static void find_leaves(IntList* out, const Quadtree* qt, int node, int depth, 
                        int mx, int my, int sx, int sy, 
                        int lft, int top, int rgt, int btm)
{
    IntList to_process = {0};
    il_create(&to_process, nd_num);
    push_node(&to_process, node, depth, mx, my, sx, sy);

    while (il_size(&to_process) > 0)
    {
        const int back_idx = il_size(&to_process) - 1;
        const int nd_mx = il_get(&to_process, back_idx, nd_idx_mx);
        const int nd_my = il_get(&to_process, back_idx, nd_idx_my);
        const int nd_sx = il_get(&to_process, back_idx, nd_idx_sx);
        const int nd_sy = il_get(&to_process, back_idx, nd_idx_sy);
        const int nd_index = il_get(&to_process, back_idx, nd_idx_index);
        const int nd_depth = il_get(&to_process, back_idx, nd_idx_depth);
        il_pop_back(&to_process);

        // If this node is a leaf, insert it to the list.
        if (il_get(&qt->nodes, nd_index, node_idx_num) != -1)
            push_node(out, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        else
        {
            // Otherwise push the children that intersect the rectangle.
            const int fc = il_get(&qt->nodes, nd_index, node_idx_fc);
            const int hx = nd_sx >> 1, hy = nd_sy >> 1;
            const int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;

            if (top <= nd_my)
            {
                if (lft <= nd_mx)
                    push_node(&to_process, fc+0, nd_depth+1, l,t,hx,hy);
                if (rgt > nd_mx)
                    push_node(&to_process, fc+1, nd_depth+1, r,t,hx,hy);
            }
            if (btm > nd_my)
            {
                if (lft <= nd_mx)
                    push_node(&to_process, fc+2, nd_depth+1, l,b,hx,hy);
                if (rgt > nd_mx)
                    push_node(&to_process, fc+3, nd_depth+1, r,b,hx,hy);
            }
        }
    }
    il_destroy(&to_process);
}

static void node_insert(Quadtree* qt, int index, int depth, int mx, int my, int sx, int sy, int element)
{
    // Find the leaves and insert the element to all the leaves found.
    int j = 0;
    IntList leaves = {0};
    
    const int lft = il_get(&qt->elts, element, elt_idx_lft);
    const int top = il_get(&qt->elts, element, elt_idx_top);
    const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
    const int btm = il_get(&qt->elts, element, elt_idx_btm);

    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, index, depth, mx, my, sx, sy, lft, top, rgt, btm);
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_mx = il_get(&leaves, j, nd_idx_mx);
        const int nd_my = il_get(&leaves, j, nd_idx_my);
        const int nd_sx = il_get(&leaves, j, nd_idx_sx);
        const int nd_sy = il_get(&leaves, j, nd_idx_sy);
        const int nd_index = il_get(&leaves, j, nd_idx_index);
        const int nd_depth = il_get(&leaves, j, nd_idx_depth);
        leaf_insert(qt, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy, element);
    }
    il_destroy(&leaves);
}

void qt_create(Quadtree* qt, int width, int height, int max_elements, int max_depth)
{
    qt->max_elements = max_elements;
    qt->max_depth = max_depth;
    qt->temp = 0;
    qt->temp_size = 0;
    il_create(&qt->nodes, node_num);
    il_create(&qt->elts, elt_num);
    il_create(&qt->enodes, enode_num);

    // Insert the root node to the qt.
    il_insert(&qt->nodes);
    il_set(&qt->nodes, 0, node_idx_fc, -1);
    il_set(&qt->nodes, 0, node_idx_num, 0);

    // Set the extents of the root node.
    qt->root_mx = width >> 1;
    qt->root_my = height >> 1;
    qt->root_sx = qt->root_mx;
    qt->root_sy = qt->root_my;
}

void qt_destroy(Quadtree* qt)
{
    il_destroy(&qt->nodes);
    il_destroy(&qt->elts);
    il_destroy(&qt->enodes);
    free(qt->temp);
}

int qt_insert(Quadtree* qt, int id, float x1, float y1, float x2, float y2)
{
    // Insert a new element.
    const int new_element = il_insert(&qt->elts);

    // Set the fields of the new element.
    il_set(&qt->elts, new_element, elt_idx_lft, floor_int(x1));
    il_set(&qt->elts, new_element, elt_idx_top, floor_int(y1));
    il_set(&qt->elts, new_element, elt_idx_rgt, floor_int(x2));
    il_set(&qt->elts, new_element, elt_idx_btm, floor_int(y2));
    il_set(&qt->elts, new_element, elt_idx_id, id);

    // Insert the element to the appropriate leaf node(s).
    node_insert(qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, new_element);
    return new_element;
}

void qt_remove(Quadtree* qt, int element)
{
    // Find the leaves.
    int j = 0;
    IntList leaves = {0};

    const int lft = il_get(&qt->elts, element, elt_idx_lft);
    const int top = il_get(&qt->elts, element, elt_idx_top);
    const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
    const int btm = il_get(&qt->elts, element, elt_idx_btm);

    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, lft, top, rgt, btm);

    // For each leaf node, remove the element node.
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_index = il_get(&leaves, j, nd_idx_index);

        // Walk the list until we find the element node.
        int node_index = il_get(&qt->nodes, nd_index, node_idx_fc);
        int prev_index = -1;
        while (node_index != -1 && il_get(&qt->enodes, node_index, enode_idx_elt) != element)
        {
            prev_index = node_index;
            node_index = il_get(&qt->enodes, node_index, enode_idx_next);
        }

        if (node_index != -1)
        {
            // Remove the element node.
            const int next_index = il_get(&qt->enodes, node_index, enode_idx_next);
            if (prev_index == -1)
                il_set(&qt->nodes, nd_index, node_idx_fc, next_index);
            else
                il_set(&qt->enodes, prev_index, enode_idx_next, next_index);
            il_erase(&qt->enodes, node_index);

            // Decrement the leaf element count.
            il_set(&qt->nodes, nd_index, node_idx_num, il_get(&qt->nodes, nd_index, node_idx_num)-1);
        }
    }
    il_destroy(&leaves);

    // Remove the element.
    il_erase(&qt->elts, element);
}

void qt_query(Quadtree* qt, IntList* out, float x1, float y1, float x2, float y2, int omit_element)
{
    // Find the leaves that intersect the specified query rectangle.
    int j = 0;
    IntList leaves = {0};
    const int elt_cap = il_size(&qt->elts);

    const int qlft = floor_int(x1);
    const int qtop = floor_int(y1);
    const int qrgt = floor_int(x2);
    const int qbtm = floor_int(y2);

    if (qt->temp_size < elt_cap)
    {
        qt->temp_size = elt_cap;
        qt->temp = realloc(qt->temp, qt->temp_size * sizeof(*qt->temp));
        memset(qt->temp, 0, qt->temp_size * sizeof(*qt->temp));
    }

    // For each leaf node, look for elements that intersect.
    il_create(&leaves, nd_num);
    find_leaves(&leaves, qt, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy, qlft, qtop, qrgt, qbtm);

    il_clear(out);
    for (j=0; j < il_size(&leaves); ++j)
    {
        const int nd_index = il_get(&leaves, j, nd_idx_index);

        // Walk the list and add elements that intersect.
        int elt_node_index = il_get(&qt->nodes, nd_index, node_idx_fc);
        while (elt_node_index != -1)
        {
            const int element = il_get(&qt->enodes, elt_node_index, enode_idx_elt);
            const int lft = il_get(&qt->elts, element, elt_idx_lft);
            const int top = il_get(&qt->elts, element, elt_idx_top);
            const int rgt = il_get(&qt->elts, element, elt_idx_rgt);
            const int btm = il_get(&qt->elts, element, elt_idx_btm);
            if (!qt->temp[element] && element != omit_element && intersect(qlft,qtop,qrgt,qbtm, lft,top,rgt,btm))
            {
                il_set(out, il_push_back(out), 0, element);
                qt->temp[element] = 1;
            }
            elt_node_index = il_get(&qt->enodes, elt_node_index, enode_idx_next);
        }
    }
    il_destroy(&leaves);

    // Unmark the elements that were inserted.
    for (j=0; j < il_size(out); ++j)
        qt->temp[il_get(out, j, 0)] = 0;
}

void qt_cleanup(Quadtree* qt)
{
    IntList to_process = {0};
    il_create(&to_process, 1);

    // Only process the root if it's not a leaf.
    if (il_get(&qt->nodes, 0, node_idx_num) == -1)
    {
        // Push the root index to the stack.
        il_set(&to_process, il_push_back(&to_process), 0, 0);
    }

    while (il_size(&to_process) > 0)
    {
        // Pop a node from the stack.
        const int node = il_get(&to_process, il_size(&to_process)-1, 0);
        const int fc = il_get(&qt->nodes, node, node_idx_fc);
        int num_empty_leaves = 0;
        int j = 0;
        il_pop_back(&to_process);

        // Loop through the children.
        for (j=0; j < 4; ++j)
        {
            const int child = fc + j;

            // Increment empty leaf count if the child is an empty 
            // leaf. Otherwise if the child is a branch, add it to
            // the stack to be processed in the next iteration.
            if (il_get(&qt->nodes, child, node_idx_num) == 0)
                ++num_empty_leaves;
            else if (il_get(&qt->nodes, child, node_idx_num) == -1)
            {
                // Push the child index to the stack.
                il_set(&to_process, il_push_back(&to_process), 0, child);
            }
        }

        // If all the children were empty leaves, remove them and 
        // make this node the new empty leaf.
        if (num_empty_leaves == 4)
        {
            // Remove all 4 children in reverse order so that they 
            // can be reclaimed on subsequent insertions in proper
            // order.
            il_erase(&qt->nodes, fc + 3);
            il_erase(&qt->nodes, fc + 2);
            il_erase(&qt->nodes, fc + 1);
            il_erase(&qt->nodes, fc + 0);

            // Make this node the new empty leaf.
            il_set(&qt->nodes, node, node_idx_fc, -1);
            il_set(&qt->nodes, node, node_idx_num, 0);
        }
    }
    il_destroy(&to_process);
}

void qt_traverse(Quadtree* qt, void* user_data, QtNodeFunc* branch, QtNodeFunc* leaf)
{
    IntList to_process = {0};
    il_create(&to_process, nd_num);
    push_node(&to_process, 0, 0, qt->root_mx, qt->root_my, qt->root_sx, qt->root_sy);

    while (il_size(&to_process) > 0)
    {
        const int back_idx = il_size(&to_process) - 1;
        const int nd_mx = il_get(&to_process, back_idx, nd_idx_mx);
        const int nd_my = il_get(&to_process, back_idx, nd_idx_my);
        const int nd_sx = il_get(&to_process, back_idx, nd_idx_sx);
        const int nd_sy = il_get(&to_process, back_idx, nd_idx_sy);
        const int nd_index = il_get(&to_process, back_idx, nd_idx_index);
        const int nd_depth = il_get(&to_process, back_idx, nd_idx_depth);
        const int fc = il_get(&qt->nodes, nd_index, node_idx_fc);
        il_pop_back(&to_process);

        if (il_get(&qt->nodes, nd_index, node_idx_num) == -1)
        {
            // Push the children of the branch to the stack.
            const int hx = nd_sx >> 1, hy = nd_sy >> 1;
            const int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
            push_node(&to_process, fc+0, nd_depth+1, l,t, hx,hy);
            push_node(&to_process, fc+1, nd_depth+1, r,t, hx,hy);
            push_node(&to_process, fc+2, nd_depth+1, l,b, hx,hy);
            push_node(&to_process, fc+3, nd_depth+1, r,b, hx,hy);
            if (branch)
                branch(qt, user_data, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        }
        else if (leaf)
            leaf(qt, user_data, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
    }
    il_destroy(&to_process);
}

Временное заключение

Это не такой уж хороший ответ, но я постараюсь вернуться и продолжить его редактирование. Однако приведенный выше код должен быть очень эффективным практически на любом языке, который допускает непрерывные массивы простых старых целых чисел. Пока у нас есть эта гарантия непрерывности, мы можем создать очень удобное для кэширования дерево квадрантов, которое использует очень небольшой объем памяти.

Пожалуйста, обратитесь к исходному ответу для получения подробной информации об общем подходе.

Грязный трюк: единые размеры

Для этого ответа я расскажу о закулисном трюке, который может позволить вашей симуляции работать на порядок быстрее, если данные подходят (что часто будет, например, во многих видеоиграх). Вы можете получить от десятков тысяч до сотен тысяч агентов или от сотен тысяч агентов до миллионов агентов. Я пока не применял его ни в одной из демонстраций, показанных в моих ответах, так как это немного обман, но я использовал его в производстве, и это может иметь огромное значение. И как ни странно, я не вижу, чтобы это обсуждалось так часто. На самом деле я никогда не видел, чтобы это обсуждалось, что странно.

Итак, вернемся к примеру с «Властелином колец». У нас есть много юнитов человеческого размера, таких как люди, эльфы, гномы, орки и хоббиты, а также у нас есть несколько гигантских юнитов, таких как драконы и энты.

Единицы человеческого размера не сильно различаются по размеру. Хоббит может быть четырех футов ростом и немного коренастым, орк может быть 6 футов 4 дюйма. Разница есть, но не грандиозная. Это не на порядок разница.

Так что же произойдет, если мы поместим вокруг хоббита ограничивающую сферу/рамку размером с ограничивающую сферу/рамку орка только ради грубых запросов пересечения (прежде чем мы перейдем к проверке более истинного столкновения на детальном/тонком уровне )? Есть немного потерянного негативного пространства, но происходит кое-что действительно интересное.

Если мы можем предвидеть такую ​​верхнюю границу для единиц общего случая, мы можем хранить их в структуре данных, которая предполагает, что все вещи имеют одинаковую верхнюю границу размера. В этом случае происходит несколько действительно интересных вещей:

1. Нам не нужно хранить размер с каждым элементом. Структура данных может предполагать, что все вставленные в нее элементы имеют одинаковый размер (просто для целей запросов грубого пересечения). Это может почти вдвое сократить использование памяти для элементов во многих сценариях и естественным образом ускоряет обход, когда у нас меньше памяти/данных для доступа к каждому элементу.
2. Мы можем хранить элементы только в одной ячейке/узле, даже для плотных представлений, в которых нет AABB переменного размера, хранящихся в ячейках/узлах.

Сохранение только одной точки

Эта вторая часть сложна, но представьте, что у нас есть такой случай:

Ну, если мы посмотрим на зеленый круг и найдем его радиус, мы в конечном итоге пропустим центральную точку синего круга, если он будет храниться только как одна точка в нашем пространственном индексе. Но что, если мы будем искать область, в два раза превышающую радиус наших кругов?

В этом случае мы бы нашли пересечение, даже если синий круг хранится только как единственная точка в нашем пространственном индексе (центральная точка оранжевого цвета). Просто чтобы визуально показать, что это работает:

В этом случае круги не пересекаются, и мы видим, что центральная точка находится за пределами даже расширенного удвоенного радиуса поиска. Таким образом, пока мы ищем удвоенный радиус в пространственном индексе, который предполагает, что все элементы имеют одинаковый размер верхней границы, мы гарантированно найдем их в грубом запросе, если мы ищем область, удвоенную радиусом верхней границы (или вдвое больше прямоугольного половинного размера для AABB).

Теперь это может показаться расточительным, поскольку в наших поисковых запросах будет проверяться больше ячеек/узлов, чем необходимо, но это только потому, что я нарисовал диаграмму в иллюстративных целях. Если вы используете эту стратегию, вы должны использовать ее для элементов, размеры которых обычно составляют часть размера одного конечного узла/ячейки.

Огромная оптимизация

Таким образом, огромная оптимизация, которую вы можете применить, — это разделить ваш контент на 3 разных типа:

1. Динамический набор (постоянно движущийся и анимирующийся) с обычной верхней границей, такой как люди, орки, эльфы и хоббиты. По сути, мы помещаем ограничивающую рамку/сферу одинакового размера вокруг всех этих агентов. Здесь вы можете использовать плотное представление, такое как плотное дерево квадрантов или плотную сетку, и оно будет хранить только одну точку для каждого элемента. Вы также можете использовать другой экземпляр этой же структуры для супермаленьких элементов, таких как феи и огоньки, с другим общим размером верхней границы.
2. Динамический набор больше, чем любая предсказуемая верхняя граница общего случая, как драконы и энты очень необычных размеров. Здесь вы можете использовать свободное представление, такое как свободное дерево квадрантов или мою свободную/узкую двойную сетку.
3. Статический набор, в котором вы можете позволить себе структуры, которые требуют больше времени для создания или очень неэффективны для обновления, например, дерево квадрантов для статических данных, в котором все хранится идеально непрерывным образом. В этом случае не имеет значения, насколько неэффективно обновлять структуру данных, если она обеспечивает самые быстрые поисковые запросы, поскольку вы никогда не будете ее обновлять. Вы можете использовать это для элементов в вашем мире, таких как замки, баррикады и валуны.

Таким образом, эта идея разделения элементов общего случая с одинаковыми границами сверху (ограничивающие сферы или прямоугольники) может быть чрезвычайно полезной стратегией оптимизации, если вы сможете ее применить. Это также то, что я не вижу в обсуждении. Я часто вижу, как разработчики говорят о разделении динамического и статического содержимого, но вы можете получить такое же улучшение, если не большее, путем дальнейшей группировки обычных динамических элементов одинакового размера и обращения с ними так, как будто они имеют одинаковые верхние пределы размеров для вашего грубые тесты на столкновение, которые позволяют хранить их как бесконечно малую точку, которая вставляется только в один конечный узел в вашей плотной структуре данных.

О преимуществах обмана

Так что это решение не особенно умное или интересное, но мышление, стоящее за ним, заслуживает упоминания, по крайней мере, для таких, как я. Я потратил большую часть своей карьеры на поиски решений uber: универсальных структур данных и алгоритмов, которые прекрасно справляются с любым вариантом использования, в надежде, что я смогу потратить немного больше времени заранее, чтобы сделать это правильно и затем повторно используйте его как сумасшедший далеко в будущем и в разных случаях использования, не говоря уже о работе со многими коллегами, которые искали то же самое.

А в сценариях, где производительность не может быть слишком сильно скомпрометирована в пользу производительности, усердный поиск таких решений может привести ни к производительности, ни к производительности. Так что иногда полезно просто остановиться и посмотреть на характер конкретных требований к данным для программного обеспечения и посмотреть, можем ли мы обмануть и создать какие-то адаптированные, более узко применимые решения для этих специфических требований, как в этом примере. Иногда это самый полезный способ получить хорошее сочетание производительности и производительности в тех случаях, когда нельзя слишком сильно скомпрометировать одно в пользу другого.

4. Java IntList

Я надеюсь, что люди не возражают, что я публикую третий ответ, но я снова исчерпал лимит символов. Я закончил перенос кода C во втором ответе на Java. Порт Java может быть проще для тех, кто занимается переносом на объектно-ориентированные языки.

class IntList
{
    private int data[] = new int[128];
    private int num_fields = 0;
    private int num = 0;
    private int cap = 128;
    private int free_element = -1;

    // Creates a new list of elements which each consist of integer fields.
    // 'start_num_fields' specifies the number of integer fields each element has.
    public IntList(int start_num_fields)
    {
        num_fields = start_num_fields;
    }

    // Returns the number of elements in the list.
    int size()
    {
        return num;
    }

    // Returns the value of the specified field for the nth element.
    int get(int n, int field)
    {
        assert n >= 0 && n < num && field >= 0 && field < num_fields;
        return data[n*num_fields + field];
    }

    // Sets the value of the specified field for the nth element.
    void set(int n, int field, int val)
    {
        assert n >= 0 && n < num && field >= 0 && field < num_fields;
        data[n*num_fields + field] = val;
    }

    // Clears the list, making it empty.
    void clear()
    {
        num = 0;
        free_element = -1;
    }

    // Inserts an element to the back of the list and returns an index to it.
    int pushBack()
    {
        final int new_pos = (num+1) * num_fields;
        
        // If the list is full, we need to reallocate the buffer to make room
        // for the new element.
        if (new_pos > cap)
        {
            // Use double the size for the new capacity.
            final int new_cap = new_pos * 2;

            // Allocate new array and copy former contents.
            int new_array[] = new int[new_cap];
            System.arraycopy(data, 0, new_array, 0, cap);
            data = new_array;
    
            // Set the old capacity to the new capacity.
            cap = new_cap;
        }
        return num++;
    }
    
    // Removes the element at the back of the list.
    void popBack()
    {
        // Just decrement the list size.
        assert num > 0;
        --num;
    }

    // Inserts an element to a vacant position in the list and returns an index to it.
    int insert()
    {
        // If there's a free index in the free list, pop that and use it.
        if (free_element != -1)
        {
            final int index = free_element;
            final int pos = index * num_fields;
    
            // Set the free index to the next free index.
            free_element = data[pos];
    
            // Return the free index.
            return index;
        }
        // Otherwise insert to the back of the array.
        return pushBack();
    }

    // Removes the nth element in the list.
    void erase(int n)
    {
        // Push the element to the free list.
        final int pos = n * num_fields;
        data[pos] = free_element;
        free_element = n;
    }
}

Java Quadtree

А вот дерево квадрантов в Java (извините, если это не очень идиоматично, я не писал на Java около десяти лет и многое забыл):

interface IQtVisitor
{
    // Called when traversing a branch node.
    // (mx, my) indicate the center of the node's AABB.
    // (sx, sy) indicate the half-size of the node's AABB.
    void branch(Quadtree qt, int node, int depth, int mx, int my, int sx, int sy);

    // Called when traversing a leaf node.
    // (mx, my) indicate the center of the node's AABB.
    // (sx, sy) indicate the half-size of the node's AABB.
    void leaf(Quadtree qt, int node, int depth, int mx, int my, int sx, int sy);
}

class Quadtree
{
    // Creates a quadtree with the requested extents, maximum elements per leaf, and maximum tree depth.
    Quadtree(int width, int height, int start_max_elements, int start_max_depth)
    {
        max_elements = start_max_elements;
        max_depth = start_max_depth;

        // Insert the root node to the qt.
        nodes.insert();
        nodes.set(0, node_idx_fc, -1);
        nodes.set(0, node_idx_num, 0);

        // Set the extents of the root node.
        root_mx = width / 2;
        root_my = height / 2;
        root_sx = root_mx;
        root_sy = root_my;
    }

    // Outputs a list of elements found in the specified rectangle.
    public int insert(int id, float x1, float y1, float x2, float y2)
    {
        // Insert a new element.
        final int new_element = elts.insert();
    
        // Set the fields of the new element.
        elts.set(new_element, elt_idx_lft, floor_int(x1));
        elts.set(new_element, elt_idx_top, floor_int(y1));
        elts.set(new_element, elt_idx_rgt, floor_int(x2));
        elts.set(new_element, elt_idx_btm, floor_int(y2));
        elts.set(new_element, elt_idx_id, id);
    
        // Insert the element to the appropriate leaf node(s).
        node_insert(0, 0, root_mx, root_my, root_sx, root_sy, new_element);
        return new_element;
    }

    // Removes the specified element from the tree.
    public void remove(int element)
    {
        // Find the leaves.
        final int lft = elts.get(element, elt_idx_lft);
        final int top = elts.get(element, elt_idx_top);
        final int rgt = elts.get(element, elt_idx_rgt);
        final int btm = elts.get(element, elt_idx_btm);
        IntList leaves = find_leaves(0, 0, root_mx, root_my, root_sx, root_sy, lft, top, rgt, btm);
    
        // For each leaf node, remove the element node.
        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_index = leaves.get(j, nd_idx_index);
    
            // Walk the list until we find the element node.
            int node_index = nodes.get(nd_index, node_idx_fc);
            int prev_index = -1;
            while (node_index != -1 && enodes.get(node_index, enode_idx_elt) != element)
            {
                prev_index = node_index;
                node_index = enodes.get(node_index, enode_idx_next);
            }
    
            if (node_index != -1)
            {
                // Remove the element node.
                final int next_index = enodes.get(node_index, enode_idx_next);
                if (prev_index == -1)
                    nodes.set(nd_index, node_idx_fc, next_index);
                else
                    enodes.set(prev_index, enode_idx_next, next_index);
                enodes.erase(node_index);

                // Decrement the leaf element count.
                nodes.set(nd_index, node_idx_num, nodes.get(nd_index, node_idx_num)-1);
            }
        }

        // Remove the element.
        elts.erase(element);
    }

    // Cleans up the tree, removing empty leaves.
    public void cleanup()
    {
        IntList to_process = new IntList(1);

        // Only process the root if it's not a leaf.
        if (nodes.get(0, node_idx_num) == -1)
        {
            // Push the root index to the stack.
            to_process.set(to_process.pushBack(), 0, 0);
        }
    
        while (to_process.size() > 0)
        {
            // Pop a node from the stack.
            final int node = to_process.get(to_process.size()-1, 0);
            final int fc = nodes.get(node, node_idx_fc);
            int num_empty_leaves = 0;
            to_process.popBack();
    
            // Loop through the children.
            for (int j=0; j < 4; ++j)
            {
                final int child = fc + j;
    
                // Increment empty leaf count if the child is an empty 
                // leaf. Otherwise if the child is a branch, add it to
                // the stack to be processed in the next iteration.
                if (nodes.get(child, node_idx_num) == 0)
                    ++num_empty_leaves;
                else if (nodes.get(child, node_idx_num) == -1)
                {
                    // Push the child index to the stack.
                    to_process.set(to_process.pushBack(), 0, child);
                }
            }
    
            // If all the children were empty leaves, remove them and 
            // make this node the new empty leaf.
            if (num_empty_leaves == 4)
            {
                // Remove all 4 children in reverse order so that they 
                // can be reclaimed on subsequent insertions in proper
                // order.
                nodes.erase(fc + 3);
                nodes.erase(fc + 2);
                nodes.erase(fc + 1);
                nodes.erase(fc + 0);
    
                // Make this node the new empty leaf.
                nodes.set(node, node_idx_fc, -1);
                nodes.set(node, node_idx_num, 0);
            }
        }
    }

    // Returns a list of elements found in the specified rectangle.
    public IntList query(float x1, float y1, float x2, float y2)
    {
        return query(x1, y1, x2, y2, -1);
    }
    
    // Returns a list of elements found in the specified rectangle excluding the
    // specified element to omit.
    public IntList query(float x1, float y1, float x2, float y2, int omit_element)
    {
        IntList out = new IntList(1);

        // Find the leaves that intersect the specified query rectangle.
        final int qlft = floor_int(x1);
        final int qtop = floor_int(y1);
        final int qrgt = floor_int(x2);
        final int qbtm = floor_int(y2);
        IntList leaves = find_leaves(0, 0, root_mx, root_my, root_sx, root_sy, qlft, qtop, qrgt, qbtm);

        if (temp_size < elts.size())
        {
            temp_size = elts.size();
            temp = new boolean[temp_size];;
        }
    
        // For each leaf node, look for elements that intersect.
        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_index = leaves.get(j, nd_idx_index);
    
            // Walk the list and add elements that intersect.
            int elt_node_index = nodes.get(nd_index, node_idx_fc);
            while (elt_node_index != -1)
            {
                final int element = enodes.get(elt_node_index, enode_idx_elt);
                final int lft = elts.get(element, elt_idx_lft);
                final int top = elts.get(element, elt_idx_top);
                final int rgt = elts.get(element, elt_idx_rgt);
                final int btm = elts.get(element, elt_idx_btm);
                if (!temp[element] && element != omit_element && intersect(qlft,qtop,qrgt,qbtm, lft,top,rgt,btm))
                {
                    out.set(out.pushBack(), 0, element);
                    temp[element] = true;
                }
                elt_node_index = enodes.get(elt_node_index, enode_idx_next);
            }
        }

        // Unmark the elements that were inserted.
        for (int j=0; j < out.size(); ++j)
            temp[out.get(j, 0)] = false;
        return out;
    }

    // Traverses all the nodes in the tree, calling 'branch' for branch nodes and 'leaf' 
    // for leaf nodes.
    public void traverse(IQtVisitor visitor)
    {
        IntList to_process = new IntList(nd_num);
        pushNode(to_process, 0, 0, root_mx, root_my, root_sx, root_sy);
    
        while (to_process.size() > 0)
        {
            final int back_idx = to_process.size() - 1;
            final int nd_mx = to_process.get(back_idx, nd_idx_mx);
            final int nd_my = to_process.get(back_idx, nd_idx_my);
            final int nd_sx = to_process.get(back_idx, nd_idx_sx);
            final int nd_sy = to_process.get(back_idx, nd_idx_sy);
            final int nd_index = to_process.get(back_idx, nd_idx_index);
            final int nd_depth = to_process.get(back_idx, nd_idx_depth);
            final int fc = nodes.get(nd_index, node_idx_fc);
            to_process.popBack();
    
            if (nodes.get(nd_index, node_idx_num) == -1)
            {
                // Push the children of the branch to the stack.
                final int hx = nd_sx >> 1, hy = nd_sy >> 1;
                final int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
                pushNode(to_process, fc+0, nd_depth+1, l,t, hx,hy);
                pushNode(to_process, fc+1, nd_depth+1, r,t, hx,hy);
                pushNode(to_process, fc+2, nd_depth+1, l,b, hx,hy);
                pushNode(to_process, fc+3, nd_depth+1, r,b, hx,hy);
                visitor.branch(this, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
            }
            else
                visitor.leaf(this, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
        }
    }

    private static int floor_int(float val)
    {
        return (int)val;
    }
    
    private static boolean intersect(int l1, int t1, int r1, int b1,
                                     int l2, int t2, int r2, int b2)
    {
        return l2 <= r1 && r2 >= l1 && t2 <= b1 && b2 >= t1;
    }

    private static void pushNode(IntList nodes, int nd_index, int nd_depth, int nd_mx, int nd_my, int nd_sx, int nd_sy)
    {
        final int back_idx = nodes.pushBack();
        nodes.set(back_idx, nd_idx_mx, nd_mx);
        nodes.set(back_idx, nd_idx_my, nd_my);
        nodes.set(back_idx, nd_idx_sx, nd_sx);
        nodes.set(back_idx, nd_idx_sy, nd_sy);
        nodes.set(back_idx, nd_idx_index, nd_index);
        nodes.set(back_idx, nd_idx_depth, nd_depth);
    }

    private IntList find_leaves(int node, int depth, 
                                int mx, int my, int sx, int sy, 
                                int lft, int top, int rgt, int btm)
    {
        IntList leaves = new IntList(nd_num);
        IntList to_process = new IntList(nd_num);
        pushNode(to_process, node, depth, mx, my, sx, sy);
    
        while (to_process.size() > 0)
        {
            final int back_idx = to_process.size() - 1;
            final int nd_mx = to_process.get(back_idx, nd_idx_mx);
            final int nd_my = to_process.get(back_idx, nd_idx_my);
            final int nd_sx = to_process.get(back_idx, nd_idx_sx);
            final int nd_sy = to_process.get(back_idx, nd_idx_sy);
            final int nd_index = to_process.get(back_idx, nd_idx_index);
            final int nd_depth = to_process.get(back_idx, nd_idx_depth);
            to_process.popBack();

            // If this node is a leaf, insert it to the list.
            if (nodes.get(nd_index, node_idx_num) != -1)
                pushNode(leaves, nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy);
            else
            {
                // Otherwise push the children that intersect the rectangle.
                final int fc = nodes.get(nd_index, node_idx_fc);
                final int hx = nd_sx / 2, hy = nd_sy / 2;
                final int l = nd_mx-hx, t = nd_my-hx, r = nd_mx+hx, b = nd_my+hy;
    
                if (top <= nd_my)
                {
                    if (lft <= nd_mx)
                        pushNode(to_process, fc+0, nd_depth+1, l,t,hx,hy);
                    if (rgt > nd_mx)
                        pushNode(to_process, fc+1, nd_depth+1, r,t,hx,hy);
                }
                if (btm > nd_my)
                {
                    if (lft <= nd_mx)
                        pushNode(to_process, fc+2, nd_depth+1, l,b,hx,hy);
                    if (rgt > nd_mx)
                        pushNode(to_process, fc+3, nd_depth+1, r,b,hx,hy);
                }
            }
        }
        return leaves;
    }

    private void node_insert(int index, int depth, int mx, int my, int sx, int sy, int element)
    {
        // Find the leaves and insert the element to all the leaves found.
        final int lft = elts.get(element, elt_idx_lft);
        final int top = elts.get(element, elt_idx_top);
        final int rgt = elts.get(element, elt_idx_rgt);
        final int btm = elts.get(element, elt_idx_btm);
        IntList leaves = find_leaves(index, depth, mx, my, sx, sy, lft, top, rgt, btm);

        for (int j=0; j < leaves.size(); ++j)
        {
            final int nd_mx = leaves.get(j, nd_idx_mx);
            final int nd_my = leaves.get(j, nd_idx_my);
            final int nd_sx = leaves.get(j, nd_idx_sx);
            final int nd_sy = leaves.get(j, nd_idx_sy);
            final int nd_index = leaves.get(j, nd_idx_index);
            final int nd_depth = leaves.get(j, nd_idx_depth);
            leaf_insert(nd_index, nd_depth, nd_mx, nd_my, nd_sx, nd_sy, element);
        }
    }

    private void leaf_insert(int node, int depth, int mx, int my, int sx, int sy, int element)
    {
        // Insert the element node to the leaf.
        final int nd_fc = nodes.get(node, node_idx_fc);
        nodes.set(node, node_idx_fc, enodes.insert());
        enodes.set(nodes.get(node, node_idx_fc), enode_idx_next, nd_fc);
        enodes.set(nodes.get(node, node_idx_fc), enode_idx_elt, element);
    
        // If the leaf is full, split it.
        if (nodes.get(node, node_idx_num) == max_elements && depth < max_depth)
        {
            // Transfer elements from the leaf node to a list of elements.
            IntList elts = new IntList(1);
            while (nodes.get(node, node_idx_fc) != -1)
            {
                final int index = nodes.get(node, node_idx_fc);
                final int next_index = enodes.get(index, enode_idx_next);
                final int elt = enodes.get(index, enode_idx_elt);
    
                // Pop off the element node from the leaf and remove it from the qt.
                nodes.set(node, node_idx_fc, next_index);
                enodes.erase(index);
    
                // Insert element to the list.
                elts.set(elts.pushBack(), 0, elt);
            }
    
            // Start by allocating 4 child nodes.
            final int fc = nodes.insert();
            nodes.insert();
            nodes.insert();
            nodes.insert();
            nodes.set(node, node_idx_fc, fc);
    
            // Initialize the new child nodes.
            for (int j=0; j < 4; ++j)
            {
                nodes.set(fc+j, node_idx_fc, -1);
                nodes.set(fc+j, node_idx_num, 0);
            }
    
            // Transfer the elements in the former leaf node to its new children.
            nodes.set(node, node_idx_num, -1);
            for (int j=0; j < elts.size(); ++j)
                node_insert(node, depth, mx, my, sx, sy, elts.get(j, 0));
        }
        else
        {
            // Increment the leaf element count.
            nodes.set(node, node_idx_num, nodes.get(node, node_idx_num) + 1);
        }
    }


    // ----------------------------------------------------------------------------------------
    // Element node fields:
    // ----------------------------------------------------------------------------------------
    // Points to the next element in the leaf node. A value of -1 
    // indicates the end of the list.
    static final int enode_idx_next = 0;

    // Stores the element index.
    static final int enode_idx_elt = 1;

    // Stores all the element nodes in the quadtree.
    private IntList enodes = new IntList(2);

    // ----------------------------------------------------------------------------------------
    // Element fields:
    // ----------------------------------------------------------------------------------------
    // Stores the rectangle encompassing the element.
    static final int elt_idx_lft = 0, elt_idx_top = 1, elt_idx_rgt = 2, elt_idx_btm = 3;

    // Stores the ID of the element.
    static final int elt_idx_id = 4;

    // Stores all the elements in the quadtree.
    private IntList elts = new IntList(5);

    // ----------------------------------------------------------------------------------------
    // Node fields:
    // ----------------------------------------------------------------------------------------
    // Points to the first child if this node is a branch or the first element
    // if this node is a leaf.
    static final int node_idx_fc = 0;

    // Stores the number of elements in the node or -1 if it is not a leaf.
    static final int node_idx_num = 1;

    // Stores all the nodes in the quadtree. The first node in this
    // sequence is always the root.
    private IntList nodes = new IntList(2);

    // ----------------------------------------------------------------------------------------
    // Node data fields:
    // ----------------------------------------------------------------------------------------
    static final int nd_num = 6;

    // Stores the extents of the node using a centered rectangle and half-size.
    static final int nd_idx_mx = 0, nd_idx_my = 1, nd_idx_sx = 2, nd_idx_sy = 3;

    // Stores the index of the node.
    static final int nd_idx_index = 4;

    // Stores the depth of the node.
    static final int nd_idx_depth = 5;

    // ----------------------------------------------------------------------------------------
    // Data Members
    // ----------------------------------------------------------------------------------------
    // Temporary buffer used for queries.
    private boolean temp[];

    // Stores the size of the temporary buffer.
    private int temp_size = 0;

    // Stores the quadtree extents.
    private int root_mx, root_my, root_sx, root_sy;

    // Maximum allowed elements in a leaf before the leaf is subdivided/split unless
    // the leaf is at the maximum allowed tree depth.
    private int max_elements;

    // Stores the maximum depth allowed for the quadtree.
    private int max_depth;
}

Временное заключение

Еще раз извините, это что-то вроде ответа на свалку кода. Я вернусь и отредактирую его и попытаюсь объяснить все больше и больше вещей.

Пожалуйста, обратитесь к исходному ответу для получения подробной информации об общем подходе.