多人游戏-客户端插值计算？

Question

多人游戏-客户端插值计算？

24

我正在使用JavaScript中的Socket IO创建一个多人游戏。目前这个游戏除了客户端插值外运作得非常完美。目前，当我从服务器接收到一个数据包时，我只是简单地将客户端位置设置为服务器发送的位置。以下是我尝试过的方法：

getServerInfo(packet) {
     var otherPlayer = players[packet.id]; // GET PLAYER
     otherPlayer.setTarget(packet.x, packet.y); // SET TARGET TO MOVE TO
     ...
}

我设置了玩家的目标位置。然后在玩家的更新方法中，我只是这样做：

var update = function(delta) {
    if (x != target.x || y != target.y){
        var direction = Math.atan2((target.y - y), (target.x - x));
        x += (delta* speed) * Math.cos(direction);
        y += (delta* speed) * Math.sin(direction);
        var dist = Math.sqrt((x - target.x) * (x - target.x) + (y - target.y)
                * (y - target.y));
        if (dist < treshhold){
            x = target.x;
            y = target.y;
        }
    }   
}

这基本上以固定速度将玩家移动到目标方向。问题是，玩家要么在下一个信息从服务器到达之前到达目标，要么在之后到达。

编辑：我刚刚读了Gabriel Bambettas关于这个主题的文章，他提到了这个：

假设您在t = 1000收到位置数据。您已经在t = 900时收到了数据，因此您知道玩家在t = 900和t = 1000时的位置。因此，从t = 1000和t = 1100开始，您显示另一个玩家从t = 900到t = 1000所做的操作。这样，您始终显示用户实际移动数据，只是您会“晚”100毫秒显示它。

这再次假定它恰好是晚100ms。如果您的ping变化很大，则无法正常工作。

您能否提供一些伪代码，以便我了解如何执行此操作？

我在这里找到了这个问题。但是没有一个答案提供如何执行此操作的示例，只有建议。

- user3011902

我也遇到了这个问题，在我的游戏中出现了抖动。您是否能够使用带有勾选标记的答案解决此问题？或者还有其他因素帮助您解决了这个问题吗？如果是这样，能否提供一些示例实现？谢谢。 - daniel metlitski

3个回答

2

这个问题被留下并请求更多细节，所以我会尝试填补Patrick Klug的回答中的空缺。他合理地建议，在每个时间点传输当前位置和当前速度。

由于两个位置和两个速度测量给出了一个四元方程组，因此我们能够解决一个包含四个未知数的系统，即一个立方样条（它有四个系数a、b、c和d）。为了使该样条平滑，端点处的一阶和二阶导数（速度和加速度）应相等。有两种标准的等效计算方法：Hermite样条和Bézier样条。对于这样的二维问题，我建议根据更新中的切线数据分离变量并找到x和y的样条，这被称为夹紧分段三次Hermite样条。这比上面链接中的样条（如基尔德样条）具有几个优点，例如控制点处的位置和速度将匹配，您可以插值到最后一个更新而不是之前的那个，如果游戏世界本质上是极坐标，则同样可以轻松地应用此方法。（另一种用于周期数据的方法是执行FFT并在频域中进行三角插值，但这似乎在此处不适用。）

这里最初出现的是使用线性代数以相当不寻常的方式推导Hermite样条的一个派生物（除非我输入错误，否则会起作用）。然而，评论使我相信给出我所谈论的标准名称将更有帮助。如果您对如何以及为什么这样做的数学细节感兴趣，这是更好的解释：https://math.stackexchange.com/questions/62360/natural-cubic-splines-vs-piecewise-hermite-splines 比我提供的更好的算法是将采样点和一阶导数表示为三对角矩阵，该矩阵乘以系数列向量产生边界条件，并解决系数。另一种方法是在采样点处的切线相交处以及端点处的切线上添加控制点到Bézier曲线中。这两种方法都产生相同的唯一平滑三次样条。

如果您选择点而不是接收更新，则可能避免一种情况，即如果您获得了错误的点样本。例如，您不能相交平行切线，或者无法告诉它是否在同一位置具有非零的第一导数。您永远不会为分段样条选择这些点，但如果对象在更新之间进行了转弯，则可能会获得这些点。

如果我的电脑现在没有坏掉，我会在这里放置像我在 TeX.SX 上发布的那样的花哨图形。不幸的是，我现在必须退出这些内容。

这比直线插值好吗？肯定是：线性插值将得到直线路径，二次样条将不光滑，高阶多项式可能过度拟合。三次样条是解决这个问题的标准方法。

它们对于外推更好吗，即您尝试预测游戏对象将去哪里？可能不是：这样，您假设正在加速的玩家将继续加速，而不是立即停止加速，这可能会使您偏离更远。但是，更新之间的时间应该很短，因此不应该偏离太远。

最后，您可以通过更多地编程动量守恒来使自己的工作变得更容易。如果物体转弯、加速或减速的速度有限制，它们的路径就不能够与您根据它们的上一位置和速度预测的轨迹偏离得太远。

- Davislor

这似乎过于复杂了。我不确定这些值在计算游戏对象移动方面代表什么。您介意概括/简化一下您的回答吗？ - user3011902

1

如果减速的物体可能会继续减速，而加速的物体可能会继续加速，那么这种方法会更好。如果物体相反，它会做得更差。如果某物刹车并向右转可能会继续这样做，你可能更成功地预测r和theta而不是x和y。如果物体总是不可预测地改变方向，无论如何都无法预测它们。 - Davislor

2

但是，插值三次样条基本上是从几个已知点生成平滑路径的标准方法。我实际上还没有尝试过它们用于此目的，但我知道这个理论。 - Davislor

1

这个答案建议使用位置和速度在两个连续时间点之间插值一个三次曲线。确实，如果它集中于思想而不是实现细节会更好。一张图片也很酷=）此外，在这里使用BLAS并不是一个好主意，因为系统非常小。只需使用任何方便的工具解决它，不要搞乱HPC计算。 - stgatilov

1

好的。重写以提供有关三次样条信息的有用参考，而不是大量数学内容。 - Davislor

显示剩余10条评论

1

根据你的游戏，你可能更希望流畅的玩家移动而不是超精确的位置。如果是这样，我建议你以“最终一致性”为目标。我认为保留“真实”和“模拟”数据点的想法很好。只需确保定期强制模拟与真实收敛，否则差距会变得太大。

关于你对不同移动速度的担忧，我建议你在数据包中除了当前位置之外还包括玩家的当前速度和方向。这将使你更顺畅地预测基于自己的帧率/更新时间的玩家位置。

基本上，你需要计算当前的“模拟”速度和方向，考虑到最后一个“模拟”位置和速度以及“最后已知”的位置和速度（更加强调第二个），然后基于此模拟新位置。

如果模拟和已知之间的差距变得太大，只需更加强调已知位置，另一个玩家就会更快地追上来。

- Patrick Klug

你能提供一些代码示例吗？将速度与数据包一起发送的问题在于，当另一个玩家突然停止移动时，他们的速度被设置为0，这意味着他在你这边会比在他那边更早地停止移动，导致他停在错误的位置。 - user3011902

1

我不明白你的疑虑。如果速度为0，那么你已经知道包裹的精确位置，因此你可以简单地调整你的速度以匹配任何感觉正确的速度限制的位置。 - Patrick Klug

2

所以您建议我发送玩家的x、y、速度、方向，然后根据这个速度对它们进行插值到那个x、y。当一个新的数据包到来时，只需将目标更新为新的x、y，并使用新的速度移动？这样会顺畅地运行吗？感谢您的回复Patrick。您能给我提供一个伪代码示例，这样我就可以了解您的意思了吗？ - user3011902

1

你可能想了解Kalman滤波器，作为这个问题更高级的版本，尽管它可能过于复杂或并不理想。Udacity有一个不错的章节介绍它们。 - Nuclearman

@TastyLemons，使用样条意味着你在当前离散轨迹上拟合了一个平滑曲线。当然，这使得它更加平滑。 - ivan866

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Lamar Latrell · Accepted Answer

我对多人游戏客户端/服务器架构和算法完全不熟悉。但是在阅读这个问题时，我首先想到的是针对每个玩家在相关变量上实现二阶（或更高阶）卡尔曼滤波器。

具体来说，卡尔曼预测步骤比简单的死区补偿要好得多。此外，卡尔曼预测和更新步骤可以作为加权或最优插值器。并且，玩家的动态可以直接编码，而不必使用其他方法中使用的抽象参数化。

与此同时，快速搜索让我找到了这个:

使用卡尔曼滤波器改进死区补偿算法以最小化3D在线游戏的网络流量

摘要：

在线3D游戏需要高效快速的用户交互支持，而网络支持通常使用网络游戏引擎实现。网络游戏引擎应该最小化网络延迟并减轻网络流量拥塞。为了最小化游戏用户之间的网络流量，使用基于客户端预测（死区算法）。每个游戏实体都使用该算法来估计自己的移动（以及其他实体的移动），当估计误差超过阈值时，实体向其他实体发送UPDATE数据包（包括位置、速度等）。随着估计精度的提高，每个实体都可以最小化UPDATE数据包的传输。为了提高死区算法的预测精度，我们提出了基于卡尔曼滤波器的死区算法。为了展示真实演示，我们使用一款流行的网络游戏（BZFlag），并使用卡尔曼滤波器改进了游戏优化的死区算法。我们提高了预测精度，并将网络流量减少了12%。

可能看起来有点啰嗦，像是一个全新的问题，需要学习离散状态空间等知识。

简单来说，卡尔曼滤波器是一种考虑到不确定性的滤波器，这就是你所拥有的。它通常在已知采样率下工作于测量不确定性，但也可以重新调整以适应测量周期/相位的不确定性。

其想法是，在没有适当的测量值的情况下，您只需使用卡尔曼预测来更新。这个策略类似于目标跟踪应用程序。

我自己在stackexchange上被推荐使用它们-大约花了一周时间才弄清楚它们与我的问题的相关性，但我后来成功地在视觉处理工作中实现了它们。

（...它让我现在想要尝试解决你的问题！）

由于我想更直接地控制滤波器，所以我将别人在matlab中编写的卡尔曼滤波器的自定义实现复制到了openCV中（使用C++）。

void Marker::kalmanPredict(){

    //Prediction for state vector 
    Xx = A * Xx;
    Xy = A * Xy;
    //and covariance
    Px = A * Px * A.t() + Q;
    Py = A * Py * A.t() + Q;
}

void Marker::kalmanUpdate(Point2d& measuredPosition){

    //Kalman gain K:
    Mat tempINVx = Mat(2, 2, CV_64F);
    Mat tempINVy = Mat(2, 2, CV_64F);
    tempINVx = C*Px*C.t() + R;
    tempINVy = C*Py*C.t() + R;
    Kx = Px*C.t() * tempINVx.inv(DECOMP_CHOLESKY);
    Ky = Py*C.t() * tempINVy.inv(DECOMP_CHOLESKY);

    //Estimate of velocity
    //units are pixels.s^-1
    Point2d measuredVelocity = Point2d(measuredPosition.x - Xx.at<double>(0), measuredPosition.y - Xy.at<double>(0));  
    Mat zx = (Mat_<double>(2,1) << measuredPosition.x, measuredVelocity.x);
    Mat zy = (Mat_<double>(2,1) << measuredPosition.y, measuredVelocity.y);

    //kalman correction based on position measurement and velocity estimate:
    Xx = Xx + Kx*(zx - C*Xx);
    Xy = Xy + Ky*(zy - C*Xy);
    //and covariance again
    Px = Px - Kx*C*Px;
    Py = Py - Ky*C*Py;
}

我不希望你直接使用这个，但如果有人能理解状态空间中的“A”、“P”、“Q”和“C”是什么（提示，理解状态空间是这里的先决条件），他们可能会看到如何连接这些点。

（顺便说一下，Matlab和OpenCV都包含了它们自己的卡尔曼滤波器实现...）