QuadTree для 2D обнаружения столкновений

Question

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

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

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

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

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

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

Answer 1

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

Затем, когда вы проверяете коллизии для узла A, вы действуете так:

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

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