Избегайте сложностей O (n^2) для обнаружения столкновений

Question

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

Я хотел бы избежать квадратной сложности. Существуют ли какие-либо известные методы для сокращения вызовов обнаружения конфликтов между объектами. Существуют ли какие-либо структуры данных (например, дерево BSP), которые легко сохраняются и позволяют одновременно отклонять множество коллизий.

Например, общее количество объектов в уровне составляет около 500, около 50 из них видны на экране в то время ...

Спасибо!

Answer 1

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

Это будет стоить практически ничего.

Answer 2

Вы можете использовать quadtree для разделения пространства и уменьшения количества объектов, необходимых для проверки на предмет столкновения.

See this article - Quadtree demonstration.

And perhaps this - Collision Detection in Two Dimensions.

Or this - Quadtree (source included)

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

Answer 3

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

В вашей сетке каждый спрайт занимает одну или несколько плиток. Спрайт знает, какие плитки он занимает, а плитки знают, какие спрайты занимают его. Когда спрайт перемещается, вам нужно только проверить наличие столкновений внутри плиток, которые занимает спрайт. Это означает, что обнаружение столкновения вообще не требуется, если спрайты не достаточно близко, чтобы занять одни и те же плитки, и даже тогда вам нужно только проверить наличие столкновений между близкими друг другу спрайтами.

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

Кроме того, в зависимости от вашей реализации вам может потребоваться использовать немного большую ограничительную рамку для определения занятости плитки, чем для определения конфликтов. Таким образом, вам гарантируется, что спрайты будут перекрываться и занимать одну и ту же плиту до того, как коснутся границы столкновения.