Быстрое, точное двухмерное столкновение

17

Я работаю над 2D-шутером сверху вниз, и теперь мне нужно выйти за рамки моей основной системы столкновений с прямоугольниками.

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

Я планирую справиться со столкновением следующим образом:

  1. Проверьте, есть ли спрайты в зоне действия игрока
  2. Провести тест столкновения прямоугольной рамки
  3. Точное столкновение (где мне нужна помощь)

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

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

неофит
источник

Ответы:

18
  1. Шаг первый, создайте сетку и обновите ее для каждого движущегося объекта.
  2. Проверяйте только столкновения между объектами в тех же квадратах.
  3. Проверьте, пересекает ли ограничивающий прямоугольник объектов (содержащий их прямоугольник).
  4. Проверьте на идеальное столкновение пикселей, используя версию схемы в низком разрешении (см. Физику игры).
  5. Выполните обычную проверку трассировки контура, как описано в разделе «Физика игры» (вопрос 2).

Шаг 1:

Создайте 2d массив сетки. Каждый объект знает, какие квадраты он занимает, это позиция x, y, а также его ширина и высота. Если объект удален, он очищается от старого квадрата и обновляет новый квадрат, который он занимает.

Это только берет O (n) всего для n объектов. Для любого конкретного объекта O (1).

Шаг 2:

Запустите все проверки на столкновения между объектами в тех же квадратах. Не нужно запускать тесты на столкновения между объектами в разных квадратах. Объект может занимать до четырех квадратов, если он среднего размера. Это означает, что очень мало проверок.

Шаг 3:

Проверьте пересечение между прямоугольниками объектов. Если пересечения не существует, остановитесь.

Шаг 4:

Проверяйте пиксельные столкновения между контурами объектов только внутри области пересечения. Это должно быть достаточно быстро. Если нет, создайте 2d-логический массив с низким разрешением и сначала проверьте его. Если вы обнаружите там коллизии, вам нужно будет только проверить небольшой сегмент в 2d-массиве с высоким разрешением, что сэкономит вам драгоценное время.

Пожалуйста, прочтите это, чтобы понять, как разделить игровой мир на сетку квадратов:

Создание эффективной системы обнаружения столкновений

Пожалуйста, прочитайте это для интуиции о том, как обнаружить идеальные столкновения пикселей .

Физика игры / 2D обнаружение столкновений AS3

Вы можете значительно улучшить производительность:

  1. Сохранение версии схемы в низком разрешении (1/16) для проверки в первую очередь.

  2. Только проверка в той области, где пересекаются две канавки.

  3. разделив контур примерно на сегменты, и сначала проверяя только столкновения между сегментами.

Пожалуйста, не стесняйтесь комментировать, и я уточню.

проверка в районе пересечения

wolfdawn
источник
1
Как сказал Артур, замените ваши шаги 1. и 2. сеткой, а для точного обнаружения столкновений вы можете использовать версию изображений с низким разрешением.
Маркус фон Броади
1
И если вам действительно нужно, вы также можете использовать аналогичную технику для моего ответа здесь: gamedev.stackexchange.com/questions/38481/…
Маркус фон Броади
Маркус указывает на хорошую идею. Вы должны использовать 2d-логический массив или 1d-массив, который обрабатывается как 2d, и вы можете сохранить 1/2 1/4 1/8 версии этого массива в низком разрешении, чтобы ускорить процесс. Это, вероятно, не потребуется, поскольку вычисления на 2d-булевых массивах выполняются очень быстро. Это все еще полезный инструмент, чтобы иметь.
wolfdawn
Если игрок полностью содержится внутри одного квадрата на сетке, вы можете проверять только предметы в этом квадрате. Игрок может находиться сразу в четырех смежных клетках. Это то, что вы имели ввиду? Если вы имеете в виду пересечение между прямоугольниками, да, вам нужно только проверять наличие столкновений, если они пересекаются.
wolfdawn
1
Я надеюсь, что обновление поможет прояснить ситуацию. После того, как вы написали некоторый код, вы можете опубликовать его в обзоре кода и связать нас для комментариев. codereview.stackexchange.com
wolfdawn