LINUX.ORG.RU

Детектор столкновений 2D. Game dev physics.

 


1

1

Готовое взять не предлагать, хочется сначала разобраться в подкапотстве.

Когда объект летит со страшной скоростью, а у движка фиксированный шаг времени, в который движок счититает, то летящий объект может перешагивать некоторые объекты. Можно наблюдать во многих гамесах, когда грузовик застревает наполовину в стене и адово дёргается в конвульсиях. Но у меня вопрос про 2D, хотя математически один хре.

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

Посоветуйте куда копать, причём с учётом почти полного дерева в физике. Что такое дифуры, например, знаю чисто теоретически, не применял никогда.

Копай исходники Box2d.


PS
луч, не луч... У тебя симуляция физических процессов идет во времени. Делай ее 1000000 раз в секунду и тогда грузовик не будет застревать в стене. Он до нее просто не доедет :)

habamax ★★★
()
Ответ на: комментарий от habamax

Насчёт 1000000 раз: есть просто класс движков априорный, когда они заранее знают с кем и когда столкнуцца. Им вообще «тикать» не надо, они это делают только когда параметры у какого-то объекта поменялись (юзер включил мотор).

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

: есть просто класс движков априорный, когда они заранее знают с кем и когда столкнуцца. Им вообще «тикать» не надо, они это делают только когда параметры у какого-то объекта поменялись (юзер включил мотор).

Не понятно. Заранее знают, что этот грузовик столкнется с этой стенкой?
Даже если грузовик свернет и поедет в другую сторону?

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

Я могу ошибаться, м.б. есть новый класс физ. движков, где обсчет физики не зависит от времени никак.

habamax ★★★
()

Сначала проверка по габаритам при помощи операций вычитания и сравнения. Затем проверка наложения по альфа-каналу.

rezedent12 ☆☆☆
()
Ответ на: комментарий от habamax

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

hlamotron
() автор топика
Ответ на: комментарий от habamax

Нет таких, просто физ модели становятся более подробными, а не парой параллелепипедов.

anonymous
()
Ответ на: комментарий от hlamotron

Проводим луч, попадаем в несшитый угол мешки, который на глаз не видно, угадай, столкнется ли грузовик со стеной?

anonymous
()
Ответ на: комментарий от hlamotron

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

Это все оптимизация дискретной физической системы.
Тебе в любом случае нужно периодически считать новые параметры - что при отсутствии событий твой грузовик упрется в стену через 3 секунды. Причем «крутанул руль» происходит не мгновенно, т.е. ты меняешь направление каждое dt, в эти моменты тоже надо считать твои «лучи».

habamax ★★★
()
Ответ на: комментарий от habamax

Не нужно, я заранее знаю через сколько (3 секунды) грузовик упрётся и куда. Если крутание руля происходит не мгновенно, вот тут рассчёты делаются чаще, но когда руль перестали так крутить, перестаём считать.

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

Это к вопросу о представлении физ модели, тут на вкус и цвет, от нескольких нормалей, до секторов и конусов. Для быстродействия используют уточняющие расчеты, с радиусами переключения надеюсь все понятно

anonymous
()

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

xmichael
()

А что будешь делать, если вместо прямых лучей будут получаться кривые, например, под действием гравитации?

sevenredlines
()
Ответ на: комментарий от hlamotron

PhysX

Bullet Physics Library

Open Dynamics Engine

Поковыряй, глядишь что-то из идей утащишь.

anonymous
()
Ответ на: комментарий от sevenredlines

Придётся юзать квадратические законы. Т.е. линия как-бы есть, но она не линейная, а квадратическая или там кубическая, кому сколько масла на хлеб смотря нужно.

hlamotron
() автор топика

Есть какой-то альтернативный подход к запилу физических движков, когда движок работает на каких-то континуумах, типа пересекает луч движения с объектами и физически ничего не может пропустить?

Есть. Вот статья про event-driven simulation например: http://algs4.cs.princeton.edu/61event/

Deleted
()
Ответ на: комментарий от hlamotron

Не нужно, я заранее знаю через сколько (3 секунды) грузовик упрётся и куда

Через 0.3 сек будет грязь и скорость изменится, через 0.7 сек наедешь на камень и направление изменится, легковушка пойдет на обгон и затормозит перед тобой через 2 сек.

Таких событий может быть очень много и все они зависят от «времени».
Ты можешь отсечь часть, чтобы они не участвовали в симуляции до определенного момента, но сама симуляция (если физ. мир достаточно сложный) будет «тикать».

habamax ★★★
()
Ответ на: комментарий от habamax

Грязь тоже является объектом и она нам будет известна заранее. Мы закинем в шедулер задачу «проснись через 0.3 сек, надо будет грязь обработать».

Все грязи, камни, стены, другие грузовики — ближайшее из «непустот» закидывается в шедулер и мы засыпаем до того времени, проснувшись обсчитываем, возможно меняем направление, а потом находим новый ближайший, кидаем его в шедулер и засыпаем обратно.

Так я вижу!

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

Хех, ответь на вопрос, когда надо закинуть в шедулер и надо ли вообще. Глядишь взгляд поменяется.

anonymous
()
Ответ на: комментарий от hlamotron

Все грязи, камни, стены, другие грузовики — ближайшее из «непустот» закидывается в шедулер и мы засыпаем до того времени, проснувшись обсчитываем, возможно меняем направление, а потом находим новый ближайший, кидаем его в шедулер и засыпаем обратно.

Угу, и шедулер у тебя не «тикает».

habamax ★★★
()
Ответ на: комментарий от habamax

Шедулер не тикает — он засыпает до времени, на которое назначена ближайшая задача. Очередь с приоритетом, структура данных под названием Heap.

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

Шедулер не тикает — он засыпает до времени, на которое назначена ближайшая задача.

Ну круто, что могу сказать. Позови, когда сделаешь. Особенно интересует шедулер, который будет время до следующего события считать не тикая. А так же, что будет происходить с большой очередью событий разделенных мизерными интервалами.

Очередь с приоритетом, структура данных под названием Heap.

Не важно, где ты будешь хранить события. Больше интересует, какими объектами предполагается оперировать, как их отражать в физическом мире и на экране? Как задавать правила взаимодействия?

habamax ★★★
()
Ответ на: комментарий от habamax

Тикать системный таймер будет, ожидать назначенного времени можно с помощью usleep( (uint64_t)useconds ), усыпляющий меня до ближайшего рассчитанного события.

hlamotron
() автор топика
Ответ на: комментарий от habamax

какими объектами предполагается оперировать

Не важно, где ты будешь хранить события

Ивентами, какими же еще, сам же и ответил. Или месагами. «Нотификациями». Это моночленно. А чего с наступлением события происходит, шедулер даже интересовать не должно, т.к. очередь — это «декоуплинг паттерн» (http://gameprogrammingpatterns.com/event-queue.html ) :) Отвязывает «чо храница» от «как», но «очередь с приоритетом» — в своем роде навязывает дисциплину вставки-извлечения. А именно сортирует события/мессаги при добавлении.

Время начала, время конца (если нужно — типа интервал). И в момент извлечения уведомление интересующихся (обсерверов), что оно наступило/закончилось.

Не важно, где ты будешь хранить события
как их отражать в физическом мире и на экране? Как задавать правила взаимодействия?

очередь с приоритетом автосортированая, это все что о ней интересно, «правила взаимодействия», «отражения в физ. мире» и «отображения на экране» — это где-то еще. Например, «в большом адронном коллайдере», «адвансед флайт модели» и «рендере». Т.к. симуляция кроме, тайм-драйвен (эти твои «тики» — квантование по времени), таки бывает ивент-драйвен, в очередь запросто можно засовывать то, что «в принципе может произойти» (а тебе это заранее известно — «клик мыши» это или «удар апстену») с заданными начальными условиями, с известной оценкой времени и экстраполяцией траектории, а в момент извлечения просто произойдет оценка — «наступило» или «нет», и нужны ли по этому поводу какие-то «отображения» и прочие спецэффекты.

Если охота — можно по пачке критериев, в мультилевел-фидбек

https://en.wikipedia.org/wiki/Multilevel_feedback_queue

Отличий от раунд-робина, который часто используется в движках с «тикерами» — в хитровыдуманных очередях приоритеты развешиваются явочным порядком, т.к. события-то все заранее известны (в раунд-робине приоритеты либо приделаны сбоку, либо... «неявные» — потому что подсчет тиков). Но это не отменяет применимости шедуляния через очередь в каком-либо событийном движке — т.к. применяется в шедулерах осей, например, где эти твои оч. важные проблемы «длины очереди» и «большого количества событий» уже решены.

slackwarrior ★★★★★
()
Ответ на: комментарий от slackwarrior

Спасибо за развернутый ответ.

а в момент извлечения просто произойдет оценка — «наступило» или «нет», и нужны ли по этому поводу какие-то «отображения» и прочие спецэффекты

Т.е. существуют все те же rigidbody+boundingboxы, для оценки «наступило или нет».
В симуляции, где есть достаточно много объектов взаимодействия, генерится большое количество просчитанных ивентов, эти ивенты в свою очередь могут генерить другие ивенты. Сама очередь кроме того, что отсортирована должна очищаться от невалидных ивентов.

Уточняющий вопрос.

Самая простая симуляция — сферический камень массой 1 кг падает с высоты 100 м на абсолютно не упругую платформу. Начальная скорость 0, а g=9.8м/с2

Какие начальные события, какие и сколько дополнительных будет создано?

Как будет рассчитываться положение камня для отображения через 0.001 сек, 0.005 сек ... и т.д.?

Чем это будет отличаться от «обычных» физических движков, на которые навешиваются разные методы экстраполяции положения объектов?

habamax ★★★
()
Ответ на: комментарий от hlamotron

Тикать системный таймер будет, ожидать назначенного времени можно с помощью usleep( (uint64_t)useconds ), усыпляющий меня до ближайшего рассчитанного события.

А между событиями у тебя что? Действуют ли на объекты силы? Как долго? Как рисовать положение этого объекта в тот фреймрейт, который у тебя есть?

habamax ★★★
()
Ответ на: комментарий от habamax

Не ломай беднягам мозг (:

А то ну как щя пойдут переизобретать алгоритмы предсказания рендринга и физики

anonymous
()
Ответ на: комментарий от habamax

Между событиями ничего. Силы подействовали в момент поиска ближайшего по времени события столкновения, дальше от сил ничего не требуется. Рисование движения на экране - другой вопрос, просто умножаем скорость на временной интервал до предыдущего нарисованного фрейма и рисуем текущую позицию. Обо всех изменениях в этом процессе нас оповестит физический шедулер (он проснётся в нужный момент и скажет: «поменяй скорость у объекта id сцуко»).

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

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

Некоторые силы действуют постоянно. Другие в заданном интервале.
Допустим на грузовик действует сила, придающая ему ускорение в течение 10 сек. Его скорость плавно изменяется. Как часто должны генериться события в этом временном интервале? Время столкновения со стенкой меняется с каждой миллисекундой...


Обо всех изменениях в этом процессе нас оповестит физический шедулер (он проснётся в нужный момент и скажет: «поменяй скорость у объекта id сцуко»).

(0 сек) Шедулер: Ого! Камень падает! Скорость 0 м/с
...
...
(n сек) Шедулер: камень падает! Скорость nnn м/с

Если шедулер сгенерит мало событий, то для отрисовки объекта между фреймами будет использована некорректная скорость. Твой камень упадет на землю, но на экране зависнет.

habamax ★★★
()
Ответ на: комментарий от habamax

Можно заранее учесть, когда ускоряющийся предмет убьётся об стену, тебе же известны все параметры (начальные координаты, начальная скорость, ускорение) заранее и они не меняются.

Шедулер сгенерит ровно столько событий, сколько столкновений. Между столкновениями все движения описываются неизменяющимися уравнениями. Чтобы камню лететь до земли с ускорением, ему шедулер не нужен вообще, достаточно задать стартовые координаты, стартовую скорость, стартовое ускорение, предел скорости, всё, на каждом фрейме графическая рисовалка апдейтит координаты камня по формуле и рисует. Когда возникнет событие столкновения с землёй, тогда шедулер проснётся и скажет, чтобы камню поменяли все параметры в этой формуле.

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

Можно заранее учесть, когда ускоряющийся предмет убьётся об стену, тебе же известны все параметры (начальные координаты, начальная скорость, ускорение) заранее и они не меняются.

Время воздействия?


Шедулер сгенерит ровно столько событий, сколько столкновений.

В интервале 10 секунд это сколько? Причем 10 секунд это или 15 или нцать — заранее не известно, например, пока пользователь кнопку жмет.

10? фпс*10?

на каждом фрейме графическая рисовалка апдейтит координаты камня по формуле и рисует

Т.е. физику (расчет по формуле) придется самому эмулировать во время графического апдейта?

habamax ★★★
()
Ответ на: комментарий от hlamotron

Ладно, забей.

Твори, может что интересное получится.

habamax ★★★
()
Ответ на: комментарий от hlamotron

В камень выпущена пуля и она сцука попадет?

И еще не маловажное замечание, расчет физ характеристик и физ взаимодействий определяется только потребностью создателя, набор модификаторов во времени можно вполне синхронизировать с отрисовкой, если ничего не происходит, то изменения минимальны нагрузки не дает

anonymous
()
Ответ на: комментарий от anonymous

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

Вторую часть коммента твоего, о великий анонимус, ваше величество, не смог понять.

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

На вторую часть моего поста ты ответил сам, только СОЗДАТЕЛЬ (эка забавно (: ) решает как работает его мир. Примерчик, заменим пулю на точку, камешек на шар, в мире есть только два объекта, можем вычислять только одно событие «точка попадает в границы шара», все остальное не имеет значения, вычисления примитивны.

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

anonymous
()
Ответ на: комментарий от hlamotron

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

тЭорЭтик ср***ый, ты хоть понимаешь что это работает только в мире где подвижный предмет - только один? И это - твой грузовик :)

Я ж и говорю - тэоретик, причём даже тэоретик - плохонький! :(

anonymous
()
Ответ на: комментарий от anonymous

Не понимаю, а что тебя смущает? Я же сраный теоретег, теоретеги ничего не понимают. Ты сам себе противоречишь, зная что я сраный теоретег и требуешь какого-то понимания. Можно ли ждать, что ты асктишься минут через 10 хотя-бы?

hlamotron
() автор топика
Ответ на: комментарий от hlamotron

Не понимаю, а что тебя смущает?

Цвет твоих мыслей. Исключительно и только :)

Я же сраный теоретег, теоретеги ничего не понимают.

сраные - нет, обычные - таки да. Потому что вторые грызут гранит наук, а первые просто так ...

Ты сам себе противоречишь, зная что я сраный теоретег и требуешь какого-то понимания.

Не требую я. Это я так на столбик писаю.

Можно ли ждать, что ты асктишься минут через 10 хотя-бы?

А тебе зачем?

hlamotron

Ты не один тролить умеешь, что тебе и демонстрируют :-p

anonymous
()
Ответ на: комментарий от anonymous

У мыслей есть цвет? Читать ли дальше - вот вопроса кусок!

hlamotron
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.