Difficult maths problem in a network game

[CommanderKeith]

Hi,

I’m working on a network game but have been struggling with the client timing issues - I’m trying to allow the game to be tolerant of very high latency and I’m doing it by rewinding back to the lagged event, applying it, then fast-forwarding to the current time. The problem is that the symmetrical rewind and fast-forward of the game world is difficult… The two biggest problems are that the game logic needs to be independent of the frame-rate (which is not fixed), and that negative time updates need to reverse positive time updates.

So here’s a maths problem that I can’t solve:
[i]
A player is moving from point A with a horizontal and vertical velocity of Vx and Vy respectively for a period of time t. He attempts to aim his turret at a fixed point M as he travels along, however his turret can only move at a maximum angular velocity of Va. At point A his turret is at angle Alpha.

What is the equation for the turret angle Beta at time t?[/i] :-\ ???

Here’s a simplified diagram, where Vy is zero and Alpha, the initial turret angle at point A, is equal to the angle of M from point A:

http://www.freewebs.com/commanderkeith/random/mathsProblem.PNG

I don’t know how to solve it. I would like to know the answer since with this equation I could make perfectly-reversible updates to the player’s turret angle using different values for t. By the way, t is the time between frames, or the ‘delta’, and M is the mouse pointer where the turret is meant to aim.

Currently I just figure out the angle Theta that the turret needs to rotate through as the player moves between points A and B, where B is wherever the player ends up after time t. If time t multiplied by the maximum angular velocity is less than Theta, I rotate by that t times the maximum angular velocity. Otherwise I just rotate the turret by Theta.

The problem with this approach is that if lots of small updates are done, so t’s are small, then the rotation of the turret is less than if t’s are big. This means that a high-frame rate player (with small t’s) turns his turret slower than a slow-frame rate player, causing trouble for me since then the server and client get out of sync. I think that this occurs because if the turret were to point at M the whole time, the rate of change of the turret angle is greatest when the player is close to H compared to when it is far away. So the maximum rotation limit only affects the turret at certain times when the player is close to H. But if t is large, then the (average) angular speed may not exceed the maximum angular speed, even though it would have for a certain portion of time.

If anyone finds this kind of maths-challenge interesting, it’d be a great help!

Thanks,
Keith

[bleb]

[quote]The problem with this approach is that if lots of small updates are done, so t’s are small, then the rotation of the turret is less than if t’s are big. This means that a high-frame rate player (with small t’s) turns his turret slower than a slow-frame rate player
[/quote]
I don’t get this bit. Shouldn’t the net effect of many updates with small t be the same as fewer steps with larger t?

[CommanderKeith]

I hope I’m not wrong, but this is what I thought…

If the player is far away from M then the required change to the turret angle will be small, so when the turret turns at full speed, it will easily make the small rotation, with some extra time left. If the player is close to M, then the required rotation is large, greater than what can be done due to the maximum angular speed. So only part of the rotation can be done.

So if updates are large, then the far-away-from-M scenario which has spare time is kind of ‘given’ to the close-to-M scenario where more time is needed, resulting in a required angular speed that can be less than the maximum, so in the big-time update case there’s no speed restriction, but in the small-time case there is.

[bleb]

@CommanderKeith

So if updates are large, then the far-away-from-M scenario which has spare time is kind of ‘given’ to the close-to-M scenario where more time is needed, resulting in a required angular speed that can be less than the maximum, so in the big-time update case there’s no speed restriction, but in the small-time case there is.

I’m having difficulty parsing this.

Anyhoo, to restate your problem as I understand it:

You have the player’s position at time 0, the turret angle at time 0, the player’s velocity (assumed to be constant), the target point. and the turret’s maximum turn rate.
You want to compute the turret angle at an arbitrary time t.

I reckon it’s going to be a bit tricky, it’s definitely non-linear. I shall have a bash at it tomorrow.

[broumbroum]

@CommanderKeith

Hi,

I’m working on a network game but have been struggling with the client timing issues - I’m trying to allow the game to be tolerant of very high latency and I’m doing it by rewinding back to the lagged event, applying it, then fast-forwarding to the current time. The problem is that the symmetrical rewind and fast-forward of the game world is difficult… The two biggest problems are that the game logic needs to be independent of the frame-rate (which is not fixed), and that negative time updates need to reverse positive time updates.

So here’s a maths problem that I can’t solve:
[i]
A player is moving from point A with a horizontal and vertical velocity of Vx and Vy respectively for a period of time t. He attempts to aim his turret at a fixed point M as he travels along, however his turret can only move at a maximum angular velocity of Va. At point A his turret is at angle Alpha.

What is the equation for the turret angle Beta at time t?[/i] :-\ ???
(…)
Currently I just figure out the angle Theta that the turret needs to rotate through as the player moves between points A and B, where B is wherever the player ends up after time t. If time t multiplied by the maximum angular velocity is less than Theta, I rotate by that t times the maximum angular velocity. Otherwise I just rotate the turret by Theta.

The problem with this approach is that if lots of small updates are done, so t’s are small, then the rotation of the turret is less than if t’s are big. This means that a high-frame rate player (with small t’s) turns his turret slower than a slow-frame rate player, causing trouble for me since then the server and client get out of sync. I think that this occurs because if the turret were to point at M the whole time, the rate of change of the turret angle is greatest when the player is close to H compared to when it is far away. So the maximum rotation limit only affects the turret at certain times when the player is close to H. But if t is large, then the (average) angular speed may not exceed the maximum angular speed, even though it would have for a certain portion of time.

If anyone finds this kind of maths-challenge interesting, it’d be a great help!

Thanks,
Keith

I’m not a math-scientist at NASA but this is quite a common issue to physics simulation (not calculation) in programmatics. The common problem is, as you described it, that your frame-rate can vary and the rendering and math-calculations must synch with the screen renderiing, a.k.a vertical-synch or skip-frames … As my ex-profesor would, I want to bring out a well-known explanation from elementary logical systems. If you’ve ever experienced this curse at High-school, there’s always a CLOCK-TIMER for every of the logical systems you build. This clock-timer cannot skip or change its rate, whatever is your architecture, isn’t it ? This is the first point.

Now sharing this logical system rule with our java codes, the clock-timer doesn’t exist, as we’d observe such blitting artefacts like your digital hand-clock would blink every seconds. You have to simulate it. Using a variable t as the clock, its like scratchin’ with your DJ’s sound-player, t doesn’t hold a periodic state; t changes through the speed of the CPU, the network lags and rushes, etc. So there’s the ONLY SOLUTION to that issue, is to get this variable t in a real-timeframe that reproduces the correct timing, which is always applied to such “Timing Frameworks”. Basically, it is the System.Time that delivers t and not the math loop or another Timer.

With this basic concept, a t variable in a physic calculation or animation, will always refer to an originating time t0, as in physics, but this is the time when you started the calculation or animation. Then the calculation has to be RANGED from a MIN and a MAX value, as animation must have a PLAYTIME, like a movie can be 2 hours and 33 min long. With those 3 VARIABLES, T becomes obsolete as it can be mesured AT EACH TICK with the STARTTIME and PLAYTIME.

Finally just code the math formulas with T REPLACED BY THE OBSERVED REAL-TIMING and you’re on !!!

This is all about the timing framework. I know one good framework, @ http://www.swinglabs.org/ , but it isn’t very difficult to get on without it, besides. ;D

[Ask_Hjorth_Larsen]

I don’t get it. I have implemented a similar system once, doing exactly the same thing with either turning at max rate or simply setting the position exactly. I see no reason why something would be slower or faster in another framerate.

[CommanderKeith]

@bleb

Anyhoo, to restate your problem as I understand it:

You have the player’s position at time 0, the turret angle at time 0, the player’s velocity (assumed to be constant), the target point. and the turret’s maximum turn rate.
You want to compute the turret angle at an arbitrary time t.

I reckon it’s going to be a bit tricky, it’s definitely non-linear. I shall have a bash at it tomorrow.

Yes, you’ve got the right idea. Thanks for considering it.

I think that this is how it needs to be solved:
first figure out the equation for the angular velocity of the turret if it was to point at M regardless of the maximum angular velocity. I think this will involve differentiating the rotation of the turret (Theta) with respect to t (dTheta/dt).
Then we can find out at what time the turret will reach that maximum angular velocity (call this time ta).

So angular distance covered up to this time will be (dTheta/dt) * ta. Then we figure out the period of time tb that the angular velocity falls back to the maximum (if it does at all). Over the this period the angular distance covered is simply maxAngularSpeed * tb. And for the distance covered in the remaining time, it will be maxAngularSpeed multiplied by however long it takes for the turret to point at M, and then for the rest of the time it will move at (dTheta/dt) * the time left.

So if anyone agrees with this, who knows how to work out dTheta/dt?

By the way, when I say that the difference in frame rate causes problems, normally the frame rate is about 60 FPS or more, and in this situation I’m sure that the effect is negligible when one computer’s frame rate is 60 and anothers is 100 or whatever. But in my case I rewind to the lagged event sent by a lagged player, and this rewind is a time of negative 1 second, the the frame rate is 1FPS. Then after applying the event I fast-forward to the current time and then that is another jump of 1 second, so 1 FPS. This is why there is a notable difference in how the different players move - t varies greatly.

Thanks,
Keith

[broumbroum]

it’s not about differentiating here, otherwise you surely get the problem of “integral” (is it in English ?) or dt that has a complex definition for a sequential calculation. if you want to get the graph of some sin or cos or whatever a trigonomical, the math algorithms do it for you. So as an example, I can share you this little function I use for the high-jump simulation of players. Here it is :

                /* F = m.a ; v = s/t ; v = a.t = (t.F)/m; t = s/v = v/a = (v.m)/F; s = (v^2.m)/F = (t^2.F)/m                /* F = m.a ; v = s/t ; v = a.t = (t.F)/m; t = s/v = v/a = (v.m)/F; s = (v^2.m)/F = (t^2.F)/m
                        High Jump formula: (x,y)t = (x0,y0) + (speed*t) - (t^2 * 0.9(G)/2) */
    private int calcHighJump(int xDirection, int t, int speed) {
        double alpha = Math.PI/2.0 - (double)xDirection/Math.abs((double)xDirection) * Math.PI/4.0;
        //System.out.println("/*************** " + "height=" + (max.y - pos.y) + " sin(pi/4)=" + Math.sin(alpha) + " y-move=" + (Math.sin(alpha) * speed + 0.9 * t));
        pos.x += (int)(Math.cos(alpha) * speed);
        pos.y -= (int)(Math.sin(alpha) * speed + gravity * (t--)) * weight;
        pos.x = Math.min(Math.max(min.x, pos.x), max.x);
        pos.y = Math.min(pos.y, max.y);
        return t;
    }

As you can see, I get no dt in here even if it could have been mathematicallly derived on t to find out the (x,y)t acceleration vector. And as a matter, this function is totally dependent of the frameRate, because t increases by 1 unit at each call-time. So as I noticed it beyond of your post, either t is replaced with the correct timelap or it will fail if the frameRate varies.
It’s up to the application Timers to synch on frame rate, by passing it to a synched method or simply to correct the gap between each tick, by mesuring that timelap from start to current time. Consequently, I’d get a t increased by one PLUS the currentTickTime MINUS lastTickTime DIVIDED BY the frameRate, i.e.

t = t + (int)((double)(System.currentTimeMillis() -  lastTickTime) / 1000.0) / frameRateInSeconds;

That seems much more approximating than derivating, understand ?

[bleb]

I’ve had a think, but haven’t come up with anything terribly exciting. I reckon your best bet is to disconnect the behaviour of your game from the framerate of your graphics, and have everyone update their positions, turret angles, etc at the same rate.

I do also see now why those with higher frame rates will have more difficulty having their turrets track a target, particularly if the target is passing close by.

[dishmoth]

As far as I can figure out, the way you would have to go about solving your maths problem is something like as follows.

Firstly, you would calculate the equation for the true angle (theta) of the target from the turret as a function of time (t). This is pretty simple since it’s basically theta = atan(y/x), with (x,y) being the relative position of the target. If you’ve chosen coordinates so that movement is always along the x-axis, then (x,y) = (x0-v*t,y0).

Next, you need to know when the target’s angle is moving too fast for the turret to keep up. If this happens, it will be as the turret passes the target. You would solve for the time at which abs(dtheta/dt) = alpha_dot_max. This will have zero, one, or two solutions. If there are two solutions, we’ll call them t_min and t_max. (If there is one solution then t_min = t_max.)

Now things get tricky. The behaviour of the turret will have up to four phases. During phase one, it will “acquire” it’s target. That is, it will turn at its maximum speed towards the target. The angle (alpha) of the turret as a function of time will be a straight line with gradient either +alpha_dot_max or -alpha_dot_max during this phase. The phase ends at the time when the line alpha(t) crosses the curve theta(t). I’m guessing that you’d have to solve for this value of t numerically.

Once the turret has acquired its target, it then goes into the second phase, which is “tracking”. During this phase, things are easy because we can just say alpha(t) = theta(t). The turret may lose the target however at time t_min when the two objects pass each other. (If we didn’t define values t_min earlier then this isn’t a problem, and phase two never ends.)

If there is a third phase, then this is “re-acquisition”, and it involves the turret turning at it’s maximum speed once again. Basically, the set-up is a repeat of the first phase.

The final phase is a repeat of the “tracking” from phase two. This phase, thankfully, doesn’t end.

So there you go! With a fantastic amount of effort you should be able to derive an equation for the turret direction alpha as a function of time!

Personally, I’d try to avoid solving this problem directly. Defining a maximum time step of one sixtieth of a second, say, and calling your update function multiple times as necessary sounds like a much better idea.

Simon

[CommanderKeith]

Hi bleb, dishmoth and broumbroum, thanks heaps for thinking about the problem…

it’s too tricky to bother solving mathematically I think and there will be so many other problems like this one that I’ll have to deal with if I don’t do some kind of solution that approximates. Like how will I do perfectly reversible collisions between objects?! So far I’ve got perfectly reversible movement but I think that’s as far as I’ll be able to get.

@bleb

I reckon your best bet is to disconnect the behaviour of your game from the framerate of your graphics, and have everyone update their positions, turret angles, etc at the same rate.

I’m trying to think of a good way to do this. The maximum time-step idea that Dishmoth suggested sounds good.

A maximum time-step will be perfectly reversible, but it won’t be perfect in this way: a time step of 1/60s won’t have the same effect as two time steps of 1/120s, which is not ideal. The difference in turret positions per time-step will be small, but it may be significant since small time-steps will happen all the time since I don’t want to lock the frame-rate of my game (so it will run on crap computers), so the time step updates will not be constant and will not occur at the maximum time step. Hopefully the difference will be negligible. If it’s not, I can just send the game world to the clients so that they are periodically re-synchronized with the server.

Thanks 8)

[dishmoth]

[…] Like how will I do perfectly reversible collisions between objects?! So far I’ve got perfectly reversible movement but I think that’s as far as I’ll be able to get.

Just curious: Can you not just record state information (position, velocity, direction, etc.) every time something interesting happens (e.g., after a collision)? That seems like the obvious way of rewinding the game, by going back to a historical state and advancing a little to the target time if necessary.
Simon

[broumbroum]

So far, did CommanderKeith solve its problem ? I’m wondering about how you want to do.
I could get your code corrected if you had some to share with us. So far I managed to build a pong game, and other impl of Pacman to bring them out on applets or Web Start. I also have got some code to share if you want to. For example I’m building my game over an already structured package, got from my high-school, yet 3-4 years old.

[CommanderKeith]

@dishmoth

Just curious: Can you not just record state information (position, velocity, direction, etc.) every time something interesting happens (e.g., after a collision)? That seems like the obvious way of rewinding the game, by going back to a historical state and advancing a little to the target time if necessary.
Simon

Good idea. I’m already storing some object state fields at the times when key and mouse events occur, and that has come in handy so that I don’t have to rewind to when exact events happen. This doesn’t solve my problems though since, for example, bullet firings happen at a certain rate and can occur in between turret movements, so I need the turret rotation angle at every bullet fire. I think it would be impractical to have a stored state for every single bullet fire and to rewind sequentially through them when there are 100 bullets fired a second by each player.

Adding collisions as events might be a good idea, but I don’t think I need that yet. With a max time update then I think the reversibility will be close enough until there is a re-synch’ing between server and clients.

@broumbroum

So far, did CommanderKeith solve its problem ? I’m wondering about how you want to do.
I could get your code corrected if you had some to share with us.

Thanks broum for the offer but my source code is a little ugly for now and I wouldn’t want to waste your time looking through it. Once I’ve finished I’ll post the source code up though.

Thanks,
Keith