I was playing a puzzle game and started wondering how they implemented their undo feature. The game only has five possible moves, and only when the player does a move does the game state change, but the game state can be quite complicated.
The standard undo implementation would be to keep track of a stack of all past game states. However, since the game state can get quite complicated, this can end up taking up a lot of memory.
Assuming the game state changes deterministically, a more memory efficient implementation would be to only keep track of all performed moves, because they require way less memory. However, an undo operation would then require recalculating all past moves which would take up a lot of processing power instead.
I was wondering if there is any literature on a data structure that tries to optimize both. Intuitively, I expect it to be possible to implement a data structure that only requires storing a logarithmic number of game states while also requiring a logarithmic number of move calculations for every undo operation. Of course this still requires storing all past moves, but the assumption is that this is significantly less memory than storing all past game states.
To be clear, I have some ideas myself of how this could be implemented. I am mostly interested in whether there already exists some literature on the topic, because I was unable to find any.
For some context, the game that made me bring this into question is called baba is you. I suspect they simply store a log of changes to the game state rather than the entire game states, because this usually, though not always, requires significantly less memory. However, it still made me wonder about this. Moreover, the game state does not always change deterministically in baba is you, but this could be fixed by storing some rng seed together with the performed moves.
