1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ I haven't thought it through yet, because I was hoping to just find a reference on this. But you can do square root complexity relatively easily by storing the last $\sqrt{n}$ states and every state multiple of $\sqrt{n}$. Whenever you've undone all past $\sqrt{n}$ states you can recalculate the last $\sqrt{n}$ states before that. I think if you do something more clever with powers of two, logarithmic complexity should be possible. $\endgroup$ Aug 31, 2023 at 12:09
  • $\begingroup$ Instead of waiting until you've undone all past $\sqrt{n}$ states, you can recalculate the $\sqrt{n}$ states before that gradually as you're performing undo operations, kind of in an amortized way. This should allow square root memory complexity with only constant processing power per undo operation. This will be way more complicated if you try something like this with powers of two to reach logarithmic memory, but I think it should be possible. $\endgroup$ Aug 31, 2023 at 12:57

1 Answer 1

1
$\begingroup$

Yes. A relevant technical term is 'persistent data structure'. (See also .) There are many techniques for building persistent versions of standard data structures (trees, lists, arrays, etc.), so you can represent your state as a standard data structure, then replace all of those data structures with persistent versions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.