Roguelike�Time Traveling

Jeremiah Reid

IRDC 2016

Oh hi there

• 7DRLs:
• A False Saint An Honest Rogue
• Golden Krone Hotel
• Dumuzid
• The Only Shadow That the Desert Knows
• I’m a time traveler from August 8, 1986

• Carousel Mondays
• The last remnant of my youth

Itinerary

• The landscape of time travel games
• How to steal from LOTR and URR
• Designing time travel
• Implementation challenges
• [You are more confused]
• Applications

Narrative games with little or no time travel mechanics

Or games limited to a simple rewind mechanic

Or games limited to a small time scale

Or games limited to discrete eras

Screw that

Pass “RR” and collect ideas

• URR – Mark R Johnson
• Largely a mystery game
• Anecdote about tracking an heirloom down to a specific cemetery
• LOTR - J. R. R. Tolkien
• 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...
• GOT - George R. R. Martin

Artifact names

• [WEAPON] of [FIRST NAME]
• [NOUN] [NOUN WITH NEGATIVE MEANING]

Design issue: Paradoxes

• Grandfather paradox
• Option 1) Parallel universes to the rescue!
• Also, ignore previous yous
• Option 2) Avoid paradoxes or you lose:

Timegame & Chronomaniac

Derrick Creamer & Elliot Bonneville

Expanded Novikov self-consistency principle

• “Seth Lloyd and other researchers at MIT have proposed an expanded version of the Novikov principle, according to which probability bends to prevent paradoxes from occurring. Outcomes would become stranger as one approaches a forbidden act, as the universe must favor improbable events to prevent impossible ones.”

Design issue: Fragging

• Player is removed from world during travel
• What happens when they come back and..
• Their location now has a solid wall?
• Their location now contains a person?
• You can either kill the player or…
• Destroy the thing in their location (“timefragging”)

Design issue: Calendar

• Hundreds of years of simulated history
• 1 turn == 1 day
• 12 months/year
• 30 days/month
• 360 days/year
• Resting to full HP can take a year!
• Seasons, but no day/night cycle

• [gif with seasons]

https://twitter.com/humbit/status/708309428953620481

​

https://twitter.com/humbit/status/708075989763559425

​

Braid’s Design

• GDC Talk
• Save entire world state on every frame
• Compression similar to video encoding
• Keyframes every 2s
• Alternatives considered:
• Reversible events
• Interpolation
• Deterministic particles, calculated not stored

TOSTTDK Design

• Naïve approach: save world state every turn
• 180,000 * 1MB = 180GB
• Instead:
• Only track changes & track things separately
• Everything is a stack!
• NPCs have position log, HP log, “event” log
• Also considered interpolation
• Simulate at 5 year intervals instead of 1 day
• Pathfinding is a nightmare, might be intractable

Forward time travel

• Simply simulate each turn until selected date
• Exactly like playing the game…
• Except the player is removed from world
• Performance depends on how far you go

Backwards time travel

• Binary search every stack & truncate
• Looking for last change, which is new top
• Performance is constant, surprisingly good

Backwards example

0 {time: 0, HP: 4}

1 {time: 1000, HP: 3}

2 {time: 1002, HP: 2}

3 {time: 1004, HP: 1}

4 {time: 1005, HP: 0}

​

Let’s travel to t=1003

​

Backwards example

0 {time: 0, HP: 4} min

1 {time: 1000, HP: 3} mid-1 (< 1003)

2 {time: 1002, HP: 2} mid0 (>= 1003)

3 {time: 1004, HP: 1}

4 {time: 1005, HP: 0} max

​

Not found. Set min to mid

​

​

Backwards example

0 {time: 0, HP: 4}

1 {time: 1000, HP: 3}

2 {time: 1002, HP: 2} min / mid-1 (< 1003)

3 {time: 1004, HP: 1} mid0 (>= 1003)

4 {time: 1005, HP: 0} max

​

Found. Now truncate mid and beyond.

​

​

Backwards example

0 {time: 0, HP: 4}

1 {time: 1000, HP: 3}

2 {time: 1002, HP: 2}

3 {time: 1004, HP: 1}

4 {time: 1005, HP: 0}

The top of the stack is the current state at t=1003. So the monster has 2 HP.

​

​

Optimizations

1.5M tiles, 1000+ monsters, 500 NPCs total

​

• Limit to 100 living NPCs at once
• Monsters live forever
• Batch NPC actions
• Dirty log on each floor

​

360*500 = 180,000 turns

• Territory/war simulation
• Books are generated
• NPCs living their lives:
• Going on adventures (pathfinding)
• Building, marrying,having children
• About 15s to simulate history

​

​

​

​

Before the game starts…

Implementation issues

• RNG
• Civilization maintenance
• Pathfinding

​

RNG Issues

• Avoid the butterfly effect
• History should be repeatable
• RNG state has to be stored on every turn
• Multiple RNGs
• Simulation
• Combat
• Visuals (throw away)

RNGesus, why have you forsaken me?

• Kept seeing nonrepeatability during 7drl
• Fix: always use correct appropriate generator
• Never Math.random()
• Fix: don’t put generation code before seeding
• Fix: sort temp arrays

Testing for Fun and Sanity

• One test that simulates time travel repeatedly
• Debugging info from each run is recorded and compared
• Only passes if both sequences result in identical RNG state & identical debug output…
• If there is a difference, you can see exactly what caused the breakdown

Civilization fails�

• 500 years of NPCs dying and dropping items
• Forgot to prevent marriages to the dead
• Objects have to be kept around after they “cease to exist”
• Civilizations kept dying out, but why?
• Not enough babies
• No divorce allowed
• A REFORMATION
• THE DEVELOPER'S “GREAT MATTER”

Pathfinding Woes

• For a path that was 1000 tiles long...
• A* was visiting 4 million tiles
• Ruh roh

Time Travel Is Confusing!

Primer

• "Primer is hopelessly confusing and grows more and more byzantine as it unravels (I've watched it seven or eight times and I still don't know what happened)." - Chuck Klosterman

Achron

• “I have never exerted so much effort in just trying to understand a videogame. After watching hours of matches and tutorials on YouTube, reading through the game's wiki guide, and replaying missions up to five times each, I finally grasped Achron's time travel mechanic.” -Allistair Pinsof (Destructoid)

The Only Shadow That the Desert Knows

• Learned helplessness when time travel doesn't save the player
• Almost no one could follow the clues to win
• Very few figured out combat usages of time travel
• “Back To The Future has conditioned us all to expect objects we're carrying from the future to reflect the changes we're making in the past!” -TravisVZ

Ideas for better understanding

• Spell things out
• Assume the help page won't be read
• Assume the message log won't be read
• Assume modals will only be partially read
• Make changes more impressive and visible
• Cities
• Giant monsters

Applications of time travel mechanics

• Make an epic time travel game, obviously
• Add time travel as an ability in your game
• Caves of Qud
• ToME
• Replays/undos
• History
• Monsters
• Items

Thanks!

http://jere.in/stuff

@humbit

@GoldenKroneGame