search

derelbenkoenig / my-amethyst-project

game development using the Amethyst game engine in Rust
MIT License
0 stars 1 forks source link

Design/implement rewindable game state model #10

Open derelbenkoenig opened 3 years ago

derelbenkoenig commented 3 years ago

At a high level, the game loop should be viewed as a function taking (current_state, events) and returning new_state.

Previous states should be remembered (maybe like in a linked list, or maybe something more sophisticated) and it should be possible to revert to an old one, and proceed from there by applying a new sequence of "events".

In some circumstances, we should have the ability to "fast forward" the game state by applying multiple "frames" of events without syncing with the frame rate. The concrete example of this is when playing over a network and we receive an event that "invalidates" a frame that we already computed; we should go back to the frame before that and then replay the game loop from then to now to correct the current state.

But this is not the only possible use case; I also want to have the ability to support game mechanics that can also support rewinding time. It also would be interesting if the graph of game states still remembers the state that it was rewound from, so then it might even be possible to revert a revert and forward back to the state we were in. 

                                                "rewind to s1"
                                                  |
+-------+           +-------+         +-------+   |  +-------+
|       |           |       |         |       |   |  |       |
|       |           |       |         |       |   |  |       |
|  s0   +---------->+  s1   +-------->+  s2   +---+->+  s3   |
|       |           |       |         |       |      |       |
|       |           |       |         |       |      |       |
+--+----+           +-------+         +-------+      +---+---+
   ^                                                     |  
   |                                                     |  
   |                                                     |  
   +-----------------------------------------------------+

If an instance of game state has a notion of its own ancestors, s3 now has two different ancestors. It is a "copy" of s1, whose ancestor is s0 in the "usual" way, but also has s2 as an ancestor via the revert operation. How do we represent this?

derelbenkoenig commented 3 years ago

Also, is this in some way incompatible with ECS in general or with Amethyst/Specs specifically? Would I be having to write this from scratch and not be able to make use of what the engine provides? Or is this well-supported?

derelbenkoenig commented 3 years ago

I had forgotten one of the other main benefits of "serializable" game state, which is of course saving and watching replays; in this case, it makes sense that you would want to display "rollbacks" that actually happened as part of the game but not the "rollbacks" that occurred as a part of correcting for network communication. I think systems that use this probably don't even save the states that are rolled back, they simply rewind to the old state and go forward from there, but I will at least sometimes want to hold on to states that got rolled back because it was actually part of the sequence of events, conceptually

fuchsnj commented 3 years ago

Also, is this in some way incompatible with ECS in general or with Amethyst/Specs specifically? Would I be having to write this from scratch and not be able to make use of what the engine provides? Or is this well-supported?

This is one of my biggest questions, but I don't see any obvious reason why it wouldn't be supported. You can just have a global Resource that contains the game history, and each system that could be impacted from the history just needs to check it and make the appropriate updates. The key to high-performance in the ECS structure is that each system can run in parallel, so if possible you would want to reduce the number of global dependencies like this. However

  1. The type of games I think you are targeting don't seem like they would require high parallelism to obtain high performance anyway. I'd image even if the entire game run in a single system, you would be fine.
  2. You could have a simple system at the beginning/end that updates the global history, and everything else is probably read-only, so the bulk of the systems could probably run in parallel anyway
fuchsnj commented 3 years ago

think systems that use this probably don't even save the states that are rolled back, they simply rewind to the old state and go forward from there

I agree with this. Rollbacks could permanently delete that history, since you won't ever need to access that again. A replay of the game would show the exact game state that was simulated

derelbenkoenig commented 3 years ago

think systems that use this probably don't even save the states that are rolled back, they simply rewind to the old state and go forward from there

I agree with this. Rollbacks could permanently delete that history, since you won't ever need to access that again. A replay of the game would show the exact game state that was simulated

But that's something I want to do differently, in some cases. Like there are situations where I do want to keep the history that got rolled back because I could conceivably roll forward to it.

Or maybe put another way: rollbacks that happen due to netcode should actually forget the states that get invalidated; but rewinds that actually happen as part of the game should be remembered. But maybe we can just append those frames to the sequence of frames and forget the linkage...

derelbenkoenig commented 3 years ago
  1. You could have a simple system at the beginning/end that updates the global history, and everything else is probably read-only, so the bulk of the systems could probably run in parallel anyway

beginning/end of what? the "game loop", meaning once per frame?

fuchsnj commented 3 years ago

beginning/end of what? the "game loop", meaning once per frame? Yea, probably beginning/ending of the game loop. I'm really just guessing here. I'd imagine the game loop isn't necessarily bound to once per frame. If it is, we probably need to look into some way to run it an arbitrary number of times per frame

derelbenkoenig commented 3 years ago

oh yeah I guess I'm being imprecise with the word "frame", I meant it to mean an iteration of the state update function, not necessarily what gets rendered

fuchsnj commented 3 years ago

Instead of a single global resource, we could consider adding a component Rewindable? that keeps track of the history for a single entity. That way you can choose exactly which entities are able to do this. (An interesting game mechanic could prevent specific entities from being modified by time, or maybe just static entities can not contain it as a perf improvement). I feel like this follows the ECS model a bit closer. So you basically have a global resource that determines which game state you are in, and when each entity is updating, it can take an appropriate action to switch to the correct state

derelbenkoenig commented 3 years ago

That sounds reasonable. I would assume there are things that can go wrong if you try to revert some entities and not others and that results in a somehow invalid state but that doesn't sound like a deal breaker, just something to watch out for