在平面上生成非相交盘运动的路径

Question

我正在寻找什么

我在飞机上有300或更少相等半径的圆盘.在时间0,每个盘都在一个位置.在时间1,每个盘处于可能不同的位置.我希望为每个光盘生成一个介于0和1之间的2D路径,这样光盘就不会相交,路径相对有效(短),如果可能的话,曲率也很低.(例如,直线比波浪线更好)

• 较低的计算时间通常比解决方案的准确性更重要.(例如,一个小交叉点是可以的,我不一定需要一个最佳结果)
• 但是,光盘不应相互传送,突然停止或减速,或突然改变方向 - "越平滑"越好.唯一的例外是时间0和1.
• 路径可以采样形式或分段线性(或更好)表示 - 我并不担心通过样条线获得真正平滑的路径.(如果我需要,我可以估算一下.)

我试过的

你可以看到我最好的尝试演示(通过Javascript + WebGL).请注意,由于涉及的计算,它将在旧计算机上缓慢加载.它似乎适用于Windows下的Firefox/Chrome/IE11.

在这个演示中,我将每个光盘表示为3D中的"弹性带"(也就是说,每个光盘每次都有一个位置)并运行一个简单的游戏式物理引擎来解决约束并将每个时间点视为一个上一次/下次弹簧的质量.(在这种情况下,'时间'只是第三个维度.)

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

还有什么我试过的

我最初的尝试是一个爬山者,从直线路径开始,逐渐变异.比目前最佳解决方案更好的测量解决方案取代了目前最好的解决方案 交叉量(即完全重叠测量比仅仅放牧更糟糕)和路径长度(较短路径更好)导致更好的测量结果.

这产生了一些令人惊讶的好结果,但不可靠的是,很可能经常陷入局部极小.N> 20时速度极慢.我尝试应用一些技术(模拟退火,遗传算法方法等)试图绕过局部最小问题,但我从来没有取得太大成功.

我在想什么

我正在优化"弹性带"模型,以便张力和约束在时间维度上传播得更快.在许多情况下,这将节省大量所需的迭代,但是在高度受限的情况下(例如,许多光盘试图穿过相同的位置)仍然需要无法维持的迭代量.我不是如何解决约束或更快地传播弹簧的专家(我已经尝试阅读一些关于非拉伸布料模拟的论文,但我还没弄清楚它们是否适用),所以我会感兴趣,如果有一个很好的方法来解决这个问题.

桌上的想法

• Spektre实施了一种非常快速的RTS风格的单位运动算法,效果非常好.它快速而优雅,但是它受到RTS运动风格问题的影响:突然改变方向,单位可以突然停止以解决碰撞.此外,单位并非全部同时到达目的地,这实际上是一个突然停止.这可能是一个很好的启发式方法,可以制作可行的非平滑路径,之后可以及时重新采样路径,并且可以运行"平滑"算法(非常类似于我的演示中使用的算法).
• Ashkan Kzme建议问题可能与网络流量有关.看起来最小成本流问题可以起作用,只要空间和时间可以合理的方式进行,并且可以保持运行时间.这里的优点是它是一组研究得很好的问题,但突然的速度变化仍然是一个问题,并且可能需要某种"平滑"的后续步骤.我目前遇到的绊脚石是决定时空的网络表示,这不会导致光盘彼此传送.
• Jay Kominek发布了一个答案,该答案使用非线性优化器来优化二次贝塞尔曲线,并得到一些有希望的结果.

Answer 1

玩过这个有趣的事情,结果如下:

算法:

1. 处理每张光盘
2. 设定速度为 constant*destination_vector
   • 乘法常数 a
   • 并限制速度恒定v之后
3. 测试新的迭代位置是否与任何其他光盘冲突
4. 如果它确实沿一个方向旋转一定角度的速度 ang
5. 循环直到找到自由方向或覆盖整圆

6. 如果没有自由方向发现标记盘卡住了

   这是圆圈到反圆路径的样子:

   

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

   

   卡住的光盘是黄色的(在这些情况下没有),而且移动的光盘已经到达目的地.如果没有路径,如果光盘已经在目的地圈中的另一个目的地,这也会卡住.为了避免这种情况,您还需要更换碰撞光盘...您可以使用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;
            }
        }
    }
//---------------------------------------------------------------------------

用法很简单:

1. 呼叫generate0/1中心和您将要放置光盘的飞机半径
2. 调用迭代(dt以秒为单位的时间)
3. 画出场景

如果你想改变这个使用 t=<0,1>

1. 循环迭代,直到目的地或超时的所有光盘
2. 记住列表中每张光盘的速度变化需要位置或速度矢量及其发生的时间
3. 循环后重新缩放光盘列表全部到的范围 <0,1>
4. 渲染/动画重新缩放的列表

[笔记]

我的测试是实时运行但我没有应用<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++;
    }