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

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

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

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

Спасибо!

Ответ 1

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

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

Ответ 2

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

См. эту статью - демонстрация Quadtree.

И, возможно, это - обнаружение конфликтов в двух измерениях.

Или это - Quadtree (источник включен)

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

Ответ 3

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

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

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

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