Не могу разобраться с проверкой столкновений с множеством объектов (в 2D).

Question

Как "нормально " реализовать проверку на столкновение, например, движущегося круга с большим кол-вом прямоугольников (допустим 100).
По тому алгоритму, что я придумал, мне нужно проверять столкновения перед каждым движением круга по очереди со всеми прямоугольниками, что вызывает лаги.... (как мне кажется )

Обобщение :
Есть управляемый круг (игроком или компом) и много прямоугольников, как сделать проверку столкновений между ними?

Татьяна Санникова · Accepted Answer

разбить пространство на прямоугольники, назовём их нодами. В каждом ноде есть некоторое количество ваших прямоугольников. Если один ваш прямоугольников лежит в нескольких нодах, то его можно продублировать или разделить, если это возможно. При каждом игровом фрейме круг может максимально двигаться на v*t, где v - скорость круга, t - время одного игрового фрейма. Вот выбираем все ноды, пересекаемые лучом движения (толк будет, если перебирать не все ноды, а начинать с самых ближайших к кругу, а потом идти вдоль луча) и находящиеся на расстоянии не более v*t. А далее уже в порядке пересечения прямой движения нодов перебирать в этих нодах ваши прямоугольники. Подсчитываем новый вектор скорости после столкновения. Далее записать траекторию, вычислить время столкновения и отнять от t его. И повторить до t = 0. После отрисовать всё это. Изначальное t равно длине фрейма и равно времени прорисовки кадра. Т. е. так можно избежать всяких заторможений физики при низкой скорости отрисовки. И делать физику надо в отдельном потоке от рендера, при чём рендер рисует "сейчашний" кадр, а физик считает следующий.

Нина Серебренникова · Answer

Нужно делить все на сектора, но 100 объектов это мало. Замени квадраты на описанные вокруг них окружности и оценивай снизу расстояния между центрами на осевых проекциях (т. е. сначала по Ox потом по Oy) - здесь используется только 4 вычитания (без мультипликативных операций) . Если оценка показывает, что коллизия допустима - применяй точные формулы.