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