Why not storing snapshots of the entire engine's state?

[slawo]

Hi, I just had a quick look at your library, Maybe I missed something, but would it be possible to rollback the entire simulation, change a few things it and replay it again?

I'm not sure I got the idea, there are new changes in you history code, but why don't you create a snapshot of the entire physics state for each frame with a rollover system (reusing previous states when the max frames have been stored)? Would it be a bad system? It could allow a few optimisations (copied from frame to frame). You could do this and save a lot of room by storing only the history of dynamic and kinematic objects (movable by hand, not tested against statics and other kinematics) and avoid storing the story of pure static objects.

Does this make sense?

[ashoulson]

Hey, thanks for taking a look!

Originally I had the system doing this kind of rollback. It saved the state of each shape at each frame in a big buffer, so you could rollback the actual world to a previous state. However, for Volatile's application (networked physics), this is overkill. Volatile is designed to be friendly towards two features: client-side prediction, and lag compensation. I'm using Valve's definitions here for this: https://developer.valvesoftware.com/wiki/Source_Multiplayer_Networking

Client-side Prediction works by sending user input from the client to the server and assuming the server will accept it as-is. The per-frame process looks like this:

Step 1: Collect user input i.

Step 2: Store i in a local queue q and also send it to the server.

Step 3: Roll back your object to the last received state from the server.

Step 4: Apply each input stored in q, in order.

Step 3 is why Volatile doesn't have things like warm-starting or cached manifolds, because your controller object is always being snapped around arbitrarily and there's no guarantee of frame coherence at each timestep. We don't need to keep an object history here because we just use whatever object position/orientation we last got from the server.

Lag compensation works on the server side by performing queries and tests in the past. When input comes in from a client saying that they fired a gun, the server "rolls back" the world to when the client shot the gun (which will be some time in the past depending on latency), and checks to see if the weapon would have hit if fired then.

Here's the thing though, you don't actually need to roll back the object to do this. To save memory and time, I do things a little differently. I don't store the absolute position/orientation for each shape for each frame. This would be very costly for polygons. Instead I pre-compute the position/orientation of each shape relative to the parent body's transform (I call this "local space" in the code). This only ever needs to be done once as long as shapes don't move relative to their body. Then whenever I do a raycast or point query, I first transform the ray/point into the body's local frame of reference, and do the test in that space.

The upside to this is that now I only have to store each body's position and orientation each frame, rather than data about the shapes themselves. Given a ray, I can transform it into the local body space for any past history entry and do the raycast in local space (take a look at Body.RayCast). The ray transformation is much faster than rolling back the complete object with all the polygon vertices, and requires less memory storage.

Now, if you really want, you could use these stored body histories to actually rollback all the shapes (just take the shape's position/orientation and recompute local->world for either a circle's origin or a polygon's vertices/axes). It wouldn't be too difficult to do, but it isn't necessary for Volatile's core purpose so I haven't included it to avoid feature bloat.

For more info, Body.State (the private internal struct) in Body.cs shows exactly what I store for each frame for each dynamic object. It comes out to around 36B per frame, or just a little over 2KB for 60 frames, which is pretty cheap. It's also independent of how complex the body is, so even if you have 15 shapes attached to the body, it's still just 2KB of storage for 60 frames of history.

On the finer points in your question, here are some additional notes:

• Static objects already don't do history rollback. See Body.StartHistory, which checks IsStatic.
• Volatile doesn't explicitly support Kinematic objects, but it would be easy to add. Kinematic objects are just dynamic objects that don't call Integrate(). You'd also just need to add checks to ignore certain kinds of collisions (kinematic/static, kinematic/kinematic).

[slawo]

It makes sense.

Is this library widely usable, if not how far is it from being usable do you think?

I also noticed your other project RailgunNet. It looks like a Good idea to implement the snapshot diff based system from quake.

[ashoulson]

I consider Volatile to be a fairly mature library. It's slimmer than something like Box2D with fewer features, but is also much simpler for someone to extend on their own and serves a purpose that other similar libraries don't. I don't expect to make major changes to the core library, though if needed I could see myself making some extensions as a separate package.

The main feature that's missing is a solution for broadphase spatial decomposition (like a dynamic AABB tree or a quadtree) that supports historical queries the same way bodies do. Unfortunately C# makes it difficult to optimize things at the heap/cache level without fighting the GC, so while I've attempted to implement this already in two different ways, the performance benchmarks weren't satisfactory. I have an idea for a third attempt, but it hasn't been a priority for me to do. Right now I just use an n^2 resolution loop with optimized AABB tests (see World.BroadPhase) and the performance is still good enough for my applications.

And yes, getting Volatile and Railgun to work together is the plan! Railgun is still very far from being mature though, maybe only at 20-25% of the way towards a first feature-complete build.

[qpaolo]

Hi, It's nice to see a network-oriented physics engine implementation.

Step 3: Roll back your object to the last received state from the server.

I want to have an instance of VoltWorld to run on the server, calculating the next state based on the clients' inputs and broadcast a snapshot or diff for clients to correct their world instance.

I have some questions:

• Is there any method that help create that kind of snapshot (returns a byte array or return a deep copy that can be serialized by serializer like ZeroFormatter).
• Or do I have to query the list of bodies and create an array of all bodies' HistoryRecord?
• If it's the case, how can I do it with VolatilePhysics?
• and how to rehydrate the snapshot too? Is there a body pool to reuse the body instance and avoid GC?

[ashoulson]

Hi there!

The "trick" that Volatile uses is that it doesn't actually save complete snapshots of an object's history. For historical records, it's far more efficient to transform the ray into the past local space than to fully move the object back into its historical position and do a raycast in world space. You get the same result for less work and memory storage. The HistoryRecord stores only an AABB (for broadphase), and the position/facing of the object at that tick. To perform a historical ray/circle cast Volatile transforms the world space ray into the old local space defined by that history record and does the geometry checking using the local space geometry of the object (see how I use bodyVertices and bodyAxes in VoltPolygon, for example).

Because of this, Volatile doesn't store complete world state snapshots, only a local space history for each individual body. You can use a HistoryRecord yourself to move an object back to its previous state but that's a pretty costly operation for polygons as you'll need to transform all the vertices and axes. All you really need to sync in most cases is the body root position and orientation though, which is stored information. If you want to create snapshots you can, as you say, query the bodies in a list and serialize them that way with a serializer (and do delta compression, etc.). I do it a little differently in RailgunNet, my high level networking library. When integrating with Railgun, I don't use the HistoryRecord for this snapshot information, hence why it isn't fully exposed. It should be safe for you to expose for your own purposes though as long as you don't edit the data in there while running.

As for pooling, pretty much everything in Volatile is pooled, including bodies and shapes. You can see bodyPool, circlePool, polygonPool, and so on in VoltWorld to track how that works. I've been making a number of changes in the internaldev branch that are far more up to date, but that branch isn't as polished or documented. Pooling works a little better in that branch.

[qpaolo]

Thanks for your response. I misunderstood your HistoryRecord, I get it now. Maybe it's not what I need.

Volatile is largely stateless

How largely? What's stateful? Cache for broad phase or anything? After a sync (reposition every body), will there be any difference between the next world tick and a normal world tick?

If bodies can be dynamically created and destroyed, a sync may involve body creation and destruction too. If I take a naive approach, destroy all bodies and create them again according to the snapshot, will there be any problem? Is the pooling good enough to avoid frame drop?

[ashoulson]

By "Volatile is largely stateless", I mean the following things:

1) Volatile does not "warm-start" bodies or make any other temporal coherence assumptions about bodies or their dynamics. The only mutable information from the previous frame used to compute dynamics in the current frame are the body's position/angle and linear/angular velocity. Everything else is cleared between frames (see ClearForces(), called in Integrate(), called in Update() on a VoltBody). This, of course, sacrifices convergence quality for external malleability. If you create a body and assign it a position and velocity, Volatile wouldn't notice a difference between that and a body that existed in the previous frame. Of course, that newly-created body won't have a history log and will be ineligible for past-state queries/casts. I handle this case better in the internaldev branch than in the master, but I haven't done a pull yet.

2) Volatile does not currently have a broadphase spatial decomposition structure. This is a nontrivial problem made complicated due to the history-logging nature of Volatile. I experimented with both a memory-block "blitting" quadtree structure in a ring buffer and a persistent dynamic tree BVH structure, but due to some quirks with C# memory management I couldn't achieve satisfactory performance gains with either. You can find these in some of the library's older commits and branches, but I've since removed them from the head for code clarity. Currently the broadphase step for a cast/query in Volatile is an O(n) AABB comparison (or O(n^2) for collision testing). Not ideal, but it works enough in practice up to at least a couple hundred bodies. The nice thing at least is that there is no such structure to have to maintain or update when adding, removing, or manipulating bodies.

I haven't tested it myself, but you should be able to create/destroy bodies with a given position/velocity each tick without Volatile caring or noticing. If that's how you want to have clients replicate then you should be functionally okay. You won't get the benefit of history checking, but that's only used by the server in the use case this feature is designed for. I'm not sure I would recommend it though optimization-wise. For the latest pooling overview you can look at the internaldev branch and review things like VoltBody.Reset(), VoltPool, and VoltWorld.FreeShape(). It's cheap, but not free.

[qpaolo]

Thank you for your time.

If you create a body and assign it a position and velocity, Volatile wouldn't notice a difference between that and a body that existed in the previous frame.

Exactly what I need :smile: The term largely stateless is quite misleading in this case though. If we consider the state (position/angle and linear/angular velocity) as input, the calculation for the next state is predictable when running on a same machine right?

And that's enough for my networking need too, maybe I won't need to use the history-logging feature at all.

• I can store snapshots of server instance and rollback+replay to check.
• Or I can run the server simulation behind. So the inputs from clients (sent with frame number) will always be in the future, snapshots from server will always be in the past. Inputs with too long delay will be discarded.
• I can use a mixture of both, maybe adding a small built-in delay on inputs to reduce the need of rollback+replay on both server and clients.

[ashoulson]

If we consider the state (position/angle and linear/angular velocity) as input, the calculation for the next state is predictable when running on a same machine right?

It should be, but I don't take anything for granted when it comes to floating point calculations. Wherever possible I would avoid creating/destroying lots of bodies and shapes each frame. Even with pooling, it's quite a waste.

If you haven't already, I'd recommend looking at something like Glenn Fiedler's tutorials to see a little more about the various timelines you're dealing with when doing present-time and past-time calculations to reconcile latency. I've had decent success emulating that approach using Volatile and Railgun in tandem.

Good luck!