Как эффективно хранить игровые объекты в квадродереве
Я реализую структуру quadtree для упрощения кода коллизий. но я не уверен насчет наилучшей практики для этого. В настоящее время quadtree создает поддерево во время установки до заданной максимальной глубины, затем я вставляю объекты в соответствующее дерево для использования при генерации пар (фактические математические операции).
Тем не менее, я слышал о других подходах, которые генерируют поддеревья только при сохранении определенного количества объектов.
Я знаю, что мой метод требует много места, но может быть вычислительно быстрее во время циклов обновления.
Что было бы лучшим способом справиться с этим?
Решение
Один из подходов заключается в хранении k элементов в каждом узле, начиная с одного родительского узла, который охватывает все пространство коллизий. Вставляя элемент k + 1, вы разделяете пространство и помещаете новый элемент в правильный квадрант.
Кроме того, вы можете использовать этот подход для статического размещения структуры данных, предполагая, что вы знаете максимальное количество узлов, которые будут использоваться, и что будет некоторая максимальная плотность. Это требует фиксированного массива узлов и элементов, которые должны быть выделены на весь срок службы приложения, но это позволяет избежать дорогостоящих динамических распределений, которые должны приводить к увеличению скорости.
Другие решения
Других решений пока нет …