Я разрабатываю квадродерево, чтобы отслеживать движущиеся объекты для обнаружения столкновений. Каждый объект имеет ограничивающую форму, скажем, все они круги. (Это 2D сверху вниз игра)
Я не уверен, сохранять ли только положение каждого объекта или всю ограничивающую форму.
При работе с точками вставка и разбиение просты, потому что объекты никогда не будут охватывать несколько узлов. С другой стороны, в запросе близости объекта могут отсутствовать коллизии, поскольку он не учитывает размеры объектов. Как рассчитать регион запроса, когда у вас есть только очки?
Если вы работаете с регионами, как обрабатывать объект, который охватывает несколько узлов? Должен ли он быть вставлен в ближайший родительский узел, который полностью содержит его, даже если он превышает емкость узла?
Спасибо.
Вы должны хранить его в наименьшем узле, который полностью содержит его, даже если он превышает емкость (используйте контейнер с изменяемым размером).
источник
Я бы добавил это в качестве комментария в ответ на ответ @Nathan Reed, за исключением того, что он слишком велик, чтобы быть комментарием, и, возможно, в любом случае заслуживает отдельного ответа.
Мы делали именно то, что было предложено в его ответе, и на самом деле имеем комментарий в источнике, ссылающемся на эту страницу. По большей части это работает очень хорошо, за исключением того, что раз в два-три месяца мы теряем случайный сервер, который перестает отвечать на запросы из-за большой продолжительности поисковых запросов.
Причиной проблемы стало мое внимание во время проверки производительности, чтобы попытаться выяснить, что вызвало это. Вероятно, это только проблема, если вы разрешаете перекрывающиеся объекты. В нашей игре это происходит, и в худшем случае это иногда приводит к резкому увеличению производительности.
У нас был один крайний случай, когда около 100 объектов, все с ограничивающими дисками, были сгруппированы в непосредственной близости. Это привело к проблеме очень глубокого пика в дереве, потому что мы добрались до точки, где объекты были больше, чем область, покрытая узлами дерева квадрантов, поэтому каждый новый объект обнаруживался в нескольких узлах, что приводило к массивному подразделению дерево, таким образом, снежный ком проблема из-под контроля.
Вывод из этого заключается в том, что если вы позволяете областям объектов перекрываться, внимательно следите за вещами, если вы получаете узкие группы объектов, чтобы убедиться, что ваше дерево не становится слишком глубоким.
Решение, которое я сейчас изучаю, состоит в том, чтобы хранить объекты в виде точек, а затем при выполнении поиска увеличивать границы прямоугольника поиска на максимальный радиус, хранящийся в дереве. Это должно сработать для нас, поскольку дерево является первым проходом поиска, затем мы выполняем проверку диапазона на основе истинного круга, а также несколько других критериев проверки, поэтому дополнительные ложные предупреждения будут отфильтрованы.
Ваш фактический пробег может отличаться.
источник