路径生成适合在飞机不相交盘运动 [英] Path generation for non-intersecting disc movement on a plane
问题描述
我有300个或更少的碟片等于半径在一个平面上。在时间0的每个光盘是在一个位置上。在时刻1每张光盘是在一个可能不同的位置上。我期待产生2D路径为0和1之间的每个光盘倍，使得盘不相交并的路径是相对高效的（短）和小曲率如果可能的。 （例如，直线是preferable到波浪线）
I have 300 or fewer discs of equal radius on a plane. At time 0 each disc is at a position. At time 1 each disc is at a potentially different position. I'm looking to generate a 2D path for each disc for times between 0 and 1 such that the discs do not intersect and the paths are relatively efficient (short) and of low curvature if possible. (for example, straight lines are preferable to squiggly lines)
- 下计算时间通常比溶液准确性更重要。 （例如，一个小路口是好的，我不一定需要最佳效果）
- 但是，光盘不应该通过对方瞬移，阻止或延缓突然，或改变方向突然 - 的顺畅就更好了。唯一例外的是时间0和1。
- 路径可以pssed在采样形式或分段线性性质（或更好）前$ P $ - 我不担心通过花键有真正的平滑路径。 （我可以近似地认为，如果我这样需要的。）
<一个href="https://www.googledrive.com/host/0B4I2ineqw370fmJxd2NtaWlXMjRPLXlvTFJaZmpaRDZOMFdXOHliWGZRTTdtR0pITjZaeWc">You可以看到我最好的尝试一个演示（通过JavaScript + WebGL的）。被警告，这将在旧的计算机上加载速度慢，由于涉及的计算。看来Windows下的Firefox / Chrome浏览器/ IE11工作。
You can see a demo of my best attempt (via Javascript + WebGL). Be warned, it will load slowly on older computers due to the computations involved. It appears to work in Firefox/Chrome/IE11 under Windows.
在本演示中，我已经重新presented每张光盘作为3D（即每个盘都有在每个时间的位置）的松紧带，跑了解决制约一个简单的游戏风格的物理引擎和将每个时间点犹如一团与弹簧的previous /下一次。 （时间在这种情况下，仅仅是第三维。）
In this demo I've represented each disc as an "elastic band" in 3D (that is, each disc has a position at each time) and ran a simple game-style physics engine that resolves constraints and treats each point in time like a mass with springs to the previous/next time. ('Time' in this case is just the third dimension.)
这实际工作pretty的非常适用于小型N（小于20），但在常见的测试情况下（例如，从光盘排成一圈，每个盘移动到圆上的点对面），这不产生令人信服的路径，因为约束和弹性，在整个弹簧传播缓慢。 （例如，如果我切的时间为100个分立的水平，紧张的松紧带只有每传播各仿真周期一个级别），这是一个很好的解决方案需要很多（> 10000）次迭代，这是我的应用程序繁琐缓慢。它也没有合理解决许多N> 40例，但这可能仅仅是因为我不能有效运行足够的迭代。
This actually works pretty well for small N (<20), but in common test cases (for example, start with discs arranged in circle, move each disc to the opposite point on the circle) this fails to generate convincing paths since the constraints and elasticity propagate slowly throughout the springs. (for example, if I slice time into 100 discrete levels, tension in the elastic bands only propagates one level per each simulation cycle) This makes good solutions require many (>10000) iterations, and that is tediously slow for my application. It also fails to reasonably resolve many N>40 cases, but this may be simply because I can't feasibly run enough iterations.
我最初的尝试是一座小山，登山者，与它逐渐突变的直线路径开始。解决方案，测量比目前最好的解决方案更好地取代了目前最好的解决方案。更好的测量结果从相交的量（即，完全重叠不仅仅是放牧测定更糟）和路径的长度（更短的路径较好）。
My initial attempt was a hill-climber that started with straight-line paths which were gradually mutated. Solutions which measured better than the currently best solution replaced the currently best solution. Better measurements resulted from the amount of intersection (that is, completely overlapping measured worse than just grazing) and the length of the paths (shorter paths were better).
这产生了一些效果出奇的好，但不可靠，容易陷入局部极小非常频繁。这是为N> 20极其缓慢。我尝试运用一些技巧（模拟退火，遗传算法的方法等），企图避开局部极小的问题，但我从来没有取得多大成功。
This produced some surprisingly good results, but unreliably, likely getting stuck in local minima very often. It was extremely slow for N>20. I tried applying a few techniques (simulated annealing, a genetic algorithms approach, etc) in an attempt to get around the local minima issue, but I never had much success.
我优化弹性带的模式，以便张力和制约更加迅速传播在时间维度。然而，这将节省一个很好的协议，在许多情况下，所需的迭代，在高度受限场景（例如，许多光盘试图穿越相同的位置）仍需要迭代站不住脚量。我对如何解决制约或更快（我试过阅读不可拉伸布料模拟几篇论文，但我一直没能找出它们是否适用）传播弹簧的专家，所以我有兴趣，如果有一个很好的方式去了解这一点。
I'm optimizing the "elastic band" model so that tension and constraints propagate much more quickly in the time dimension. This would save a good deal of needed iterations in many cases, however in highly-constrained scenarios (for example, many discs trying to cross the same location) an untenable amount of iterations would still be required. I'm no expert on how to solve constraints or propagate springs more quickly (I've tried reading a few papers on non-stretchable cloth simulation, but I haven't been able to figure out if they apply), so I'd be interested in if there's a good way to go about this.
- Spektre已经实现了非常快速的RTS风格的机组运行的算法，令人钦佩的工作很好。它的快速和优雅，但它从RTS-的运动风格也经常出现问题：突然改变方向，单位可以停止硬生生地解决冲突。此外，单位不所有到达目的地的同时，它基本上是突然停止。这可能是一个很好的启发式使之后的路径可以被重新采样时间和一个平滑算法可以运行可行的非光滑路径（很像在我的演示中使用的。）
- Ashkan Kzme建议，该问题可能与网络流。这样看来，在最小费用流问题的可以工作，只要空间和时间可在一合理地discritized方式，和运行时间可保持下来。这里的优点是，它是一个很好的研究组的问题，但突然的速度变化仍然是一个问题，某种平滑后的步骤可能是可取的。的绊脚石，我目前有是决定时空网络重新presentation，不会导致光盘通过相互传送的。
- 周杰伦Kominek发帖称，使用非线性优化，优化二次贝塞尔曲线有一些令人鼓舞的结果答案。
- Spektre has implemented a very fast RTS-style unit movement algorithm that works admirably well. It's fast and elegant, however it suffers from RTS-movement style problems: sudden direction changes, units can stop abruptly to resolve collisions. Additionally, units do not all arrive at their destination at the same time, which is essentially an abrupt stop. This may be a good heuristic to make viable non-smooth paths after which the paths could be resampled in time and a "smoothing" algorithm could be run (much like the one used in my demo.)
- Ashkan Kzme has suggested that the problem may be related to network flows. It would appear that the minimum cost flow problem could work, as long as space and time could be discritized in a reasonable manner, and the running times could be kept down. The advantage here is that it's a well studied set of problems, but sudden velocity changes would still be an issue and some sort of "smoothing" post-steps may be desirable. The stumbling block I'm currently having is deciding on a network representation of space-time that wouldn't result in discs teleporting through each other.
- Jay Kominek posted an answer that uses a nonlinear optimizer to optimize quadratic Bezier curves with some promising results.
推荐答案
有玩过本作的乐趣了一下，在这里的结果是：
Have played with this for fun a bit and here the result:
算法：
- 在过程中的各个盘
- 设置速度
常数* destination_vector- 乘恒
A - 并限制速度常数
v之后
- 乘恒
- process each disc
- set speed as
constant*destination_vector- multiplicative constant
a - and limit the speed to constant
vafterwards
- multiplicative constant
如果没有免费的方向发现标记光盘作为卡住
if no free direction found mark disc as stuck
这是它的外观像圆逆圆路径：
This is how it looks like for circle to inverse circle path:
这是它的样子随机随机路径：
This is how it looks like for random to random path:
- 套牢盘是黄色的（没有在这种情况下）
- 在不动的光盘是在目的地已经
- 这也卡住，如果有一样，如果盘没有路径已在目的地界另一个那些目的地。要避免这种情况，你也需要改变碰撞盘也...
- 您可以使用
昂，A，V常数，以使不同的外观 玩
- 你也可以尝试旋转角度任意方向，以避免旋转/捻线机移动
- stuck disc are yellow (none in these cases)
- not moving discs are at destination already
- this can also get stuck if there is no path like if disc already in destination circles another ones destination. To avoid that you need also change the colliding disc also ...
- you can play with the
ang,a,vconstants to make different appearance - also you could try random direction of angle rotation to avoid that swirling/twister movement
在这里，源$ C $ C我用（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;
}
}
}
//---------------------------------------------------------------------------
用法很简单：
Usage is simple:
- 在调用generate0 / 1与中心和你的飞机半径在哪里光盘将放在
- 在调用迭代（dt的时间过去了秒）
- 绘制场景
如果你想改变这种使用 T =＆LT; 0.1＆GT;
if you want to change this to use t=<0,1>
- 在循环迭代，直到所有的光盘在目的地或超时
- 记得在速度列表中的任何改变每个光盘
- 在需要的位置和速度矢量和时间，它发生
- loop iterate until all disc at destination or timeout
- remember any change in speed for each disc in a list
- need the position or speed vector and time it occur
[注意事项]
我的测试运行的实时，但没有适用＆LT; 0.1＆GT; 范围内，还没有太多的碟片。所以，你需要测试这是否足够快为你的设置。
My test is running in real time but did not apply the <0,1> range and have not too many discs. So you need to test if this is fast enough for your setup.
为了加快您可以：
- 放大的角度步
- 与去年相撞盘旋转后测试冲突，只有当免费试用休息...
- segmentate光盘插入（由半径重叠）区处理每个区域单独
- 我也想在这里有些外地的做法可能加速之类的东西在一段时间创建字段映射一次更好地判断障碍物躲避方向
一些调整，以避免无限振荡各地obstackle
有关更多的碟片他们中的一些会被卡住蹦跳着已经停盘。为了避免这种情况只是改变了 ANG 步方向过一段时间，这是结果：
For more discs some of them get stuck bouncing around already stopped disc. To avoid that just change the ang step direction once in a while this is the result:
您可以看到振荡结束前反弹
you can see the oscillating bouncing before finish
这是改变的来源：
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++;
}
这篇关于路径生成适合在飞机不相交盘运动的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
