Как обработать столкновение объектов?

Итак я собираюсь писать свою игру на SDL. Собственно действие будет происходить на игровой плоскости, по которой предстоит двигаться объектам, состоящим из координат и 2-мерного массива, в котором значения могут принимать значения 0 или 1. 0 — пусто, 1 — занято. И, собственно вопрос: как проверить 2 объекта на столкновения и определить, какими частями массивов столкновение произошло?


Сам я дошел до 2х вариантов, но они ресурсотребовательны:


1) «в лоб»: Сравнить каждую точку 1го массива с каждой точкой второго, если координаты одинаковые -> столкновение.

2) «по лбу»: создать еще один двумерный массив «игровая плоскость». Скопировать на него 2рой объект. Потом перебрать все точки 1го объекта, если одновременно у 1го объекта и у плоскости точка занята -> столкновение.


Есть ли менее затратные способы? Что скажете насчет 2го?
  • Вопрос задан
  • 10704 просмотра
Решения вопроса 1
@rPman
Судя по акценту на любые конфигурации объектов вам нужна корректная обработка даже таких случаев, когда по координатно объекты проходят друг сквозь друга, но из-за особенностей их конфигурационных матриц они не сталкиваются.
Универсальное решение — только хранение дополнительных матриц кешей, уменьшенного масштаба объектов. Количество и конфигурация кешей зависит от сложности этих матриц. На один объект может быть несколько матриц, последовательного уменьшения масштаба (например с коэффициентом 4 — 128x128 -> 32x32 -> 8x8 -> 2x2), тогда при обнаружени столкновения прямоугольных областей объектов последовательно проверяются пересечения точек сначала на матрицах конфигураций объектов с низким разрешением, при обнаружении пересечения повторяется проверка для соответствующих точек уже из матрицы с более высоким разрешением.

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

p.s. еще неплохим подспорьем может оказаться дробление объекта на составляющие (т.е. представлять объект сразу несколькими объектами, параметры которых вычислять тут же, даже не требуется физически хранить и двигать эти объекты синхронно)
Ответ написан
Пригласить эксперта
Ответы на вопрос 8
exponentum
@exponentum
Если точка уже занята — увеличивайте Плоскость[x координата точки][y координата точки] на единицу.
Потом проверяете: если (Плоскость[x][y] > 0) столкновение произошло.
Ответ написан
Пересчитывать координаты движущегося объекта и сравнивать с остальными.

Совет: хотите разобраться, то напишите свой тетрис — это прекрасный пример обработки столкновений.
Ответ написан
Комментировать
@gleb_kudr
Начните с того, что объекты сталкиваются поверхностями.

Далее — можно проводить дискретизацию формы объекта с уменьшением точности (скажем, контур объекта 1000 точек, построить производные объекты с 100 точками, с 10). Обсчитывать полностью только грубую модель. На выходе вы не будете знать, столкнулимь объекты или нет (на то она и грубая), но сможете примерно прикинуть вероятность (коэффициенты зависят от формы модели) и узлы которые ближе всего друг к другу и потенциально участвуют в столкновении.

Если вероятность столкновения по грубой модели велика, обсчитать этот участок в более высоком разрешении и т.д.
Ответ написан
Комментировать
AxisPod
@AxisPod
Все зависит от ситуации, но в большинстве случаев игровое пространство делится на зоны (зона больше самого большого объекта). А тут уже как внутренний голос решит. В итоге приходилось проверять максимум 4 зоны, на предмет столкновения. Зон было много.объектов по сути тоже и ничего не тормозило. Опять же еще вариант, где есть растровое поле и каждый объект за собой помечал, что он уже занял место, в итоге был всего лишь мелкий массивчик с быстрым доступом к элементам, если же объект попадал в область помеченную занятой, то проводились более точные проверки.
Ответ написан
Комментировать
retran
@retran
С очень большой вероятностью вам не нужна такая точность.
Оконтурить векторами, или еще проще закрыть объект набором прямоугольников и окружностей, и сравнивать уже их.
Ответ написан
Комментировать
Lerg
@Lerg
Defold, Corona, Lua, GameDev
Почему бы вам не воспользоваться игровыми SDK со встроенным (или легко прикручиваемым) датчиком столкновений?
pygame, moai, LÖVE и другие.
Ответ написан
@j7sx
описывается для pygame, но для тебя тоже будет актуально:
https://youtu.be/FxInYJC2LD4
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы