Jump to content

Proposal: Implementing deterministic lockstep for physics and animations


santarcade
 Share

Recommended Posts

Hello,
the game I'm currently working on will be multi-player and needs to show replays. Instead of snapshotting complete game states, I would like to have a deterministic engine, so supplying the same initial state and the same inputs should result in same state evolutions over time.
To achieve this, I need physics and animations to be frame-rate independent and to be in sync with each other.

The idea is quantize the state execution time, by updating the game state at a fixed frequency, keeping an accumulator so to carry over exceeding time to the next frame update (the code would be similar to the one featured by CannonJS in its step function. The amount of internalStep can be capped to a maximum value, to avoid accumulating delay into the so-called spiral of death.

I would be patching BABYLON.Scene.render() code, which is where animations and physics steps are triggered, by adding a conditional change if BABYLON.Engine is constructed with deterministicLockstep flag set to true, defaulting to false to keep compatibility with today code.
I would add even a couple of observable events like onBeforeInternalStepObservable and onAfterInternalStepObservable so to be able to plug game logic code to execute before and after each internal discrete step.

So, particularly to @Deltakosh would a pull request matching the criteria above be accepted?

Thank you in advance,
santarcade

Link to comment
Share on other sites

Sounds like a great addition.  I have setup my game so it is self testing.  A page loads a scene and interactions occur with physics running - then I make assertions on the end result to ensure that the game is working as expected.  Different scenes run to completion in succession like a test fixture - using a BDD style testing (given - when - then).  I think your proposal would be useful as it would be an even stronger guarantee.  ie: even though it always passes on my machine I wonder about slower/faster machines.

Link to comment
Share on other sites

Ok, I made a PR for this.
To explain the change briefly, this new feature can be enabled with:

this.engine = new BABYLON.Engine(theCanvas, true, {
  deterministicLockstep: true,
  lockstepMaxSteps: 4
});

This way, the scene will render quantizing physics and animation steps by discrete chunks of the timeStep amount, as set in the physics engine. For example:

let physEngine = new BABYLON.CannonJSPlugin(false);
newScene.enablePhysics(this.gravity, physEngine);
physEngine.setTimeStep(1/60);

With the code above, the engine will run discrete steps at 60Hz (0.01666667s) and, in case of a late frame render time, it will try to calculate a maximum of 4 steps (lockstepMaxSteps) to recover eventual accumulated delay, before rendering the frame.
Note that when explicitly creating the CannonJSPlugin, it is important to pass false as _useDeltaForWorldStep parameter in constructor, to disable CannonJS internal accumulator.

To keep all the game logic in sync with the steps, I've added a couple of callbacks that can be registered on the scene:

newScene.onBeforeStepObservable.add(function(theScene){
  console.log("Performing game logic, BEFORE animations and physics for stepId: "+theScene.getStepId());
});

newScene.onAfterStepObservable.add(function(theScene){
  console.log("Performing game logic, AFTER animations and physics for stepId: "+theScene.getStepId());
});

As soon as there will be a playground available with this version, I will make a sample showing all the code above.

A room for possible improvement that requires some overview is in my change in scene.render().
For internalSteps (non-rendered steps calculated when performing multiple steps inside a single frame), I had to add this call:

                if((internalSteps>1) && (this._currentInternalStep != internalSteps-1)) {
                    // Q: can this be optimized by putting some code in the afterStep callback?
                    // I had to put this code here, otherwise mesh attached to bones of another mesh skeleton,
                    // would return incorrect positions for internal stepIds (non-rendered steps)
                    this._evaluateActiveMeshes();
                }

Otherwise I experimented divergences (game state desynchronization) on some internalSteps on the absolutePositions of meshes attached to other meshes bones.
As if proper skeleton calculation are performed only when some code internal to this function is executed.
@Deltakosh: is the above call reasonable to be kept there or should we define a best practice of functions to call in the before/after step, to keep skeleton transforms in sync?

Best,
santarcade

Link to comment
Share on other sites

Ok, I should have fixed the things pointed out by @Deltakosh.

Now the engine is properly deterministic, same scene with same inputs evolves in the same manner over different browsers and platform. I tested on MacOS, Linux, Windows, iOS, Android on different platforms and browsers, and I only got minor differences caused by floating point rounding (past the 11th decimal position).
A truncation of floating point values at a good decimal position should be enough to guarantee a good screening of this problem: in my case this will be directly workaround by periodical re-sync of game state.

Now I see another very good enhancement subject for BabylonJS.
At the moment, the game loop looks something like this:

for(discreteTicksToDo in Math.floor(elapsedFrameTime / fixedUpdateTime)) {
  updatePhysics();
  updateAnimations();
  updateGameLogic();
}

// will render the actual game world after last discrete game tick
render();

This is very nice since it makes sure the world is coherent and deterministic, offering the same experience at any given tick, eg: even showing a replay on a different machine.
But it comes with a drawback!
Consider a game running at 60 FPS, with a fixed update loop at 60FPS: when frames are rendered at 60 FPS steadily, the game runs very smoothly.
If, instead, a frame arrives late, say between step 100 and step 101 instead of 0.0167s it takes 50% more, the game will result shattering.
The reason of that is: the step being rendered will be 101, as if there was no delay, while to smooth things out it should render a frame in the middle between step 101 and step 102.

A way to solve this is keeping a buffer of the last two game states and what is being rendered is an interpolation of these two. So while the real tick being calculated is step 102, what is shown on screen is an interpolation of steps 100 and 101, according to how late the last frame was.

The big enhancement can be evicted by the following screen-shot:

profiler.thumb.png.9cf18e77eeaeee04add57c3dc1013842.png

The more internalSteps  needed between frames, the higher the risk is to degrade the next frame time, while for half of frame time the CPU is idle.
Long story short: according to me it would be VERY nice to split the code responsible of rendering with the one responsible of calculating the game state.

In my dream world, we should have two threads:

  1. the render loop triggered by requestAnimationFrame, responsible of doing a dumb interpolation of the last two game state snapshots
  2. the game tick loop, put inside a web worker, responsible of keeping the game state buffer up to date.

Does this ring true to you? Do you see a technical issue with web workers to achieve this?

Best,
santarcade

PS.
I realized this could be moved on a new thread. I will if there is enough traction.

Link to comment
Share on other sites

Just a tiny comment and I'll merge your change

regarding your dream, I don't see it in bjs for now because:

- Webworkers shared buffers are not available everywhere (and this is te only performant way to communicate between threads)

- Even if we rely on shared buffers they are just float32 buffers so it 's gonna be tough to simply use them

 

Link to comment
Share on other sites

  • 2 months later...

Hey @santarcade ,

One note, probably you should mention that this addition is available only in the 3.1 alpha preview. People may be thinking that it is already available in the 3.0 stable version.
Also, I saw that you set a default timestep value when one is not ommited through a physic engine. Probably in cases when we don't have a physic engine setup we might still want to change the value. It would make sense in my opinion to have a function say engine.setTimeStep(60.0 / 1000.0) .

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Loading...
 Share

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...