Telling Bullet That Something Happened In The Past

Would you like to see a Partial-Rewind-And-Replay system in bullet?

Yes and I would use it.
3
75%
Yes but I wouldn't use it.
0
No votes
No there is a better approach.
1
25%
 
Total votes: 4

User avatar
KKlouzal
Posts: 44
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Telling Bullet That Something Happened In The Past

Post by KKlouzal »

Is it possible to tell bullet that something has happened in the past so it can take this information and adjust internal interpolation to show this change in the present?
There would never be a need to go back in time more than 1-5 seconds, 5 being a very rare occasion, more realistically between 1.5 and 2.5 seconds is where most of the change would occur.

The ability to query an objects position, rotation, and velocities at a specific time in the past would be needed as well, but this can easily be accomplished.

The reason behind all of this would be to facilitate easier synchronization of two physics simulations, specifically in a networked environment.

A server constantly running the simulation in real-time would send position, rotation, and velocity updates to client simulations at periodic intervals. These updates would arrive at the client 'in the past' from the client simulation's perspective due to network latency, thus the need to query the updated objects values in the past to see if they are different arises, if they are different the need to change these values in the past is also necessary. During the next simulation step bullet would take these past-changes into account and update the object accordingly.

Is this ability present in bullet or would it need to be emulated somehow? If emulation is needed could someone point me in the correct direction to getting started on this "rewind and replay" feature?

If you are unfamiliar with "rewind and replay" this article goes into great detail about the theory behind implementation for someone who may be going about creating their own physics library. http://gafferongames.com/game-physics/n ... d-physics/
Last edited by KKlouzal on Tue Aug 19, 2014 8:27 am, edited 1 time in total.
STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Telling Bullet That Something Happened In The Past

Post by STTrife »

I'm also interested in learning more about this. I'm pretty sure Bullet does not have a build in method to rewind the simulation.
I don't know if you could in theory rewind by simulating the reverse of the current simulation, but I think that even if that is possible, I think it would be very costly to rewind 5 seconds then, because in total you'd have to simulate 10 seconds (5 back and 5 forward), and with 60 fps that is 600 frames.

Perhaps a better, but more memory intense solution would be to save the last 600 states in a double ended queue. Then the rewind would be a matter of switching back X frames, which would be 'instantaneously'. Then of course you have to replay the last X frames again, which is costly. maybe you could (temporary) decrease the resolution to for example 10 fps to do this faster.
I think that (depending on how complex your scene is) it would be unrealistic to assume that bullet could simulate 300 frames fast enough so you don't notice the lag.
User avatar
KKlouzal
Posts: 44
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Re: Telling Bullet That Something Happened In The Past

Post by KKlouzal »

Rewinding the entire simulation and playing it back would just not be feasible, however, if each object in the simulation were to keep track of it's state for an arbitrary amount of time (a setting which could be changed for individual objects or the entire physics environment) as well as which objects are near that object during the state (again a distance setting that could be changed for individual objects or the entire physics environment) then that would allow for the ability to only rewind parts of the physics and play them back. Of course this is just a generalized approach and may not cover all possible scenarios. I believe this is very doable and would open the door to much broader uses for Bullet.
STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Telling Bullet That Something Happened In The Past

Post by STTrife »

That's easier said than done, if you only rewind parts of the simulation, how do you know if non-rewinded parts weren't supposed to collide with the part(s) you rewind?
If you have simulation islands, sure I can imagine you only have to rewind the island the object with lag is on, if you are sure that no objects crosses from or to other islands.

But within an island, I don't see another option besides to rewind all objects. Perhaps some optimizations can be made if you know more about other objects. If objects have a maximum speed then you might calculate for objects whether or not there was even a possibility to intersect with the one you are rewinding, but then again.. there is also the snowball effect. Perhaps there was no possible direct collision between object A and the rewind-object, but maybe your rewind object was actually hitting object B 2 seconds ago, and then object B hit object A 1 second ago. Thus even though it was not possible for object A to have hit the rewind object in the rewind-time, it was still affected during that time, and if you didn't rewind object A , then both object A AND B will be in the wrong position, because you have missed the collision between those two, putting them both on different paths! So my conclusion is that you HAVE to rewind the complete state (of an island).

If you know a way around that, or my reasoning is false, I'd love to hear it!
User avatar
KKlouzal
Posts: 44
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Re: Telling Bullet That Something Happened In The Past

Post by KKlouzal »

As long as the basis for this entire feature was to deal with the issue of lag compensation and synchronizing multiple physics environments then yes I believe it could be vastly optimized. Either each individual object or the entire simulation would need the following variables.

MTimeDilation - The max amount of time you can go 'into the past' on a particular object and change its position/rotation/velocities.
MCompDist - The maximum amount of distance an object can be compensated (moved) during any 'past update'
MAffectorRadius - The maximum radius any object should worry about doing collision checks on objects around it

These three variables combined would allow you to optimize away most of the useless collision checks on a per object basis when doing these 'past updates' but, like I said in my previous post, this isn't perfect and doesn't provide a use case for every scenario, there may be a more elegant way to achieve the same end results, and there may be a few more things to look at other than these three.

You also have to remember, this doesn't have to be picture perfect (or maybe it does) because in the event that two objects don't collide when they should, whichever simulation you've delegated to be the authority should already be sending full position/rotation/velocity updates at regular intervals to catch these types of mishaps in synchronization.
STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Telling Bullet That Something Happened In The Past

Post by STTrife »

if you send regular full updates on the entire state from the authority then I agree you could try local updates in the past, but then 5 seconds seem like a very very long time to 'locally' rewind. I think it can be easily underestimated how much it can go out of sync if you fail to simulate a single collisions that happened :) Imagine you missed one collision at 0.5 seconds into the rewind, and on of the bodies should have reversed direction from 10 m/s in the positive x to 9 m/s in the negative x direction. Then the object would be more than 85 meters out of sync after the rewind... and how much collisions would that object have missed in the 85meters that it traveled in the wrong direction? But then again, who would expect a game or networked simulation to work well with a lag of 5000 ms... I don't think even the old quake games that were designed to be played using a dial up worked correct with that much lag.

Anyway, in bullet I suppose you would have to freeze all bodies (disable simulation on them), except the local-rewind object and anything near it. Then reset the local-rewind objects X frames, and then simulate the X frames that you rewound, then unfreeze the whole simulation. Seems possible to me, Bullet has methods to disable bodies and such, but for the rest I don't know about any built-in functionality that is designed for your goal. But since it's open source it should be possible. I'm not not even very experienced in working with existing frameworks myself but for Bullet I was able to understand the basic functionality as far as I've looked into it, so if you have any experience with understanding and working in open source frameworks you should be fine. Good luck :)
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Telling Bullet That Something Happened In The Past

Post by Basroil »

Are you sure you want to "rewind" at all? Why not just record local player input for a set amount of time, keep a copy of the last server state, and the transmitted server delta (changed objects)? The last server state + delta is the new server state, and from there you just step your simulation as many times as you need to to catch it back up to the current time using the recorded input. It is far from optimized, but if you start there you can completely avoid reverse simulations. Assuming only objects near the delta change, you can merge objects based on that mask (changed objects simulated again while everything else just copies state information from your last local simulation) like STTrife stated. No sense in copying state information a ridiculous number of times just to throw it all away
User avatar
KKlouzal
Posts: 44
Joined: Thu Mar 06, 2014 5:56 am
Location: USA - Arizona

Re: Telling Bullet That Something Happened In The Past

Post by KKlouzal »

Of course you could do it this way but like you mentioned the steps you described are far from optimized. If you were to implement it that way and fully optimize it the entire approach is less optimized than the one I'm using/suggesting if you look at it from a "bandwidth is the bottleneck" standpoint (which it almost always is).

I'm taking all user input (as it happens) and sending it off to the server. The server takes this data and uses it to update it's own simulation. The input data is also relayed back out to all other clients (as soon as the server receives it) who then in turn use it to update their own simulations, effectively "predicting" the server's state. I call this the "ASAP Paradigm" since bandwidth and latency are the number one bottlenecks.

You cannot be constantly sending full/partial server states as the size of this data would increase as more and more physics objects are created. Relaying inputs is the most efficient use of bandwidth possible.

Now due to the whole bullet not being 100% deterministic thing especially when running the same simulation on different machines/architectures means clients will slowly 'drift' away from each other and the server requiring you to periodically send full updates but you can do this conservatively based on how accurate you need to keep everything.

I'll reiterate the issue with relaying inputs as a way to sync the physics. let T be time and T0 is when the server application was started. If ClientA sends an input change at T1000 and their current ping is 100 the server will receive this update at T1050. The server then immediately relays this information out to ClientB who also has a ping of 150. ClientB has now received input at T1125 for input that occurred at T1000. During this gap in time ClientB may have sent out input that directly effects what ClientA's input effects causing a discrepancy. Thus the need to 'rewind and replay' past actions as their received due to the fact that every client essentially sees everything that happens on the server 'in the past'.

So while your argument is valid Basroli, it's not correct. Bandwidth is super expensive and memory is extremely cheap. Not to mention now that Bullet can run multi-threaded/on the GPU processing is no longer an issue either. :)
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Telling Bullet That Something Happened In The Past

Post by Basroil »

KKlouzal wrote:So while your argument is valid Basroli, it's not correct. Bandwidth is super expensive and memory is extremely cheap. Not to mention now that Bullet can run multi-threaded/on the GPU processing is no longer an issue either. :)
Lets say you have a server running 60fps simulation, with 4 players, roundtrip times of about 30Hz, 15Hz, 10Hz, 9Hz (a lot of games deal with lower, especially those not in the US). If you send everything back exactly when it happens, you need to recalculate the server state every time you get data. But since data flow depends on a lot of things lets just estimate it as being one bunch of data each send/receive cycle having everything at one time with zero delay (just timed). This means you need to recalculate at least one frame (plus simulate current, so calculate two frames) for the first player, recalculate 3 frames for the second, 5 for third and 4th (4th will need a 6th frame every once in a while).

Lets call the simulation frames 0-6, and all players have data from frame 0. You calculate frame 1, and then get data from player 1 (delayed). In order to have the newest state for player 1, you need to calculate frames 1 and 2, so you've ended up calculating frame 1 twice. You then calculate frame 3, and then get data from players 1 and 2. Because player 2 has old data, you need to recalculate frames 1-3 based on both player 1 and 2's data. Calculation counts for each fame is (3,2,3,1), so 4 "current server states" and 5 discarded states. Add players 3-4, and your server data gets up to (5,4,5,3,5,2,5), 6 "current states" and 22 discarded ones. Another way to look at it though, the longest recalculated step chain is as long as the number of steps you need to simulate the longest round trip time between the server and your slowest client at that frame. That result doesn't matter if the clients send all the data at once with zero lag or they send it one frame at a time with lag, since all frames after have to be recalculated (though sending 1 at a time means you recalculate the maximum each and every frame). Sure bandwidth is expensive, but so is calculation time, especially when you end up with several clients that overlap perfectly and have high latency. If your simulation takes 1ms it could be fine, but what if you have advanced physics and it takes 5ms? Just three frames of constant recalculation would mean you shoot above 1 second per second of simulation (and goodbye realtime physics). Since you're sending back the same info to everybody, you don't have to worry just about the server, but each and every client that is connected. While what you want can work, it doesn't tend to work well without some restrictions. You'll see that usually games that do that sort of simulation have huge object inertias, the clients just can't move the object in a highly non-linear way in a few frames, and you can linearize motion well enough that reasonable latencies don't start falling apart (teleporting objects, death behind walls, player rewinding, etc, though high latency can still cause issues).

This seems to need a different forum though, since it'll be getting into things entirely outside bullet. To summarize though, bullet cannot rewind by itself (negative timesteps not possible), but you can copy entire world states with some overall simulation performance cost. Though Bullet3 does have GPU parallel solving, it does reduce the performance of the GPU, and does not support all the features of the single threaded solvers for Bullet2 line of code.
STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Telling Bullet That Something Happened In The Past

Post by STTrife »

Is there a general 'best practice' way of doing networked physics (what do they use in modern games)? or do game engines all use different methods of networked physics?
c6burns
Posts: 149
Joined: Fri May 24, 2013 6:08 am

Re: Telling Bullet That Something Happened In The Past

Post by c6burns »

I've always felt the Source engine's multiplayer implementation was quite solid. It's server authoritative, and revolves around shifting rendering back in time a small amount so that objects can be interpolated between known positions: https://developer.valvesoftware.com/wik ... Networking

To be honest, I've only done one implementation based on this method, so I can't speak to whether it's a best practice or even what other methods are out there. It worked extremely well for me though. RakNet (which is now free and open source) comes with an Ogre popcorn example that uses this method as well. Personally, an implementation that rewinds physics does not interest me in the slightest, but I'll read the post-mortem of anyone who has finished one :lol:
Basroil
Posts: 463
Joined: Fri Nov 30, 2012 4:50 am

Re: Telling Bullet That Something Happened In The Past

Post by Basroil »

STTrife wrote:Is there a general 'best practice' way of doing networked physics (what do they use in modern games)? or do game engines all use different methods of networked physics?
If there was a best practice we wouldn't see games like BF4 :wink:
STTrife
Posts: 109
Joined: Tue May 01, 2012 10:42 am

Re: Telling Bullet That Something Happened In The Past

Post by STTrife »

Meaming BF4 did a poor job? ;) (didn't play it...)
c6burns
Posts: 149
Joined: Fri May 24, 2013 6:08 am

Re: Telling Bullet That Something Happened In The Past

Post by c6burns »

I didn't play it, but I remember it being somewhat of a catastrophe according to those who did:
http://www.ign.com/articles/2014/03/04/ ... ine-issues
Some issues DICE is fixing or investigating include:
Rubber banding: Players are randomly flung around the map and yanked back to a spot they occupied before.
Kill camera delay: Sometimes the kill cam begins before you receive the last bit of damage, making it look like you died too early.
Not doing damage to your opponent: Happens even when bullets clearly impact the enemy.
Instant death upon sprinting: Catapulting at high speed and colliding with an object, causing death.

DICE also included a list of the issues it has fixed:
Disappearing crosshairs: PC players sometimes lost their crosshairs and hit markers when their enemies deployed gadgets.
Hit impact sounds: Because the sounds did not line up with the number of bullets fired, it felt like death came too quickly.
Kill card shows zero health: The game sometimes showed your killer as having zero health, yet remaining alive.
Broken collision: Some objects couldn't be shot past, even after they were destroyed.
Granyte
Posts: 77
Joined: Tue Dec 27, 2011 11:51 am

Re: Telling Bullet That Something Happened In The Past

Post by Granyte »

There is a best practice only any one that is related from close of far to EA will not follow it

i don't think it's a good idea to use this for network but it could be usefull for some effects in-game
Post Reply