Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am a programmer and I don't have much background in mathematics. I know this question might look much more clear to you if I could articulate it in mathematical terminologies. The problem is this is my first question here and I don't know how to ask it in maths languages! So bare with me...

I am making a car-racing game where multiple players on the Internet can compete with each other. Each player drives a car whose position and rotation changes continuously over time. To let players over the network share the same game I have to quickly deliver each player's position and rotation to all other player. The problem is there is always going to be a network latency between data being sent and being received. In other words, by the time a piece of data reaches another player, it is already dated.

I think the solution to my problem is to make a function that can predict the position and rotation of other cars based on the previous data collected. When newer data arrives, the function should have a feedback so that error could be corrected. Parameters used for prediction should also be modified, maybe.

For example, I am thinking about sampling the position as well as velocity of my car evenly over time, and sending them to other player one by one. Now before other players receive my new data, they can use their own "predicted velocity" to approximate my movement. Once the new data arrives, they can use the new position and velocity to do error correction and make new predictions.

Some additional requirements about the function includes:

  1. Efficiency: the prediction and error correction function must be efficient because it is going to be computed by computer every tens of milliseconds.
  2. Robust: I will sample evenly but the other players won't receive data at an even speed, due to network uncertainties.
  3. Error Bound: it would be great if there is a way to confine error within a certain range.

I have been googling papers for such functions but I haven't found much useful information. Maybe it's because I don't have the correct keywords. So any answer/comment that

  1. helps to identify & clarify the problem in the math realm
  2. points to papers of solutions

is highly appreciated!

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

You might want to consider a Kalman filter with a very low measurement error (since presumably, when a player receives an update about position and rotation through the network, that update is treated as gospel).

In a little more detail, if you have last known position $x$, velocity $v$, rotation $\theta$ and angular velocity $\omega$, then you can compute an updated position and velocity after time $\delta t$:

$$x \leftarrow x + v \delta t$$ $$v \leftarrow v$$ $$\theta \leftarrow \theta + \omega\delta t$$ $$\omega \leftarrow \omega$$

Since this involves two multiplications and two additions, it should be fast. You do this every $\delta t$ seconds until you receive an update, at which point you set the position, velocity, rotation and angular velocity to their updated values, and continue as before.

If you additionally have the last known acceleration $a$ and angular acceleration $\nu$ then your update equations become:

$$x \leftarrow x + v \delta t + \tfrac{1}{2} a \delta t^2$$ $$v \leftarrow v + a \delta t$$ $$\theta \leftarrow \theta + \omega \delta t + \tfrac{1}{2} \nu \delta t^2$$ $$\omega \leftarrow \omega + \nu \delta t$$

which will be more accurate, as they take the time-varying velocity and angular velocity into account (whereas the previous equations assume they are constant).

As for bounding the error, it will depend somewhat on how the game works and how fast quickly the players can change their accelerations. For a naive estimate, you can say that the error in position from the first set of equations is $O(n v \delta t^2)$ where $n$ is the number of time steps since you received an update, and in the second case it is $O(na\delta t^3)$, but if the accelerations have changed significantly since you last received an update, these bounds can be violated.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.