Как я могу реализовать быстрое и точное обнаружение двумерных столкновений?

Я хорошо знаю, как обнаружить, сталкиваются ли два или более 2D-объекта, но мне интересно, как решить, нужно ли проверять наличие конфликта. В предыдущих проектах я просто проверил каждый объект против каждого другого объекта (я знаю, O (n ^ 2) уровень глупости), и он создал менее гибкий игровой процесс.

Различные форумы приветствуют величие Quadtrees, B-Trees и любого другого дерева или структуры, о которых вы можете думать.

Какова наиболее эффективная структура для определения того, нужно ли проверять столкновение?

10 голосов | спросил Mike Cluck 7 +04002011-10-07T23:47:27+04:00312011bEurope/MoscowFri, 07 Oct 2011 23:47:27 +0400 2011, 23:47:27

3 ответа


11

Для 2-й игры, если 2D-объекты не имеют очень тяжелого распределения на одной стороне вашей карты, равномерная сетка - это почти всегда путь. Сложность памяти прямолинейна (пропорциональна размерам вашей карты) и с разумным распределением имеет O (1) время поиска и среднее значение log (numberOfObjects /(rows * columns)) ^ 2 тесты пересечения для каждой ячейки. Вы можете решить только проверить ячейки, в которых объект перемещался, что делает статическую геометрию намного более эффективной. Легко модифицировать единую сетку «на лету» (гораздо меньше боли, чем в решениях на основе дерева), и ее проще реализовать. Единственный раз, когда я бы сказал, что не использовать его в 2D-игре, - это когда требования к памяти однородной сетки становятся слишком большими (скажем, космический сим, где уровни разрежены, но огромны).

ответил Darcy Rayner 8 +04002011-10-08T11:43:14+04:00312011bEurope/MoscowSat, 08 Oct 2011 11:43:14 +0400 2011, 11:43:14
1

Двигатели 2D-физики, такие как Box2D и Chipmunk, сильно используют пространственную карту хэшей

см. http://chipmunk-physics.net/release/ChipmunkLatest-Docs/#CollisionDetection для справки. Демоверсии с микрочипами включают в себя действительно хороший пространственный хэш-визуализатор, который делает его действительно понятным, как работает техника.

ответил pSK 9 +04002011-10-09T00:22:28+04:00312011bEurope/MoscowSun, 09 Oct 2011 00:22:28 +0400 2011, 00:22:28
1

Если ваш мир имеет очень «длинное» измерение (назовите его X), по сравнению с другими, вы можете сохранить объекты в упорядоченном списке, которые вы можете повторно сортировать по мере их перемещения, а затем обнаружение столкновения означает только проверку для объектов, которые перекрываются по оси X.

Другая возможность - сохранить активные /пассивные списки объектов и не беспокоить пассивные объекты (которые вообще не перемещаются).

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

Кроме этого, я с Дарси, равномерная сетка хороша.

ответил MarkR 11 +04002011-10-11T01:09:38+04:00312011bEurope/MoscowTue, 11 Oct 2011 01:09:38 +0400 2011, 01:09:38

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132