Когда квадри предпочтительнее пространственного хеширования?

12

Я делаю 2D платформер с множеством объектов одновременно. Они все обнаружены столкновения AABB. Сначала я попробовал квадродерево, чтобы уменьшить количество проверяемых объектов, попробовал несколько разных конфигураций, но это оказалось не так эффективно, как мне было нужно. Я реализовал пространственный хеш, и он стал более эффективным, количество объектов для проверки для каждого столкновения резко сократилось.

Есть ли случай, когда двухмерное обнаружение столкновений с использованием квадродерева предпочтительнее пространственного хеширования? Согласно моим тестам, кажется, что пространственное хеширование всегда заканчивается меньшим количеством объектов для проверки на столкновение?

Я еще не выбрал время для алгоритмов, но хэширование просто очень дорого или сложно реализовать, когда вы, например, программируете на C? Стоит отметить, что я пишу игру в javascript, где у вас есть хеширование «бесплатно».

Вот сравнение, я что-то упустил? http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

Крис
источник

Ответы:

12

Основным преимуществом четырехъядерного дерева является то, что оно позволяет очень быстро отбросить целые группы сегментов из рассмотрения.

Например, предположим, что у меня есть четырехугольное дерево с шестью уровнями. На самом низком уровне это 32x32 коробки; 1024 коробки, содержащие этот самый нижний, самый подробный уровень. Для сравнения мы также рассмотрим «пространственный хеш» - плоскую сетку, которая также содержит 32x32 блока, всего 1024 блока. (в четырехугольном дереве более 1024 ящиков, так как оно также содержит большие ящики на своих более высоких уровнях)

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

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

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

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

Разумеется, все это не означает, что древовидная структура всегда является правильным выбором. Плоские сетки идеально подходят для ситуации, которую вы имеете в своем примере - плотные облака объектов почти равномерно распределены по всему миру, и мы проводим простые и недорогие тесты на столкновение. Абсолютно сетка, вероятно, будет оптимальным подходом в этом случае!

Тревор Пауэлл
источник
5
Лаконичная сводка, для крайне ленивых: Quadtree быстрее обрабатывают объекты разных размеров.
Anko
Спасибо, это отличный ответ! Я подозревал, что объекты одинакового размера.
Крис
На самом деле вам, как правило, придется искать по всем уровням четырехугольного дерева, чтобы проверить, нет ли объектов, так как обычно уровень содержит информацию только об объектах, которые полностью помещаются в границы этого уровня и не умещаются на более низком уровне.
Мальте
1
@malthe Если вы настаиваете на использовании реализации четырехъядерного дерева, которая не может быть ранней в таком запросе, то вместо этого обязательно используйте пространственный хеш; Вы сэкономите 33% от стоимости памяти, и вы все равно не получите никакой выгоды. Или, в качестве альтернативы, вы можете ослабить свою идеологическую чистоту только на кусочке и использовать четырехугольное дерево, которое может быть заблаговременно, либо с помощью каждого узла отслеживать количество сущностей в своих дочерних элементах, либо с помощью разреженного квадродерева, чтобы пустые узлы были не связаны с деревом, пока они не понадобятся. На самом деле. Более пяти лет спустя.
Тревор Пауэлл
@TrevorPowell конечно, ты прав. Я просто упал из-за твоей гарантии, что тебе нужно было посмотреть только на одну коробку. Это просто неправда, потому что вам придется продолжать эти подсчеты. Насколько я могу судить, вы можете обнаружить столкновения выше и ниже по дереву.
Мальта