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

Непрерывное обнаружение столкновений [2d] [FixedMath]

Страницы: 1 2 Следующая »
#0
1:41, 21 июня 2022

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

Они решаются итерационно примерно по следующему алгоритму.

  • Строится КД дерево.
  • Для каждого юнита из КД дерево выбираются потенциально пересекающиеся по радиусу.
  • Дальше по расстоянию Чебышева определяются пересекающиеся.
  • Пересекающиеся добавляются в хеш сет что бы повторно не обрабатывать пару.
  • Пары добавляются в список колизий.
  • Если один из юнитов статический то делается еще проверка по честному расстоянию.
  • Статические коллизии обрабатываются отдельно.
  • Дальше для статических колизий происходит выталкивание на расстояние равное сумме радиусов.
    Для обычных колизий рассталкиваем пару по вектору, который образуется разницей между центрами юнитов, пропорционально весам.

    В общем то ни чего особо сложного.

    Но решили мы, что обрабатывать все это 60 раз в секунду не за чем, и в целом мы можем механику считать хоть 5 раз в секунду например, а визуал интерполировать.

    Но на землю нас вернул САБЖ.

    И теперь вопрос, в целом я понимаю что можно механику считать 5 раз в секунду.
    А рассталкивание сделать итерационо с более мелкой дельтой, но хочется чего то иного.

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

    Что мне понятно.
    Из КД дерева надо запрашивать потенциально пересекающихся юнитов по радиус + расстояние перемещения.

    Проверку пересечения по Чебышеву надо заменить на проверку пересечения двух движущихся окружностей.

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

    Дальше в рамках проверки пересечения необходимо определить точку контакта...

    И вот тут я уже начинаю сыпаться. Чего в общем хочется.

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

    Хочется что бы решение столкновений учитывало веса юнитов.

    А дальше я еще понимаю что на самом деле движется N юнитов, а не пара и все становится как то совсем уныло. Может это вообще не особо решаемая задача?

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

    Пните в нужном направлении, пожалуйста.

    #1
    1:57, 21 июня 2022

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

    #2
    7:47, 21 июня 2022

    Оффтоп, но на хешгриде у меня получилось выжать 6мс при 250к окружностей. 25к динамических, остальные статические. Статика против статики не рассчитывается, конечно же. Причем 4.5мс занимает построение хешгрида. КД дерево вроде строится значительно дороже.

    #3
    10:22, 21 июня 2022

    Все таки осталась проблема что быстрые юниты перепрыгивают через остановившихся перед ними колег...
    Так что если все таки кто то подскажет куда лучше копать буду рад.

    Dampire
    Хешгрид это просто берем координа ты на гриде имеющем определенный размер ячеек и складываем в хешмапу?

    Надо подумать... такой вариант наверное приемлем, но у нас еще радиусы юниты отличаются.
    Ну и в целом КД дерево конечно кушает, но пока не кажется ботлнеком

    #4
    (Правка: 11:06) 11:05, 21 июня 2022

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

    #5
    11:33, 21 июня 2022

    Suslik
    ну я держу в голове и всякие steering behaviour и crowd simulation.
    Но это следующий шаг на самом деле. У нас ограниченая область в которой юниты броуновское движение изображают, и в любом случае колизий не изебжать. А слишком умное поведение мобов когда они будут избегать столкновений немного другую картинку даст.
    Сейчас задние юниты толкают впереди идущих и все это выглядит как стенка на стенку с толкотней.
    А с crowd simulation будет битва интелегентов какая то.

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

    #6
    14:35, 21 июня 2022

    если у тебя цель — эффективно переместить группу юнитов из одной точки в другую, то это в принципе очень трудно сделать, используя только локальное взаимодествие между агентами. для этого нужны глобальные алгоритмы, в которых сразу каждый опосредованно воздействует на каждого, например, через поле течения во fluid dynamics. это даёт не локальное поведение "как мне избежать столкновений", а глобальное "в каком направлении нам всем идти, чтобы избежать затора".

    #7
    (Правка: 15:59) 15:58, 21 июня 2022

    cNoNim
    > Хешгрид это просто берем координа ты на гриде имеющем определенный размер ячеек
    > и складываем в хешмапу?
    Типа того. Разбиваем пространство на сетку с бакетами, тривиальная хешфункция раскидывает позиции по бакетам. Разные радиусы вообще не критичны, так как размер ячеек подбирается эмпирически и обычно его хватает даже для максимального радиуса.
    > Ну и в целом КД дерево конечно кушает, но пока не кажется ботлнеком
    По-моему самый что ни на есть ботлнек. Я конечно хз какая у тебя реализация, но обычно скорость доступа и локальность данных в КД очень не очень. Я пытался сделать две хешмапы, статическая для статики, динамическая для динамики. Просевшая скорость выполнения броадфазы сожрала весь профит от увеличенной скорости генерации хешмапы. А в КД обычно даже не два бакета на итерацию и абсолютно рандомный доступ.

    #8
    16:53, 21 июня 2022

    Dampire
    > Разные радиусы вообще не критичны, так как размер ячеек подбирается эмпирически
    > и обычно его хватает даже для максимального радиуса.
    тут вот в этом затык как раз, я понял что ты имеешь ввиду, но нам такое неподходит именно потому что у нас по большому счету не большая карта, и сопоставимые с ее размерами радиусы мобов, если ячейку брать по макс радиусу, то толку от такой ускоряющей структуры особо не будет.
    Но я говорю на счет того что КД щас не ботлнек потому что построение КД щас не самое тормозное что там происходит

    #9
    17:06, 21 июня 2022

    Вот на 84х мобах
    Collision Detection 1.96 ms
    Из них
    Построение KD дерева 0.17 ms
    Запросы в KD дерево 0.46 ms

    #10
    17:13, 21 июня 2022

    На 84 мобах по-моему брутфорс будет оптимальнее, нет?

    #11
    17:55, 21 июня 2022

    Dampire
    там еще игра играется же... ну и изначально было брутфорсом и было явно не быстрее )
    а КД дерево там еще по чуть и для логики юзается. Выбор цели и тд и тп

    #12
    21:47, 21 июня 2022

    7к коллизий сфера-сфера занимает больше 2мс? По-моему что-то пошло не так.

    #13
    0:05, 22 июня 2022

    7к коллизий сфера-сфера занимает больше 2мс? По-моему что-то пошло не так.

    Не тот процессор с али привезли :)

    #14
    2:09, 22 июня 2022

    Dampire
    ну я хз чего тебе сказать... fixed math, мобилки, юнити... я могу конечно еще разок почекать в билде.
    ну или надо данные по локальней упаковать, но вот я тупо щас в редакторе для чека поменял запросы в KD tree на брут форс и на одинаковом количестве брутфорсом 5.5мс, через КД дерево 4.2мс

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