Physics Collisions + Network Latency

[tom]

Even without StrictMath/strictfp, any differences will usually be tiny. However estimating the likely size of these differences for particular algorithms is a highly specialized skill.

It do not mather how tiny the difference is. Don't have to be an expert to know that the error will add up very quickly and the game will end up out of synch.

If you are not an expert you should probably not say anything at all on this subject. Whether the errors accumulate and how fast depends on the algorithms involved. While some algorithms would diverge rapidly, others can proceed for billions of operations with only tiny differences. In my opinion (as a PhD in mathematics) attempting to avoid floating point is not the correct answer to this problem. After all a great deal of effort was put into the design of the arithmetic used in modern computers (and required by Java) with the intention that the behaviour of floating point is well controlled. Perhaps instead of treating floating point as "here be demons", more programmers should learn to understand it.

I'll put in another way. All operations have to be exactly the same or you'll get out of sync. The tiniest difference in precission can mean the difference between hitting a wall or not. I don't see how you can "manage the errror" out of the problem. But I'm sure you'll tell me how, and I'm looking forward to your reply . You could use floating point if you could find out wich operation can differ and replacing those with StrictMath. Maybe it's only the trig functions. But they are quite important in 3d simulations.

This method is mostly used in RTS games where integer is used anyway. A friend of mine used it in a football game. He started with floating point but found out it did not work and switched to integer.


Now slightly more on topic:
For a car game I would consider the Q3 method of transmitting the difference in state from the last acknowledged timestamp, using udp. There is a limited number of entities that changes every frame so it would work quite well.

[Ask_Hjorth_Larsen]

Okay, so let me get this straight:

1) All the methods in StrictMath (which are in most cases dentical to those in Math) produce exactly the same results on all platforms.

2) All floating point operations with +, -, * and / produce exactly the same results on all platforms EXCEPT when numerical overflow occurs.

3) The strictfp keyword kan be used to make sure that identical results are achieved even when numerical overflow occurs.

Is this correct? Because I guess strictfp operations are slower than nonstrict ones, and it would be very nice to avoid strictfp if the numbers stay within reasonable bounds.

On another issue, since we are talking about games, all we care about is synch. Whether the simulation is realistic (like using Runge-Kutta instead of Euler to stop numerical solutions from diverging from would-be reality) is not essential in most cases. Only the local looks-like-realism is important.

[Mark Thornton]

1) through 3) correct.

4) Methods in Math which do not mention "ulp" also give the same result on all platforms except perhaps when overflow occurs.

Of course JVM's can have bugs which may be unique to a particular JVM.

Games published by our own members! Check 'em out!

[Ask_Hjorth_Larsen]

Thank you, Mark Thornton, for your clear response.

By the way, as many of you probably know, most of the Math methods delegate to StrictMath presently. This includes the trig functions. I guess this depends on version number.

[Mark Thornton]

By the way, as many of you probably know, most of the Math methods delegate to StrictMath presently. This includes the trig functions. I guess this depends on version number.

You should ignore that apparent delegation of implementation. The JVM can replace the implementation of Math methods with anything it likes subject to meeting the specification.

[Jeff]

Okay, Im jumpign in rather later here so forgive me if all this has been said...

Basically, you are trying to do one of the  hardest things to do in a WAn networked game.

Car racing invovles objects moving very very fast very very close to eahc other where a tiny difference  in position can make ahuge difference in result.  When we did Nascar Racing OnLine at TEN we used a special network for gameplay provided by concentric.  They ran a star netrowk out of michigan. We put the server there and prioritized packets going to and from that machine to reduce latencies.  That was the only environment in which we could gaurantee game-play.

An open-loop client based system is right out because the whole reason that situation works well for many games is because clients are allowed drift a moderate degree apart from each other to cover latencies.  Given your situation you will probably need a central server.  However that will not solve all your problems.  Imagine trying to drive a race with a race-car that has variable lag between when you turn the wheel and when you move the wheels and thats the situation your players will be facing.  Its a definite ecipe for disaster.  A latency spike might well mean a crash.

You can reduce this somewhat by making this a broadbamnd only game.  Analog modems have terrible latency spikes all of their own making.  Broadband modems typically dont add much to the problem already existant on the internet.  You also might want to consider carefully your communications protocol.  Sicne youare pusing the inmternet to the limit ehre this is one of the games Ive seen where the pain of UDP might really be worth it.  You also might be able to improve apparent latencies by sending packets both to the server AND P2P.  Packets from the server are "correct", packets from other players are in-between "hints" to help in your prediction. You will probably have to have a TCP channel for really critical information (eg crashes from the server.)

This is really really a bleeding edge thing youare trying to do, I wish you luck!

[darkprophet]

Thanks for the wise words jeff, its getting hairy now, as you said, latency kills...

Regards,
DP

[swpalmer]

You can reduce this somewhat by making this a broadbamnd only game.  Analog modems have terrible latency spikes all of their own making.  Broadband modems typically dont add much to the problem already existant on the internet.

Just a related anecdote.. In my area (greater Toronto), the cable modems are worse than dialup as far as latency spike go.  The latency is so all over the place that you simply can't play Q3 with someone on a cable modem.  That person cannot be hit.  They bounce around the screen in a totally spastic way, I assume because the algorithms in the Q3 network code that attempt to compensate for latency get so screwed up from the widely and constantly varying latency.   E.g. ping the server and you sill see the latency vary from 70 to 300 ms.

All of the techy folk that I know specifically dumped cable and went with DSL because the issues with cable were so bad.

[Jeff]

Ouch. Cable in the US is generally a lot better.

Id guess your Canadian providers ar trying to put too many people on too little bandwidth and since its a shared conenction between many users, your effectviely getting "swapped out", but thats just a guess.

One thing to consider, annoying but perhapse better then the alternatives:  There are a lot of studies that show that humans deal *much* better with repdictable latency then with uinpredictable spikes.  YOu might try to figure out a 90%+ latency max and actually *induce* the latency when data arrives sooner.  This would at elast even it out though,as  someone pointed out, it might start to feel like "lunar buggy racing" if that lag is too big.

[darkprophet]

Early tests show that a Server-Client model is "good" enough. A ping of 15 can be achieved from birmingham to london with normal broadband connections. Is 15ms low enough? Isn't that the usual ping in a LAN network? 

Regards,
DP

Games published by our own members! Check 'em out!

[tom]

15 is very good, almost to good to be true. Aim for 2-300 unless you know the topoligy of the network.

[swpalmer]

Is 15ms low enough? Isn't that the usual ping in a LAN network?

No.
Yes.

Even on a LAN the effects of latency can affect game play -- it all depends on the nature of the game.  Some people argue that your reflexes are not fast enough for the latency on a LAN to matter.  That is crap.  The latency can cause the screen to redraw with "wrong" information.  If the display is synchronized to the video beam then for sure you will get a complete frame of garbage.  You *will* notice that..  That is when you will *begin* to react to the erroneous information.  It may take 100ms for your reaction to complete, and the screen may have refreshed with the correct game state by that time, but it is too late.

Depending on the nature of the game most of the time the bogus information won't be off far enough to matter.  But sometimes it might matter, it all depends.  Fast-action "twitch" games it would seem are the most vulnerable.

[Alan_W]

A most interesting thread.  I remember reading an article about GT4 on PS2, where this problem was mentioned and stated as one of the reasons for the delay to release.  As it stands GT4 supports LAN gaming but not online.  I guess they couldn't solve those >15ms latencies.

I haven't tried writing an online game yet (on my todo list ), but I would transmit linear & angular positions and velocities and use the velocities to provide local prediction of future position.  This requires that all players are time-synched, which is an issue in itself when the round trip delays are variable.

Player to player interactions are still a problem.  A sudden swerve to avoid a collision, may not reach the other player until 500ms later (via server), which is obviously ludicrous.  Peer to Peer would halve this, which has to be a good thing, but then there's all the problems with trying to tunnel though NAT routers (or insist that users forward ports).  Trouble is even 250ms is way too much latency.

So I suspect that means either:
i) LAN gaming only (or local internet, say on the same cable segment)
OR
ii) No collisions between cars (they just pass through each other)

Maybe one could tart up the no-collision scenario a touch.  If your computer detects a collision with another car, it could make a limited authority alteration to your control inputs.  i.e. if you ram from behind, your car slows down a touch, if you side-swipe, your steering angle is adjusted slightly to make your track more parallel with the other car.  There is however no effect on the other car; collisions are handled locally.  This means you can't ram the other car off the track (unless the collision is also detected locally by the other player's comp, which also makes a steering correction).

Thus, if the other player attempts to sideswipe you, but you have moved in the meantime, you see the other car make a velocity correction for no apparent reason.  If this is a small correction, it will just look like the other driver is swerving to avoid you, rather than as the result of an impact.  I reckon this is Ok.

However this raises the question of how large a correction can be made.  If it is unlimited then the other car may appear to spin off the track for no apparent reason.  Also if you crash into the other car then it is possible that you spin off and the other car appears uneffected.

Limiting the maximum correction to making your track parallel to the velocity of the other car would reduce this weirdness, but there would still be some artifacts in extreme cases.  There would also be no spectacular crashes.

Alan

[darkprophet]

Just for you US people, birmingham is about 140 miles away from london. The server tested was in Surrey, which adds another 20 miles. 160 Miles in short....

Im gonna be doing a very rough test today, with collisions, to see if this really is a *huge* problem and at what ping does it actually become a huge problem. Maybe even have a ping ban so that if players have a ping larger than the maximum allowed for this game, they get banned...Or even sent to another server which is titled "EXPECT LAG!" 

DP

[Alan_W]

Hummm.  On coming into a sharp curve, the last transmitted velocity may be straight ahead.  Due to latency at the other end, this could result in the predicted position appearing to be off-track on the other players' computers, when in reality the first player made it round the curve.  This would appear as cars skidding off & then miraculuously jumping back onto the track.

One solution is to cause all remote cars to slide round the track edges, unless a positive off-track position is reported from the remote players computer.  There will still be some position jumping as cars go round the track though.

Another possibility is to have all cars belonging to remote players being driven by the same program as is used for computer cars in a single player game.  When a position/velocity fix comes in, the car data is updated.  This means that cars will try to go round the curves on the best track available from the current position/velocity.  If the remote player provided position/velocity is such that there is no way to stay on track, the predicted path will now go off-track.  This looks like a fair solution.

Alan

[tom]

Hummm.  On coming into a sharp curve, the last transmitted velocity may be straight ahead.  Due to latency at the other end, this could result in the predicted position appearing to be off-track on the other players' computers, when in reality the first player made it round the curve.  This would appear as cars skidding off & then miraculuously jumping back onto the track.

One solution is to cause all remote cars to slide round the track edges, unless a positive off-track position is reported from the remote players computer.  There will still be some position jumping as cars go round the track though.

Another possibility is to have all cars belonging to remote players being driven by the same program as is used for computer cars in a single player game.  When a position/velocity fix comes in, the car data is updated.  This means that cars will try to go round the curves on the best track available from the current position/velocity.  If the remote player provided position/velocity is such that there is no way to stay on track, the predicted path will now go off-track.  This looks like a fair solution.

Alan

Another approach is to put a delay on remote cars. That will give them a chance to send their real positions before you start guessing what they did. The local car would be ahead in time of the other cars, but it would reduce the jumpingness of correcting extrapolated positions.

[Alan_W]

Another approach is to put a delay on remote cars. That will give them a chance to send their real positions before you start guessing what they did. The local car would be ahead in time of the other cars, but it would reduce the jumpingness of correcting extrapolated positions.

That would work, although there could be arguments about who has won, since you could visibly come in first, when in real time you are behind the other player.

The main trouble with multi-player is of course finding some long suffering friends to test it with you

[darkprophet]

I know a couple of people with a terminally ill condition known as "TestWhatDPMakes". Its a rare and tragic disease....

I did a couple of tests across birmingham today (<10ms ping), and it doesn't seem to be a problem! I gotta test it to london tomorrow, see how much it is affected...

Regards,
DP

[swpalmer]

Another approach is to put a delay on remote cars. That will give them a chance to send their real positions before you start guessing what they did. The local car would be ahead in time of the other cars, but it would reduce the jumpingness of correcting extrapolated positions.

Does that translate to: "Give the local player a head start."
In which case everyone *thinks* they are in the lead, only to find out at the end who really won.  Collisions between cars can't make sense in that case. Each local machine would have a different state entirely. E.g. player 2 thinks they bumped player 1, but player 1 thinks he is far away from player 2.   Whose car bounces? On which screen does the bounce show?

[darkprophet]

Thanks for the suggestions everyone. Its been really helpfull.

Me and my mate implemented a PeerToPeer network for the game and it seems to be keeping up to the job with a ping of no more than 20 across the UK with around 10 people playing. So its looking up and the collisions are better now.

Having said that, we all had broadband...

DP

[Jeff]

Thanks for the suggestions everyone. Its been really helpfull.

Me and my mate implemented a PeerToPeer network for the game and it seems to be keeping up to the job with a ping of no more than 20 across the UK

Wow. Wish we could rely  on that here  in the US.

[Mark Thornton]

Thanks for the suggestions everyone. Its been really helpfull.

Me and my mate implemented a PeerToPeer network for the game and it seems to be keeping up to the job with a ping of no more than 20 across the UK

Wow. Wish we could rely  on that here  in the US.

I think it is only cable modem users who see pings that low here. ADSL gives a ping of more than that just getting to the local exchange. It also helps that cable modems here are bandwidth limited to relatively low values (3MB/s max, and most are 1MB/s). This helps because the bandwidth limiting doesn't kick in for a second or so, meaning that small packets go at the real modem speed.

[darkprophet]

You sure? Because my mate (who actually implemented the SuperServer) is on ADSL in surrey (virgin is his ISP)...

Mark, would you mind if you ran a little networking test to see your ping with small packets? I'd like to see the pure ping between my connection and yours...I'l PM you the details if your not busy?

/DP

[Mark Thornton]

I don't mind doing a test. I have cable at home and ADSL at work. From work a ping to the BBC is currently averaging around 26ms, whereas at home it is often down to around 14ms. You can contact me at mthornton at optrak.co.uk (not sure why I bother to disguise that, every spammer in the universe already has the address).

[blahblahblahh]

I think it is only cable modem users who see pings that low here. ADSL gives a ping of more than that just getting to the local exchange. It also helps that cable modems here are bandwidth limited to relatively low values (3MB/s max, and most are 1MB/s). This helps because the bandwidth limiting doesn't kick in for a second or so, meaning that small packets go at the real modem speed.

Hmm. I think you need a new DSL provider . Typical worst-case response for me is 14ms onto the provider's network (their dsl-router.blah.blah etc) and 15-24ms for any sites that have good connectivity to them (e.g. stuff in LINX/telehouse/etc). This has been the same with each of the last 3 providers I've had in 3 places around the UK a bit more than a hundred miles or so apart.

e.g. sitting in a house in a private road several miles from the nearest village (population circa 500) marooned in the countryside I'm getting sub-20ms pings getting *beyond* LINX.

Random reasonably large UK sites, including ones I know are hosted in non-London towns like e.g. Cambridge, I'm getting sub-25 ms pings.

...OTOH, IME cable providers in the UK (I've had IIRC 4 in 4 different towns/cities) have generally had basic ping of 35ms to get to the provider, and typically 40ms to get anywhere close, 55-65ms to get anywhere interesting. However, it's been more than 2 years since I last had a cable modem, so my knowledge there is probably way out of date .

[kevglass]

Yeah, fraid you're out of date on that one. Telewest (me) to provider is <20ms, NTL (a collegue) also sub 20ms to provider.

Kev

[Mark Thornton]

Hmm. I think you need a new DSL provider . Typical worst-case response for me is 14ms onto the provider's network (their dsl-router.blah.blah etc) and 15-24ms for any sites that have good connectivity to

Given that from work it is 26ms ping to the nearest visible bit of BTs infrastructure, changing ISP would be pointless. No unbundled lines available, and NTL can't get a line in to the premises (can't get wayleave).

[Jeff]

Heh.

I am SO jealous.  Here in the states you need to design for spikes of 400ms or more. 

And thats on broadband.

Course you are dealign with a smaller area but still I'm imrpessed.

[Mark Thornton]

I am SO jealous.  Here in the states you need to design for spikes of 400ms or more. 

The nearest I can get to java.sun.com that is responding to pings is 64.125.27.102. Over 50 pings minimum is 167ms, maximum 192ms, average 170ms.

[Jeff]

I am SO jealous.  Here in the states you need to design for spikes of 400ms or more. 

The nearest I can get to java.sun.com that is responding to pings is 64.125.27.102. Over 50 pings minimum is 167ms, maximum 192ms, average 170ms.

My 400ms number is from a number of years ago (my TEN days).  Its possible ISPs have imrpoved or ebven the infrastructure has imrpvoed some what.  We were also dealing mostly with analog modems which have their own issues and problems, but AIR that 400ms high end spike was somethign we even saw over ISDN liones. It was rare but we'd see it.