Non-determinism in BroadPhase when restoring from serialized snapshot

[raysplaceinspace]

I am making a multiplayer game using rollback netcode and Rapier, and I found that there was some non-deterministic behaviour. After snapshotting the entire world state between different clients and comparing that it was bit-for-bit identical, I noticed that there were often differences in the BroadPhaseBvh tree. It appears this would cause further divergences as the game continues and be the explanation for desynchronization in my multiplayer games.

Upon looking into it further, it appears to be because BvhWorkspace is not serialized, but the BvhWorkspace::rebuild_frame_index value is actually important and changes which optimization strategy gets chosen during each frame. My game is using rollback netcode, which means it is quite often restoring serialized snapshots and therefore losing all state in BvhWorkspace. This means different clients execute different optimization strategies of the BVH at different times, which results in different BVHs on different machines.

In rapier: src/geometry/broad_phase_bvh.rs - see the BvhWorkspace is skipped during serialization:

#[cfg_attr(feature = "serde-serialize", serde(skip))]  
workspace: BvhWorkspace,

In parry: src/partitioning/bvh/bvh_optimize.rs - see the BvhWorkspace::rebuild_frame_index variable is significant data that determines which optimization gets performed:

workspace.rebuild_frame_index = workspace.rebuild_frame_index.overflowing_add(1).0;  
let config = self.optimization_config(workspace.rebuild_frame_index);

Disabling BroadPhase optimization fixes the issue. I have verified this by serializing the world state and checking it is bit-for-bit identical on all machines:

BroadPhaseBvh::with_optimization_strategy(BvhOptimizationStrategy::None)

However, it seems to me that I wouldn't want to have a production system that does not do any BVH optimization, so this does not appear to be a workable solution.

BroadPhaseBvh contains a field called BroadPhaseBvh::frame_index which does get serialized. It seems like this should be used when calling Bvh::optimization_config instead of BvhWorkspace::rebuild_frame_index in order to be deterministic.

Unfortunately from the looks of it, there is also a second field, BvhWorkspace::rebuild_start_index which also appears to be significant to the execution which also does not get serialized as it is part of BvhWorkspace which does not get serialized. So it will be a bit more complicated than just replacing with BroadPhaseBvh::frame_index.

This would affect anyone who is using serialization/deserialization of the physics state. This might not just be people who are doing rollback netcode, but even anyone who is sending the state to the client and doing some client-side prediction.

Rapier version: 0.30.1