Quadtree vs Красно-черное дерево для игры на C ++?

Question

Я искал реализацию узла quadtree / quadtree в сети целую вечность. Есть некоторые базовые вещи, но нет ничего, что я мог бы реально использовать в игре.

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

Как бы я написал базовый, но полный класс дерева квадрантов (или октри) в C ++? Как бы вы использовали четырехугольное дерево для столкновений?

Answer 1

Quadtree используются, когда вам нужно только хранить вещи, которые находятся на плоскости. Как юниты в классической RTS, где они все на земле или чуть выше. По сути, каждый узел имеет ссылки на 4 дочерних элемента, которые делят пространство узла на равномерно распределенные кварталы.

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

Если вы ищете двоичное дерево - например, красно-черное дерево - тогда вы хотите использовать структуру данных, называемую бинарным деревом разбиения пространства (BSP-деревом), или ее версию, называемую KD-деревом. Они разделяют пространство пополам, используя плоскость, в дереве KD плоскости являются ортогональными (по осям XZ, XY, ZY), поэтому иногда это работает лучше в трехмерной сцене. Деревья BSP разделяют сцену, используя плоскости в любой ориентации, но они могут быть весьма полезны, и они использовались еще в Doom.

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

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

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

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

Answer 2

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

Answer 3

Причина использования квадродерева состоит в том, что вы можете разделить координаты x и y, октри на x, y и z, что делает обнаружение столкновений тривиальным.

Quadtree: если элемент не находится в топлете, он не будет сталкиваться с элементом в верхнем, нижнем левом или нижнем правом.

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

Я бы не писал такой класс, я просто позаимствовал бы его у проекта с подходящей лицензией.

Answer 4

Я настоятельно рекомендую вам использовать движок рендеринга, например, Ogre3D. Насколько я знаю, он поддерживает Octrees для управления сценой. Но вы можете расширить класс на основе Octree, как пожелаете. Раньше я сам кодировал то, что мне нужно, но для сложных проектов это просто не правильный путь.

Answer 5

Прямо сейчас STANN - лучшая реализация с открытым исходным кодом.

http://sites.google.com/a/compgeom.com/stann/

Answer 6

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

Скорее всего, вы захотите отсортировать ваши объекты на подвижные и статические и проверить все, что двигалось в данном кадре, на предмет статических объектов.

Деревья BSP являются приемлемым решением для статической геометрии (граничные случаи обрабатываются путем разбиения объекта на две части), для динамического использования что-то вроде Sort и Sweep (также известное как Sweep и Prune).