Как смешивать обычное и квадретное обнаружение столкновений?

Question

У меня есть квадрадерево создать для всех статических объектов соударения, который прекрасно работает как для обнаружения столкновений и raycasting

Однако, как я также не-статические объекты столкновений, когда я raycast я хотел бы включить их в качестве возможные коллидируемые объекты для луча

Что было бы лучшим (с точки зрения производительности) способом достижения этого? Мои нынешние идеи:

1) клонировать квадрадерево, добавьте не-статические объекты, а затем использовать его для raycast

2) добавить нестатические объекты текущего квадрадерево, с некоторыми флагами, которые в основном чтобы квадранты не раскалывали свои квадратики, даже если в квадрате было больше детей, чем разрешено. Квадрат затем должен был «очистить» после себя после завершения raycast

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

Все эти идеи кажутся немного громоздкими, поэтому я ищу любые альтернативные идеи, которые могут быть более эффективными

В случае, если это имеет значение, я использую Java

Answer 1

В 1) Клонирование quadtree, вероятно, очень дорого, если у вас более 10 объектов, поэтому я бы этого не сделал.

В 2) Почему бы просто сохранить список нестатических объектов? Просто добавьте все объекты в дерево (я не вижу, почему расщепление является проблемой), и после вычисления rempove их из дерева.

В 3) Это довольно дорого, если у вас много нестатических объектов, но, вероятно, самое дешевое решение, если у вас их очень мало.

еще несколько идей:

4) Построить второе квадрадерево для не-статических объектов и сделать обнаружение столкновений (похожее на 5)). После столкновения просто отбросьте второе дерево.

5) Если разделяющие узлы действительно являются проблемой, как насчет использования PH-Tree? Это как квадрант, но он ведет себя намного более статично, чем квадтри (без вставки/удаления никогда не будет изменено более одного узла (кроме создания дополнительного удаления одного пустого узла).

6) В зависимости от того, -статические объекты, вы можете использовать «движущееся дерево объектов» (для этого просто Google, есть некоторые выделенные структуры). Если объекты не слишком быстры, PH-Tree снова может быть хорошим выбором, у него есть выделенный метод перемещения/обновления.