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

Question

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

Если я использую QuadTree, я должен очистить каждый кадр QuadTree и вставить все мои объекты, а затем пропустить его, чтобы получить все возможные объекты столкновения. И затем пройдите через это, чтобы получить мой объект столкновения, в котором я нуждаюсь. Почему это лучше, чем цитировать все мои объекты? Для QuadTree мне нужно O (n logn), если im right. Но цикл через все мои объекты О (п)

Greetz

Answer 1

Сравнивая каждый объект со всеми остальными О (п^2), потому что вы должны пройти через весь объект (O (п)), и для каждого объекта вам нужно проверить (почти) все остальные, так что это еще один O (n), в результате чего O (n^2).

Это хуже, чем O (n log n).

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

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