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.
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?
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.
[...] 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...
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.
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.
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?
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.
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.
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*
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.
But is it patented? If so, you may not implement it until roughly 20 years after publication of Prince of Persia: Sands of Time.
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.
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.
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:
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]
Can you interrupt rewinding to play the "past" forward noninteractively and interactively (rerecord)? I would love to have a setup with a SNES or PSX L button as rewind, the R button as forward speed throttle. Can you post binaries or source. Linux binaries or source if ya got them.
Can you interrupt rewinding to play the "past" forward noninteractively and interactively (rerecord)?
Not currently, but it's just a matter of implementing it. I'll probably post again if I make it really sleek and flexible, as confirmation that it is all workable in practice. After proving that the basic idea works, I'm confident there are no serious limitations.
Can you post binaries or source. Linux binaries or source if ya got them.
Unfortunately it won't be usable to anyone else. It's written for Classic Mac OS based on an old set of libraries I've written over the years. The source is quite messy (very experimental) and it only runs a handful of older games (MMC1 basically). Sorry :(
When I clean it up I'll post the core backwards/forwards code as a guide for someone else implementing it in their emulator. This should be a breeze to implement in a well-written emulator (including playing audio backwards, heh).
I was finally able to play through Castlevania without dying or losing the holy water :) "Oops, just got the knife. Reverse a second. Now don't get it!" etc.
blargg, what's the impact on emulation speed? You said low CPU % usage but... the own context implies extra work.
Sound backwards? I was doubtful that it would be easy enough to do that. Smooth 60FPS backwards video and sound would be a trip to see and hear in game. If you can post a concise writeup of how to implement it, I could really see it becoming the new hot emulator feature... possibly even for SNES emulators.
To keep things simple, it is probably best to not have non-interactive forward playback. Its only use would be to correct for over-rewinding. If things rewound at half-speed slow-motion, over-rewinding wouldn't be a problem. So, I think the best interface for the final polished implementation would just be one button, that when held rewinds at half-speed and when released, interrupts the rewind, returning gameplay to normal forward interactive mode. Hence there are only two modes of gameplay...
1. forward: full speed, interactive, interruptable on SoT-button press
2. rewind: half speed, noninteractive, interruptable on SoT-button release
...where as the previous ideas involved a third gameplay mode to correct to correct for over-rewinding. So yeah, scratch the idea about that third, forward mode of noninteractive, interruptable on action button press. It makes things too complicated from a user-interface point of view.
I definitely plan on writing a tutorial on implementing this in an emulator, since I'd like to see this feature adopted. Your focus on user-interface is good, because a refined minimal user-interface can make a big difference in its use. That's something useful I can do with my emulator.
Playing audio backwards might be a little tricky regarding seamless transition between each separately-emulated second (or whatever the snapshot interval is). I haven't implemented backwards audio yet. If I do I'll try putting a short fade at the transitions, which shouldn't be too audible since backwards audio will sound quite odd anyway.
I'll try again at summarizing it.
Code:
Emulator is running normally. When joypad read occurs, add byte to history buffer. Every second, take snapshot of emulator state and current position in history buffer.
1 2 3 4 5 snapshots
----------------------------- joypad history
Emulator switches to reverse mode. For simplicity, assume this occurs just before the next snapshot.
1 2 3 4 5 rewind initiated
------------------------------<
Restore snapshot 5 and replay joypad input from history buffer, generating 60 frames into an image buffer without displaying anything on screen:
5 snapshots
----------------- joypad history
0 1 2 3 ... 58 59 image buffer
Now you have 60 completely rendered graphic frames of the last second.
Restore snapshot 4 and set joypad replay to corresponding position in history buffer. Display frame 59 on screen then emulate frame 0 into the image buffer:
4 5 snapshots
----------------------------------- joypad history
0 1 2 3 ... 58 59 0 1 2 3 ... 58 59 image buffer
^ ^
emulated frame 0 displayed frame 59
Then display frame 58 and emulate next frame (1):
4 5 snapshots
----------------------------------- joypad history
0 1 2 3 ... 58 59 0 1 2 3 ... 58 59 image buffer
^ ^
emulated frame 1 displayed frame 58
Eventually frame 0 from the next snapshot will be displayed and frame 59 from the previous snapshot will have been emulated, just in time to be displayed next:
4 5 snapshots
----------------------------------- joypad history
0 1 2 3 ... 58 59 0 1 2 3 ... 58 59 image buffer
^ ^
emulated frame 59 displayed frame 0
At this point the process repeats. Restore snapshot 3 and joypad history position, display frame 59, emulate frame 0.
The image buffer only needs to hold 60 images. In the above example, the emulated frame 0 is placed where the just-displayed frame 59 was, frame 1 where 58 was, etc. Then for the next snapshot, the image buffer is run through in the opposite direction.
As you can see, for each frame displayed, only one frame is being emulated, and state is only being restored every 60 frames, so CPU usage is similar to that of normal emulation. I just profiled it on my 400 MHz G3 PowerMac and normal emulation uses 39% CPU, backwards 43% CPU. Double-speed uses 45% for forward, 53% for backwards. Running everything (including PPU emulation and rendering) but not copying it to the video display, I get 8% CPU for forwards, 11% for backwards.
If sound were emulated backwards, it would be totally cool to have it slow down to a rumbling crawl before changing directions, like in The Matrix. That would actually be useful so you could get ready to continue playing.
Couldn't you apply the same logic to reverse audio? As long as you're rendering 60 frames, couldn't you just render 44100 or whatever samples and play them in reverse? Wouldn't be very slow at all, wouldn't use much memory, and would perform the desired effect.
Yep, audio is easy; I just implemented it and it works well. Along with each frame image you also store whatever samples were generated during emulation of that frame. Then when displaying that frame later, play the samples in reverse. Fade in the first sample buffer just after restoring the state, and fade out the last frame just before restoring the previous second's state.
I also implemented the Matrix-like slowdown and speed up when changing directions. It's totally cool and really helps when picking up play while it's rewinding. I am able to pick up jumps in Mario after rewinding just a fraction of a second before landing on a platform. It is totally seamless changing directions, and you can change back and forth at any time, replaying the same moves over and over. I can't make a video but here's the audio which is kind of fun:
smb_matrix.mp3
blargg wrote:
Yep, audio is easy; I just implemented it and it works well. Along with each frame image you also store whatever samples were generated during emulation of that frame. Then when displaying that frame later, play the samples in reverse. Fade in the first sample buffer just after restoring the state, and fade out the last frame just before restoring the previous second's state.
I also implemented the Matrix-like slowdown and speed up when changing directions. It's totally cool and really helps when picking up play while it's rewinding. I am able to pick up jumps in Mario after rewinding just a fraction of a second before landing on a platform. It is totally seamless changing directions, and you can change back and forth at any time, replaying the same moves over and over. I can't make a video but here's the audio which is kind of fun:
smb_matrix.mp3blargg you are awesome! That mp3 sells it. Real-time rewind isn't just useful gameplay-wise, it is freakin cool looking and cool sounding
PoP:SoT does the "Matrix" slow down during transition, but they don't do reverse audio, which after listening to the mp3 is a must! This is so fricking cool! You said you can't get video, but if you could find a way to get some video of it, with audio, that alone would sell the feature to emulation authors
Prince of Persia doesn't do reverse audio because its implementation is most likely very high-level. Doing rewind at a lower-level apparently gives more results for "free".
I forgot to ask. Is there a noticable delay for the first 60 frames to queue up? Once that buffer is created, I realize that it would be basically as fast as doing normal forward emulation, but while it is buffering in the very beginning, on slower computers, there would be a very small delay, of at most 1 second, right? If 60 frames are going to be in memory at a time during rewind, why not just keep the 60 most recent frames in memory during forward play, to eliminate possible buffering delay?
Also, what does memory consumption look like? CPU overhead looks very small, of course it would be worse for the ultra-accurate emulators such as Nintendulator, but I think you have proven that CPU overhead is not a worry.
...well, I am going to listen to that mp3 one more time, as the reverse audio addition has really got me pumped
I forgot to ask. Is there a noticable delay for the first 60 frames to queue up? Once that buffer is created, I realize that it would be basically as fast as doing normal forward emulation, but while it is buffering in the very beginning, on slower computers, there would be a very small delay, of at most 1 second, right?
It would have to be less, since at worst it's doing one second of emulation without having to play the audio or display the graphics (no pixel doubling, slower video memory, etc.)
If I disable the Matrix-style slowdown when changing directions, I notice a very slight pause when going into reverse, on the order of 1/8 second or so. With the Matrix-style slowdown enabled, it's slowed down to near zero when changing directions, thus the pause isn't noticeable.
If 60 frames are going to be in memory at a time during rewind, why not just keep the 60 most recent frames in memory during forward play, to eliminate possible buffering delay?
Right, that's the general idea I have (but haven't worked out completely). Consider going into reverse in the middle of a second. The 60-frame buffer would have frames 0 to 29 from the current second, then 30 to 59 from the previous second. Display frame 29, restore snapshot from previous second and generate frame 0 from the previous second in its place ... display frame 0 from the current second, generate frame 29 from the previous second. At this point the buffer has the complete previous second, in the order 29, 28 ... 1, 0, 30, 31 ... 59. Now restore the snapshot from two seconds ago and go from there normally.
This is more complex because the image buffer isn't arranged neatly. This could be solved by adding a simple image allocation layer that knows where particular frames are stored (like a file system on a disk). It gets more complex when changing back to forward before reverse has run for very long. I'll have to work out the details. I might find a way to handle this concisely and simply. It will be nice and elegant if I do.
If this overhead when going into reverse can't be removed, it can at least be reduced by using a smaller image buffer, say 30 frames.
Also, what does memory consumption look like? CPU overhead looks very small, of course it would be worse for the ultra-accurate emulators such as Nintendulator, but I think you have proven that CPU overhead is not a worry.
I render graphics to an "offscreen" 8-bit work area, then copy that to the screen and double the pixels. If an emulator uses an 8-bit work area, then at most a frame uses 64K memory (assuming 256x256 area), or about 3.75MB for the fixed 60 frame buffer. The state snapshots are around 8K each, or about 480K per minute. At worst, the joypad history is 3600 bytes per minute. Being able to rewind the last minute is plenty.
I've implemented this feature in an emulator of mine, not NES though. And I must say that the result is indeed awesome. Before implementing it, I thought it would be an unnecessary feature, but I've changed my mind now. It's very handy (and cool ;p ) to use it, especially in action games where you'd savestate every 10 seconds instead. I died/got hit ? oh, I'll just rewind 2 seconds and retry.
If you're hesistating to implement this, just create a test version of this feature first. It'll just take a few minutes.
something like this (psuedocode, only rewind, no playback):
BYTE* rs[1000]; // lots of savestates
int r=0; // rewind location
newframe();
if (readkeys()==rewindkey) loadstate(rs[r--]);
else savestate(rs[r++]);
r<0?:r=999.. r>999?:r=0
I put in a feature request for real-time rewind (we should probably drop the copyrighted name) at the Nintencer forums. Nintencer is the sucessor to FCE Ultra:
http://nintencer.fobby.net/
... the author seems to be interested to give it a try. As far as accuracy and game compatibility go, the FCE Ultra lineage is pretty high up there. I would even say up in the top 3, but I am sure those more in the know will correct me on that. It is also one of the most portable NES emulators, and has had ports in the past to: DOS, Windows, Linux, various BSDs, Mac OSX, Solaris, and even the Xbox. Though currently Nintencer only officially supports Linux and Windows. It may still compile for other platforms.
A little anecdote. I remember playing FF3j translated on an emulator years ago (probably in NESticle), saving my game with a savestate. One time I saved it when walking around, right before getting into an unwinnable battle. D'oh! Since I never saved using the game's interface, losing the battle meant all my progress was gone. For times like that a rewind feature would've been really nice. But I was more careful about when I saved states in any games after that, heheh.
Memblers wrote:
A little anecdote. I remember playing FF3j translated on an emulator years ago (probably in NESticle), saving my game with a savestate. One time I saved it when walking around, right before getting into an unwinnable battle. D'oh! Since I never saved using the game's interface, losing the battle meant all my progress was gone. For times like that a rewind feature would've been really nice. But I was more careful about when I saved states in any games after that, heheh.
Slower paced games will require a larger rewind window, but according to blargg's benchmarks, a 1 minute rewind window is feasible memory and CPU-wise. That should be far more than enough for any action game. However, I think that some Final Fantasy battles can last longer than 1 minute. So that could be a problem. However, if real-time saves keep the rewind time window with the save, then your situation would have been fix-able as you would load the save which is right at the start of the battle and try to win the battle again, rinse and repeat a few times until you realize that it is un-winnable. So then you load the save one last time but then rewind right after loading it, just enough to avoid the battle.
Hence we have a perfect example of the power of real-time saving and real-time rewinding used together. You no longer have to worry about quick-saving yourself into a corner.
Jagasian wrote:
So then you load the save one last time but then rewind right after loading it, just enough to avoid the battle.
That wouldn't work. There would be nothing to rewind to. Once you play forward from that savestate, the 'rewind window' as you called it gets filled with data
after the savestate. Loading a state will not allow you to rewind any further back from the time of the state -- not unless you do something crazy like actually save 61 states with the savestate (to re-create the rewind window on state load)
I really think such a feature would work well with user customizable savestate benchmarks, and length of the time to save. This way a user would be able to extend the savestate window past 1 minute if they're willing to cough up the extra needed RAM -- and other users could keep the window smaller (or disable it completely) if they don't have the RAM/CPU to spare.
Disch wrote:
Jagasian wrote:
So then you load the save one last time but then rewind right after loading it, just enough to avoid the battle.
That wouldn't work. There would be nothing to rewind to. Once you play forward from that savestate, the 'rewind window' as you called it gets filled with data
after the savestate. Loading a state will not allow you to rewind any further back from the time of the state -- not unless you do something crazy like actually save 61 states with the savestate (to re-create the rewind window on state load)
Well, save stating could be implemented by writing the state at the beginning of the rewind window and all of the user data after that up until the current state. The total size of that would be very small, basically the size of a state plus a movie. On load, this could be converted back into the format needed for real-time rewind and the emulator could also recreate the final state in the time window so that emulation could start where the gamer left off. This way a copy of the rewind window, at the moment at which the save state button was pressed, is written to disk, but it is done in a way that doesn't waste disk space.
Disch wrote:
I really think such a feature would work well with user customizable savestate benchmarks, and length of the time to save. This way a user would be able to extend the savestate window past 1 minute if they're willing to cough up the extra needed RAM -- and other users could keep the window smaller (or disable it completely) if they don't have the RAM/CPU to spare.
Yeah, definitely make it configurable so the spoiled sports emulating the NES with a 3Ghz CPU / 2GB RAM power house can crank the rewind window to an hour
Of course variable speed rewind will be needed then as rewinding through an hour of history, even at normal speed, would be a lesson in patience. For really long rewind windows, it would become worthwhile to use blargg's more complicated algorithm that keeps older snapshots with less frequency. This would put memory overhead close to that required for movies.
I've just written a clean standalone C implementation of the core reverse emulation algorithm that can be used as-is in an emulator by defining the callback functions. The size of the frame buffer is configurable. I also wrote a fairly thorough test and it works well in my emulator. It's only 71 lines of source with plenty of comments.
It includes the recently discussed optimization of keeping the most recent 60 (or however big your frame buffer is) frames around so that switching to reverse doesn't have any latency. It took a while to find a clean way to handle this (it's not as simple as it seems).
reverse_emulation-0.1.0.zip
I do plan on improving it and documenting the algorithm more thoroughly.
(should this go in a new thread? this thread has gotten unwieldy)
blargg wrote:
I've just written a clean standalone C implementation of the core reverse emulation algorithm that can be used as-is in an emulator by defining the callback functions. The size of the frame buffer is configurable. I also wrote a fairly thorough test and it works well in my emulator. It's only 71 lines of source with plenty of comments.
It includes the recently discussed optimization of keeping the most recent 60 (or however big your frame buffer is) frames around so that switching to reverse doesn't have any latency. It took a while to find a clean way to handle this (it's not as simple as it seems).
reverse_emulation-0.1.0.zipI do plan on improving it and documenting the algorithm more thoroughly.
(should this go in a new thread? this thread has gotten unwieldy)
Yeah, so many variations of the real-time rewind idea have been brainstormed in this thread, that new-comers will be overwhelmed. It is probably best to start a new thread, with a high-level description of the feature from a user/gamer's POV, why it is cool, etc, along with your MP3 to help people "visualize" it in action. Then a high-level description of the current algorithm, and then a link to your code. It could all be done with some cut-n-pasting of content from this thread, with parts rewritten for clarity.
Might this belong in the wiki as well?
*bumpity*
This topic is starting to contain information related to this older topic.
If we can emulate 'reversely' let's debug the same way, shall we?
Can I get a wootz?
A "step backwards" debugging feature wouldn't share anything with rewinding except use of the periodic save states. The two features are otherwise different because backwards playback uses a special technique for avoiding constant seeking to go back each successive frame, while stepping backwards for debugging is only done one instruction at a time at the user's request.
Even so, if the user holds down the "-1 instruction" key and makes it autorepeat at -20 instructions per second, that's a lot like rewinding.
Quote:
Even so, if the user holds down the "-1 instruction" key and makes it autorepeat at -20 instructions per second, that's a lot like rewinding.
If the emulator can run at 60 frames per second, then it can easily restore the most recent beginning of frame save state and emulate to the point within that frame at 20 frames per second.
But it would still have to dip into the rewind buffer if the user rewinds to a previous frame, or if the user wants to "scrub" back and forth across a section with constant input.
I have nothing useful to say except that when I saw this thread title on page 1 my first thought was, "but that thread is like 2 years old!"