我为了好玩尝试了一下，以下是结果:
算法:
- 处理每个圆盘
- 将速度设置为
constant*destination_vector
- 测试新迭代位置是否与其他圆盘冲突
- 如果有冲突，则将速度旋转一个角度步长
ang
- 循环直到找到自由方向或完整覆盖圆周
如果没有找到自由方向，则标记圆盘为卡住状态
这是圆形到反向圆形路径的样子：
这是随机到随机路径的样子：
卡住的圆盘为黄色（在这些情况下没有）而不动的圆盘已经到达目的地。 如果没有路径，例如如果圆盘已经在另一个圆盘的目的地上，也会卡住。为了避免这种情况，您还需要更改发生碰撞的圆盘... 您可以调整 ang,a,v 常数以使其外观不同，并且还可以尝试随机旋转角度方向以避免涡流/漩涡运动
以下是我使用的源代码（C ++）：
const int discs =23;
const double disc_r=5;
const double disc_dd=4.0*disc_r*disc_r;
struct _disc
{
double x,y,vx,vy;
double x1,y1;
bool _stuck;
};
_disc disc[discs];
void disc_generate0(double x,double y,double r)
{
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)
{
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)
{
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
- 调用 iterate（
dt 是经过的时间，以秒为单位）
- 绘制场景
如果你想改成使用 t=<0,1>
- 循环迭代直到所有圆盘到达目标位置或超时
- 记住每个圆盘速度变化的列表
需要位置或速度向量以及发生变化的时间
- 循环结束后将所有圆盘列表重新缩放到
<0,1> 范围内
- 渲染/动画显示重新缩放的列表
[注]
我的测试是实时运行的，但我没有应用 <0,1> 范围，并且圆盘数量也不多。因此您需要测试一下这是否足够快。
加速的方法：
- 增加角度步长
- 旋转后针对最后相撞的圆盘进行碰撞检测，只有在空闲时才检测其余圆盘……
- 将圆盘分成（重叠的）区域，分别处理每个区域
- 我认为某些场景方法可以加速，例如定期创建场地图以更好地确定避免障碍的方向
[编辑1] 一些调整以避免在障碍物周围无限振荡
对于更多的圆盘，有些圆盘会被卡在已经停止的圆盘周围弹跳。为了避免这种情况，只需偶尔改变 ang 步骤方向，就可以得到以下结果：
你可以看到结束前的振荡弹跳
这是修改后的源代码：
void disc_iterate(double dt)
{
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);
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; }
if (int(cnt&128))
{
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{
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;
}
}
cnt++;
}
