Quadtree vs Red-Black tree для игры на C++?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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