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

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

Страницы: 1 2 3 4 5 Следующая »
#15
21:11, 30 июля 2021

Вообще, если речь идёт о пулях, то обычно принято использовать лучи.


#16
18:02, 31 июля 2021

gamedevfor
> и ты будешь искать пересечение прямой с этими фигурами через решение простых уравнений
Как тогда определить столкновения пули, если она летит быстро и пролетает расстояние большее чем объект, получается что она его проскочит и не столкнётся. Мне что, надо проводить линию от старой позиции объекта до новой и проверять пересечение этой линии с фигурами?

#17
(Правка: 18:16) 18:08, 31 июля 2021

ArtProg
> Но все-таки нужна конкретика
Объекты есть круглой формы, формы бумеранга из двух отрезков, серпы и длинные пули в один отрезок. Нужен факт столкновения и определение типа столкнувшегося объекта. Так же при каждом столкновении объекты выполняют свою колбэк-функцию для этого случая. Пули могут летать очень быстро, чтобы они не проскакивали объекты, я делю расстояние которое должна пройти пуля на размер её хитбокса и получаю число, которым нужно поделить dt. Этот новый dt используется для пошагового движения и определения столкновения на всех шарагах
hits-demo | Оптимизация проверки столкновений объектов в 2D
Противников в игре может быть не более 50, но пуль может быть до 4000 и проверять их столкновения надо даже за экраном на определённом расстоянии

#18
18:13, 31 июля 2021

Азаг Тот
> Честно, не ожидал такого
Потоки могут одновременно читать одни и те же данные, но они не могут записывать в одно и то же место одновременно, потому что не будет известно кто последний запишет данные. Для исправления этого используют блокировку потоков - мьютексы, но это приостанавливает все потоки что убивает в них смысл.

#19
18:14, 31 июля 2021

rcsim
> использовать лучи
У меня буллет хэлл игра где их много и они движутся не мгновенно, от них надо уворачиваться

#20
(Правка: 18:36) 18:29, 31 июля 2021

HPW-Dev
Несколько тысяч рэйкастов в кадр (для летящих пуль) при 10 потенциальных мишенях со сферическим коллайдером, той же юнькой хорошо пережевываются хорошо даже на webgl.

#21
18:48, 31 июля 2021

HPW-Dev
> Пули могут летать очень быстро, чтобы они не проскакивали объекты, я делю
> расстояние которое должна пройти пуля на размер её хитбокса и получаю число,
> которым нужно поделить dt. Этот новый dt используется для пошагового движения и
> определения столкновения на всех шарагах
Для этого лучше использовать continuous collision detection (ccd). В кратце - проверять колизии не с текущим точечным положением пули, а с отрезком, который пролетела пуля за последний апдейт. Если пуля толстая, то можно проверять и с капсулой (ака толстый отрезок).

По теме - рекомендую использовать regular grid, в каждую ячейку класть все объекты, AABB которых задевает эту ячейку. Для проверки колизий будет достаточно проверить все пары объектов в каждой ячейке. Query'ить тоже просто - для любой области можно определить какие ячейки задевают область, все объекты из этих ячеек - кандидаты на коллизию.
Такой подход поддерживает произвольный размер объектов. Ячейки рекомендую брать поменьше и оптимизировать хранение объектов в ячейках, а если мир большой, то разбить глобальную решётку на блоки и выгружать неактивные.

Из минусов - объекты будут записаны в нескольких ячейках одновременно, поэтому при кверении будут дупликаты и их нужно фильтровать. Но в целом обычно это не проблема.
Также будет много ячеек и много записей об объектах в них, но это оптимизируется (например до 4 байт на каждую ячейку + 8 байт на каждую запись об объекте в ячейке, всё это в плотном массиве).

И да, это параллелится на произвольное количество потоков без использования мютексов.

#22
(Правка: 19:11) 19:10, 31 июля 2021

HPW-Dev
Про распараллеливание: ты уже отметил, что писать в одно место из нескольких тредов - плохая идея. Но проверка коллизий - это по сути read-only операция. Затем следующий шаг - разрешение колизий (resolve) - это уже write операция. Так вот, первый шаг - определить все пары столкнувшихся объектов (что обычно и есть самая тяжелая операция) можно и параллельно. Каждый тред процессит некоторую область (например несколько ячеек) и составляет список пар столкнувшихся объектов. Можно проверять либо на потенциальную коллизию (AABB x AABB), либо сразу на полную (с учётом реальной геометрии объектов). Затем когда все треды отработают - у тебя будет набор списков (от каждого треда по списку), и эти списки уже можно обработать (т.е. разрешить коллизии) в главном треде - суммарно там уже будет не очень много объектов и это будет быстро.

Если будешь распределять обработку ячеек по тредам, то рекомендую ещё использовать что-то для балансировки нагрузки, какой-нибудь простенький work stealing шедулер или шедул областей на обработку через общий atomic индекс. Потому что часто бывает так, что в некоторой области объектов мало и треды на этой области быстро закончат обработку, а другие треды, которым попадётся область с большим количеством объектов - будут долго молотить, в итоге часть ядер может простаивать.

#23
20:52, 31 июля 2021

HPW-Dev
> Мне что, надо проводить линию от старой позиции объекта до новой и проверять
> пересечение этой линии с фигурами?

В общем то да и это не самый сложный случай, например рикошет пули уже будет посложнее.

#24
0:00, 1 авг. 2021

  Собственно многое уже ответили выше, я лишь немного дополню. Если снаряд(пуля) движется за экраном, то тут наверное только какая нибудь ускоряющая структура типа октодерева. А вот, например, со Screen-Space физикой уже можно немного схитрить. У себя делал так. Для случая столкновения шарообразного снаряда со стеной(отрезком) строил сумму Минковского такого же по радиусу как и снаряд круга и всех отрезков которые попали на экран. Получалась эквидистантная линия. Дальше оставалось только установить факт пересечения этой эквидистантной линии с отрезком, соединяющим центр круга и следующую позицию снаряда(круга). 2DMinkovskiCollision | Оптимизация проверки столкновений объектов в 2D Причем такой способ достаточно шустро работал даже на нескольких десятках тысяч снарядов(пуль) на CPU. Ну а дальше, конечно придется подключать и GPU, так как скорость просчета будет уже опиратся не в физику, а в банальную прорисовку спрайтов(в зависимости от того конечно какой размер спрайта). Для обьектов более сложной формы думаю их можно аппроксимировать несколькими кругами.

#25
(Правка: 18:28) 18:27, 1 авг. 2021

Alexander K
> проверять колизии не с текущим точечным положением пули, а с отрезком, который пролетела пуля за последний апдейт
У некоторых пуль есть анимации взрыва/разрушения, хотелось бы чтобы они были на позициях, где пуля врезалась в объект, а если проверять когда она уже пролетела, то она взорвётся дальше от места столкновения. Растягивание до капсулы звучит хорошо, но надо бы иметь понятие где в этой капсуле состоится столкновение, чтобы там отобразить анимацию взрыва.
> рекомендую использовать regular grid
Обязательно это добавлю. Ячейки будут хранить ссылку на объект, а объект будет иметь ссылку на следующий объект, таким образом получится связь по цепочке и не придётся выделять новую память
> И да, это параллелится на произвольное количество потоков без использования мютексов.
Распараллелю через OpenMP все проверки хитбоксов, но без мютексов не обойдётся - взрыв пули вызывает создание объекта в общем хранилище и этот момент надо синхронизировать.

#26
18:31, 1 авг. 2021

Alexander K
> определить все пары столкнувшихся объектов (что обычно и есть самая тяжелая операция) можно и параллельно
Действительно
> то рекомендую ещё использовать что-то для балансировки нагрузки
В OpenMP есть разные балансировки, я их попробую

#27
(Правка: 18:42) 18:40, 1 авг. 2021

В общем надо нагрузить тестовую сцену чтобы все стреляли друг в друга и замерить скорости всех предложенных оптимизаций. Сейчас в игре тормозит проверка дистанций и проверка пересечения разных фигур. Не буду упрощать всё до сфер, иначе длинные пули придётся заполнять мелкими кругами по всей длине. Добавлю разбиение пространства чтоб не дёргать дальние объекты и надеюсь, что построение окто-дерева или обновление сетки не будет сильно затратным

#28
19:16, 1 авг. 2021

HPW-Dev
> Растягивание до капсулы звучит хорошо, но надо бы иметь понятие где в этой
> капсуле состоится столкновение, чтобы там отобразить анимацию взрыва.
Когда ты обнаружил коллизию на капсулах - дальше обычно запускается бинарный поиск. Т.е. зная скорости объектов считаешь капсулы для половины таймстепа, потом в зависимости от результатов для 1/4 или 3/4 таймстепа и т.д.

#29
19:24, 1 авг. 2021

HPW-Dev
> Потоки могут одновременно читать одни и те же данные, но они не могут
> записывать в одно и то же место одновременно, потому что не будет известно кто
> последний запишет данные. Для исправления этого используют блокировку потоков -
> мьютексы, но это приостанавливает все потоки что убивает в них смысл.
Во-первых мьютексы приостанавливают не все потоки, а только те, которые пытаются войти в один и тот же мьютекс. Например если у тебя регулярная сетка и ты заведешь по мьютексу на каждую ячейку, то потоки редко буду упираться в мьютекс.
Во-вторых, есть локфри структуры данных. Самая простая для реализации linked list. Если в каждой ячейке грида у тебя будет такой линкед лист - то весь твой грид будет многопоточным без единого мьютекса.

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