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

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

Вот несколько заметок о моем QuadTree

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

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

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

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


c++ recursion data-structures recursive-datastructures quadtree
person epitaque    schedule 15.07.2015    source источник
comment
Это может быть слишком много, чтобы пройти и просить. Если у вас есть какой-то конкретный код, и он не работает, вы можете разместить его здесь.   -  person Satish Chalasani    schedule 16.07.2015
comment
Самый простой способ — просто удалить, а затем снова добавить объект. Если вам нужна лучшая схема пространственного разделения для движущихся объектов, взгляните на свободные деревья квадрантов.   -  person Buddy    schedule 16.07.2015

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

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

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

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

person anthonyvd    schedule 30.07.2015

arrow_upward
0
arrow_downward

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

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

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

person Community    schedule 30.07.2015