Генерация пути для непересекающегося движения диска на плоскости

Ответ 1

Играли с этим для удовольствия немного, и вот результат:

Алгоритм:

• обрабатывать каждый диск
• установить скорость как constant*destination_vector
  • мультипликативная константа a
  • и затем ограничьте скорость до постоянной v
• проверить, что новая итерационная позиция не конфликтует с другим диском
• если он вращает скорость в одном направлении на некоторый шаг угла ang
• до тех пор, пока не будет найдено свободное направление или полный круг.

• если не обнаружено свободного направления диска с отметкой

  Вот как выглядит круг для обратного круга:

  Вот как выглядит случайный случайный путь:

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

Здесь используется исходный код (С++):

//---------------------------------------------------------------------------
const int    discs =23;     // number of discs
const double disc_r=5;      // disc radius
const double disc_dd=4.0*disc_r*disc_r;
struct _disc
    {
    double x,y,vx,vy;       // actual position
    double x1,y1;           // destination
    bool _stuck;            // is currently stuck?
    };
_disc disc[discs];          // discs array
//---------------------------------------------------------------------------
void disc_generate0(double x,double y,double r)     // circle position to inverse circle destination
    {
    int i;
    _disc *p;
    double a,da;
    for (p=disc,a=0,da=2.0*M_PI/double(discs),i=0;i<discs;a+=da,i++,p++)
        {
        p->x =x+(r*cos(a));
        p->y =y+(r*sin(a));
        p->x1=x-(r*cos(a));
        p->y1=y-(r*sin(a));
        p->vx=0.0;
        p->vy=0.0;
        p->_stuck=false;
        }
    }
//---------------------------------------------------------------------------
void disc_generate1(double x,double y,double r)     // random position to random destination
    {
    int i,j;
    _disc *p,*q;
    double a,da;
    Randomize();
    for (p=disc,a=0,da=2.0*M_PI/double(discs),i=0;i<discs;a+=da,i++,p++)
        {
        for (j=-1;j<0;)
            {
            p->x=x+(2.0*Random(r))-r;
            p->y=y+(2.0*Random(r))-r;
            for (q=disc,j=0;j<discs;j++,q++)
             if (i!=j)
              if (((q->x-p->x)*(q->x-p->x))+((q->y-p->y)*(q->y-p->y))<disc_dd)
               { j=-1; break; }
            }
        for (j=-1;j<0;)
            {
            p->x1=x+(2.0*Random(r))-r;
            p->y1=y+(2.0*Random(r))-r;
            for (q=disc,j=0;j<discs;j++,q++)
             if (i!=j)
              if (((q->x1-p->x1)*(q->x1-p->x1))+((q->y1-p->y1)*(q->y1-p->y1))<disc_dd)
               { j=-1; break; }
            }
        p->vx=0.0;
        p->vy=0.0;
        p->_stuck=false;
        }
    }
//---------------------------------------------------------------------------
void disc_iterate(double dt)                    // iterate positions
    {
    int i,j,k;
    _disc *p,*q;
    double v=25.0,a=10.0,x,y;
    const double ang=10.0*M_PI/180.0,ca=cos(ang),sa=sin(ang);
    const int n=double(2.0*M_PI/ang);
    for (p=disc,i=0;i<discs;i++,p++)
        {
        p->vx=a*(p->x1-p->x); if (p->vx>+v) p->vx=+v; if (p->vx<-v) p->vx=-v;
        p->vy=a*(p->y1-p->y); if (p->vy>+v) p->vy=+v; if (p->vy<-v) p->vy=-v;
        x=p->x; p->x+=(p->vx*dt);
        y=p->y; p->y+=(p->vy*dt);
        p->_stuck=false;
        for (k=0,q=disc,j=0;j<discs;j++,q++)
         if (i!=j)
          if (((q->x-p->x)*(q->x-p->x))+((q->y-p->y)*(q->y-p->y))<disc_dd)
            {
            k++; if (k>=n) { p->x=x; p->y=y; p->_stuck=true; break; }
            p->x=+(p->vx*ca)+(p->vy*sa); p->vx=p->x;
            p->y=-(p->vx*sa)+(p->vy*ca); p->vy=p->y;
            p->x=x+(p->vx*dt);
            p->y=y+(p->vy*dt);
            j=-1; q=disc-1;
            }
        }
    }
//---------------------------------------------------------------------------

Использование прост:

• вызов generate0/1 с центром и радиусом вашей плоскости, где будут размещены диски
• call iterate (dt - время, прошедшее через несколько секунд)
• нарисовать сцену

если вы хотите изменить это, чтобы использовать t=<0,1>

• цикл повторяется до тех пор, пока весь диск в пункте назначения или тайм-аута
• запомнить любое изменение скорости для каждого диска в списке нужен вектор положения или скорости и время его возникновения.
• после цикла перемасштабируйте список дисков всего в диапазоне <0,1>
• рендеринг/анимация перемасштабированных списков

[Примечание]

Мой тест работает в режиме реального времени, но я не применял диапазон <0,1> и не слишком много дисков. Поэтому вам нужно проверить, достаточно ли это для вашей установки.

Чтобы ускорить работу, вы можете:

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

[edit1] некоторые настройки, чтобы избежать бесконечных колебаний вокруг препятствия

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

вы можете увидеть колеблющееся подпрыгивание перед финишем

это измененный источник:

void disc_iterate(double dt)                    // iterate positions
    {
    int i,j,k;
    static int cnt=0;
    _disc *p,*q;
    double v=25.0,a=10.0,x,y;
    const double ang=10.0*M_PI/180.0,ca=cos(ang),sa=sin(ang);
    const int n=double(2.0*M_PI/ang);
    // process discs
    for (p=disc,i=0;i<discs;i++,p++)
        {
        // compute and limit speed
        p->vx=a*(p->x1-p->x); if (p->vx>+v) p->vx=+v; if (p->vx<-v) p->vx=-v;
        p->vy=a*(p->y1-p->y); if (p->vy>+v) p->vy=+v; if (p->vy<-v) p->vy=-v;
        // stroe old and compute new position
        x=p->x; p->x+=(p->vx*dt);
        y=p->y; p->y+=(p->vy*dt);
        p->_stuck=false;
        // test if coliding
        for (k=0,q=disc,j=0;j<discs;j++,q++)
         if (i!=j)
          if (((q->x-p->x)*(q->x-p->x))+((q->y-p->y)*(q->y-p->y))<disc_dd)
            {
            k++; if (k>=n) { p->x=x; p->y=y; p->_stuck=true; break; }   // if full circle covered? stop
            if (int(cnt&128))   // change the rotation direction every 128 iterations
                {
                // rotate +ang
                p->x=+(p->vx*ca)+(p->vy*sa); p->vx=p->x;
                p->y=-(p->vx*sa)+(p->vy*ca); p->vy=p->y;
                }
            else{
                //rotate -ang
                p->x=+(p->vx*ca)-(p->vy*sa); p->vx=p->x;
                p->y=+(p->vx*sa)+(p->vy*ca); p->vy=p->y;
                }
            // update new position and test from the start again
            p->x=x+(p->vx*dt);
            p->y=y+(p->vy*dt);
            j=-1; q=disc-1;
            }
        }
    cnt++;
    }

Ответ 2

Это не идеально, но моя лучшая идея состояла в том, чтобы переместить диски по квадратичные кривые Безье. Это означает, что у вас есть только 2 бесплатных переменных на диск, которые вы пытаетесь найти значения для.

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

Только один фактический хит:

Не мешает отображать удары, диски фактически начинают перекрываться:

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

double errorf(unsigned n, const double *pts, double *grad,
              void *data)
{
  problem_t *setup = (problem_t *)data;
  double error = 0.0;

  for(int step=0; step<setup->steps; step++) {
    double t = (1.0+step) / (1.0+setup->steps);
    for(int i=0; i<setup->N; i++)
      quadbezier(&setup->starts[2*i],
                 &pts[2*i],
                 &setup->stops[2*i],
                 t,
                 &setup->scratch[2*i]);

    for(int i=0; i<setup->N; i++)
      for(int j=i+1; j<setup->N; j++) {
        double d = distance(&setup->scratch[2*i],
                            &setup->scratch[2*j]);
        d /= RADIUS;
        error += (1.0/d) * (1.0/d);
      }
  }

  return error / setup->steps;
}

Игнорировать n, grad и data. setup описывает оптимизацию конкретной задачи, количество дисков и начало и остановку. quadbezier интерполирует кривую Безье, помещая ее ответ в ->scratch. Мы проверяем, что ->steps указывает часть пути по пути и измеряет, насколько близко друг к другу находятся диски на каждом шаге. Чтобы сделать проблему оптимизации более гладкой, у нее нет жесткого переключателя, когда диски начинают касаться, он просто пытается удержать их так далеко друг от друга, насколько это возможно.

Полностью компилируемый код, Makefile и некоторый Python для превращения кучи квадратичных кривых безье в серию изображений можно найти на https://github.com/jkominek/discs

Производительность немного вялая на огромном количестве точек, но есть ряд вариантов улучшения.

• Если пользователь делает небольшие изменения в начальном и конечном положениях, после каждой настройки, запустите оптимизацию в фоновом режиме, используя предыдущее решение в качестве новой отправной точки. Фиксирование закрытого решения должно быть быстрее, чем воссоздавать его с нуля каждый раз.
• Распараллеливать цикл n^2 по всем точкам.
• Проверьте, улучшат ли другие алгоритмы оптимизации эти данные. Сейчас он начинается с глобального прохода оптимизации, а затем проходит локальный прогон оптимизации. Есть алгоритмы, которые уже "знают", как это делать, и, вероятно, умнее об этом.
• Если вы можете выяснить, как вычислить функцию градиента бесплатно или близко, я уверен, что было бы целесообразно сделать это и переключиться на алгоритмы, которые могут использовать информацию о градиенте. Это может стоить того, даже если градиент не дешев.
• Замените все действия шага субоптимизацией, которая находит t, где два диска наиболее близки, и затем использует это расстояние для ошибки. Вычисление градиента для этой субоптимизации должно быть намного проще.
• Улучшенные структуры данных для промежуточных точек, поэтому вы не выполняете кучу ненужных вычислений расстояния для дисков, которые очень далеки друг от друга.
• Возможно, больше?

Ответ 3

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

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

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

Вот несколько статей с примером кода, показывающим, как использовать карты тепла:

http://haufler.org/2012/05/26/beating-the-scribd-ai-challenge-implementing-traits-through-heuristics-part-1/

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/the-core-mechanics-of-influence-mapping-r2799

Игра AI Pro, том 2, глава "Карты тепла"

Ответ 4

Мне не хватает комментариев, чтобы прокомментировать, так что извините за неответ. Но для RTS-угла RTS обычно использует алгоритм A * для поиска пути. Есть ли причина, по которой вы настаиваете на использовании модели на основе физики?

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

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

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

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

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

Если время немного рандомизировано, я думаю, что вы получите поведение, которое вы ищете.

Надеюсь, это поможет.