Quadtree против красно-черного дерева для игры на C++?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

http://sites.google.com/a/compgeom.com/stann/< /а>