Пытается использовать квадранты для обнаружения столкновений в игре

Question

В настоящее время я внедряю систему обнаружения столкновений с использованием квадрантов. Я смог реализовать quadtree, но у меня был вопрос относительно конкретной ситуации. Допустим, что у моей начальной квадранты есть граница 200x200. Так что мой первый уровень суб-quadtrees будет иметь границу:

NW: (0, 0) ~ (100100)

SW: (0, 100) ~ (100, 200)

СВ: (100, 0) ~ (200, 100)

SE: (100, 100) ~ (200, 200)

Допустим, есть квадратный предмет в точке (98, 98), и ее ширина и высота - 5. Я беру центральное положение при вставке их в поддеревья, поэтому этот объект будет помещен в квадрант NW. Однако, так как его ширина и высота равны 5, они технически также относятся ко всем трем трем четвёртаям. Должен ли я проверить, распространяется ли граница объекта на другую сторону квадранта, и если да, добавьте несколько экземпляров в квадрант?

Answer 1

Да - либо это, либо при вставке в этом случае разделить квадрат на 4 отдельных. Проще просто разрешить дубликаты хранить на листьях и делать это дешево (указатель/указатель на квадрат, например)

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

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

Я предлагаю только начать с дубликатов. Другие методы могут быть настоящими хлопотами, и вам не нужно беспокоиться о таких хлопотах (пока вы не заметите необходимость в ней).

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

Кроме того, для 2D-корпусов вы можете иногда уйти с фиксированной сеткой. Иногда бывает лучше работать с сеткой NxM, чем с четырехъядерным деревом, поскольку она настолько проста в построении (что упрощает обновление для очень динамичного контента, где у вас есть, скажем, спрайты, перемещающиеся по экрану на каждом кадре) , и не имеет сложных худших сценариев, поскольку в нем нет такого понятия «глубина», а всего лишь ячейки, содержащие элементы.