Работая над своей игрой, я нахожусь в точке, где мне нужно отследить все юниты в мире, чтобы я мог делать проверки ближайших соседей на бой. Это RTS-подобная игра, в которой могут перемещаться тысячи маленьких автоматических юнитов.
Я изучал KD-Trees и Quadtrees (особенно Point Quadtrees). Я все еще пытаюсь изучить детали того, как они работают, но до сих пор Point Quadtrees имеют для меня наибольшее значение. Тем не менее, у меня складывается впечатление, что KD-деревья быстрее искать, что важно, учитывая количество точек в дереве.
С другой стороны, в моем случае я собираюсь отслеживать огромное количество единиц, которые всегда движутся. От кадра к кадру их положение всегда будет отличаться. Очевидно, Quadtree быстрее перебалансируются, чем KD-Trees, но я не знаю, применимо ли это, когда вы перебалансируете каждую точку дерева.
Я задаюсь вопросом, что было бы лучше в этом случае просто очистить дерево каждого кадра и восстановить его с нуля, а не пытаться сбалансировать каждую точку дерева? Если Quadtree быстрее перебалансировать, значит ли это, что его быстрее построить с нуля? Если это так, это может быть важнее для производительности, чем скорость поиска в KD-Tree, в зависимости от того, насколько тяжело создать дерево, но я не знаю ...
Lærne предлагает отличные предложения, но я бы также предложил динамическое ограничивающее дерево томов AABB. Концептуально динамическое дерево ограничивающих томов поддерживает сбалансированное дерево узлов, которое можно в любое время запросить для близких элементов, передав AABB и получив перекрывающуюся пару. Дерево не перестраивается каждый кадр. Вместо этого AABB каждого узла слегка раздувается, когда помещается в дерево, и дерево перестраивается только тогда, когда фактическая AABB узла больше не содержится в надутой AABB. Я использую его в своем физическом движке, и он прекрасно работает.
Исходный код Box2D имеет отличную реализацию.
https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h
Вот хороший обзор их реализации:
http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/
источник