QuadTree для обнаружения двумерных столкновений

Question

В настоящее время я работаю над 2D-стрельбой по типу игры, и я использую квадровое дерево для обнаружения коллизий. Я написал рабочее квадратное дерево, которое правильно подталкивает моих актеров в узлы/листья, которыми они принадлежат в дереве. Однако у меня есть несколько проблем.

Во-первых, как я на самом деле использую свой квадрант, чтобы выбрать, какие другие объекты должен испытывать объект? Я не уверен, как это делается.

Что вызывает второй вопрос. Скажем, у меня есть объект в узле, который не является соседом другого узла, но что объект достаточно велик, что он охватывает несколько узлов, как я могу проверить фактическое столкновение, так как я предполагаю, что дерево может считать, что это не достаточно близко, чтобы столкнуться с объектами в «удаленном» узле? Должны ли объекты, которые не полностью вписываются в узел, сохраняются в родительском узле?

В моей игре большинство объектов имеют разные размеры и перемещаются.

Я читал большое количество блогов/статей о квадрантах, но большинство из них просто объясняют, как построить дерево, которое на самом деле не то, что я ищу.

Любая помощь/информация приветствуется.

Answer 1

Вы можете установить соглашение, что каждый элемент содержится в самом маленьком узле Quadtree, который содержит его полностью.

Тогда при проверке столкновений для узла А, вы действуйте следующим образом:

1. текущий узел = корневой узел
2. проверки столкновений А с каждым элементом непосредственно в текущем узле
3. если Можение полностью содержаться в любом из подузлов текущего узла, установить текущий узел на этот подузел и снова перейти к 2
4. , проверить столкновения A со всеми элементами в дочерних узлах текущего узла, рекурсивно ,

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