рекурсия — Как обновить QuadTree после перемещения объекта в C ++?

Question

рекурсия — Как обновить QuadTree после перемещения объекта в C ++?

Самый простой метод — удаление и вставка объекта, но, возможно, существуют более быстрые методы. (Если я обдумываю это, и я должен просто сделать это простым способом, дайте мне знать)

Вот некоторые заметки о моем QuadTree

Движущиеся объекты являются AABB и могут быть больше, чем
наименьший узел QuadTree.
Объекты не удаляются при создании дочерних QuadTrees. Тот
означает, что корневой QuadTree имеет указатель на каждый объект внутри
Квадрадерево.
Объекты хранятся в виде указателей в векторе вне QuadTree.

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

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

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

4

c++data-structures quadtree recursion recursive-datastructures

Решение

Другие решения

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

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

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

0

Источник

Accepted Answer

Это будет действительно трудно сделать лучше, чем удалить и снова вставить, особенно в вашем случае, так как:

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

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

void insert_from_leaf(object* o) {
if (!is_in_this_subtree(o)) {
parent->insert_from_leaf(o);
return;
}
find_child_node_for_object(o)->insert(0);
}

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

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

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

1