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

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

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

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

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

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

Ответы

Ответ 1

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

Затем, когда вы проверяете столкновения для node A, вы выполняете следующее:

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

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