Как осуществляется локальное предотвращение RTS?

15

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

Для игр RTS, таких как Starcraft 2, как делается локальное уклонение? Смоделирована ли физика или универсальный контроллер решает, где все должно быть? Я знаю, что этот вопрос может быть немного широким, поэтому я спрашиваю конкретно, как добиться локального поведения избегания в Starcraft 2; хотя все, что работает, будет очень цениться.

Я не ищу какой-либо код - просто полезные ресурсы или объяснения того, как Starcraft 2 (или подобные игры) справляются с локальным уклонением.

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

Требуемое решение должно удовлетворять следующим требованиям (как в Starcraft 2):

  • Объекты не должны пересекаться; или, по крайней мере, совпадения должны быть в конечном итоге разрешены.
  • Объекты не отталкивают друг друга больше, чем необходимо, поэтому 2 отряда могут стоять и двигаться рядом друг с другом в формации.
  • Не должно быть никаких странных действий, когда объекты слипаются в направлении одного и того же пункта назначения.
  • Может поддерживать единицы разных размеров и даже разных выпуклых форм.

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

JPtheK9
источник
"поведение стада" (термин Google) - очень большая проблема,
урод, чудак,
Это было в очереди на закрытое голосование как «слишком широкое» - я склонен согласиться. Попытка сузить: что вы пробовали? Какие «нежелательные эффекты» вы хотите избежать? Правильно ли я сказал, что вы хотите, чтобы юниты оставались в строю?
Анко
Игры RTS часто работают каждым клиентом, выполняющим одно и то же детерминированное моделирование на каждой машине. Таким образом, в основном, если вы можете решить эту проблему для одной машины, вы можете применить одно и то же решение к многопользовательским ситуациям, независимо от того, какую локальную технику избегания вы используете.
Алан Вульф
Спасибо за отзыв по вопросу. Я немного сузил вопрос и объяснил, чего конкретно я пытаюсь достичь.
JPtheK9
Это отличный ресурс: red3d.com/cwr/steer
tbkn23

Ответы:

11

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

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

Теперь, чтобы выполнить симуляцию:

  1. Для каждого агента, предполагая, что он неподвижен, рассчитайте все скорости, которые могут привести к его столкновению в любой точке в будущем с любым другим движущимся агентом. Это может быть представлено в «пространстве скоростей» как набор пересекающихся полуплоскостей (также известный как скоростное препятствие ).
  2. Определите точку в этом месте, ближайшем к v_p, это новая скорость единицы.

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

Для вычисления двух этапов алгоритма, описанного выше, вы можете использовать суммы Минковского, чтобы определить, что является скоростным препятствием, а затем использовать модель линейного программирования (например, симплексный алгоритм ), чтобы определить ближайшую точку, v_pкоторая избегает скоростного препятствия. Кроме того, код для предотвращения столкновений доступен для вашего просмотра и был портирован на C # для использования в игровых движках, таких как Unity. Эта техника использовалась по крайней мере в Warhammer 40000: Space Marine и, возможно, в других играх .

Mokosha
источник
Это была потрясающая статья, и я чувствую, что прочитал половину из вашего объяснения. Спасибо за эту информацию.
JPtheK9
0

Я не знаю, как работают ваши юниты, но я предполагаю, что они похожи на конечный автомат:

Возможные состояния

  • Бег к (х, у, г)
  • Атакующий (врага_ид)
  • Сбор ресурсов (ressource_id)

Если вы обратите внимание на то, как Starcraft подходит к этой проблеме, вы обнаружите, что:

  1. Если есть место для движения в каком-либо направлении, персонаж движется в этом направлении.
  2. Если места нет, блок на пути будет двигаться, чтобы освободить место
  3. Если юнит, которому нужно переместиться, чтобы освободить место, уже имеет команду, он сохранит команду, но слегка ее изменит, чтобы в конечном итоге освободить место.

Вот сценарий 1:

введите описание изображения здесь

У меня есть место, чтобы пойти туда? Да ? Затем перейти

Сценарий 2:

введите описание изображения здесь

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

Итак, что вам нужно будет реализовать:

  • Подразделения должны знать свое окружение
  • Юниты должны иметь возможность общаться друг с другом
  • Вы должны реализовать способ продолжать выполнение команды при размещении другого модуля
Antoine
источник
Спасибо за информацию и визуализацию. Прямо сейчас я использую обнаружение столкновений, чтобы выяснить, может ли юнит переместиться в другое место или другой юнит занимает его. Главное, что я пытаюсь выяснить - это какой-то алгоритм, который сообщает другому юниту, на какое расстояние двигаться или какую скорость регулировать. Другими словами, как блокирующий блок разместит блок, пытающийся пройти.
JPtheK9
Поскольку это поведение рассчитывается при каждом обновлении физики, вам не нужно указывать расстояние, оно будет двигаться, пока оно не исчезнет. Для направления, вы сканируете просто умножьте скорость двух единиц, это даст вам точку на полпути, чтобы она продолжала двигаться во время аккомодации. После этого вы можете поиграть с этим, чтобы сделать так, чтобы он больше прилипал к порядку или быстрее уходил с пути.
Антуан
Что вы имеете в виду под "движется, пока это не с пути"? Как движется юнит в первую очередь?
JPtheK9
Извините, я забыл упомянуть: Единицы не являются конечными автоматами. Они имеют много способностей в своем шкафчике, которые имитируются каждый кадр - за исключением того, что эти способности имеют эффект только при активации, независимо от того, находится ли пункт назначения на расстоянии X или с существованием цели. Движение юнита является результатом его скорости, которая может быть изменена способностью.
JPtheK9
0

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

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

// Defines a phalanx (box) formation
class Formation
    // Center of the box in the world
    Position center;
    // Width in # of units
    int width;
    // Height in # of units
    int height;
    // Space between units
    float scale;
    // How much force units will apply to stay near
    // their assigned spot.
    float springforce;

    // Return a position of a unit at the given row and column
    // Todo: add a rotation to this formation so it can rotate when moving.
    Position GetUnitPhalanxPosition(int row, int column)
        return new Position(center.X + column * scale - width * scale /2, 
                            center.Y + row * scale    - height* scale / 2);

// Represents a simple point object with a velocity and position;
// it belongs to a formation.
class Unit
    Position pos;
    Velocity vel;
    Formation formation;
    // What's our assigned spot in the formation?
    int row;
    int column;

    void Update(float dt)
        // Get the desired target position in the formation
        Position target = formation.GetUnitPhalanxPosition(row, column);
        // Apply a spring force toward the position (todo: you might want to damp this)
        vel += (target - position) * dt * formation.springforce;
        // Move along the velocity vector.
        pos += vel * dt;
mklingen
источник
Благодарность! Это действительно интересное и креативное решение. Я реализовал нечто подобное для поведения / формирования толпы, но у меня все еще есть проблема перекрытия юнитов. Что должно произойти, если 2 формирования сталкиваются друг с другом?
JPtheK9
Я думаю, что это зависит от дизайна. Проще всего было бы применить другую рулевую силу вдали от соседних подразделений в других формированиях, как на этом изображении . Другая вещь, которую вы можете сделать, это объединить формирования, когда они выбраны игроком, или даже сформировать «мета-формирования»
mklingen
Мета-формации звучат действительно сложно и глючно: C. Изображение, которое вы связали, может быть именно тем, что мне нужно. Я собираюсь провести еще какое-то исследование в отношении управления силами. У вас есть ссылка на статью изображения?
JPtheK9
У меня проблема похожая на вашу, было бы интересно узнать, как вы ее решили. После прочтения этой статьи на ум пришла одна идея: возможно, комбинирование Pathfinding (A *) для планирования макро-пути при использовании силы отталкивания для предотвращения микроколлизий:
ColdSteel
0

Я знаю, что некоторые люди недовольны демпингом ссылок, однако я нашел очень многообещающий документ «Многоагентный подход на основе потенциальных полей для стратегических игровых роботов в реальном времени» (ISBN 978-91-7295-160-0), и он явно передает гораздо больше, чем я мог бы уточнить. В статье рассматривается использование искусственных потенциальных полей (концепция, основанная на робототехнике), чтобы облегчить локальное предотвращение столкновений в контексте разработки игры.

DanoThom
источник
Благодарность! Исследование так же полезно, как объяснение для меня. Я нырну в эту газету.
JPtheK9
У меня уже есть карта влияния, но она кажется слишком сложной для моих вкусов. Главное - генерировать потенциальные поля для разных единиц, чтобы перемещать их, а также преобразовывать данные из потенциального поля в скорость, с которой нужно двигаться. В принципе, я не думаю, что это будет работать для юнитов разных размеров. Это отличная книга с множеством интересных идей.
JPtheK9