Избегайте сложности O(n^2) для обнаружения столкновений
Я занимаюсь разработкой простой 2D-игры на основе плитки. У меня есть уровень, заполненный объектами, которые могут взаимодействовать с плитками и друг с другом. Проверить коллизию с помощью тайлакарты довольно просто, и это можно сделать для всех объектов с линейной сложностью. Но теперь я должен обнаружить столкновение между объектами, и теперь я должен сравнить каждый объект с каждым другим объектом, что приводит к квадратной сложности.
Я хотел бы избежать квадратной сложности. Существуют ли какие-либо общеизвестные способы уменьшения количества вызовов при обнаружении столкновений объектов Существуют ли какие-либо структуры данных (например, дерево BSP), которые легко поддерживаются и позволяют отклонять множество коллизий одновременно.
Например, общее количество объектов на уровне около 500, около 50 из них видны на экране одновременно...
Спасибо!
3 ответа
Почему бы вам не позволить плиткам хранить информацию о том, какие объекты занимают их. Тогда столкновения могут быть обнаружены всякий раз, когда объект перемещается в новую плитку, проверяя, содержит ли эта плитка другой объект.
Это будет стоить практически ничего.
Вы можете использовать квадродерево, чтобы разделить пространство и уменьшить количество объектов, которые необходимо проверить на столкновение.
Смотрите эту статью - демонстрация Quadtree.
И возможно это - Обнаружение столкновения в двух измерениях.
Или это - Quadtree (источник включен)
На первый взгляд может показаться, что для поддержания дерева требуется много ресурсов процессора, но это также значительно уменьшает количество проверок (см. Демонстрацию в первой ссылке).
Ваша игра уже имеет концепцию карты тайлов, связанных с игровым процессом. Вы можете использовать эту карту тайлов для обнаружения столкновений или наложить вторичную сетку на игровое поле, используемое специально для отслеживания спрайтов и обнаружения столкновений.
Внутри вашей сетки каждый спрайт занимает одну или несколько плиток. Спрайт знает, какие плитки он занимает, а плитки знают, какие спрайты занимают его. Когда спрайт перемещается, вам нужно только проверять наличие столкновений внутри тайлов, которые занимает спрайт. Это означает, что обнаружение столкновений вообще не требуется, если спрайты не расположены достаточно близко, чтобы занимать одни и те же тайлы, и даже тогда вам нужно только проверять наличие столкновений между спрайтами, которые находятся близко друг к другу.
Если ваш игровой процесс таков, что спрайты часто собираются вместе, вы можете реализовать свою сетку в качестве квадродерева, чтобы позволить каждому плитке быть разделенной и не допустить, чтобы слишком много спрайтов занимали одну и ту же сетку.
Кроме того, в зависимости от вашей реализации, вам может понадобиться использовать немного большую ограничивающую рамку для определения занятости плитки, чем для определения коллизий. Таким образом, вам будет гарантировано, что спрайты будут перекрываться и занимать одну и ту же плитку до того, как их границы столкновения коснутся.