Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I was wondering how to implement time travel into a game. Nothing super complex, just time-reversal like what's in Braid, where the user can rewind/fast forward time by 30 seconds or whatever.

I searched around the web a lot, but my results usually referred to using time as in like "it's 3:00" or a timer and such.

The only thing I could think of was using 2 arrays, one for the player's x position and the other for the player's y position, and then iterating through those arrays and placing the character at that position as they rewind/fast forward time. Could that work? If it would work, how large would the array have to be and how often should I store the player's x and y? If it doesn't work, what else could I try?

Thanks in advance!

share|improve this question

migrated from stackoverflow.com Jul 27 '11 at 9:06

This question came from our site for professional and enthusiast programmers.

11  
Don't you read the news (ust.hk/eng/news/press_20110719-893.html)? They've just shown that time travel is not possible. Therefore, it's impossible to code. –  D.N. Jul 26 '11 at 23:18
    
You need to think a possible semantics for time-travel, only afterwards you can start to think about implementation. –  Paŭlo Ebermann Jul 26 '11 at 23:48
1  
Learn yourself some vector math. If you're proposing two separate arrays that suggests you've never worked with them. I consider them vital for a games programmer to know because of how much they can simplify things. –  Jonathan Hobbs Jul 28 '11 at 4:14
5  
import universal.back2future.FluxCapacitor; –  jhocking Sep 13 '11 at 19:49
1  
+1 for the hilarious title :-) –  Valmond Sep 14 '11 at 12:07

9 Answers 9

The array idea is pretty much how it was implemented in Braid. When the only things acting on a character are gravity, keyboard/joypad input, and other characters, you pretty much only need to store the position and the velocity at each step to know everything important about that character. If you store 10 snapshots per second per character then it's still less than 50K for a minute of one character's history - easily manageable on most systems, and you can find ways that are more efficient than that too.

share|improve this answer
    
This is the right track. For example store active commands : keypresses with timestamps. You can extrapolate most other behavior if the system is deterministic. 10 fps tracker is fine for a rewind system, even less might be acceptable, as long as the actual commands are retained, in effect the state or statechanges of the objects. –  karmington Sep 13 '11 at 23:23

Read up on the Command Pattern. It provides for undoing actions (and for later re-doing them.) That would handle more than just position of a ship, but all actions the player takes.

But I think your array idea is sound as well.

share|improve this answer
    
Probably not a great idea - besides being more memory-intensive (every time you add an entity's velocity to its position, you need to store that as an "action"), it pretty much requires fixed-point math, since if you use floating-point for your positions/speed, (x+v)-v might not be equal to x. –  BlueRaja - Danny Pflughoeft Jul 27 '11 at 16:53
1  
@BlueRaja - Don't see where that approach would be memory-intensive. At 100 FPS and storing the last 10 seconds, you need to store 1000 n-tupels of commands, where n is at most 5 or so. Or, even better, you store only the absolute position in each of those frames, and for the rewind, you simply animate the character backwards along that path. That would also eliminate any possible floating point issues and brings you back exactly to where you started. –  Hackworth Sep 13 '11 at 21:26

Rather than have two separate arrays, you should probably have one class that describes the player's position (there's probably a Point class in Java already... I'm a C# guy lately) and use one single array to hold past positions.

You need to setup a "ring buffer", meaning that when you get to the end of the array, you circle back to the beginning of the array, overwriting the oldest entries. If you travel back in time, the opposite is true (when you get to the beginning, circle up to the end).

If you want to hold 30 seconds worth of past data, you need to know your frame rate if you want to pre-allocate space and use a fixed-size array. If you render the game at 10 frames/second, times 30 seconds, that's 300 elements.

share|improve this answer

GDCVault has a lecture by Jon Blow (the creator of Braid) on their site called The Implementation of Rewind in Braid for $3.95. I'll bet this has the info you want ;)

EDIT: Probably won't be in Java but the ideas should hold.

share|improve this answer
    
Do you know if they sell the transcript too, or only the audio? –  Lohoris Sep 14 '11 at 19:15
    
I couldn't find anything via a quick search of the site. Maybe you could use some transcription software? –  NoobsArePeople2 Sep 15 '11 at 20:37

There was a game released for the XBox360 that involved time-manipulation. It was mediocre, so I can't remember the title at this time. Anyway, in an interview with a developer for it, they outlined how they managed time manipulation:

Every X frames (with lower values of X leading to more fine-grained manipulation), you take a "snapshot" of the gameworld at that point, and associate it with an in-game time.

While playing through the game normally, time-forward, every input an reaction contributes to the snapshot set at some time in the future.

The game world then iterates between the snapshot at the current time, and the snapshot X frames in the future.

Then, when you want to reverse time, just set the direction of time to be backwards, so that it is iterating between the present and the snapshot X frames in the past (while disabling the ability to create future snapshots).

share|improve this answer
    
+1 for the point about the granularity of the snapshots. –  Omar Kooheji Sep 15 '11 at 20:19

Like Erik J said, storing the player's past positions as a collection of point objects in a ring-buffer sounds reasonable.

However, I would suggest using a queue to implement the buffer. It's much cheaper to update than an array and you don't have to know your frame rate in advance:

update():
   time_queue.push(player.positions)
   if current_time() - start_time > n:
       queue.pop()

This does not yet consider varying frame rates or what should happen if you actually do any time-traveling, so I suggest you store a time stamp with each entry and check that instead:

update():
    time_queue.push({
        'pos': player.positions,
        'time': current_time()
    })
    first_entry = queue.peek()
    while current_time() - first_entry['time'] > n:
       queue.pop()
       first_entry = queue.peek()

Hope this helps!

share|improve this answer

There's a design pattern called Memento, I think it's a starting point for a game like Braid

The memento pattern is a software design pattern that provides the ability to restore >an object to its previous state (undo via rollback).

The memento pattern is used by two objects: the originator and a caretaker. The originator is some object that has an internal state. The caretaker is going to do something to the originator, but wants to be able to undo the change. The caretaker first asks the originator for a memento object. Then it does whatever operation (or sequence of operations) it was going to do. To roll back to the state before the operations, it returns the memento object to the originator. The memento object itself is an opaque object (one which the caretaker cannot, or should not, change). When using this pattern, care should be taken if the originator may change other objects or resources - the memento pattern operates on a single object.

http://en.wikipedia.org/wiki/Memento_pattern

Adcional info here: http://dofactory.com/Patterns/PatternMemento.aspx

share|improve this answer
2  
I fail to see how this should help. Looks like it is a "instant-rollback", while the OP asked for something smooth like Braid's one. Maybe I misread something? –  Lohoris Sep 13 '11 at 19:34
    
This is pattern not implies on a single rollback, you can create a "timeline" of actions, for example. Here's an Brazillian's blog post about that usage of this pattern: abrindoojogo.com.br/padroes-de-projeto-memento Here's an example made in Flash: abrindoojogo.com.br/files/fasteroids.swf Move: Arrows | Shoot:Space | Rewind Actions:Backspace –  Marcelo Assis Sep 13 '11 at 20:03

You can simply treat the game's virtual time as another space-like dimension. So what's time travel from the outside is a simple n+1 dimensional movement in the game's virtual universe.

Assuming some user interaction and some sort of physics system that determine the behaviour of your universe when there's no user input, all you need to record is the effect of user interactions (for example, changes in the n+1 dimension speed/acceleration vectors), as your physics should be time-reversible.

This way you'd need much less memory to calculate the state of the game universe at any given time coordinate.

share|improve this answer
    
As I mentioned in another comment, physics in video games is usually not time-reversible, because when using floating-point numbers, (x+v)-v might not be equal to x –  BlueRaja - Danny Pflughoeft Jul 27 '11 at 16:56

Let's say an entity has a velocity, rotation, x and y position. These are, with acceleration, the basic movement states, values, whatever you call it. You can save the data in two ways:
1. Save rotation, x and y position
2. Save rotation, x velocity and y velocity

If you have a fixed velocity, you could also only save rotation, or save only one velocity for both axis.

Saving rotation is necessary in games, unless your entity has a static rotation, what it is not in most cases.

That said, using a list of objects for multiple values is necessary. If you have a nice timer system, which, for example, calls update methods 20 times in a second, and therefore is fps independent, you can create an array of 20 * 30 objects to store the movement values you need for the last 30 seconds. Using a simple array is not recommended, since you would have to move every element one index left each update call.

Based on this, you can go through the list or whatever to go back. If you really want to gain a "realistic" effect, use this technique for all moving objects. But this is game design related.

If you destroy objects, remember to pool them, to ensure that you do not stress your neat friend Mr. Garbage ;)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.