Войти
ПрограммированиеФорумИгровая логика и ИИ

Оптимизация проверки столкновений объектов в 2D

Страницы: 1 2 3 4 5 Следующая »
#0
(Правка: 7 авг. 2021, 20:33) 3:48, 29 июля 2021

В игре много пуль и противников с полигональными хитбоксами. Уже добавлена оптимизация, где просчитываются столкновения только близких по дистанции объектов. Ещё добавлю упрощение хитбоксов до кругов, типа круг покрывает все хитбоксы и проверяется только он, а когда круги столкнулись, проверяются подробно полигоны. Как ещё можно ускорить просчёт столкновений? Какие разбиения пространства я могу использовать? В игре всё движется каждый апдейт, ничего не стоит на месте и нужно проверять столкновения всех со всеми.

UPD: Я проверил всё что мне предлагали и не предлагали, самый крутой варик это сетка с фиксированным размером секторов, в которой многопоточно проверяются ячейки и 3 соседа. Проверить пересечение кругов - самое быстрое что можно сделать, поэтому я упрощаю хитбоксы до кругов, а когда они столкнулись, проверяю настоящие хитбоксы


#1
5:23, 29 июля 2021

HPW-Dev
> Какие разбиения пространства я могу использовать?
Решение влоб - octree например.

У меня лично еще хорошо заходит регулярная сетка. Допустим все твои объекты не очень большие и их AABB не превышает некоторого (SizeX, SizeY). Ты можешь сделать регулярную сетку с размером ячейки (SizeX, SizeY). Все объекты складывать в ту ячейку, в которой находится центр AABB объекта:

cellX = round(AABB.center.x); cellY = round(AABB.center.y);

Тогда для проверки столкновений объекта A с другими объектами тебе нужно будет проверить столкновения с объектами только в 4 ячейках:

floor(A.AABB.center.x), floor(A.AABB.center.y)
floor(A.AABB.center.x), ceil(A.AABB.center.y)
ceil(A.AABB.center.x), floor(A.AABB.center.y)
ceil(A.AABB.center.x), ceil(A.AABB.center.y)

#2
(Правка: 9:52) 9:43, 29 июля 2021

HPW-Dev
> просчитываются столкновения только близких по дистанции объектов. Ещё добавлю
> упрощение хитбоксов до кругов, типа круг покрывает все хитбоксы
Звучит как одно и то же.
Обязательно запомни когда будешь делать пересечения кругов - нужно сравнивать не расстояния, а квадраты расстояний (чтобы избавится от квадратного корня).
И погугли sweep-and-prune.

#3
(Правка: 9:51) 9:48, 29 июля 2021

MrShoor
> У меня лично еще хорошо заходит регулярная сетка.
У меня сложилось впечатление что она хороша лишь когда все объекты не сильно отличаются по размеру, а если один объект больше другого в десять раз (что как раз очень может быть в случае столкновения "пуля-монстр"),  то регулярная сеть уже не очень. Или я ошибаюсь?

#4
10:12, 29 июля 2021

MrShoor
> У меня лично еще хорошо заходит регулярная сетка.
У меня тоже, для кучи объектов близкого размера.

> проверить столкновения с объектами только в 4 ячейках:
5? Со своей тоже надо, если там больше одного объекта.

#5
10:14, 29 июля 2021

MrShoor
А, не, по твоему способу - действительно 4.

#6
10:23, 29 июля 2021

HPW-Dev
> Какие разбиения пространства я могу использовать?

Как вариант - можно использовать дерево отрезков https://en.wikipedia.org/wiki/Interval_tree (по двум осям)

MikeNew
> И погугли sweep-and-prune.

Это видимо вариация дерева отрезков.

#7
20:15, 29 июля 2021

MikeNew
> У меня сложилось впечатление что она хороша лишь когда все объекты не сильно
> отличаются по размеру, а если один объект больше другого в десять раз (что как
> раз очень может быть в случае столкновения "пуля-монстр"), то регулярная сеть
> уже не очень. Или я ошибаюсь?
Оно будет плохо только если хочется проверять столкновения пуля-пуля, и при этом большое количество пуль попадет в одну ячейку.

#8
15:39, 30 июля 2021

MikeNew
>Звучит как одно и то же
Действительно, одно и то же ;]
Квадрат расстояний был добавлен

#9
15:40, 30 июля 2021

MrShoor
>octree
так и хочу сделать, но есть и другие деревья и я не знаю какие у них плюсы и минусы, может они быстрее

#10
15:41, 30 июля 2021

MikeNew
> когда все объекты не сильно отличаются
А они точно отличаются, есть длинные пули, мгновенные лазеры, большие сферы и широкие противники

#11
15:46, 30 июля 2021

Азаг Тот
Решения для юнити точно не подойдут, движок на C++. Распараллеливание не получится добавить - при столкновениях меняются состояния объектов и не все потоки увидят изменения

#12
15:57, 30 июля 2021

Круги не всегда лучший вариант. Используй разные простые фигуры для разных объектов. Квадрат, прямоугольник, треугольник. Где-то их смесь, как вариант.

#13
15:59, 30 июля 2021

1. Наиболее быстро это решать задачу геометрически, это в случае если обьекты можно представить в виде геометрических фигур и ты будешь искать пересечение прямой с этими фигурами через решение простых уравнений.
2. Более медленное решение через quad_tree.query();
3. Наиболее медленное но самое точное решение это через ZBuffer;

В принципе все типы решений подьемные для сегодняшнего CPU, если счет объектов не идет на миллионы.

#14
17:33, 30 июля 2021

  Как вариант взять Box2D, там уже должно все быть из коробки. Но все-таки нужна конкретика: какие по форме(круги, квадраты, отрезки) обьекты сталкиваются, будет ли просчитываться физика вне экрана, нужен ли только факт столкновения или еще и траектория просчета отскока.

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумИгровая логика и ИИ