Java-Gaming.org    
Featured games (78)
games approved by the League of Dukes
Games in Showcase (428)
Games in Android Showcase (89)
games submitted by our members
Games in WIP (466)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  Braid-like time reversal  (Read 5086 times)
0 Members and 1 Guest are viewing this topic.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Posted 2012-03-02 04:47:07 »

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.

See my work:
OTC Software
Offline Cero
« Reply #1 - Posted 2012-03-02 06:51:24 »

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

Offline lhkbob

JGO Knight


Medals: 32



« Reply #2 - Posted 2012-03-02 07:08:24 »

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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #3 - Posted 2012-03-02 07:11:41 »

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.
Offline Cero
« Reply #4 - Posted 2012-03-02 09:30:31 »

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

Online Roquen
« Reply #5 - Posted 2012-03-02 10:49:49 »

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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 613
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #6 - Posted 2012-03-02 11:31:35 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline SmokeNWrite

Junior Member


Projects: 1



« Reply #7 - Posted 2012-03-02 13:44:23 »

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 (:
Online Riven
« League of Dukes »

JGO Overlord


Medals: 613
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #8 - Posted 2012-03-02 13:49:11 »

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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline SmokeNWrite

Junior Member


Projects: 1



« Reply #9 - Posted 2012-03-02 14:05:21 »

ah, just an idea never tried it before (:
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Online Roquen
« Reply #10 - Posted 2012-03-02 15:15:00 »

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:

1  
2  
3  
4  
5  
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:

1  
2  
3  
4  
5  
backwardUpdate()
{
   velocity -= acceleration;
   position -= velocity;
}


But wait!  Consider the following useful FP computation:
1  
2  
3  
4  
5  
6  
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".
Online Riven
« League of Dukes »

JGO Overlord


Medals: 613
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #11 - Posted 2012-03-02 15:34:44 »

Not only does order matter, but every computation introduces errror.  I suppose you could do everything in fixed-point, but like I said "PITA".
I don't see how fixed-point solves the problem. Most mathematical operations are destructive, only adding and subtraction are guaranteed to be reversable.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline JayTech

Junior Member


Medals: 1



« Reply #12 - Posted 2012-03-02 17:23:06 »

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.
Online Roquen
« Reply #13 - Posted 2012-03-02 17:24:01 »

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|.
Offline CommanderKeith
« Reply #14 - Posted 2012-03-02 17:33:13 »

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.

Offline sproingie

JGO Kernel


Medals: 200



« Reply #15 - Posted 2012-03-02 17:43:48 »

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.
Online Riven
« League of Dukes »

JGO Overlord


Medals: 613
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2012-03-02 17:49:29 »

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|.
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

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #17 - Posted 2012-03-02 23:37:47 »

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.

See my work:
OTC Software
Online Riven
« League of Dukes »

JGO Overlord


Medals: 613
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2012-03-02 23:49:44 »

Thanks for all the ideas, people. Sounds like I'm pretty much on the track I need to be on.
I don't know how you reach that conclusion, as every reply in this thread basically advises you not to use negative deltas.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #19 - Posted 2012-03-03 00:28:07 »

Thanks for all the ideas, people. Sounds like I'm pretty much on the track I need to be on.
I don't know how you reach that conclusion, as every reply in this thread basically advises you not to use negative deltas.
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.

See my work:
OTC Software
Offline Yogr

Junior Newbie





« Reply #20 - Posted 2012-11-19 19:50:41 »

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.


This. Listen to sproingie.

Create a time stack of saved positions/states of each object and pop them off as you reverse time.
Online Roquen
« Reply #21 - Posted 2012-11-19 21:16:50 »

I think I mentioned this before:  You just need deterministic sim from initial conditions, then you just save events.
Offline Eli Delventhal

JGO Kernel


Medals: 42
Projects: 11


Game Engineer


« Reply #22 - Posted 2012-11-30 22:47:08 »

This is all made and implemented and works quite well. I am basically just using float arrays to hold all the data.

I'll post the game that uses this some time in the next couple of months.

See my work:
OTC Software
Pages: [1]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (79 views)
2014-04-15 18:08:23

BurntPizza (71 views)
2014-04-15 03:46:01

UprightPath (82 views)
2014-04-14 17:39:50

UprightPath (66 views)
2014-04-14 17:35:47

Porlus (82 views)
2014-04-14 15:48:38

tom_mai78101 (106 views)
2014-04-10 04:04:31

BurntPizza (166 views)
2014-04-08 23:06:04

tom_mai78101 (262 views)
2014-04-05 13:34:39

trollwarrior1 (212 views)
2014-04-04 12:06:45

CJLetsGame (221 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!