algorithm - 平面上非相交圆盘运动的路径生成

Question

我在找什么

我在一个平面上有 300 个或更少的等半径圆盘。在时间 0，每个圆盘都在一个位置。在时间 1，每个圆盘可能处于不同的位置。我希望为每个圆盘生成 0 到 1 之间的时间的 2D 路径，以便圆盘不相交并且路径相对高效(短)并且如果可能的话曲率较低。 (例如，直线比波浪线更可取)

较低的计算时间通常比解决方案的准确性更重要。 (比如有点交集就可以了，我不一定需要一个最优的结果)

但是，圆盘不应相互传送、突然停止或减速，或突然改变方向——“越平滑”越好。唯一的异常(exception)是时间 0 和 1。

路径可以以采样形式或分段线性性质(或更好)表示——我不担心通过样条获得真正平滑的路径。 (如果需要，我可以近似计算。)

我试过的

You can see a demo我最好的尝试(通过 Javascript + WebGL)。请注意，由于涉及计算，它会在较旧的计算机上加载缓慢。它似乎适用于 Windows 下的 Firefox/Chrome/IE11。

在这个演示中，我将每个圆盘表示为 3D 中的“弹性带”(即，每个圆盘在每次都有一个位置)并运行一个简单的游戏式物理引擎，该引擎解决约束并将每个时间点视为一个 Spring 质量到上一次/下一次。 (在这种情况下，“时间”只是第三维。​​)

这实际上对于小 N (<20) 非常有效，但在常见的测试用例中(例如，从排列成圆圈的圆盘开始，将每个圆盘移动到圆上的相对点)这无法生成令人信服的路径，因为约束和弹性在整个 Spring 中缓慢传播。 (例如，如果我将时间分成 100 个离散级别，则每个模拟循环中弹性带中的张力仅传播一个级别)这使得好的解决方案需要多次 (>10000) 次迭代，这对于我的应用程序来说非常缓慢。它也无法合理地解决许多 N>40 的情况，但这可能仅仅是因为我无法运行足够的迭代。

我还尝试过什么

我最初的尝试是爬山，从直线路径开始，然后逐渐变异。测量结果优于当前最佳解决方案的解决方案替换了当前最佳解决方案。更好的测量结果来自交叉量(即，完全重叠的测量比仅仅掠过更糟糕)和路径的长度(更短的路径更好)。

这产生了一些令人惊讶的好结果，但不可靠，很可能经常陷入局部最小值。 N>20 时非常慢。我尝试应用一些技术(模拟退火、遗传算法方法等)来试图解决局部最小值问题，但我从未取得太大成功。

我在尝试什么

我正在优化“弹性带”模型，以便张力和约束在时间维度上传播得更快。在许多情况下，这将节省大量所需的迭代，但是在高度受限的情况下(例如，许多磁盘试图穿过同一位置)仍然需要站不住脚的迭代量。我不是如何更快地解决约束或传播 Spring 的专家(我曾尝试阅读一些关于不可拉伸(stretch)布料模拟的论文，但我无法弄清楚它们是否适用)，所以我会对是否有解决此问题的好方法感兴趣。

table 上的想法

Spektre 实现了一种非常快速的 RTS 式单位移动算法，效果非常好。它快速而优雅，但它存在 RTS 运动风格的问题:突然的方向改变，单位可能会突然停下来解决碰撞。此外，单位不会同时到达目的地，这本质上是突然停止。这可能是一种很好的启发式方法，可以生成可行的非平滑路径，然后可以及时对路径进行重新采样并可以运行“平滑”算法(很像我的演示中使用的算法。)

Ashkan Kzme 建议该问题可能与网络流量有关。看起来minimum cost flow problem可以工作，只要空间和时间可以以合理的方式进行区分，并且可以控制运行时间。这里的优点是它是一组经过充分研究的问题，但是突然的速度变化仍然是一个问题，并且可能需要某种“平滑”的后期步骤。我目前遇到的绊脚石是决定时空的网络表示，它不会导致光盘相互传送。

Jay Kominek 发布了一个答案，该答案使用非线性优化器来优化二次贝塞尔曲线，并取得了一些有希望的结果。

Answer 1

玩这个有点好玩，结果如下:

算法:

处理每张光盘

设置速度为 constant*destination_vector

乘法常数 a

并将速度限制为恒定 v事后

测试新的迭代位置是否与任何其他磁盘冲突

如果它确实以某个角度步长在一个方向上旋转速度 ang

循环直到找到自由方向或整个圆圈被覆盖

如果没有找到自由方向，则将光盘标记为卡住

这是圆到逆圆路径的样子:



这是随机到随机路径的样子:



卡住的盘是黄色 (在这些情况下没有)并且不移动的光盘已经到达目的地。 如果没有路径，例如光盘已经在目的地圈另一个目的地 ，这也可能会卡住。 .为避免这种情况，您还需要更换碰撞盘...您可以使用ang,a,v 进行游戏。常量以产生不同的外观，您也可以尝试随机角度旋转方向以避免旋转/扭曲运动

这里是我使用的源代码(C++):

//---------------------------------------------------------------------------
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将放置光盘的平面的中心和半径

调用迭代( dt 是以秒为单位的时间)

绘制场景

如果您想将其更改为使用 t=<0,1>

循环迭代直到所有磁盘到达目的地或超时

记住列表中每个光盘的速度变化
需要位置或速度向量以及它发生的时间

循环后将光盘列表重新缩放到 <0,1> 的范围内

渲染/动画重新缩放的列表

【备注】

我的测试是实时运行的，但我没有应用 <0,1>范围和没有太多的光盘。因此，您需要测试这对于您的设置是否足够快。

要加快速度，您可以:

放大角度步

在对最后一个碰撞的圆盘旋转后测试碰撞，并且仅当自由测试其余的圆盘时...

将磁盘分割成(按半径重叠)区域分别处理每个区域

此外，我认为这里的一些现场方法可以加快速度，例如偶尔创建现 field 图以更好地确定避障方向

[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++;
    }