Union-Find is a fast, highly efficient way to determine if two items have a common ancestor. The two operations, union and find, operate in effectively linear time. I made a single-file Rust implementation that is available for download here: https://gist.github.com/JosephCatrambone/19c3c3ef278c7a175f4acfae81f24d46
At the close of my earlier update I mentioned wanting to try 'Tracer-style' time travel where only the player moves backwards and everything else stays in place. I gave it a go and got it working, but it wasn't particularly interesting. It was basically just the player moving in the opposite direction. Animation could probably jazz that up, but a more fun idea came to me in the middle of a sleepless night:
Seeing the future.
Trivially, if everything in the world rewinds and the player can make different decisions, that's basically seeing the future. And that's what I built:
It's not perfect. You'll notice that the dynamic cubes retain their velocity after the time rewind happens, but that's solvable.
Here's how it works: there's a global time keeper which records the current tick. The base class has three methods (_process, get_state, and set_state), and two variables (start_tick and history).
The global time keeper sends a signal when time starts to rewind. During the rewind process, each tick is a step backwards instead of a step forward. The _process method of the base class checks to see if a rewind is active and, if so, calls set_state(history[global_tick]). If rewind is not active, we append or update the history. There's some nuance to tracking deltas and despawning, but really that's about it. Simple, eh?
"Your theme is... 60 Seconds!"
And so the brain storming begins. I feel like anything that doesn't explicitly involve time-travel of some sort will get dinged by the Theme-Adherence police, and besides, time travel is fun.
I've never made a game with time travel before, but it presents plenty of opportunities to do novel things. At the very least, even if the mechanics aren't original, I can do things like make the player character switch from replay to AI-driven if the player interacts with his/her previous self or force players to avoid interacting with their previous selves by avoiding line-of-sight and such. All of this is predicated on Terminator-style time travel, where the player goes back into a previous timeframe and can never return to their original. Minute Physics calls this "new/changed history" time travel and I'd call it 'forked history' time travel. The other form would be self-influencing time travel, where you happen to see yourself from the future coming in to your present.
I tried a lot of architectures. It began with the simplest thing I thought would work: A controller component would record keypresses and emit signals. The parent object would listen for signals on the child component and act as though it were receiving input. This worked, but it was hard to jump to a specific point in time.
The next thing I tried was a 'global manager'. Each actor had a 'get state' and 'set state' method. In record mode, actors would append to their history. In replay mode, they'd pull from history and set state. Things got complicated when it came to handling travelling backwards in time and then interacting differently. It was easy to go back to a time and replay, but it wasn't easy to go back, replay, and record at the same time. That part was necessary if we wanted to see ourselves and interact in tandem.
The third thing I tried was similar to the first. Each actor would be a deterministic function of time. We 'set time' which consists of taking the time and setting state accordingly. Functions are determined as only a function of the current timestamp. That works fine. After playing with it, however, it's really hard to make puzzles for it.
I'm going to try the Tracer-style time travel thing where the player can go back 60-Seconds into their previous state while the world stays as it is. This is closer to the self-consistent/non-branching timeline.
Thematically, I really want to rip off Zero-Wing and do a terrible translation of the plot. Character has a time-travel device that sends him/her back 30 seconds, but it has a 60-second recharge. The player got a lethal dose of radiation and needs to go back to save him/herself. The goal is to get past unity and into the net-time-gain territory. Either a recharge of 29 seconds or a jump of 61 seconds.
The teller slides a plain brown box across the counter and tells me the total with a smile. I mirror it and hand over my card. In the brown box is a stack of tracking markers -- the product of a brief flash of inspiration. If you've ever spent some time doing camera matching in Blender, you'll know that it can be a boring, tedious process that's wrought with false starts and disappointments.
A few well constructed, highly visible tracking marker can solve most of these headaches, and while one doesn't always have control over the footage, when it's possible to add them in, the effort-to-return ratio is immense.
I decided to try my hand at making up a marker with the (albeit limited) knowledge I have about camera tracking in Blender, OpenCV, and general image processing. In the interest of brevity, all of the important details are condensed in the image below:
I have not yet tested this marker, but I'll be able to put it through the wringer in a short while. Until then, if you'd like to print your own and give it a whirl, I've included the full multi-resolution SVG here.
I put together this halftone shader effect in Blender earlier today:
The key realization for me was that Blender's shader nodes allow you to use Diffuse BSDF or other shaders as inputs to your setup. This means we can take the lightness of our mesh and use that as an input to a color ramp with a step function in it. In more detail, here's the shader setup:
I'd wager a more skilled artist could replace the dot-pattern generator with something that gives more consistent result and doesn't have that semi-circular banding issue. Give it a try and let me know if it works out for you.