java - 2d自上而下平滑寻路libGDX

Question

我正在尝试制作一个跟随玩家（由您控制​​）的伙伴AI，目前它可以正常工作，但是当我添加碰撞检测时，当伙伴撞到障碍物时效果不佳。我只是想知道什么是使ai运动平稳并避免障碍的最佳方法（例如a *算法的实现）？
这是我的好友类当前的更新方法：

public void update() {

    setBounds(getX(), getY(), getWidth(), getHeight());

    float xDiff = Math.abs(player.getX() - getX());
    float yDiff = Math.abs(player.getY() - getY());

    if (player.getX() > getX() && xDiff > buddyDistance) {
        setX(getX()+speed);
    }
    else if (player.getX() < getX() && xDiff > buddyDistance) {
        setX(getX()-speed);
    }

    if (player.getY() > getY() && yDiff > buddyDistance) {
        setY(getY()+speed);
    }
    else if (player.getY() < getY() && yDiff > buddyDistance) {
        setY(getY()-speed);
    }

}

Answer 1

易于实施且可能根据您的障碍物类型而起作用的解决方案是使用潜在字段。

这个想法很简单：玩家的行为就像一块磁铁，将好友拉向自己。同时，障碍物会排斥伙伴，以便伙伴避开它们。

为了更好的可读性，我将首先使用向量而不是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 / | b-o_i |更好，例如1 / | b-o_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中了解更多有关

但是我认为您喜欢易于实施的东西。