Jump to content

  • Log In with Google      Sign In   
  • Create Account

We're offering banner ads on our site from just $5!

1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Don't forget to read Tuesday's email newsletter for your chance to win a free copy of Construct 2!


Implementing "Rewind Time", like in the Prince of Persia - Sands of time series


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
15 replies to this topic

#1 chondee   Members   -  Reputation: 135

Like
1Likes
Like

Posted 14 January 2012 - 03:32 PM

Hi,

I am not sure if you guys are familiar with the PoP Sands of time series, I was trying to look for a video on youtube demonstrating this feature, surprisingly I haven't found one, I'll try to describe it however. In these games, you have the ability, to hold down a button, and rewind the last 5-10 seconds of time that has just passed, affecting you, the objects and enemies, and all this is going smoothly in real time. It would be similar as if you are watching a video, then you rewind 5 seconds of it, then go again. Only in the game if you made a mistake, fell off a platform now you have the chance to get another shot at it.

I found this feature improving the game experience a lot, such that after any small mistake you don't die, face a loading screen, have the whole thing interrupted, then start from a checkpoint, but at the same time the usage of this ability was limited, so it didn't make the game too easy either.


I am now thinking of implementing this in my 2d scrolling space shooter engine, but it makes me wonder how am I supposed to do this..
The only way I can imagine it, is that the past 5 seconds from current time, so the past 300frames at 60FPS is "recorded", such that for the player and every object, at every iteration of the game loop "saves" all their important variables, for example x,y position, velocity, current action etc into a corresponding past_x[300], past_y[300], past_velocity[300] etc.. array, and when rewind is flagged, at each game loop iteration, the current x,y, velocity, etc is updated from the past_x, past_y etc.

Now, considering enemies, bullets, particles, that is a lot of information to store, and would take up quite some memory.


Do you guys think this is the way I should try to implement this as I described above, or there is some better/more efficient way that I am overlooking?

Sponsor:

#2 frob   Moderators   -  Reputation: 22242

Like
3Likes
Like

Posted 14 January 2012 - 04:49 PM

Basically, yes, that is what you need to do. Another fun game to do it was Braid.


Rather than recording the position of every particle, store the events behind everything.

Recording events at timestamps requires less space. You know an event at a time "bullet 7 fired from (x,y) @30:14.03", another event "bullet 7 hit target at (x,y0) @30:29.54". Then if your clock is at 30:16.43, you can figure out where the bullet was at that time.

Also, consider organizing your events into a spatial tree with one dimension as time so your list of items doesn't overwhelm you when rolling back and forth over time.

Check out my book, Game Development with Unity, aimed at beginners who want to build fun games fast.

Also check out my personal website at bryanwagstaff.com, where I write about assorted stuff.


#3 Infernal-rk   Members   -  Reputation: 135

Like
2Likes
Like

Posted 17 January 2012 - 05:00 PM

What happens to your physics or particle pathing if you use negative time as your timestep?


if for instance particles animated exactly backwards for path and effects using a negative timestep, you wouldn't have to record anything but their "fizz out" locations to spawn backwards animating particles as it rewinds the scene.



#4 Krohm   Crossbones+   -  Reputation: 3171

Like
1Likes
Like

Posted 19 January 2012 - 02:32 AM

I've experimented a bit with this some time ago for a very stupid platformer. I could more or less make it work for most "well known" objects but in general, allowing a generic object to go back in time imposed quite some limitations I could not really live with.
Simply mandating timestep to be always positive nonzero (time monotonically increasing) simplifies things a lot. When I abandoned that assumption I had to rewrite some gameplay code with some propagations in logic as well.
I later experimented with "stateless" systems, where objects would collect events in queues. Instead of going back and forth in time, each object would be fetched a time gap from t0 (start of the event queue). This initially worked as expected but at this point I ran out of time for further experiments.

#5 BeerNutts   Crossbones+   -  Reputation: 2978

Like
2Likes
Like

Posted 19 January 2012 - 08:18 AM

Recording events is the idea, but events are not only when things are created (ie a bullet fired), but also when their velocity changes. If you record their changing velocity for a certain amount of time, you can reverse the velocities and work backwards. So, you store all these events in a queue, but clear out old events that happen longer than 5 seconds ago (or whatever your max rewind time is).

For example, an enemy spawns at position 10, 10 and begins chasing the player to the right (record timestamp, new location (10, 10), and velocity (10, 0)). 1.5 seconds later, he jumps up, following the player onto a platform (record timestamp, location and new velocity (10, -10)). When he lands on the platform 0.5 seconds later, his y velocity goes to 0 (record timestamp, location, and new velocity (10, 0)). 2 seconds later, the player kills the enemy (record timestamp and location of enemy dying).

1 second later, the player falls off the screen, but hits the "rewind button." Record the time he hit the rewind button, and work through the queue in reverse by subtracting the timestamp when rewind was hit by the time elapsed since then. 1 second later, you'll hit the enemy dies event, and location, but you'll actually spawn the enemy, and set his velocity to reverse what it was when he died (-10, 0).

And so on. If you are doing a platformer, I'd suggest working gravity into the events, since, when a player or enemy is jumping/falling, the velocity will be changing every frame, and you don't want to store all those changes.

Anyway, just a thought.
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#6 chondee   Members   -  Reputation: 135

Like
0Likes
Like

Posted 19 January 2012 - 11:59 PM

Thank You for all your comments and help!
I would use this on a scrolling shooter, with no physics involved. I would plan on making 3 seconds of max rewind time at 60FPS -> 180frames

My concerns so far:
Randomly generated stuff:
most enemies are randomly generated, and let's say they have a chance of dropping something when they die too.
My solution to this would be, that everything that is randomly generated has to be determined/generated BEFORE the rewind time range, so before 180frames. So a randomly appearing enemy at the current frame must have been generated 180 frames ago, that way the rewind won't screw with anything that was supposed to happen in the future (counted from the -3 sec rewind time Posted Image)
I am still wondering if this would be a good method, or it won't work well.

Other than that I could divide everything else into 2 categories:
1. Stuff that has a constant speed or constant acceleration, not AI driven.
These are primitive bullets that just go straight, stars, scrolling background and background objects and particles.
To record the state of every frame for each of these would consume too much resources, and would be unnecessary, and the above suggested timestamp method would be enough to calculate these objects position at any time having known the velocity (or acceleration if applicable).

2. Anything more complex than above
More intelligent projectiles and AI driven enemies, that would be really hard (or not quite possible) to calculate their behavior at any given timestamp.
For these I really would just "record" their related variables/states for the last 180 frames in a stack, and during rewind I'd keep popping the topmost one into the corresponding current variables.

Do you guys think this is a good plan, or would you make some adjustments, or do it in an entirely different way?

#7 Krohm   Crossbones+   -  Reputation: 3171

Like
1Likes
Like

Posted 20 January 2012 - 01:24 AM

Recording events is the idea, but events are not only when things are created (ie a bullet fired), but also when their velocity changes.

Yes, let me elaborate. Main problem is that each object must have some sort of log to post its interesting state changes and variable changes. In general this can be done with some way for each object to add events to a queue.
I experimented with both a "central event repository" (try to centralize management) and a distributed queue system (try to simplify). I am inclined to the second, although the amount of redundant code was a source of concern.

Randomly generated stuff:
most enemies are randomly generated, and let's say they have a chance of dropping something when they die too.
My solution to this would be, that everything that is randomly generated has to be determined/generated BEFORE the rewind time range...

I'd generate the loot when the enemy is spawned. I'd eventually give it its own random seed and generator.

Do you guys think this is a good plan, or would you make some adjustments, or do it in an entirely different way?

I think it's a good start.

#8 AlysiumX   Members   -  Reputation: 152

Like
-1Likes
Like

Posted 20 January 2012 - 10:25 AM

Personally, I would attempt to create an object that hold everything on the screen on each frame. So you could have a screen object. The screen object has a list of objects and there current state that is currently on the screen. You then create an array of these, for the first 300 frames, you save the state of each screen.

After your at 300 frames, you pop off the first frame, and add the next so frame 301 becomes becomes 300 and all other screens move back in the array(probably faster just to copy it into a new array). In this way, after the first 300 your taking just a single "screen shot" of the screen and getting rid of the first one.

Your also not worried about projectile calculations or anything like that since it should just be a matter of running backwards through the frames to restore the state of all objects on the screen 300 frames ago.

#9 AlysiumX   Members   -  Reputation: 152

Like
-1Likes
Like

Posted 20 January 2012 - 10:58 AM

I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.

#10 Cornstalks   Crossbones+   -  Reputation: 6991

Like
0Likes
Like

Posted 20 January 2012 - 11:05 AM

If you're curious enough to spend $3.95, you can get Jonathan Blow's GDC 2010 talk on the Implementation of Rewind in Braid. There's an interesting thread about it here, as well.

If I remember what Jonathan Blow said about it, he took a full world snapshot every some-odd frames (or seconds). That was to make sure a user couldn't abuse the physics engine through floating point errors. Then, for the in between frames, I believe he recorded the deltas for each object, but I believe he limited the deltas to just a few bits in order to save storage space (with the limitation that there was an upper limit of how fast an object could move, otherwise the object's delta couldn't be saved in just a few bits). Braid needed to do this though because you can rewind the entire game, practically. If you're only rewinding a few seconds, you don't have to worry as much about compressing the deltas. Unfortunately, I can't remember any other details. (for the curious, this is similar to how a lot of video codecs work, like H.264).
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#11 Nypyren   Crossbones+   -  Reputation: 4499

Like
0Likes
Like

Posted 20 January 2012 - 12:01 PM

I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.


You would still need to store states for every frame.
1. The user is typically allowed to cancel rewind at any point in the recording.
2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength]

#12 Cornstalks   Crossbones+   -  Reputation: 6991

Like
0Likes
Like

Posted 20 January 2012 - 12:10 PM


I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.


You would still need to store states for every frame.
1. The user is typically allowed to cancel rewind at any point in the recording.
2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength]


To add to the list:
3. That will significantly slow the application because writing a screenshot of each frame to disk is slow
4. You'll need to compress each image (png maybe?) or else you'll end up with gigabytes of screenshots (and compressing/decompressing each frame would be another bottleneck)
5. If you don't write to disk, but instead keep the screenshots in memory, you'll use about a gigabyte of memory for 5 seconds of screenshots at 30 fps and 1080p resolution (uncompressed, but even compressed will be quite large), which will probably kill cache performance in some areas of the program
[ I was ninja'd 71 times before I stopped counting a long time ago ] [ f.k.a. MikeTacular ] [ My Blog ] [ SWFer: Gaplessly looped MP3s in your Flash games ]

#13 BeerNutts   Crossbones+   -  Reputation: 2978

Like
0Likes
Like

Posted 20 January 2012 - 12:14 PM

I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.




I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.


You would still need to store states for every frame.
1. The user is typically allowed to cancel rewind at any point in the recording.
2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength]


What he said. For example, if you just picked up a power-up, then died, when you rewind 3 seconds, you will go back to before you had the power-up, so saving screens/frames isn't enough. You could store the event of "Acquired Power-up" at x time, then, when reversing, at that time, you remove that power-up, etc.
My Gamedev Journal: 2D Game Making, the Easy Way

---(Old Blog, still has good info): 2dGameMaking
-----
"No one ever posts on that message board; it's too crowded." - Yoga Berra (sorta)

#14 AlysiumX   Members   -  Reputation: 152

Like
-1Likes
Like

Posted 20 January 2012 - 12:16 PM


I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.




I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.


You would still need to store states for every frame.
1. The user is typically allowed to cancel rewind at any point in the recording.
2. During recording, you can't throw away state, since a recorded frame T[n] must be saved until T[n+historyLength]


What he said. For example, if you just picked up a power-up, then died, when you rewind 3 seconds, you will go back to before you had the power-up, so saving screens/frames isn't enough. You could store the event of "Acquired Power-up" at x time, then, when reversing, at that time, you remove that power-up, etc.


Well it seems like a terrific shortcut lol. Ya so basically what I originally said.

#15 chondee   Members   -  Reputation: 135

Like
0Likes
Like

Posted 20 January 2012 - 12:57 PM

If you're curious enough to spend $3.95, you can get Jonathan Blow's GDC 2010 talk on the Implementation of Rewind in Braid. There's an interesting thread about it here, as well.


I think Braid is a really brilliant game and the time rewind thing was a main point game mechanic of it. If I remember correctly it had a some stuff going backward in time, some is going forward (at the same real world time), or depending on which direction the player is moving (while the player is moving forward in time) other objects may move either backward or forward in time.

For my game I think Braid's implementation would be overkill.
I would like to implement something simple, only covering my needs for rewinding time in case the player screwed up to have a second shot at it. The core game itself would not rely in time manipulation puzzles.

I just thought of a terrific short cut for this. Just capture a screenshot of every frame and store them in an array, do the pop off of the first and add onto the back operation describe above. Then just run through the array backwards displaying each screen for a rewind and restore the players state at the end of it. Your grabbing 1 screen shot per frame, no huge object array, no calcuations, no hassles.


Let's say taking 60 raw screenshots/second doesn't take an insane amount of memory and processing power.
I try to fight off 3 enemies, I kill two in the process, they explode, but I took too much damage, my health decreased to a minimum, I want to reverse the whole encounter.
Rewind everything.
How will the 2 enemies I killed come back to life, how will my health grow back, how will my position revert back?
That doesn't seem like the way to go.



I guess we can all agree that the current state at a given frame need to be captured of all objects.
For some objects that move constantly in a predictable way, like particles or scrolling stars, the current state can be calculated, this way saving memory and possibly processing power (in contrast to saving all variables for 500 particles and stars / frame)

For more complex AI driven objects I could only imagine that (almost) every variable they which is not constant must be saved for every frame. There are not that high numbers of these objects at any given moment, so that shouldn't be too expensive.


For me the obvious way would be that each objects before its state updated pushes its current variable on top of the corresponding variable's memory stack. On rewind the values are popped from the memory stack to the current.

EDIT:
Another important thing that I just thought of:
In my current implementation of the game, in every frame all objects are polled to see if their alive flag is turned off, because if it is, they have to be erased from their vector container. (All particles, stars, enemies are stored inside vectors, a new one spawned is push_back() -d on it, dead ones are erased.)
This needs to be adjusted so after the object is not alive, it should not be drawn anymore, and it should not perform any logic anymore (other than keep updating the memory stack of its variables), but it should not be erased until enough time has passed that even after a full (3 seconds -> 180 frames) of rewind, it would not come back to life. So it can only be erased 180 game loop iterations after it died.
/EDIT

My concern/question now:
Some of you are saying that there should be a separate class that dynamically handles/creates all the memory variables of each object, in contrast to having each object care about its own stuff.

To me having a separate object that has access to all variables of all other objects, and dynamically creates them for each by polling them every frame (lets say a new enemy spawns, after that this time manager object scans through all enemies, recognizes that there is a new one, in response to that it will dynamically allocate memory for all variables of that enemy, gets all values then stores it there) seems unnecessary complicated.

Is there any benefit of having a time state manager object doing all this, instead of having each object doing it for itself? Wouldn't it only over-complicate things?

#16 Bacterius   Crossbones+   -  Reputation: 9066

Like
-1Likes
Like

Posted 23 January 2012 - 05:03 AM

Well it seems like a terrific shortcut lol. Ya so basically what I originally said.

It's not a shortcut, it's impractical. Constantly recording the X last seconds would consume a lot of CPU time, would saturate the PCI-E bus, would consume an immense amount of memory, and it would be fundamentally very limiting (you wouldn't be able to add visual features, etc...), and it wouldn't be scalable (resolution-dependent, among others).

The correct way to do it (or at least a better way) is to store the state of every relevant object in the game. Also you probably don't need to store state information for every single frame. If you are rewinding say 5 seconds over a duration of 2 seconds, you only need to store states for 2 frames out of 5, instead of all 5. Also you can probably get away with storing states for once every 10 frames and interpolating, it shouldn't be noticeable.

And yes, some items' states don't need to be stored, such as simple physics objects for which the position can be calculated by simply knowing the current time (like particles).

I would probably get a time state manager object to do it, it's just simpler (and once everything is working you can always change it - it's easier to change something that works than to implement the hard way from scratch).

The slowsort algorithm is a perfect illustration of the multiply and surrender paradigm, which is perhaps the single most important paradigm in the development of reluctant algorithms. The basic multiply and surrender strategy consists in replacing the problem at hand by two or more subproblems, each slightly simpler than the original, and continue multiplying subproblems and subsubproblems recursively in this fashion as long as possible. At some point the subproblems will all become so simple that their solution can no longer be postponed, and we will have to surrender. Experience shows that, in most cases, by the time this point is reached the total work will be substantially higher than what could have been wasted by a more direct approach.

 

- Pessimal Algorithms and Simplexity Analysis





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS