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

Question

我在一个平面上有300个或更少的等半径圆盘。在时间0时，每个圆盘都在一个位置。在时间1时，每个圆盘都在一个潜在的不同位置。我希望为每个圆盘生成一个2D路径，时间在0到1之间，这样圆盘就不会相交，路径相对有效（短），如果可能的话，曲率较低。（例如，直线比曲线更好）

• 较低的计算时间通常比解的精确性更重要。（例如，一个小交叉口是可以的，我不一定需要一个最佳结果）

你可以看到我最好的尝试的演示（通过Javascript WebGL）。请注意，由于涉及的计算，它在旧电脑上加载会很慢。它似乎在视窗下的火狐/Chrome /IE11工作。

在这个演示中，我将每个光盘表示为3D中的“弹性带”（也就是说，每个光盘在每个时间都有一个位置），并运行一个简单的游戏式物理引擎，该引擎可以解决约束，并将每个时间点视为一个带有Spring的质量，直到上一次/下一次。（“时间”在本例中只是第三维度。）

这实际上对小N（

我最初的尝试是爬山，从逐渐变异的直线路径开始。比当前最佳解决方案更好的解决方案取代了当前最佳解决方案。更好的测量来自交叉点的数量（也就是说，完全重叠的测量比仅仅放牧更糟糕）和路径的长度（较短的路径更好）。

这产生了一些令人惊讶的好结果，但不可靠，很可能经常陷入局部极小值。对于N来说，这非常慢

我正在优化“弹性带”模型，以便张力和约束在时间维度上传播得更快。在许多情况下，这将节省大量所需的迭代，但是在高度受限的情况下（例如，许多光盘试图穿过同一位置），仍然需要大量的迭代。我不是如何更快地解决约束或传播Spring的专家（我试着阅读了几篇关于不可拉伸布料模拟的论文，但我还没有弄清楚它们是否适用），所以我想知道是否有一种好的html" target="_blank">方法来实现这一点。

• Spektre实现了一个非常快速的即时战略风格的单位移动算法，效果非常好。它既快又优雅，但是它存在即时战略风格的问题：方向突然改变，单位可以突然停下来解决碰撞。此外，单位并不都同时到达目的地，这本质上是一个突然停止。这可能是一个很好的启发式，可以创建可行的非平滑路径，之后可以及时重新采样路径，并运行平滑算法（很像我演示中使用的算法）。
• Ashkan Kzme认为这个问题可能与网络流有关。看起来最小成本流问题是可行的，只要空间和时间能够以合理的方式进行描述，并且运行时间能够被降低。这里的优点是它是一组经过充分研究的问题，但是突然的速度变化仍然是一个问题，某种“平滑”的后步骤可能是可取的。我目前面临的绊脚石是决定时空的网络表示，这不会导致光盘相互传送。
• Jay Kominek发布了一个答案，使用非线性优化器优化二次Bezier曲线，并获得了一些有希望的结果。

Answer 1

这类问题的通常解决方案是使用所谓的“热图”（或“影响图”）。对于场中的每个点，计算一个“热量”值。磁盘向高值移动，远离冷值。热图对你的问题类型有好处，因为它们编程非常简单，但可以生成复杂的、类似人工智能的行为。

例如，假设只有两个圆盘。如果你的热图规则是等径向的，那么圆盘将只是朝着彼此移动，然后后退，来回振荡。如果你的规则在不同的径向上随机化强度，那么行为将是混乱的。您还可以使规则依赖于速度，在这种情况下，磁盘在移动时会加速和减速。

一般来说，热图规则应该使区域在接近某个最佳距离时“更热”。离磁盘太近或太远的地方会变得“更冷”。通过更改此最佳距离，可以确定磁盘聚集在一起的距离。

这里有几篇文章，其中包含了演示如何使用热图的示例代码：

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卷，热图章节

Answer 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和数据<代码>设置描述了正在优化的具体问题、光盘数量以及它们的开始和停止位置quadbezier执行贝塞尔曲线插值，将其答案放入-

完全可编译的代码、Makefile和一些Python，可用于将一系列二次贝塞尔曲线转换为一系列图像https://github.com/jkominek/discs

在很多分数上表现有点迟缓，但有很多改进的选择。

1. 如果用户正在对起始和结束位置进行微小调整，那么每次调整后，都要在后台重新运行优化，使用之前的解决方案作为新的起点。修复一个封闭的解决方案应该比每次从头开始重新创建要快
2. 在所有点上并行化n^2循环
3. 查看其他优化算法是否能更好地处理这些数据。现在它从全局优化过程开始，然后进行局部优化过程。有些算法已经“知道”如何做这类事情，而且可能更聪明
4. 如果你能想出如何免费或接近计算梯度函数，我相信这样做是值得的，并切换到可以利用梯度信息的算法。即使梯度不便宜，也可能是值得的
5. 将整个步骤替换为次优化，找到两个光盘最接近的t，然后使用该距离作为错误。计算出次优化的梯度应该容易得多
6. 为中间点提供更好的数据结构，这样就不会对相距很远的光盘执行大量不必要的距离计算
7. 可能更多

Answer 3

为了好玩，我玩了一下，结果如下：

算法：

• 处理每张光盘

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

这是圆到反圆路径的样子：

以下是随机到随机路径的情况：

卡住的光盘是黄色的（在这种情况下没有），没有移动的光盘已经到达目的地。如果没有路径，这也可能卡住，比如光盘已经在目的地圆圈中，另一个目的地。为了避免这种情况，你还需要改变碰撞的光盘...您可以使用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. 调用生成0/1，其中包含放置圆盘的平面的中心和半径
2. 调用iterate（dt是以秒为单位的时间）
3. 画出场景

如果要将其更改为使用t=

1. 循环迭代，直到所有磁盘到达目的地或超时
2. 记住列表中每个磁盘的速度变化需要位置或速度向量和时间
3. 循环重放后，磁盘列表全部到的范围内

[注]

我的测试正在实时运行，但我没有应用

要加快速度，您可以：

• 放大角度步长
• 测试碰撞后，对最后一个碰撞的光盘旋转，只有当自由测试其余
• 将光盘分割成（按半径重叠）区域，分别处理每个区域
• 此外，我认为这里的一些野外方法可以加快一些事情，比如偶尔创建野外地图，以便更好地确定避障方向

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