This is exactly what happened to me. Originally i wanted some clever tree like diagram, but it was way too complicated. Whereas it had to be something so simple people would not need an explanation. That was the real problem.
In the end, i have still effectively a single timeline for undo and redo.
A few points of interest:
Whenever you undo, you’re moving “now” back along the line.
You can move back forward in time so long as you do not make changes.
If you make a change to the world in the “past” it can either:
erase the old future
auto-branch
Currently it erases the old future because i have no UI for branches anyhow. But because not all commands change the world (eg look) You can go “back in time” to examine things, then go back “forward” in time to where you started.
The other cool thing is that save game is just the timeline. This means you can load a save then undo!
Actually, it’s usually somewhat less than the commands would take. The deltas are singletons (X), pairs (X Y), triples (X R Y) and n-tuples in general. Most entries are triples like (X R Y). Elements will be pointers.
Although it’s true that a command (or turn) can wind up making more than one entry to the timeline. For example, your command may trigger some game event. Then there are some commands that make no world changes (like inventory and examine).
How do you deal with randomness. Let’s say the player is in a casino. the exact same commands won’t work in playback if the game played has any randomness.
Well, you could have the state of the PRNG be part of what gets rolled back in an undo. Normally it’s explicitly not for the sake of keeping the appearance of randomness while saving and restoring, but there’s no reason it couldn’t be.
It depends on the story/game. You can’t replay events without a predictable RNG. That’s why most formats take a snapshot of the memory rather than keep a list of player events - a memory snapshot can always be valid regardless of the RNG state, whereas player events could be contingent on the RNG.
One solution could be to have two RNGs, one replayable and the other not. But you’d have to be careful how you use the latter.
Well, it depends on your goals! If you don’t want players to be able to undo and redo over and over to get favorable RNG, then rolling back the PRNG will prevent that.
You can’t replay events without a predictable RNG.
That’s true if you’re replaying them by replaying the game commands, but not if you are replaying the original world changes. But as @draconis points out, there is a case for rewinding the RNG - although i think this is still a bad idea.
Presumably memory snapshot systems like Inform do, in fact, rewind the RNG when you undo. Which would mean in a game where you must roll dice, you can know the outcome by undo and redo. Even so, this is somewhat of a moot point since it’s essentially cheating anyhow.
FWIW, i don’t store the RNG state in the same game. I could do, but i think it works better without. Or if not better, the same difference.
The Z-machine and Glulx specifically and explicitly don’t store the PRNG state in the save-game data (including undo saves). I’m not sure what rationale went into that decision, but it makes sense to me; if you undo, or restore a save, it’s presumably because you want things to be different on your next run rather than exactly the same.
I thought your original point was not to reprocess the commands.
You want to separate the idea of a player command (which goes through the parser and action routines) from a world state delta. Applying (or unapplying) a world state delta doesn’t involve any RNG calls, so you can leave the RNG out of the question entirely.
Good. Thanks for clarifying that. I think that is right. A lot of the time i use the RNG for varying dialogue responses, If you undo or need to rewind, you can get slightly different text the next time through. This helps a lot to alleviate repetition.
Yes indeed. I was referring to the suggested idea of replaying the commands through the system, which i think isn’t a good way to do it.
Earlier there was a question of whether the deltas cost more than storing the text. I thought it probably about the same. However, if most deltas are (X R Y) and these are pointers, then on a 64 bit machine, you’re seeing already 24 bytes per delta and most commands would probably be less than that. So i guess it depends on word-size (in both senses!)
You are correct that applying delta does not involve the RNG whatsoever. The RNG is outside the state and therefore not affected. Looks like this is also true of Inform too, which is good.
Yes, but there’s more. The deltas are the world state! So there is no need to actually store the world as well;
To solve a query such as > what is the player in, i search backwards from “now” until i find (player in X) for X.
And to solve, > what is in the box, i search backwards from “now” to find the set of things (X in box). If, say a coin is taken from the box, i add a negative delta !(coin in box). Deltas can be positive or negative so that negatives can retract changes.
The save game is just the timeline and undo works by moving “now” back a turn.
I just checked this. Essentially all of the undo state in Quixe is the uncompressed memory slice, which is 4332724 bytes for the current release of Counterfeit Monkey.
(The stack is maybe another kilobyte or four, depending on how you assume JS stores objects. Not worth worrying about.)
(Note that Counterfeit Monkey is both unusually large and unusually RAM-intensive for an Inform game, because of all the letter tables. Hadean Lands is 566832 bytes, in comparison.)
So, if we want to handwave a 10-megabyte limit on undo usage, that’s two undo slots. Pretty bad! But then the current Quixe stores ten undo states, which is 43 megabytes, and nobody’s complained.
I still haven’t found a good source on how much JS memory usage is “too much” on a typical phone browser. When I search, all I find is people yelling about how much system memory their browser app is using.
I guess the conclusion is that any compression of the ram slice would be enormously beneficial. But the RLE we do in C terps, trivial as it is, might be too heavy for a phone browser.
Oh wow. Yeah I was expecting at most 1MB per undo state for the biggest games like CM. That 4.3MB is with typed arrays? If we’re not going to do any kind of compression I doubt it would be reasonable to use more than 100MB on a phone. But a lot of memory is also used for everything else an interpreter is doing (including the browser’s side of the DOM.)
Quetzal’s RLE is not great, though the XORing with the initial state is a good idea. I wonder how much of a time drain it would be to do it using 32bit words at a time. Browsers might be able to auto-parallelise it now?
With a library like fflate we can easily and quickly (de)compress data in JS. Again I’m not sure how much it would be worth it.
I’d like to eventually be able to make a sharable link to a snapshot in Parchment. It would have to use the autosave system, but there’s a lot of overlapping concepts with undos. For that to be feasible I’m planning to use both XOR and fflate (as well as a denser binary format for the GlkOte state.)
I wonder what the “cache locality” is like. Maybe if we compare the RAM with the original game file in 1024-byte chunks, and only keep the chunks that differ…?
If you jump over to Twine, SugarCube stores previous moments as compressed state representations using LZString compression on a base64 version. Harlowe, on the other hand, stores deltas, and tries to be even more aggressive in storing some variables only as references to where they were first defined in code (where the value has not changed since initial declaration). Both store their saves in localStorage, which has a 5mb per domain limit on most browsers — I think that’s the limit you are looking for.
I’ll note that SC’s approach can certainly run out of memory on large games where the number of saved moments is large — but large is usually 50+ in this case. (SC 2.37 lowered the default number of saved moments, equivalent to undos, to 40). Harlowe rarely has that problem, but its deltas often get out of sync with actual game state and lead to corrupted saves.
No, Quixe stores UNDO records in regular browser memory, as I said. SAVE records go in localStorage, but they use the Quetzal format Dannii was describing above. That specifies RLE compression (run-length encoding, primitive but fast).