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

Question

我正在使用JavaScript中的套接字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毫秒。

这再次假设它正好晚了100毫秒。如果您的ping变化很大，这将不起作用。

你能不能提供一些伪代码，这样我就能知道怎么做了？

我在网上找到了这个问题。但没有一个答案提供了如何做的例子，只有建议。

Answer 1

这个问题还没有解决，我们要求提供更多的细节，所以我将尝试填补Patrick Klug回答的空白。他合理地建议，你在每个时间点同时传输当前位置和当前速度。

由于两个位置和两个速度测量给出了一个四个方程组，它使我们能够求解一个四个未知数的系统，即三次样条（它有四个系数a、b、c和d）。为了使这个样条光滑，一阶和二阶导数（速度和加速度）在端点处应该相等。有两种标准的、等价的计算方法：Hermite样条(https://en.wikipedia.org/wiki/cubic_hermite_spline)和Bézier样条(http://mathfaculty.fullerton.edu/mathews/n2003/beziercurvemod.html)。对于像这样的二维问题，我建议分离变量，并根据更新中的切线数据为x和y找到样条，这被称为钳位分段三次Hermite样条。与上面链接中的样条（如基数样条）相比，这有几个优点，后者不利用这些信息。控制点的位置和速度将会匹配，你可以插值到上次更新而不是之前的更新，如果游戏世界是天生的极地，就像太空战争一样，你可以很容易地将这种方法应用到极坐标上。（有时用于周期性数据的另一种方法是执行FFT并在频域中进行三角插值，但这在这里听起来并不适用。）

最初出现在这里的是埃尔米特样条的一个派生，它使用线性代数，以一种有点不寻常的方式（除非我输入错误）将会起作用。然而，这些评论让我相信，给我所说的东西取个标准的名字会更有帮助。如果您对如何和为什么这样做的数学细节感兴趣，这是一个更好的解释:https://math.stackexchange.com/questions/62360/natural-cubical-splines-vs-piecewise-hermite-splines

一个比我给出的更好的算法是将样本点和一阶导数表示为一个三对角矩阵，乘以系数的列向量，产生边界条件，并求解系数。另一种选择是将控制点添加到Bézier曲线上，在该曲线上，采样点处的切线相交，并且在端点处的切线上。这两种方法都产生相同的、唯一的、光滑的三次样条曲线。

如果您选择点数而不是接收更新，您可能可以避免的一种情况是，如果您得到了一个坏的点数样本。你不能，例如，相交的平行切线，或告诉发生了什么，如果它回到同一个地方，一个非零的一阶导数。您永远不会为分段样条选择这些点，但是如果一个对象在更新之间发生了变化，您可能会得到这些点。

如果我的电脑不是现在坏了，我会在这里放一些像我发到tex.sx上的那些花哨的图片。不幸的是，我现在不得不退出。

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

它们对于外推更好吗？在外推中，你试图预测一个游戏对象会去哪里？可能不是：这样的话，你假设一个加速的球员会继续加速，而不是他们会立即停止加速，这会让你走得更远。但是，更新之间的时间应该很短，所以您不应该离得太远。

最后，您可以通过在更多的动量守恒中编程来使事情变得更容易。如果物体旋转、加速或减速的速度是有限制的，那么它们的路径就不能与你根据它们最后的位置和速度预测的地方偏离那么多。

Answer 2

我对多人游戏客户机/服务器体系结构和算法是完全新鲜的，然而在阅读这个问题时，首先想到的是为每个玩家在相关变量上实现二阶（或更高）卡尔曼滤波器。

具体来说，卡尔曼预报步骤比简单的航位推算要好得多。此外，卡尔曼预测和更新步骤在某种程度上作为加权或最优插值器工作。此外，玩家的动态可以直接编码，而不是在其他方法中使用抽象的参数化。

与此同时，我快速地搜索了一下：

一种改进的基于卡尔曼滤波的3D在线游戏航位推算算法

摘要：

在线3D游戏需要在网络上提供高效、快速的用户交互支持，而这种网络支持通常是通过网络游戏引擎来实现的。网络游戏引擎应尽量减少网络时延，缓解网络流量拥塞。为了最小化游戏用户之间的网络流量，使用了基于客户端的预测（航位推算算法）。每个游戏实体利用该算法估计自身的移动（也包括其他实体的移动），当估计误差超过阈值时，将更新（包括位置、速度等）包发送给其他实体。随着估计精度的提高，每个实体可以最小化更新分组的传输。为了提高航位推算算法的预测精度，提出了基于卡尔曼滤波的航位推算方法。为了给出真实的演示，我们使用了一款流行的网络游戏(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都附带了自己的卡尔曼滤波器实现...）