Heh, this grid image is all too familiar to me right now.
I’m building a grid based game and engine, and I have a game replay format which is not video.
I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution.
Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second…
What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game?
It’s an extremely fun problem to solve. I tried:
- encoding changes into bits eg using 2 bits for direction
- movement pattern batching (ie batching 2 moves into 3 bits)
- crowd patterns and movement prediction
- treating movement as a “projectile” and deriving intermediate states
And all sorts of other wild crap that I will write up about on game launch
What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.
Yes you are definitely onto something! Love to see more people talking about deterministic games.
My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations
That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB
How much did your clever approach save over a naive approach + file compression?
I will post back with real numbers tonight, but naive approach did not compress well at all (KB easily).
But of the “smart” approaches (pre compression):
- 5 move motif over 2 bytes - best
- 2 move motif - insanely small
- 2 move motif with non linear tick delta even better
- “naive” 1 byte cardinal directions (worst)
- less-naive - byte relative direction changes (middle of the pack)
—-
But post compression with brotli the naive approach was second best and the less-naive approach was first (2-10% better than naive), I was so bummed that the better ones didn’t compress as well (about 10% worse than second best on average)