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

Question

我正在 javascript 中使用套接字 io 创建多人游戏。除了客户端插值外，该游戏目前运行完美。现在，当我从服务器收到数据包时，我只需将客户端位置设置为服务器发送的位置。这是我尝试做的事情：

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

所以我设置了球员的目标位置。然后在 Players Update 方法中我只是这样做了：

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 Article，他提到了这一点：

Say you receive position data at t = 1000. You already had received data at t = 900, so you know where the player was at t = 900 and t = 1000. So, from t = 1000 and t = 1100, you show what the other player did from t = 900 to t = 1000. This way you’re always showing the user actual movement data, except you’re showing it 100 ms “late”.

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

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

我在网上找到了这个问题here。但是 none 的答案提供了如何操作的示例，仅是建议。

Answer 1

根据您的游戏，您可能更喜欢流畅的玩家移动而不是超精确的位置。如果是这样，那么我建议瞄准 'eventual consistency'。我认为您保留 'real' 和 'simulated' 数据点的想法很好。只要确保不时强制模拟与真实收敛，否则差距会变得太大。

关于您对不同移动速度的担忧，我建议您在数据包中除了当前位置之外还包括玩家的当前速度和方向。这将使您能够根据自己的 framerate/update 时间更顺利地预测玩家的位置。

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

如果模拟和已知位置之间的差距太大，只需更加强调已知位置，其他玩家就会更快赶上。

Answer 2

我完全对多人游戏client/server架构和算法很陌生，但是在阅读这个问题时首先想到的是实现二阶（或更高）卡尔曼过滤每个玩家的相关变量。

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

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

An improvement of dead reckoning algorithm using kalman filter for minimizing network traffic of 3d on-line games

摘要：

Online 3D games require efficient and fast user interaction support over network, and the networking support is usually implemented using network game engine. The network game engine should minimize the network delay and mitigate the network traffic congestion. To minimize the network traffic between game users, a client-based prediction (dead reckoning algorithm) is used. Each game entity uses the algorithm to estimates its own movement (also other entities' movement), and when the estimation error is over threshold, the entity sends the UPDATE (including position, velocity, etc) packet to other entities. As the estimation accuracy is increased, each entity can minimize the transmission of the UPDATE packet. To improve the prediction accuracy of dead reckoning algorithm, we propose the Kalman filter based dead reckoning approach. To show real demonstration, we use a popular network game (BZFlag), and improve the game optimized dead reckoning algorithm using Kalman filter. We improve the prediction accuracy and reduce the network traffic by 12 percents.

可能看起来很冗长，就像一个全新的问题来了解它的全部内容......以及离散状态 - space 就此而言。

简而言之，卡尔曼滤波器是一种考虑了不确定性的滤波器，这就是你在这里得到的。它通常适用于已知采样率下的测量不确定性，但可以重新设计以处理测量中的不确定性 period/phase。

想法是代替适当的测量，您只需使用卡尔曼预测进行更新。该策略类似于 target tracking applications.

我自己在 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' 处于状态-space（提示提示，状态-space 理解是这里的先决条件）他们可能会看到如何连接点。

（顺便说一下，matlab 和 openCV 都有自己的卡尔曼滤波器实现...）

Answer 3

这个问题悬而未决，要求提供更多详细信息，因此我将尝试填补 Patrick Klug 回答的空白。他合理地建议，你在每个时间点都传输当前位置和当前速度。

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

最初出现在这里的是使用线性代数以一种有点不寻常的方式推导 Hermite 样条（除非我输入错误）会起作用。但是，这些评论使我相信，为我所谈论的内容提供标准名称会更有帮助。如果您对它如何工作以及为什么工作的数学细节感兴趣，这是一个更好的解释：https://math.stackexchange.com/questions/62360/natural-cubic-splines-vs-piecewise-hermite-splines

比我给出的更好的算法是将样本点和一阶导数表示为三对角矩阵，乘以系数的列向量，产生边界条件，并求解系数。另一种方法是将控制点添加到贝塞尔曲线，其中采样点处的切线相交并位于端点处的切线上。两种方法都产生相同、独特、光滑的三次样条曲线。

如果您选择点而不是接收更新，您可能可以避免的一种情况是您得到的点样本不佳。例如，您不能与平行切线相交，或者如果它回到具有非零一阶导数的相同位置，则无法判断发生了什么。您永远不会为分段样条选择这些点，但如果对象在更新之间突然转向，您可能会得到它们。

如果我的电脑现在没有坏掉，我会在这里放置精美的图片，就像我发布到 TeX.SX 的图片一样。不幸的是，我现在不得不退出这些。

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

它们是否更适合外推，您可以在其中尝试预测游戏对象的去向？可能不会：通过这种方式，您假设正在加速的玩家会继续加速，而不是他们会立即停止加速，这可能会使您离得更远。但是，更新之间的时间应该很短，所以你不应该离得太远。

最后，您可以通过在更多的动量守恒中编程来让事情变得容易得多。如果物体转动、加速或减速的速度有限制，它们的路径将无法偏离您根据其最后位置和速度预测的位置。

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

Multiplayer Game - Client Interpolation Calculation?

javascript

algorithm

multiplayer