Adding a "Sands of Time" feature to an emulator

Discuss emulation of the Nintendo Entertainment System and Famicom.

Moderator: Moderators

Jagasian
Posts: 417
Joined: Wed Feb 09, 2005 9:31 am

Adding a "Sands of Time" feature to an emulator

Post by Jagasian » Thu Jun 02, 2005 10:18 am

I just wanted to put an idea out here, which I previously mentioned in another thread, for an emulator feature that is inspired by the "Prince of Persia: Sands of Time" game. For those that haven't played it, the "sands of time" feature lets the gamer rewind via the press of a button, the past 15 seconds of gameplay. This really smooths out the frustrating moments in such a platformer, and its simplistic interface is really easy to make good use of. So it got me thinking about unifying and generalizing current emulator features: save states and movies into a higher-level construct called a "snapshot".

The sands of time feature is implemented by using what is effectively an advancing or "sliding" continuous interval of save states. However, since storing each individual state of a computation is too costly, a list of bidirectional save state deltas could be used to implement the same thing. This delta-list could be implemented as a list of triples: ( key, old_val, new_val ), where key is the address, register, or whatever part of the state you are saying has changed, old_val is the previous save state value for that aforementioned piece of state, and new_val is the next save state value for that same piece of state. Each delta-list tells how to go forward from state A to B and backward from state B to A. So even if an emulation core only understands save states, to save memory or disk space, delta-lists can be used. Commercial databases that support undoable/redoable transaction logging use a similar method.

Instead of gamers dealing with movies or save states, they use a higher-level construct, a snapshot, which unifies them both. Lets define a snapshot as the current save state paired with, N delta-lists denoting the previous N save states. For example, a traditional movie/demo would be a snapshot without a limit on the number of previous save states, i.e., N = infinity, and a traditional save state would be a snapshot with N = 0.

Whenever a game is being played, a current snapshot is automatically and constantly being recorded, as a sliding window of time in which the previous N states occur. Instead of the gamer taking save states in order to save their current point in a game (e.g. right before fighting a boss, right before a fork in the road, etc), they save the current snapshot, using the typical Nesticle style save state slots to store multiple snapshots. Since each snapshot would consist of a K second window of states taken when the gamer feels is an important moment in the game, the gamer will no longer have to worry about taking a snapshot too late, and yet like traditional save states, it gives them the flexibility to explore multiple gameplay paths. Hell, it would even be useful for re-reading dialog that an NPC won't repeat, just rewind and non-interactively play it, then fast-forward back to the current state. On the other hand, when the gamer wants to record a movie, they simply temporarily set N to infinity, play the game, and when the they want to stop recording the movie, they save the current snapshot, and return N to its default value.

So the gamer would have the traditional action buttons: D-pad, SELECT, START, A, B, as well as state buttons: play-pause, rewind, fast-forward, and record. While traversing through recorded states, things are non-interactive, like a pre-recorded movie, until the gamer presses an action button, at which point the game becomes interactive and the current sliding snapshot is again constantly recorded. play-pause toggles between playing and pausing the progression of states and rewind plays the progression of states in reverse and pressing rewind multiple times could speed up this progression. The semantics of fast-foward and record are slightly non-standard. While traversing through recorded states, fast-foward has VCR-like semantics, but if fast-foward is pressed when not traversing recorded states, i.e., when in the current state, it causes the game to be speed throttled so that fast-fowarding through recorded states into and past the last recorded state is a seemless and smooth sequence of fastly transitioning states. On the other hand, pressing "record" brings up a list of slots in which to store the current snapshot.

If you use a SNES controller, the L could be rewind, R could be fast-forward, Y could be play-pause, and X could be record. The action buttons would map to the rest. So its not like there would be too many buttons for the gamer, as everything maps easily onto a SNES controller in an intuitive manner. Hence the anybody could quickly and easily make use of the sands of time in their favorite NES game.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Thu Jun 02, 2005 10:24 am

I imagine it would be plenty fast to take normal save states every minute or so and then internally fast-forward to the point 15 seconds before present when necessary.

How does the Prince of Persia game implement it?

Jagasian
Posts: 417
Joined: Wed Feb 09, 2005 9:31 am

Post by Jagasian » Thu Jun 02, 2005 10:49 am

blargg wrote:I imagine it would be plenty fast to take normal save states every minute or so and then internally fast-forward to the point 15 seconds before present when necessary.

How does the Prince of Persia game implement it?
I am not sure how Prince of Persia implements it, but it is a modern game, so you can't just look at a binary and figure out what is going on, as the binary is so large. The rewinding in the sands of time is very smooth, so they must be recording a state change undo list of some kind. Since it is tailored to that specific game, they most likely use a highly specialized notion of state, which keeps things at a low computational cost.

With regards to the NES, the best way would be to modify the core so that it spits out a delta-list every time the state changes, but a more hacky method that doesn't require changing the core would take a save state once every second, compare it to the last save state and create a delta-list from that. This would allow it to implement rewinding, though it wouldn't be as smooth. However, even worse, it would prevent smooth play of a snapshot in the forward direction, as things would be 1 frame per second. So it would no longer be a perfect unification and generalization of save states and movies.

You could always try to take a save state 60 times a second and calculate delta-lists between each state to keep memory consumption low at the cost of using more CPU time, but that might affect emulation speed. Finally, you could also not bother with calculating delta-lists and just store states at 60 states per second, but that would limit the size of the sliding time window that could be stored in memory, which would limit its use as a replacement for movies. It might make it possible to have a 10 second sliding window at 60FPS in both foward and backward playback.

Again, the most efficient method would be to have a core that spit out a delta-list each time the state changed, but if an emulator wasn't designed with this in mind, it might require significant changes to existing code.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Thu Jun 02, 2005 5:45 pm

[...] but a more hacky method that doesn't require changing the core would take a save state once every second, compare it to the last save state and create a delta-list from that. This would allow it to implement rewinding, though it wouldn't be as smooth. However, even worse, it would prevent smooth play of a snapshot in the forward direction, as things would be 1 frame per second. So it would no longer be a perfect unification and generalization of save states and movies.

Take a snapshot every second and record user input in real-time, with timestamps. To seek to frame n, restore the snapshot before it then emulate up to frame n. The worst case is a snapshot restore and 59 frames of emulation. To play back smoothly from any point, seek to frame n then emulate normally except supply the recorded user input (as I figure movies on most emulators work). Unless I'm missing something...

User avatar
Disch
Posts: 1849
Joined: Wed Nov 10, 2004 6:47 pm

Post by Disch » Thu Jun 02, 2005 6:27 pm

This method, while pretty quick, would absolutly KILL RAM usage and/or suck up HD space.

A savestate in my emu is about 14k (rounded down -- add an additional 8k if the game uses CHR-RAM) -- though I could've cut it to ~12k. Assuming a savestate every second -- that works out so that a mere 5 mins of gameplay will need over 3.5 MB for the savestates alone (6.4 MB if CHR-RAM) -- not counting the keypress recordings between savestates (though those shouldn't tally up to too much).

Plus what about MMC5 games with all sorts of RAM? You're talking 32k or 64k of extra RAM for every savestate (* 60 * 5 + 3.5MB = 22 MB for 5 minutes of gameplay)

A feature like this would have to be capped after a short while -- rewinding the entire game would be out of the question -- it just simply isn't practical... at least not using this method. I suppose an option to have the user say how much RAM they want to make available to this feature would be a good way to go. Maybe even having the user specify how much time between savestates.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Thu Jun 02, 2005 9:52 pm

Memory usage could be reduced by reducing the number of older snapshots, i.e. 60 for the last minute, 60 for the last hour, etc. Another way to reduce them would be similar to the way a virtual memory system marks modified ("dirty") pages. Break RAM into pages (maybe 256 bytes each) and keep track of those that were modified. Though this would make it more complex to throw out old snapshots due to interdependencies. This would be a simpler intermediate to full fine-grained logging.

How quickly can an emulator run a movie if video and sound rendering are turned off (but still emulated in whatever way is necessary for full accuracy)? I'm guessing around 50-100x on a modern machine.

Not that I'm claiming this simplistic approach is feasible in actuality...

An emulator with fine-grained logging would be excellent for development and debugging, since you could single-step backwards. Reminds me of a message about adding a checkpoint feature to Linux.

Jagasian
Posts: 417
Joined: Wed Feb 09, 2005 9:31 am

Post by Jagasian » Fri Jun 03, 2005 11:20 am

blargg wrote:Take a snapshot every second and record user input in real-time, with timestamps. To seek to frame n, restore the snapshot before it then emulate up to frame n. The worst case is a snapshot restore and 59 frames of emulation. To play back smoothly from any point, seek to frame n then emulate normally except supply the recorded user input (as I figure movies on most emulators work). Unless I'm missing something...
I didn't understand it at first, but now I do. blargg's method seems to be the best, assuming the emulator core can save state and record a movie, but you can't have the core spit out the equivalent of delta-lists. Just take a snapshot of the state at a fixed interval, say every 2 seconds, and when rewinding to the previous state, transparently playback the movie from the last snapshot up until the previous state, and then display the previous state. This process of constantly recomputing the movie to get the previous state happens for each state during rewinding. This method is simple and lets you make a trade off between the following:

1. memory
2. CPU
3. maximum rewind speed

A faster max rewind speed requires either more memory consumption or a faster CPU speed. If you want to decrease memory consumption, you take snapshots less frequently, and therefore have to recreate more states in a fixed amount of time. Similarly, if you want to put less stress on the CPU, you need to take snapshots more frequently, so that you don't need to recreate as many states in order to rewind to the previous state.

Ignoring blargg's varied snapshot rate idea for a second, lets calculate the maximum rewind speed when using a naive implementation of blargg's method, and to make things easy, lets assume that an NES normally runs at 60 states per second. Lets say "Speed" stands for the maximum speed the emulator can run, given in states per second, and lets say "Interval" denotes the number of seconds between snapshots. Then "Rewind" the maximum speed at which the player can rewind, is:

Rewind = Speed / ( 3600 * Interval )

If on a modern computer, the NES emulator can run at, say 60 times the normal speed, that is Speed = 60 * 60 = 3600 states per second, then keeping the snapshot interval at 2 per second, the max rewind speed is:

Rewind
= Speed / ( 3600 * Interval )
= 3600 / ( 3600 * 2 )
= 0.5

That is, the player would be able to rewind at up to 0.5x the normal speed. If you have played Prince of Persia, you know that the sands of time run at something like half speed, which is good because the player wants to go back to a very specific moment and doesn't want to over shoot. Also, since the sands of time is something like a 10 second window into the past, going at 0.5x might be acceptable, as it only takes 20 seconds to fully rewind.

So what would the memory consumption be for a 10 second window into the past? Assuming that the memory consumption due to storing the movie data is negligible, this is easy to calculate. It would be 5 states worth of memory, and going by Disch's numbers, we have an upper bound on a save state size of, say, 100k. That would be 500k or half a meg of memory.

These can easily be compressed and uncompressed too. All that needs to be stored on disk is the snapshot at the beginning of the window and the movie from that point until the end of the window. Similarly, as blargg already pointed out, for large windows, older snapshots could be kept with less frequency, as they could be recreated when needed. But this does complicate things allot, and according to my numbers above, this isn't needed for a "sands of time" feature. It would be needed for a generalization of movies, because in that case the time window has to be really large. Though the generalization would be cool. Users would only have one file type, which is basically a movie that can be rewound in real time. The end of the movie is effectively the save state.

Anyway, do these numbers sound accurate? It would be great to have an emulator author willing to modify their emulation core to do it right, i.e. with delta-lists, but otherwise blargg's method seems to make a "sands of time" feature possible, as the time window is short, rewinding is at half speed, and most emulators on modern hardware can run at orders of magnitude faster than a real NES.

P.S.
Here is a good link of a review of the Prince of Persia: Sands of Time game, which makes mention of the feature that I am referring to:
http://www.zengamer.com/review.php?revid=113

It really is a simple, basic idea, that almost seems obvious once you play the game because it fits in with the gameplay so well and isn't as jarring as saving and reloading. Even a 10 second window, at a fluid 0.5x rewind speed would be, in my opinion, a very popular new emulator feature. Emulator authors already augment NES game's graphics by providing various pixel filters, so why not augment the gameplay with another optional feature?

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Fri Jun 03, 2005 3:21 pm

This is getting interesting. I didn't realize one of the features was real-time backwards playback. I thought it just jumped back ten seconds or so, a single seek.

If the backwards play is only graphics, you could use two different history schemes: regular snapshots of full emulator state, and snapshots every frame of graphics state or possibly raw images of each frame. Once you switch to forward playback with sound, seek using emulator state as described previously.

An odd hybrid of this comes to mind too. Take regular snapshots of emulator state (say every second). To play the previous second backwards, start the emulator at the snapshot from one second ago, generate all 60 graphic frames and keep each one in memory, then play them backwards. *While* these are playing backwards, restore the snapshot two seconds ago and generate those 60 frames. This way CPU use is spread out evenly and memory is only needed for 60 total graphic frames. You could even always keep the last 60 frames around to avoid having to generate them all at once when switching to backwards mode. If the save states are handled in a way that doesn't require lots of memory copying, this would use no more CPU time than normal forwards emulation!

If I have some free time I might try this last idea in my experimental emulator, since it isn't very complex to implement.

User avatar
teaguecl
Posts: 210
Joined: Thu Oct 21, 2004 4:02 pm
Location: San Diego

Post by teaguecl » Fri Jun 03, 2005 6:23 pm

This is a very cool feature. If only we could implement it in hardware! I suppose it wouldn't be impossible if you had something like the FPGA NES, but I don't think you can do better than savegames on a unmodifed NES.
One question though. Why is this helpful? I've played Sands of Time, and the feature is really cool, especially with the sound effects and "dreamlike" look to the rewind. But as far as the NES goes, how is this better than having multiple savegame slots to revert to where you were? It seems like a huge investment in complexity and resources for a marginal improvement in your ability to get a re-do.

User avatar
Disch
Posts: 1849
Joined: Wed Nov 10, 2004 6:47 pm

Post by Disch » Fri Jun 03, 2005 7:58 pm

I think the general idea is it will make speed run movies easier to make. Although there are already cheat utils available to get the keystokes down to just about the exact right frame -- so I don't really see how it will be a significant improvement in that area either. Perhaps it will make such movies easier... *shrug*

Jagasian
Posts: 417
Joined: Wed Feb 09, 2005 9:31 am

Post by Jagasian » Sat Jun 04, 2005 6:01 am

The feature is interesting from a user-interface point of view. Typically people use a circular queue of quick save state slots for the same purpose, i.e. to redo little mistakes such as missing a jump or accidentally getting shot, but no matter how you bind things, it is far less user-friendly to make sure you are hitting the quick save key at the right moments, not too fast but not too slow either. When you mess up, you also have to manually select the best quick save to load from the circular queue of save slots as sometimes the most recent save is not the best.

With the sands of time feature this is all simplified, you just have a rewind key, which when held down does a real-time smooth rewind up to 10 seconds into the past. Letting go plays the prerecorded stuff either: up until the present or until the user presses an action key.

You could still have both save slots and the real-time rewind because different save slots would be used for more coarse grained saving (before a fight with a boss, before a quest, at the start of a level, etc), and the real-time rewind supersedes the need for manual quick saving, which is used to quickly go back and fix little mistakes.

So again, the options:
1. Quick saving with a circular queue: less user-friendly
2. sands of time: more user-friendly

I also don't think that blargg's simple method complicates things too much. Most of the core stuff needed is already there in emulators: save states and movies. Another application would be speed run movies, as well as debugging a game, but I mainly see it as a popular feature for casual emulator gamers.

tepples
Posts: 21755
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » Sat Jun 04, 2005 9:20 am

But is it patented? If so, you may not implement it until roughly 20 years after publication of Prince of Persia: Sands of Time.

Jagasian
Posts: 417
Joined: Wed Feb 09, 2005 9:31 am

Post by Jagasian » Sat Jun 04, 2005 9:35 pm

tepples wrote:But is it patented? If so, you may not implement it until roughly 20 years after publication of Prince of Persia: Sands of Time.
Well, it is just real-time rewinding combined with rerecording (a feature recently added to emulators for speed demo creators). I don't know how they could patent that, but dumber things have happened.

tepples
Posts: 21755
Joined: Sun Sep 19, 2004 11:12 pm
Location: NE Indiana, USA (NTSC)
Contact:

Post by tepples » Sun Jun 05, 2005 8:24 am

Jagasian wrote:Well, it is just real-time rewinding combined with rerecording (a feature recently added to emulators for speed demo creators). I don't know how they could patent that, but dumber things have happened.
If A is a substantial piece of prior art, and B is another substantial piece of prior art, then A+B is patentable, more likely than not.

User avatar
blargg
Posts: 3715
Joined: Mon Sep 27, 2004 8:33 am
Location: Central Texas, USA
Contact:

Post by blargg » Sun Jun 05, 2005 6:34 pm

I just implemented the scheme I posted about a few days ago and it's awesome. I can play a game, fall off, hit backwards and watch it immediately reverse, then start playing just before I fall off. It indeed doesn't use much more CPU time than normal forwards emulation. Snapshots are currently taken every second. It was not much code at all.

There was a fine point I encountered while implementing the backwards play function, regarding the frame image buffer. Consider the order of frame generation and playback for a few seconds of backwards play, using a single buffer of 60 frame images. -1.0 means frame 0 from one second ago. The fine point is how to store the frames in the buffer. What I came up with is back-and-forth scheme:

Code: Select all

restore state at -1.0

	generate -1.0 to -1.59 into buffer [0] to buffer [59]

restore state at -2.0

	display frame -1.59 from buffer [59]
	generate frame -2.0 to buffer [59]
	
	display frame -1.58 from buffer [58]
	generate frame -2.1 to buffer [58]
	
	...
	
	display frame -1.0 from buffer [0]
	generate frame -2.59 to buffer [0]

restore state at -3.0

	display frame -2.59 from buffer [0]
	generate frame -3.0 to buffer [0]
	
	display frame -2.58 from buffer [1]
	generate frame -3.1 to buffer [1]
	
	...
	
	display frame -2.0 from buffer [59]
	generate frame -3.59 to buffer [59]

Post Reply