2d 自上而下平滑寻路 libGDX

Question

我正在尝试制作一个跟随玩家（由你控制）的伙伴 ai，目前它可以工作，但是当我添加碰撞检测时，当伙伴遇到障碍物时它不能很好地工作.我只是想知道什么是最好的方法（比如 a* 算法的实现）来使 ai 运动平滑并避免障碍？这是我哥们目前的更新方式class:

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)就是从好友指向玩家的向量。我们还需要的是从障碍物 i 指向好友的向量 (b-o_i)。此外，我们不是直接使用向量 (p-b)、(b-o_i)，而是先将它们归一化。

那么，normalized(p-b)已经是我们把好友拉到玩家那里的全部了。

为了使伙伴远离障碍物，我们希望在伙伴靠近时排斥力强，在伙伴远离时排斥力小（甚至为零）。因此，一个明显的选择是缩放我们想要的方向，即 normalized(b-o_i) 和 1/|b-o_i|，其中 |.|表示向量的范数。

现在，我们可以简单地将所有这些 "magnetic forces" 与：

混合

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 值也可能会得到更好的结果。
如果障碍物是圆形的并且两个障碍物之间有足够的空间，则避障效果最好。否则，伙伴可能会陷入局部最优，玩家将不得不 "rescue" 移动到一个使伙伴远离局部最优的位置。
如果障碍物不是很好的圆形而是大多边形，你可以尝试覆盖大部分多边形的非常大的排斥力（即对于这种障碍物来说非常大的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 的更多信息

但我假设您更喜欢易于实施的东西。

2d 自上而下平滑寻路 libGDX

2d top down smooth pathfinding libGDX

java

libgdx

artificial-intelligence

path-finding