Я хорошо знаю, как определять, сталкиваются ли два или более 2D-объекта, но мне интересно, как решить, проверять ли столкновение. В предыдущих проектах я просто проверял каждый объект на предмет любого другого объекта (я знаю, уровень глупости O (n ^ 2)), и это создавало не очень плавный игровой процесс.
Различные форумы приветствуют величие Quadtrees, B-Trees и любых других видов деревьев или структур, о которых вы только можете подумать.
Какова наиболее эффективная структура для определения необходимости проверки столкновения?
2d
collision-detection
data-structure
Майк Клак
источник
источник
Ответы:
Для двумерной игры, если 2D-объекты не имеют очень сильного распределения по одной стороне вашей карты, равномерная сетка - почти всегда путь. Сложность памяти прямолинейна (пропорциональна размерам вашей карты), и с разумным распределением имеет время поиска O (1) и среднее значение log (numberOfObjects / (строки * столбцы)) ^ 2 теста пересечения сделано за клетку. Вы можете решить проверять только те ячейки, в которых есть объект, который перемещается, что делает статическую геометрию намного более эффективной. Однородную сетку легко изменить на лету (гораздо меньше проблем, чем в древовидных решениях), и ее проще реализовать. Единственный раз, когда я бы сказал, чтобы не использовать его в 2D-игре, это когда требования к памяти для равномерной сетки становятся слишком большими (скажем, космический сим, где уровни редки, но огромны).
источник
Механизмы 2D Physics, такие как Box2D и Chipmunk, активно используют пространственную хэш-карту
см. http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection для справки. Демонстрации бурундука включают действительно хороший визуализатор пространственного хеша, который дает понять, как работает их техника.
источник
Если в вашем мире есть одно очень «длинное» измерение (назовите его X), по сравнению с другими, вы можете хранить объекты в упорядоченном списке, который можно сортировать по мере их перемещения, а затем обнаружение столкновений означает только проверку объектов, которые перекрываются по оси X.
Другой возможностью является сохранение активных / пассивных списков объектов и не беспокоиться о пассивных объектах (которые вообще не движутся).
Если это все объекты среднего размера, которые видны игроку на экране, то все против всего, вероятно, не так уж плохо.
Кроме этого, я с Дарси, хорошая сетка хороша.
источник