Braid-like time reversal

Game Mechanics
#1

I’m working on a game that has a Braid-like mechanic where the player can reverse time to any previous event that happened. I’m trying to figure out the best way to do this.

The simplest solution is to store a snapshot of each objects’s state each timestep, and then upon rewind pop those states. The giant unavoidable drawback here is that this uses a massive amount of memory if you’re supporting infinite playback, not to mention potential object allocations for state representations. This is definitely not how Braid does it since you can play a level for several hours or more.

A more difficult solution that works for an infinite length of time is by passing in a delta to each update (usual variable timestep behavior) and simply making the delta negative in the case of time reversal. That works great for a lot of stuff but leaves certain large holes.

For example, a character who is up on a ledge might be walking, and then falls off and walks at ground level. When passing in a negative delta, he will walk backwards as expected. However when he reaches the point that he hit the ground, he has no way of knowing that he was ever in the air, so will keep walking backwards on the ground and never return to the ledge.

It seems like in this case you need to perhaps store the Y velocity in a giant array and timestamps where it changes, then pop them off as you reach those stamps. This is the same as storing the state, though, and although it avoids a lot of the overhead it still can get huge. If the main character goes up and down ledges for 1 hour that needs to be supported. I can make a couple gigantic float arrays without more than like 100k pf overhead, but that’s still a lot.

So what would you guys do? The state/delta combo will probably work but a system that eventually breaks seems really dirty to me.

#2

the braid guys have actually done a fair amount of talks about game development
maybe there is some concrete information on that already out there

just an idea that came to mind is:
you know how strategy games and fighting games have replay files; and in these replay files they usually only store the inputs, right ? Because a game is a computer program, and given the same inputs twice, should yield the same results (like in testing/debugging)
I remember this actually might be non-trivial, because many versions of Starcraft replays were buggy as hell and it took long for them to get it work properly…

Anyway, storing all the inputs as opposed to the data itself and then actually letting it run backwards, kinda similar to your negative delta idea.

I always thought of the Prince of Persia kinda way, there of course, you dont have this infinite problem, as you can only rewind like 15 seconds or so max

#3

I think storing the velocities, positions, or inputs is a reasonable way of consolidating the entire state of the world. I don’t know what would be best, but you can think of it as a dimension-reduction problem. The current state displayed to the player has a huge number of variables, but most of them are dependent on each other, especially if you consider the previous frame.

I don’t know if it’s required to instantly jump back in time, but I bet you could just write the state to disk and then stream it in as necessary. You’d keep a fixed block of history in memory so small jumps to nearby points in time would be fast and then you’d pull in more as they player moved forwards or backwards. It’s a similar idea to infinite world streaming like what Skyrim uses, although I think it can be much simpler for you.

#4

As I’ve mentioned in a couple of previous threads: using fixed time step simulations = possible deterministic behavior. Then you could save complete state every N frames. Store player input. Keep some set of time info in memory and page out older to file.

#5

Of course one has also to consider object/entities/whatever that are deleted/killed/nulled which have to come back when reversing

maybe something like, depending on time direction an object gets created or removed

#6

What I’m suggesting is to not directly reverse time. When running backwards you simply go the then nearest keyframe and run forward. Directly backward is a PITA.

#7

I doubt memory usage (or disk space for that matter) is really a problem. You can diff your snapshots to reduce it to a level you can easily ignore. I wouldn’t resort to input replay, as it forces you to make the entire game deterministic. This might sound easy, but it would probably surprise you how much state is non-deterministic, especially once you deal with multi-threading. I would simply go to the nearest keyframe and leave it at that.

#8

could reverse time while you have created snapshots of a few variables (jumping, falling, speed, etc)
then reverse the process with the variables activating at the time they activated.
Just an idea.
I might attempt this at some point (:

#9

With reverse physics, you most likely end up flying through walls and getting stuck.

#10

ah, just an idea never tried it before (:

#11

A limited type of determistic is not too bad. Off the top of my head (probably missing a thing or two):

  • Fixed timestep simulation, otherwise forget it.
  • Simulation is isolated from everything else. All other systems, like at a peep show, can only “look but never touch” (read but not write) any simulation related data.
  • The simulation should run on a single thread. The rule can be broken, but makes the problem much harder.
  • Process entities in a fixed order.
  • All libraries used in simulation must be deterministic.
  • Random numbers must come from a generator(s) only used by simulation.
  • The player is just another entity, and it’s updating occurs in the simulation sub-system. Input is the AI, which provide actions the player entity uses during its update.

By “limited type”, I mean that Java is kinda weird for FP computation. I’d be a shame to force all FP computations to be strictfp. So a given simulation is only deterministic on a given piece of hardware using a given JVM, after all the methods are warmed by the VM.

WRT: Attempting to directly reverse time. Forget it. It’s a PITA. You’d have to do everything in reverse order…everything. And then you still wouldn’t get truely reversed results. Consider the following pseudo-code:


forwardUpdate()
{
   position += velocity;
   velocity += acceleration;
}

(Don’t anyone bother to complain about me doing physics wrong…wait for it). You can’t just negate ‘velocity’ & ‘acceleration’ and get reversed results. You have to do:


backwardUpdate()
{
   velocity -= acceleration;
   position -= velocity;
}

But wait! Consider the following useful FP computation:


strictfp double orderedAddError(double a, double b)
{
  double s = a+b;

  return  b-(s-a);
}

Not only does order matter, but every computation introduces errror. I suppose you could do everything in fixed-point, but like I said “PITA”.

#12

I don’t see how fixed-point solves the problem. Most mathematical operations are destructive, only adding and subtraction are guaranteed to be reversable.

#13

Add a button for reverse time, player holds the reverse time button allowing for x amount of seconds where you control the frames and coordinates and other objects and bam it saves those, release the key and bam reverse time. To me I feel like this is an efficent way.

#14

The fixed-point thing was an afterthought and it probably doesn’t really help. But note kids, that FP addition and subtraction are not reversible and that was the point of the orderedAddError method, which returns the error on adding two doubles if |a|>=|b|.

#15

Yes reverse physics is really difficult. Even a player shooting a bullet, when reversed, kills the player since the reversed bullet will often just touch the player when reversed even though it didn’t when it was first shot. Stored key frames would be the easiest way.

#16

All you need to record are positions and state (player/mob is alive/dead, door is open/closed, key is usable/broken). You don’t have to “run physics backward” to do this, just record the positions and states that result. Braid doesn’t look like it even uses a physics engine.

#17

Why wouldn’t addition/subtraction be reversible in fixed-point arithmetic? Your example using double doesn’t really support your statement, as it is not fixed-point. My interpretation of fixed-point is that you store your value in an integer, which is fully reversible in addition & subtraction, even through overflow and underflow.

I presume that, as you used ‘fixed-point’ followed by ‘FP’, that ‘FP’ means ‘fixed-point’, not ‘floating point’ :persecutioncomplex: next time, DNA*

* do not abbreviate

#18

Thanks for all the ideas, people. Sounds like I’m pretty much on the track I need to be on.

To elaborate what I’m doing:

  • Where possible, I use reverse deltas to calculate things. For simple entities like traps (imagine the cannon in Braid) this works exactly as needed. In some other cases, like a trap that fires and then resets itself after firing (not just one shot), I also had to store a stack of the times it has finished retracting. Then when a time has passed, it goes back into a reverse firing state.
  • For more complex situations, I use large parallel array/stacks, one for the values, and one for the times that those values existed. Then when they change I revert to the previous value. This is the most memory reduced way to do this, and avoids a lot of object allocations (I used to have a List of HashMaps, and that was extremely expensive on the gc).
  • For certain things, only add another state onto the stack if a certain amount of time has passed since the previous state. This basically means that like at 10hz I would update a certain value, rather than 60.

One big thing I’ve found that is necessary (and many have pointed out) is that I can’t add timing values. Originally I was storing timeSincePreviousState rather than timeOfPreviousState, so I would add the delta to that value and if it was <= 0.0 then I’d pop. I was noticing especially bad issues here with gravity, as rewinding and replaying a character falling over and over caused him to eventually reach 3x the height he started. So I started passing in timestamps and that was sorted.

Oh and the idea of storing states on the disk is very interesting… I may go that route, depending on how this turns out.

#19

I don’t know how you reach that conclusion, as every reply in this thread basically advises you not to use negative deltas.

#20

As I said, I’m only doing that in certain situations where it works and not using it in areas where the floating point math will cause issues.

Something whose only purpose is to shoot an arrow can absolutely use deltas. The player, for the most part, cannot.