Comment by jerf | Hacker News Reader

Comment by jerf | Hacker News Reader

Parent Full thread

Not necessarily. While playing Braid, in the back of my head I was reverse-engineering the engine.

It's a programmer thing. I'm sure you can all relate. :)

Anyhow, if you come at this sort of program in the imperative mindset, it looks impossibly complicated. Imperative programs live in the now, constantly fiddling with their state with no ability to go back. But if you come at this from a functional viewpoint, suddenly it's not so hard; functional programs naturally live in a timeless way and the challenge there is to actually hook them up to reality in a meaningful way!

Instead of recording the state and constantly mutating it, you record the inputs and replay them as needed. The engine will be entirely deterministic, so the game state can be freely rolled back and forth. And, here's the key: While retrofitting an imperative program to do this would be a nightmare, if you know what you are doing and you start with the understanding you need this, it's not so hard. You build a small test engine with the ability to do just one thing (maybe move units around), work out the necessary primitives, then start expanding the engine, maintaining the necessary properties as you go. You grow it from a small, maintainable seed.

This is where, even though you can't go to school and take "mutatable chronology mathematics", it really helps if you have a lot of math under your belt, because you need to be thinking in terms of invariants and maintaining properties and other such mathematical things. Sitting down to just hack this out Will. Not. Work.

Oh, I don't want to trivialize the accomplishment. This is the basic structure, but you're still going to encounter fundamental contradictions you need to work out how to resolve, and there will be tricky interactions that don't work quite right, and slight violations of some relevant property (that you may not even have fully understood or articulated) may manifest as some of the subtlest bugs you've ever seen (with their only saving grace being that they should be fully replicatable, in a system that basically has a time-traveling debugger). My point here is that while it is complicated and possibly the subtlest real-time strategy engine ever built, it is not as complicated as your imperative intuition is telling you. It's just fiendishly complicated, not impossibly complicated.

It doesn't even have to be fiendishly complicated. Each "time wave" is simply a different run of the simulation engine, with a differing set of inputs. The videos also explain how seemingly paradoxical situations, like units fighting alongside time-shifted selves are handled.

The JWARS simulation engines built by the US Department of Defense (in Smalltalk, BTW) could handle theater-wide simulations down to the individual soldier level at 10,000X speed, and this was implemented in Smalltalk many years ago. Handling a dozen or two dozen "time waves" in parallel shouldn't be too much of a burden.

I called it "fiendishly complicated" in this case because even if the code is simple when written out, the underlying mathematics is tricky. A programmer off the street couldn't just wander up and modify it meaningfully in the way that a programmer can hack on the Quake III engine without breaking it; the slightest change could cause massive bugs, if you're not maintaining the invariants. The word "fiend" is chosen carefully :)

The chronoporter is underspecified by the demo (which is not surprising and I do not mean as a criticism, buy the game to find out more). I can come up with several possibilities for how that works in game terms that match what we see in the demo, each with their own problems and benefits for the player.

What I'm talking about doesn't take any fancy mathematics. Earlier in this thread, someone else was talking about functional programming. You could do the same thing with OO, deterministic pseudo-random generators, and a few patterns like Action. All you have to do is support multiple time-shifted simulations in parallel, and you are mostly there. The complicated part is displaying "overlaps" but that is also not "fiendish." (And the game dynamics discussed in the videos would make that much easier.)

What is truly clever is the introduction of the propagating "Time Waves" in the first place! Once you have that insight, such a game becomes easier to envision implementing.

That "functional programming" someone was me.

And you missed my point entirely about mathematics, I think. "Fancy math" here is not calculus or fancy topology or graph theory. "Fancy math" here is that you need to build a new fancy math that works with your temporal engine. You can't just sit down and hack shit out, or you will die under the combinatorial explosion of temporal possibilities. You need to build yourself a system of primitives that are time-safe under the temporal transformations you wish to run, and make sure that as you add actions they are also time-safe.

Or you will be crushed by the complexity. Standard OO will not help. You don't need "a functional language", but you damn well need functional style. You'll end up reinventing it even if you didn't know about it advance, with rigid, explicit control over side effects.

If you set out to implement this, you will find the standard Action/Command pattern to be not very helpful. This game has a much richer timeline than the usual Command pattern is designed to handle.

"All you have to do is support multiple time-shifted simulations in parallel, and you are mostly there."

No, that will be inadequate. That doesn't get you to backing up to arbitrary points in the timeline, and since the simulations are not independent, you're going to have a hell of a time expressing all the dependencies in standard OO.

(Note that you could easily do functional-style OO. No problem. But it's not just standard imperative OO, such as might work with Starcraft. This takes more.)

If you don't believe me, try implementing it in a model system. I can only handwave so hard here before you need code to see my point, unfortunately, but I am extremely confident that if you approach this with the standard grab-bag of imperative techniques, you will fail, hard.

Most game replay systems work this way - they store the chain of user inputs, and then just resimulate it in order, with the same random seed. Thats the main reason they don't give you the option to rewind the replays and you have to start over.

This game just has multiple simulators running through the chain of commands at the same time, a "movable" simulator (the player's view) and the ability to modify the chain of commands. Once you can distill the idea of "moving backwards through time" into a command, it can be added to the chain of commands and be deterministically simulated like everything else.

For the game replay system you describe, the only requirement is total determinism. That's not the same as what is being shown here, where the "separate simulators" are actually not independent.

Both you and stcredzero are significantly underestimating the complexity introduced by the chronoporters. Without those, you'd be right, but those introduce additional complexity that I would despair of getting right with imperative programming.

It always looks simple when you just look at a demo. It's much harder when you go to actually do it.

Reply on news.ycombinator.com