Time Travel Is ******* Hard
For my fourth entry into the Seven Day Roguelike Challenge, I decided to go big. Time travel. Hundreds of years of procedural history. Procedural maps and biographies. Someone described the idea as "Dwarf Fortress Lite." In other words, I was trying to develop a simplified version of a game that's been in development for 14 years in a week. And I wanted to add time travel to it.
It was a bit tougher than I expected. I came up with something cool, but failed in many ways. This post explains what happened.
Design
I got an idea after hearing Mark Johnson talk about his plans for Ultima Ratio Regum. He described a scenario in which you would try to hunt down an heirloom by figuring out who owned it and where they were buried.
Then Lord of the Rings came to mind. In LOTR, the one ring itself has a pretty convoluted story:
| SA 1600 | Ring forged by Sauron |
| SA 3441 | Cut from Sauron's hand, taken by Isildur |
| TA 2 | Lost by Isildur in a river |
| TA 2463 | Déagol finds ring in riverbed and is promptly murdered by Sméagol |
| TA 2470 | Sméagol/Gollum moves to Misty Mountains |
| TA 2941 | Ring found and taken by Bilbo Baggins... |
Wouldn't it be cool if you were tasked with tracking down the ring yourself? That's the idea: hunting down several legendary artifacts and using time travel to do it. That and simulating civilizations at war and NPCs living and dying and a bunch of other stuff.
The competition
Of course there are a boatload of time travel games, but most are extremely limited in their design.
Time travel is usually either limited to a narrative element (Bioshock Infinite), limited to a small time scale (3 days in Majora's Mask), limited to a VCR-like rewind mechanic (Braid), or limited to a small set of discrete time points (7 eras in Chrono Trigger).
I'm aware of very few, if any, big simulationist games featuring time travel.
The details
Now, how do we implement time travel? The simplest thing you could do is to save the entire game state whenever something changes. When you want to travel back in the time, simply load the appropriate game save. Going forward is even easier; just simulate the game for a given duration. Roguelikes are the perfect genre to implement time travel because the game only changes on discrete turns!
But even so, this naive approach falls down pretty quickly. By the time my game loads, it's already simulated 180,000 turns. Here's what the memory usage looks like if we assume a game save is only 1MB.
1 turn/day
* 360 days/year
* 500 years of simulation
* 1MB save
=
180GB
Uh oh. 180GB is nearly the size of my harddrive. Obviously, that isn't going to work. We need to prune the amount of data saved or compress it.
My solution was to only save variables when they changed and to track the changes individually rather than save the entire world at once. After all, I planned for most of the objects (monsters, NPCS, tiles, etc.) in the game to change only infrequently. Specifically, I used a stack for each variable. Each element on the stack has a time and a value. The current state of the world is represented by the top of each stack. Travelling to previous times just involves binary searching and truncating all stacks. For example, let's say you start fighting a monster at turn 1000. The monster's HP variable might look like this:
{time:0, hp:100}{time:1000, hp:70}{time:1002, hp:50}{time:1003, hp:10}{time:1005, hp:0}
If we time travel to turn 1004, the stack only has 4 elements and we find that the monster has 10HP.
For another perspective, see this talk by Jonathan Blow on Braid's design. Blow stores the entire world state on every frame, with some clever optimizations akin to video encoding. I'm tempted to say they're similar approaches (at least compared to the alternatives), but I'll let you be the judge.
Honestly, this part of the time travel was rather easy to design and implement. There were more thorny challenges ahead...
Concessions
My game has a fairly large world consisting of about 1.5 million tiles, 1000+ monsters, and 500 NPCs in total. To simulate all of this over the course of 180,000 turns and do it in a reasonable time (15s on my machine) required some simplifications to the game world.
NPCs take up the bulk of the simulation, so I capped the total number of living NPCs to 100 at any given time. This solves one problem and creates another: with such small populations, it becomes harder to guarantee that each civilization in the game will survive for hundreds of years. More on that later.
Except for a dozen "bosses", I don't simulate monsters during time travel. Furthermore, the monsters never die of old age. You could imagine a game with monsters who reproduced, migrated, and died, but I didn't want to take the performance hit.
One optimization I considered was simulating at 5 year intervals instead of 1 day intervals. The idea was that events would still be slated to happen on specific days, but I'd only have to handle the simulation loop for 100 iterations instead of 180,000. Long story short: that idea was a total nightmare because it was nearly impossible to tell if planned events completed succesfully. I threw it out.
Paradoxes I could care less about
Perhaps the most mind bending part about time travel is the concept of paradoxes. There's the famous Grandfather paradox where you go back in time to kill your grandfather, but now you would never have been born and never able to travel back in time. Thus paradox.
I quickly decided that I didn't want to deal with paradoxes. I decided to use the Parallel Universes cop out and say whenever you travel it's always to another universe.
However, in a weird coincidence, there were two other time travel 7DRLs this year and they both focus on paradoxes: Chronomaniac and Timegame.
The week
Things were already off to a bad start as I woke up sick the first day. Ugh! It only lasted 24 hours, but I spent most of the day with severe brain fog.
ASCII: "It'll be so easy"
I've wasted a lot of time on pixel art in years past, so I thought making an ASCII roguelike would save time. Unfortunately, I was rather confused about how to proceed. I didn't even understand where I would find the glyphs common to ASCII games, but I was pointed to Code Page 437.
That sounded great, but I couldn't find a good web font for it. Some fonts had inconsistent sizes (totally defeating the purpose of a monospaced font). After finding a decent font, I realized Chrome was rendering the fonts blurry in the canvas. I finally gave up and decided to render images (stolen from the amazing REXPaint program). All told, I wasted more time on font rendering than I did on a time travel proof of concept!
At least my screw ups were beautiful in ASCII.
World generation
This part went swimmingly. I got my hands on some noise using rot.js. I quickly added a couple gradients, combined it with the noise, and used the resulting heightmap as my world map. World generation took a few short hours.
Random number generation
As I said earlier, the kernel of the time travel mechanic was pretty easy to implement. But the devil is in the details. I had a simple constraint in mind for time travel. If you travel from year 500 to year 400, leave no trace, and then travel back to 500, things should be exactly as you left them. I specifically wanted to avoid an inexplicable "butterfly effect", at least if the player didn't do anything substantial in the past. I needed to repeatedly run a simulation involving random numbers and have it turn out the same way. So I kept track of the RNG state on each turn and reloaded it upon time travel. And I had to keep separate random number generators on hand for different purposes (simulation, combat, and rendering).
Even after that, I was plagued by the dreaded butterfly effect throughout the challenge. It would go like this: I would code for a couple hours, then realize that I had somehow introduced the effect, and then spend the next 4 hours ripping my hair out trying to figure out how to fix it.
Sometimes I forgot to reset stack variables. Sometimes I, very stupidly, put some generation code before the RNG was first seeded. However, the most pernicious bug (one I saw many times) was not resetting temp arrays. You see, some of the variables in the game are too unwieldy to save in the same manner as other data (e.g. an array of living characters). In many cases, I was recalculating these arrays after time travel and still having a problem. The cause? The arrays didn't necessarily maintain the same order! Ugh! So I spent a lot of time tracking down variables that needed to be sorted after time travel.
One thing that really helped was a unit test that would perform the repeated time travels and check to see that the world state was the same both times. I coded it late into the project, but it was a big win.
The RNG woes didn't stop there. I also ran into a problem with a lazy loading of tiles. I didn't want to generate all 1.5 million tiles in the game at once, so I tried generating them only when you first see them. But that alters the RNG. To fix this, I pregenerated RNG state for each tile at the beginning of the game.
In hindsight, I probably should have let the "butterfly effect" requirement go. Despite annoying the hell out of me, I very seriously doubt anyone would notice.
Pathfinding surprises
Late on the 5th night, I ran into another big problem.
It helps to know that the crux of my game is about NPCs going on adventures. They travel from cities to dungeons hundreds of tiles away. They descend through the dungeon all the way to the bottom. At the bottom, they try to fight a boss. If victorious, they return all the way back to their city of origin.
I was using rot.js and its A* implementation for pathfinding. I've used it before without issue. That night, however, I was asking rot to pathfind a distance of ~1000 tiles and rot was visiting over 4 million tiles to do it.
WHAT
THE
FUCK
At the time, I decided to stay up until 3am writing my own pathfinding code. It was a really dumb idea, considering that I could have fixed the rot issue with a couple lines of code. In fact, after the challenge was over, I did just that and submitted my first pull request. And it was accepted! :D
I wrote more about the pathfinding issue and created a little demo here.
Civilization is also hard
Part of the world simulation involves 4 distinct races/civilizations. They fight each other for territory on the world map. Within each civilization, NPCs are born, get married, have children, wander around, go on adventures, and die. I had all sorts of hilarious problems with this.
- I didn't realize how much junk would get stacked up after 500 years of NPCs dropping items on death.
- I forgot to prevent NPCs from marrying the dead. No kidding.
- Civilizations kept dying out.
For that last one, I realized I had put too many restrictions on the NPCs. They had to be married to have children and I didn't feel like coding second marriages. Thus, the solution was a REFORMATION. No, seriously. I had to allow NPCs to get divorces and get remarried after their spouses died.
Aftermath
Because the end result was much less than what I imagined, I came close to calling this year a "failure." But I had a working game with a lot of stuff going on and so I submitted it. I polished it up over a few versions and have come up with something that I think is really fun and interesting. And yet...
While I did get a lot of positive feedback, most players could simply not figure out what the hell was going on. Almost every aspect of the game, especially the time travel, was misunderstood.
Part of that is me. I'm really bad at making intuitive games. I've failed at it time after time and it's been a consistent piece of feedback. Honestly, it pains me to have to spell things out for the player, but I'm not kidding myself here. I know I have to get better at making things that people can understand.
At least part of the confusion can be attributed to the fact that time travel is just really confusing. Anyone who has seen Primer knows that. Recently, I watched the latest GDC Experimental Gameplay Workshop. One of the developers was Chris Hazard. He's from my alma mater (go Wolfpack!) and made a crazy time travel RTS called Achron. Achron seems like one of the most interesting time travel games ever made and yet it has a 54 on Metacritic. The poor reception was due to incredibly confusing mechanics. During the GDC panel, Dr. Hazard shares a new game he's working on with the goal of "making time travel more simple." It's called "Plosh" and can be summarized as a time travel Bomberman. But despite the stated goal, I was struck by how confusing it still was. I had absolutely no clue what was going on. I hope I get to figure it all out one day.
So to summarize: time travel is fucking hard.
See for yourself by playing my 7drl entry, The Only Shadow That the Desert Knows.
Vote on HNDiscuss on Hacker News, you know, if that's like your thing.
Hitherto
Year in Review 2015Turning 10 bucks into $1600 - How I gambled against a dotcom millionaire and won
Getting addicted to game jams
Permalinks
Short: http://jere.in/15Pretty: http://jere.in/time-travel-is-hard
Oh hi there. I'm Jeremiah. I like to make stuff with code.
