问二维自上而下平滑寻路libGDX

EN

一个易于实现并可能根据您的障碍类型而工作的解决方案是使用潜在字段。

这个想法很简单:玩家的行为就像一块磁铁，把同伴拉向他。同时，障碍击退了伙伴，从而避免了障碍。

我将首先使用向量来解释它，而不是Java，以获得更好的可读性。

比方说，b是好友的位置，p是玩家的位置，o_1, ... o_k是障碍的位置。

每个b, p, o_1, ..., o_k都是具有x和y坐标的二维矢量。

然后向量(p-b)是从伙伴指向播放器的向量。我们还需要向量(b-o_i)，它从障碍物i指向好友。另外，我们不再直接使用向量(p-b)、(b-o_i)，而是首先对它们进行规范化。

那么，normalized(p-b)已经是我们需要的全部，把伙伴拉到玩家身边。

为了击退同伴的障碍，我们希望如果巴迪离它很近，我们的排斥力就会很强，如果巴迪离它很远，我们希望排斥力很小(甚至为零)。因此，一个明显的选择是缩放我们想要的方向，即normalized(b-o_i)，用1/|b-o_i|表示向量的范数。

现在，我们可以简单地将所有这些“磁力”与：

w = normalized(p-b) + normalized(b-o_1)/|b-o_1| + ... + normalized(b-o_l)/|b-o_k|

这个向量w通常指向玩家，但是每当伙伴接近障碍物时，它就会被击退，这正是你想要的。

但是我们怎样才能确保伙伴以正确的速度移动呢？这很简单。我们将w标准化，然后按速度进行缩放。也就是说，我们的最终速度矢量是v = speed*w/|w|。

这可以很容易地添加到代码中：

public void update() {

    setBounds(getX(), getY(), getWidth(), getHeight()); //I kept this from your code, but I don't actually know what it does

    float dx = player.getX() - getX(); //note: I removed abs
    float dy = player.getY() - getY();

    float norm = Math.sqrt(dx*dx + dy*dy);

    //normalization:
    float wx = dx/norm;
    float wy = dy/norm;

    for (obstacle o : obstacles) { //assuming obstacles is an iterable datastructure containing instances of the class obstacle
         //note, it suffices to iterate over close by obstacles
         dx = getX() - o.getX();
         dy = getY() - o.getY();

         norm = Math.sqrt(dx*dx + dy*dy);

         //normalization:
         float ox = dx/norm;
         float oy = dy/norm;

         //add scaling to get the repulsion force we want
         wx += ox/norm;
         wy += oy/norm;
    } 

    float norm_of_w = Math.sqrt(wx*wx + wy*wy);
    float vx = speed * wx / norm_of_w;
    float vy = speed * wy / norm_of_w;

    setX(getX() + vx);
    setY(getY() + vy);
}

不幸的是，有几件事需要考虑：

• 不同类型的斥力可能比1/x_b_o_i_i_x，例如1/x_b_o_i_i^2更好。
• 它可能有助于与力量，例如尝试c*(b-o_i)/|b-o_i|的不同值的c (即ox = c*dx/norm;等)。如果c太小，那么伙伴会在一定程度上移动到障碍物中，如果c非常大，他就会在离他们很远的时候避开它们。对于不同的障碍物尺寸，使用不同的c值也可以得到较好的效果。
• 如果障碍物是圆形的，并且在两个障碍物之间有足够的空间，那么避障效果最好。否则，巴迪可能被困在局部擎天柱，玩家将不得不“拯救”他，移动到一个位置，把巴迪从当地的最佳状态。
• 如果障碍物不是很好的圆形而是很大的多边形，你可以尝试一种很大的排斥力，它覆盖了大部分多边形(也就是这种障碍物的一个很大的c)。优点是，伙伴可以避免障碍，但不幸的是，如果你想让它靠近它，它会简单地拒绝由于强烈的排斥。
• 重要的是要记住，如果好友和障碍比较近，1/|b-o_i|是很大的。如果它们处于相同的位置，那么您的程序将尝试将其除以零。您可能想检查一下这个情况，并避免它。

就是这样，但也许值得注意的是，通常对于潜在的领域，想法是用负电荷来实现目标，而对障碍使用正电荷，即

w = -|p-b| + 1/|b-o_1| + ... + 1/|b-o_k|

注意，在这里，w只是标量，而不是向量。然后，采用梯度下降来实现目标。这意味着w相对于b.x，b.y的梯度被计算出来。然后，这个梯度指向到达球员的方向，同时避免障碍。这是一个比我建议的更好的方法，但需要更多的数学知识。可以自由地尝试或者询问这是否是你想要的。

最有可能的，最好的答案，如果障碍有任意形状和局部极小是不可接受的，你可以使用Delaunay三角剖分结合漏斗算法。您可以在https://www.aaai.org/Papers/AAAI/2006/AAAI06-148.pdf中阅读更多关于is的信息。

但我想您更喜欢易于实现的东西。