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

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

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

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

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

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

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

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