Реализация оберточной проволоки (например, Worms Ninja Rope) в 2D физическом движке

34

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

Для игрового процесса важна способность веревки обматывать окружающую среду, а затем разворачивать ее. Он даже не должен вести себя как веревка - подойдет «проволока», состоящая из отрезков прямых линий. Вот иллюстрация:

Веревка ниндзя, обвивающая препятствия

Это очень похоже на «Веревку ниндзя» из игры Worms.

Потому что я использую 2D физический движок - моя среда состоит из 2D выпуклых многоугольников. (В частности, я использую SAT в Farseer.)

Поэтому мой вопрос заключается в следующем: как бы вы реализовали эффект «обертывания»?

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

Но что такое математика / алгоритм, используемый для определения того, когда и где нужно разделить активный сегмент линии? И когда его нужно объединить с предыдущим сегментом?

(Ранее этот вопрос также задавался о том, как сделать это для динамической среды - я решил разделить это на другие вопросы.)

Эндрю Рассел
источник

Ответы:

18

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

Полезная схема положения веревки ниндзя

Способ обнаружения столкновений заключается в том, что для корня текущего сегмента веревки O - конечное положение веревки на предыдущем кадре, A - конечное положение веревки на текущем кадре, B и каждая угловая точка P в многоугольнике. геометрию уровня, которую вы рассчитываете (OA x OP), (OP x OB) и (OA x OB), где «x» представляет собой получение координаты Z перекрестного произведения между двумя векторами. Если все три результата имеют одинаковый знак, отрицательный или положительный, а длина OP меньше, чем длина сегмента веревки, точка P находится в пределах области, охватываемой качелями, и вам следует разбить веревку. Если у вас есть несколько угловых точек соударения, вам нужно использовать первую точку, которая ударяется о веревку, то есть ту, где угол между OA и OP наименьший. Используйте точечное произведение, чтобы определить угол.

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

Для математики для соединения сегментов мы будем использовать точку крепления предыдущего сегмента веревки, Q, а также те, которые мы имели для случая разделения. Итак, теперь вы хотите сравнить векторы QO, OA и OB. Если знак (QO x OA) отличается от знака (QO x OB), веревка пересеклась слева направо или наоборот, и вам следует присоединиться к сегментам. Это, конечно, также может произойти, если веревка поворачивается на 180 градусов, поэтому, если вы хотите, чтобы веревка могла оборачиваться вокруг одной точки пространства вместо многоугольной формы, вы можете добавить специальный случай для этого.

Этот метод, конечно, предполагает, что вы делаете обнаружение столкновений для объекта, висящего на веревке, чтобы он не оказался внутри геометрии уровня.

Pekuja
источник
1
Проблема этого подхода состоит в том, что ошибки точности с плавающей точкой позволяют канату проходить «через» точку.
Эндрю Рассел
16

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

Так что здесь очень мало реальной физики. Активная секция может быть смоделирована как одна жесткая пружина с массой на конце

Интересным моментом будет логика разделения / соединения неактивных участков веревки с активной секцией.

Я предполагаю, что будет 2 основных операции:

«Раскол» - веревка что-то пересекла. Разбейте его на пересечении на неактивный раздел и новый, более короткий, активный раздел

«Соединение» - активная веревка переместилась в положение, в котором ближайший перекресток больше не существует (это может быть просто тест на угловое / точечное произведение?). Присоединяйтесь к 2 разделам, создавая новый, более длинный, активный раздел

В сцене, построенной из 2D многоугольников, все точки разделения должны находиться в вершине сетки столкновений. Обнаружение столкновений может упроститься до чего-то вроде «Если веревка проходит через вершину в этом обновлении, разделить / соединить веревку в этой вершине?

bluescrn
источник
2
Этот парень был прямо на месте ... На самом деле, это не "жесткая" пружина, вы только вращаете какую-то прямую линию вокруг ...
спидер
Ваш ответ технически правильный. Но я вроде бы предположил, что наличие отрезков, разделение и соединение их было очевидным. Я заинтересован в реальном алгоритме / математике, чтобы сделать это. Я сделал мой вопрос более конкретным.
Эндрю Рассел
3

Посмотрите, как была реализована веревка ниндзя в Гусаносе :

  • Веревка действует как частица, пока не присоединится к чему-либо.
  • После прикрепления веревка просто прикладывает усилие к червю.
  • Прикрепление к динамическим объектам (как и другим червям) все еще является TODO: в этом коде.
  • Я не могу вспомнить, поддерживается ли обтекание объектов / углов ...

Соответствующая выдержка из ninjarope.cpp :


void NinjaRope::think()
{
    if ( m_length > game.options.ninja_rope_maxLength )
        m_length = game.options.ninja_rope_maxLength;

    if (!active)
        return;

    if ( justCreated && m_type->creation )
    {
        m_type->creation->run(this);
        justCreated = false;
    }

    for ( int i = 0; !deleteMe && i < m_type->repeat; ++i)
    {
        pos += spd;

        BaseVec<long> ipos(pos);

        // TODO: Try to attach to worms/objects

        Vec diff(m_worm->pos, pos);
        float curLen = diff.length();
        Vec force(diff * game.options.ninja_rope_pullForce);

        if(!game.level.getMaterial( ipos.x, ipos.y ).particle_pass)
        {
            if(!attached)
            {
                m_length = 450.f / 16.f - 1.0f;
                attached = true;
                spd.zero();
                if ( m_type->groundCollision  )
                    m_type->groundCollision->run(this);
            }
        }
        else
            attached = false;

        if(attached)
        {
            if(curLen > m_length)
            {
                m_worm->addSpeed(force / curLen);
            }
        }
        else
        {
            spd.y += m_type->gravity;

            if(curLen > m_length)
            {
                spd -= force / curLen;
            }
        }
    }
}
Leftium
источник
1
Хм ... это, похоже, не отвечает на мой вопрос вообще. Весь смысл моего вопроса в том, чтобы обернуть веревку вокруг мира, сделанного из полигонов. Кажется, у Гусаноса нет мира обёрток и растровых изображений.
Эндрю Рассел
1

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

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

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

Пи-3
источник
1

Вот пост, в котором есть ссылки на статьи о подобных типах симуляций (в инженерном / академическом контексте, а не для игр): https://gamedev.stackexchange.com/a/10350/6398

Я попробовал по крайней мере два разных подхода к обнаружению столкновений + отклик для такого рода «проводной» симуляции (как видно в игре Umihara Kawase); по крайней мере, я думаю, что это то, что вам нужно - кажется, нет особого термина для такого рода симуляции, я просто называю это «провод», а не «веревка», потому что кажется, что большинство людей считают «веревку» синонимом «цепи частиц». И, если вы хотите, чтобы у ниндзя было поведение прилипания (то есть он может толкать и тянуть), это скорее напоминает жесткий провод, чем веревку. Так или иначе..

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

(Я не могу полностью вспомнить OTOH, но вы можете подойти к нему следующим образом: найдите время t, когда точка a содержится в линии, проходящей через b, c, (я думаю, что я сделал это, решив, когда точка (ab, cb) = 0, чтобы найти значения t), а затем, учитывая действительное время 0 <= t <1, найдите параметрическую позицию s a на сегменте bc, то есть a = (1-s) b + s c, и если a находится между b и c (то есть, если 0 <= s <= 1), это допустимое столкновение.

AFAICR, вы можете подойти к нему и с другой стороны (то есть решить для s, а затем подключить это, чтобы найти t), но это гораздо менее интуитивно понятно. (Извините, если это не имеет никакого смысла, у меня нет времени, чтобы выкопать свои записи, и это было несколько лет!))

Таким образом, теперь вы можете рассчитать все моменты, в которые происходят события (т.е. узлы веревки должны быть вставлены или удалены); обработать самое раннее событие (вставить или удалить узел), а затем повторять / повторять до тех пор, пока не останется больше событий между t = 0 и t = 1.

Одно предупреждение об этом подходе: если объекты, которые может обернуть веревка, являются динамическими (особенно, если вы имитируете их И их влияние на веревку, и наоборот), тогда могут возникнуть проблемы, если эти объекты обрезают / проходят через каждый Другое - провод может запутаться. И, безусловно, будет сложно предотвратить такого рода взаимодействие / движение (углы объектов проскальзывают друг через друга) в физическом моделировании в стиле box2d. Небольшое проникновение между объектами - нормальное поведение в этом контексте.

(По крайней мере ... это была проблема с одной из моих реализаций "wire".)

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

Я думаю, что подход Пекуджи работает и для этого, однако есть альтернативные подходы. Один из подходов, который я использовал, заключается в добавлении вспомогательных данных о столкновениях: в каждой выпуклой вершине v в мире (то есть в углах фигур, которые может обернуть веревка), добавьте точку u, образующую направленный отрезок линии uv, где u - некоторая точка «внутри угла» (то есть внутри мира, «позади» v; для вычисления u вы можете направить луч внутрь от v вдоль его интерполированной нормали и остановиться на некотором расстоянии после v или до того, как луч пересечется с краем мира и Выход из сплошной области. Или вы можете просто нарисовать сегменты вручную, используя визуальный инструмент / редактор уровней).

В любом случае, теперь у вас есть набор "угловых линейных сегментов"; для каждого uv и каждого сегмента ab в проводе проверьте, пересекаются ли ab и uv (т. е. статический, логический запрос пересечения lineseg-lineseg); если это так, выполните возврат (разбейте линейный сегмент ab на av и vb, т. е. вставьте v), записав, в каком направлении изогнут верёвку в v. Затем для каждой пары соседних линейных сегментов ab, bc в проводе проверьте текущее направление изгиба в точке b то же самое, что и при генерации b (все эти тесты «направления изгиба» являются просто тестами со знаком области); если нет, объедините два сегмента в ac (то есть удалите b).

Или, может быть, я слился, а затем разделился, я забыл - но это определенно работает по крайней мере в одном из двух возможных заказов! :)

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

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

raigan
источник
0

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

Вот демоверсия с источником: http://www.ewjordan.com/rgbDemo/

(Переместитесь вправо на первом уровне, есть красная веревка, с которой вы можете взаимодействовать)

Рейчел Блум
источник
2
Э-э, это именно то, чего я не хочу (см. Вопрос).
Эндрю Рассел
Ах. Это не было ясно из исходного вопроса. Спасибо, что нашли время, чтобы прояснить это так много. (Отличная диаграмма!) Я бы по-прежнему использовал серию очень маленьких фиксированных соединений, в отличие от динамических разбиений - если в вашей среде это не является проблемой с большой производительностью, код намного проще.
Рэйчел Блум