Проблема с огромными объектами в дереве квадрантов

Это интересная проблема. Может быть, вы можете расширить узел или ячейку с информацией о высоте дерева? Если у вас есть объект больше, чем самая маленькая ячейка, вложенная в него с высотой дерева. Это то, что делает приложение карты, такое как карты Google или Bing.

Вот ссылка на похожее решение: http://www.gamedev.net/topic/588426-2d-quadtree-collision---variety-in-size. Я перепутал скрин с квадриком. Вы можете проверить столкновение с помощью простого отказа.

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

Обзор

Во время поиска, начиная с самых больших объектов в первую очередь...

Протестируйте Object.Position.X против QuadTreeNode.Centre.X, а также

проверить Object.Position.Y на QuadTreeNode.Centre.Y;

... Затем, принимая абсолютное значение разницы, рассматривайте объект как лежащий в пределах определенного дочернего узла, когда абсолютное значение НЕ превышает радиус объекта...

... то есть, когда какая-то часть объекта вторгается в этот квадрат :)

То же самое можно сделать с AABB (Ограничительные рамки, выровненные по осям).

Единственная реальная оговорка заключается в том, что ОЧЕНЬ большие объекты, занимающие большую часть экрана, заставят искать все дерево. В этих случаях может потребоваться другой подход.

Конечно, это заботится только об объекте, против которого тестируется все остальное. Чтобы убедиться, что все другие крупные объекты в мире правильно идентифицированы, вам нужно будет немного изменить свое дерево квадрантов...

Использовать несколько образов

В этом варианте QuadTree мы размещаем объекты ТОЛЬКО в конечных узлах QuadTree в качестве указателей. Более крупные объекты могут появляться в нескольких листовых узлах.

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

So...

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

Хотя это и имеет смысл, это расточительно, если проводить тесты на попадание «все против всех».

Итак... Немного поумнев, мы можем вообще избежать какой-либо очистки, используя указатель 'ptrLastObjectTestedAgainst' внутри каждого объекта в сцене. Это позволяет избежать повторного тестирования одних и тех же объектов в этом запуске (указатель устанавливается после первого обнаружения)

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

Я использовал последний подход в сценах с совершенно разными размерами объектов, и он работал хорошо.

Эластичные деревья QuadTree

Я также использовал «эластичный» QuadTree. По сути, вы устанавливаете ограничение на количество элементов, которые ИДЕАЛЬНО могут поместиться в каждом QuadTreeNode, но, в отличие от стандартного QuadTree, вы позволяете коду переопределять это ограничение в определенных случаях.

Основное правило здесь заключается в том, что объект НЕ может быть помещен в узел, который не может его удерживать ПОЛНОСТЬЮ... с верхним узлом, ловящим любые объекты, которые больше экрана.

Таким образом, небольшие объекты будут продолжать «проваливаться», образуя обычное QuadTree, но большие объекты не всегда будут проваливаться до конечного узла, а вместо этого будут расширять узел, который последним соответствовал им.

Думайте о нелистовых узлах как о «просеивании» объектов, когда они падают вниз по дереву.

Это оказывается очень эффективным выбором для многих сценариев :)

Заключение

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

Поэтому не просто учитесь применять алгоритмы... учитесь из этих алгоритмов и применяйте сами принципы новыми и подходящими способами. Это НЕ единственные инструменты, и они не обязательно лучше всего подходят для вашего приложения.

Надеюсь, некоторые из этих идей помогли.