Undo stacks -- is a hybrid state/command approach typical?

Technical Development Interpreters
1

Weird title, I know. I just finished undo/redo for a little parser IF thing and the approach I ended up with doesn’t feel like a typical undo setup, but I wonder if it’s normal for IF.

Basically it works like this: the internal state is saved (almost) every time the player inputs something, in a ring buffer. So far this could be called a state-based approach; we can use “undo” to reload an old state.

The problem is that there should be some kind of output to let the user know where they are. So in addition to saving the old states, the player’s commands are saved in another ring buffer. To undo an action, we can load the state before the previous state and then issue the command that was used to get from there to the following state (command approach). Same with redo; always load the state prior to the one we want, and re-issue the command. This way the player sees the same output they saw before, and knows where they are in the undo history.

This feels a little strange, but I’m wondering if it’s normal for IF interpreters. It could be extended pretty easily to only save the state every 10 turns or so, with several commands stored in between. Then you’d rewind to the appropriate saved state and execute however many commands you need to get to the desired state, hiding the output from all but the last command. That could allow for pretty large undo stacks without hogging too much memory… is an approach like that normal/expected?

I suppose drawbacks of “extended” version would be taking slightly longer to execute more commands, added complexity, and the fact that undo history size would fluctuate between, say, 90 and 100 (for 10 states with 10 commands in between each).

Another thing I’m wondering is whether it would be crazy to ditch all the yes/no prompts and maintain the undo stack in atypical places, like after restoring, restarting, or quitting the game (assuming “quit” leaves you at some kind of title screen where you can still restore/restart). I feel like this was becoming the norm for UI a while back – just do stuff without double-checking and let the user undo it if they want, like deleting an email in gmail. I’m not sure if it ever really caught on, though.

1 Like
2

Clever approach, I’m tempted to steal it :innocent:. My first thought was that it would fail with non-deterministic actions but it should be fine if you include the RNG in the state.

In my current WIP system I simply have a (relatively wasteful) state stack and when I undo I issue an implicit “look” command. I save some memory by not pushing turns that don’t change the state (examining stuff, most talking, …). I include the undo stack in the save file though.

3

Reissuing commands is possible (with RNG state, as you say) but I wouldn’t want to do it. It feels like a needless point of potential failure.

If you want to save the recent output for the user, save it as text data. You don’t have to worry about RNG state with text. :) That’s what I did for my iOS and Lectrote interpreters which support auto-restore on launch.

1 Like
4

RNG state is only the tip of the iceberg. The replayed command could play sounds, open files, turn transcripting on or off, rearrange windows, etc.

5

That’s something else I was wondering about. Seems like anything that doesn’t change state could be ignored, but so far I’m just ignoring undo, redo, and debug logging.

That’s sort of what I was worried about. Considered just saving the text, but was worried about long monologues broken up with “hit enter” failing, or any other transitional stuff like a scene fading in or a sound effect or something. Replaying the last transition between the two states feels more solid somehow.

I felt like sounds should be played again if they were part of entering that state, no? Same with opening files, I think; it seems reasonable to undo restoring a savegame (in place of a yes/no prompt).

Not sure what transcripting is?

Anything that’s affecting something other than the game state could be problematic, but I’m just leaving it off the undo stack for now. So if you say debug 1 and then say undo, it’ll undo the thing you did before that, and debug will still be on. Same would go for a command that maximizes the window or something like that. I’m not sure if that’s a problem since those commands don’t affect the game state at all, and player may not expect undo to affect stuff like that anyway.

Thinking about it more, any command that affects both game state and internal state would be problematic, but I don’t think anything like that exists in my scenario, and I’m not sure what kind of thing it would be. Stuff that only affects internal state, like changing the color scheme or turning on debug logging, I feel like it’s reasonable to leave out of the history, and stuff that affects game state obviously needs to go in the history.

If commands for internal state really feel like they need to be on undo stack, settings like debug logging, color scheme, window layout and so on could be moved into game state pretty easily, I guess.

6

Yeah. I like your overall idea, and I think the best workaround for commands that could cause problems is just not put them on the stack in the first place.

I feel like I can offer frequently occurring practical examples from Inform-made games during UNDO. The first problem with Inform (that you address) is that the output of the turn undone to is unavailable. All you get after UNDO is the room name. That’s not very helpful for actually working out what the game state is now.

The second problem is that commands that can’t really be undone take up an UNDO slot. Like saving the game. You have to UNDO back through a SAVE (the undoing of which has no effect) then UNDO again to get back to the last action you actually took. It’s not intuitive, it’s not useful, and it drains the game of one of its – apparently – precious UNDOs. I say apparently because at least two scenarios in Cragne Manor reminded me of how dangerous UNDO troubles can be for a game, given that interpreters don’t dispense the same number of UNDOs as each other.

I’ve worked with hacks to reproduce output after Inform UNDOs (I’m working with one now, helped by the narrow circumstances in which it operates) and they’re less than ideal, obviously. They don’t have the universality of a system that would avoid these problems in the first place. However… I concede there could be a halfway house if the game system itself saved the previous output text, ready to automatically dispense it again after UNDO. Inform doesn’t do this out of the box, and it’s not elementary or universally possible to use extensions or other third party solutions to get it going.

-Wade

7

You can’t effectively implement that kind of text-context-saving in Inform code. It has to happen at the interpreter level.

However, if you’re implementing a new system – which is what the original question was about – you can think about this.

8

That doesn’t sound useful at all. I’m skipping save commands also, forgot to mention that. It’s strange, because they must be leaving the undo/redo commands themselves off the undo stack, so you’d think they’d be able to leave saving off too.

I’m considering just comparing the new state to the old state at the end of each turn and only updating the undo stack if it’s different. Hopefully can get away with it pretty easily, as game state is just a flat list of “facts.” Incrementing turn count is the least significant thing I can think of that would affect state, so most things that didn’t take a turn should be left off the history.

I’m still thinking about this. If those “hit enter” pauses are the only issue, I might think about encoding them into the text as some kind of markup. I’m not sure about the other stuff like sounds and visual effects. If it’s a quick transitional sound effect like footsteps on terrain type of current location, I feel like it should be replayed since it’ll just help solidify player’s notion of where they are in undo history. If someone sticks a five minute cutscene at the beginning of a state transition, that’s an issue…

9

Hm, but actually a lot of things that I’d expect to be undoable can be set to not take a turn. At least if you’re me as an author :slight_smile: For instance, a lot of actions that produce an inner thought of response from the PC, but are also set to not take a turn. If the thought is transient enough I don’t want NPCs or the world to keep going, I set it to not take a time. But the player would expect to be able to undo it, because it produced good text. Just an example.

-Wade

10

Good point. I need to think about that a bit, because it seems to me if there was some conversation you want to rewind, and the state didn’t change during the conversation the first time, whatever triggered it must be going to trigger it again at some point, since there couldn’t have been any “don’t say this again” flag set.

I’d expect the only places where state really doesn’t change at all to be things like bumping into walls or typing ‘look’ again, or meta stuff like saving the game, but I’m not sure.

What’s critical with this setup is if the state does change, it definitely needs to be recorded (where you can get away with skipping it if you’re not going back an extra step and replaying the command).

11

Versificator just remembers the command text along with the previous state, and tells you what command you undid (“undid ‘take necklace’”). On RESTORE, it reprints the room description. I think that does the job.

12

I like that idea. I tried it earlier actually, tested it by walking around a bit, messing with stuff and hitting undo a few times here and there. I felt like for actions like picking stuff up, it was clear enough, but for walking around a lot of (undid n) and (undid w) didn’t leave me with a clear idea of where I was.

I’ve added it back in now though, at the end of the played-back turn, and it’s a nice addition.

Do you mean REDO? The nice thing about storing the command is REDO can amount to just re-issuing the command (assuming a deterministic setup).

I issue a LOOK command on RESTORE and at the start of a new game (after any introductory text). Those are the only times I issue a hard-wired command on behalf of the player, I think. Actually it bothers me a little that it’s hard-wired; if you throw out the “core rules” then LOOK doesn’t mean anything anymore. Will probably make that configurable somehow eventually.

13

Just following up on this in case anyone else tries it.

It ended up working out pretty well. The one snag was sometimes the game would be in a state where it’s not listening for “undo,” for example:

> drop

  What do you want to drop?

> undo

  You don't have that.

That would effectively lock you out from the rest of the undo history. To get around it, I let game code signal that the next undo state should replace the state at the top of the stack, and the next command should be concatenated to the command at the top of the stack. So whenever it’s asking for clarification like that, you end up with all of those interactions as one “compound” command, like drop/foo (I’m using slash for command separator), which is then undone/redone as a unit.

Also, when pushing a new state onto the stack, I’m checking if it’s the same as the state that’s already there and ignoring it in that case. That neatly leaves all those “look” and “x foo” commands out of the undo history, without any special handling (I’ve decided those shouldn’t pass a turn by default – if they did, turn count would increase, so state would be different and they’d go on the stack).

14

I don’t like undo, but testers advised me to implement undo functionality in XVAN.

Here’s some thoughts I would appreciate feedback on.

The easiest way would be to do a “save game” after each (non-meta) command and keep the save data in memory. This would also be the most expensive way, considering memory usage.

I want to be able to cap the memory used by the undo implementation and I see 2 ways that complement each other to do that:

  1. limit the amount of undo data stored each turn to the bare minimum, i.e. only store information on things that changed.

  2. cap the amount of memory that can be used for storing undo data for multiple turns. When memory gets full, overwrite the oldest turns.

Ad 1: all changes to the game world are done by a limited set of functions at the lowest level in the interpreter source code:

  • move objects to other objects/locations;

  • set and clear flags;

  • assign new values to attributes (properties);

  • start and stop timers.

These functions will be expanded to write an undo-record to the undo-stack. The undo-record will contain information on the type of action, the items involved and the old value to restore. At the end of each turn, the interpreter will then write an End Of Undo (EOU) record to indicate which undo records belong to the turn and where the next undo starts.

Ad 2: The undo-stack will be a circular stack, so it will roll over when it gets full. Upon roll over detection, all undo records until the next EOU will be erased first to prevent that we leave part of a turn on the stack. In the unlikely case that one turn has so many records that it will overwrite itself, we will throw an error and empty the undo stack.

Now, when the player issues an undo command, the interpreter will read undo records back from the current position on the undo stack and roll back the changes until it encounters an EOU record.

With this mechanism the number of turns that can be undone varies. It depends on the amount of undo data (undo records) used during the specific part of the game. With many ‘small’ turns you can go back further than with many ‘large’turns.

15

(Sorry for the late response!) No, I mean restoring from a saved game. With the visuals of Versificator it looks extra weird to see the introductory text at the same time as the noun/verb buttons for a spot halfway through the game.

16

This was, in effect, the Counterfeit Monkey situation – the undo state was so large that the undo mechanism limited itself to zero turns.

The lesson is that users would rather err on the side of having at least one undo turn available. If that takes extra memory in a large game, well, that’s a large game that takes extra memory.

17

Also, that the “unlikely case” is going to happen. Plan for it now.

18

How about having the interpreter make an estimate for the undo stack size, based on the game size?

Let’s say we have a game with 50 locations and 200 objects. If we want to ensure we always have one undo available, the most expensive command would likely involve all objects and locations and change all of them. Let’s assume this command would change 3 properties for each object and location and also all objects will get a new owner.

So, 250x3 + 200x1 = 950 changes. Each undo record is currently 4 int32s, so that gives an undo stack size of 3800 int32s. That does not seem like an issue for current systems.

19

@Marnix: I wonder if you could use some drop-in delta encoding scheme here – diff current savegame with the previous one and store the patch on the undo stack, then undo/redo by applying the patch. If you don’t have room to store a whole patch, bump earliest patches off until you do.

I bet XVAN is fast enough to plow through a bunch of player commands, though. Have you considered just saving one game state, a fixed (user-configurable) number of turns back from “live” state, and then rewind to there and silently replay all the player commands up to the target state? The memory would be capped in the sense that you’d just be storing a fixed number of player commands plus 2 game states (backup state could even live on disk in a pinch).

Thinking about it more, I feel like ideally the author should have control over undo stack size (as a number of undo steps available), with a sensible default. Player could have a cheat to override that, and game should try to make it happen.

If you have the undo stack automatically sized based on available memory, I guess you’d often have the entire history on there, which I’m not sure you’d need as a player or want as an author. But you can probably make a guess at how much you need to allocate for a given number of undo steps, and expand it as needed.

1 Like