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

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

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

Гретц


javascript collision quadtree
person R3Tech    schedule 25.04.2016    source источник
comment
Хотя это очень классный и увлекательный вопрос, я не думаю, что он совсем в тему StackOverflow. Возможно, вам повезет больше на gamedev.stackexchange.com. Если коротко, QuadTrees может помочь ограничить количество объектов, которые необходимо проверить. для обнаружения столкновений, что повышает производительность. Обнаружение столкновений стоит дорого, если вам нужно проверять его на каждом отдельном объекте в сцене. mikechambers.com/blog/2011/03/21/< /а>   -  person Brandon Anzaldi    schedule 25.04.2016

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

person TilmannZ    schedule 26.04.2016
comment
Так что, если мне нужно только проверить мой плеер на все объекты, работа без quadtree должна быть лучше? Спасибо - person R3Tech; 26.04.2016
comment
Если перемещается только один объект, ему даже не обязательно находиться в дереве квадрантов. Чем лучше дерево квадрантов, зависит от количества объектов. Лучше всего попробовать. - person TilmannZ; 26.04.2016