I'm working on a game with a replay system, so I need the game logic to be deterministic. A part of this is collision detection and I'm having a bit of a conceptual problem here. (I'm programming in Python but I think my question is more general than that.)
I need collisions to be solved in a deterministic unbiased order. For example, it would be unfair if collisions would always be solved first for the red team, because e.g. they would always collide with (and thus pick up) ammo first. I can't imagine I'm the first person experiencing this problem.
The way the engine works is somewhat as follows:
Until no objects colliding:
- Find overlapping objects and separate them
- Add the object pair to a "collided" set (so no duplicates).
- Sort the "collided" set based on some property.
- Iterate through "collided" set and tell each object pair that they collided with the other object.
Is there a way to sort the set for this final iteration while keeping it fair?
Things that won't work:
- Memory location (python's default for sorting objects) because this is nondeterministic.
- Internal object ID's, because these ID's are always lower for the "red team", as they are added first.
- X/Y coordinates, don't give a complete sorting order, because objects can have identical positions, additionally, this is biased because the "red team" spawns at X=0.