Determinism

[Uriopass]

Determinism is a requirement for multiplayer as the state is too big to be synchronized live. We use lockstep networking which means only sending the initial state and subsequent inputs. It is also very useful to be able to save replays to help with bug reports as it is easier to see what the player did to get there.

However this comes with a lot of hurdles as the game needs to be deterministic even through ser/deserialization cycles as the game is sent over the network and serialized mid-replay.

Usually, this means that iteration order must be stable wherever used, ids must be stable if they are stored and used elsewhere, and in general any hidden state should be saved if it affects the game state in any way.

Note that determinism must only be there for the game state (the egregoria crate), the UI can be as random as it wants.

With that said, here's a list of recommendations and tracking issues about this:

• Use BTreeMap/BTreeSets instead of HashMap/HashSet for deterministic iteration order even through ser/de (which isn't necessarily the case of indexmap::IndexMaps) for a modest runtime cost.
• https://github.com/orlp/slotmap/issues/104 SlotMaps don't keep freelists, a fork will be made
• https://github.com/Ralith/hecs/issues/332 hecs doesn't serialize entity state, so either a fork will be made or we will move out of hecs entirely, Egregoria does not really use the component/system ergonomics that much as entities don't share a lot of state
• Floating point determinism is a tough issue but Factorio devs say it has never been an issue for them once they had their own trigonometric functions.
• Parallelism is a tough one to get right, systems must be run sequentially and iteration order must be absolutely unimportant. That's why ParCommandBuffer sorts the operations to do to make sure they are done in order at the end of the system.
• Dependencies for game logic must be kept at a minimum to be able to inspect and make sure they don't incur non-determinism.
• Functional tests that run replays and check for determinism and ser/de consistency are very useful tools to check for regressions about this
• Save/loading itself can be a bit complicated, Factorio has a good document about this + around Lua modding saving https://gist.github.com/Rseding91/a309cf0a30782a2e96ef081c39326f42
• Use hashing instead of RNG to avoid order-dependencies

[Uriopass]

After a big rewrite I have removed hecs in favor of a simple "entity lists" that has been working well for me for the map.

This allows me to get a better grip on determinism and serialization. However it makes iterations a bit more expensive (less cache friendly).

[Uriopass]

A fork of slotmap with serialized freelist has been made although it is unsound if the serialized data cannot be trusted. (fixed since then)