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

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

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

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

Спасибо!