Efficient Algorithm for Recording gameplay's objects positions

Question

So, I have a game idea in mind, and for that I need to record the game around the player. I'me not talking about recording it as video, but rather recording the scene objects, and their positions within the game, and then render them, giving the player the ability to go back and forth, to stop time and move around.

I've made a prototype with some data structures in C#, since this is going to be the programming language we'll be using in our game, but if we want the player to be able to go back just five minutes back with the data of just 100 NPC's, it takes almost 1GB of RAM.

Right now, I'm just storing a Doubly linked list, each item with the object position. In the game, I'll need to store even more data in each node, so I need something even more ligher. Of course, this algorithm is zero optimized, but still, that is a lot.

The alternatives would be create the NPC's that aren't really important to the game when the user is viewing the past, but I don't really like it very much for the sake of realism.

I wonder if there is a better way to store this?

Thanks in advance, Scorch

Answer 1

1. Don't use a linked list, use a linked list of arrays that each have (say) 1min reserved

2. You probably don't need to be recording most frames. Recording only every 3rd frame would save a lot of space, and you could get away with less than that.

3. If your game is deterministic, you could just record the player input

4. Your position is most likely being stored as either 3 floats or 3 doubles (12/24 bytes, possible 16/32 if the memory is being padded). You could probably save some space and save them as integer shorts (short x=position.x*10). This would be lossy saving, as you would lose precision (only one decimal place if you multiply by 10, and your positions couldn't be greater than 3,276)

Answer 2

Instead of recording all object positions at every frame, just record the information you need to recalculate them. Generally, this consists of three things:

1. The initial state of the world, including object positions, velocities etc., at the beginning of the recording.

2. Player input, i.e. every action taken in direct response to player commands. (You don't necessarily have to record irrelevant details like the exact path of the mouse cursor, if that doesn't affect what happens in the actual game world. Just pick whatever abstraction of the player's actions that seems most compact and natural.)

3. Random events. In general, this can be achieved by recording the outcome of every call to the random number generator, but if you're using a deterministic PRNG, it's enough to record its initial state.

---

Note that, if you only record the initial PRNG state, any changes made to the timeline are likely to have very strong global "butterfly effects" as soon as they change the number of calls made to the PRNG, which will cause the sequence of outputs to be shifted. If you find this undesirable, you could mitigate it in various ways, such as:

• Try to make sure that each entity makes the same number of calls to the PRNG regardless of external circumstances. This may not be very practical, but I include it for completeness.

• Reseed the PRNG regularly (e.g. before each frame) from an external source (either a recorded copy of its state or a second "master" PRNG which is only used for this purpose). This will temporally limit the butterfly effect, since changes in the PRNG output will not propagate between frames.

• Give each NPC or other entity that makes random choices a separate instance of the PRNG with its own state. That way, any butterfly effects will be spatially localized to the affected entities (until, of course, these entities interact with others, which may cause the behavior of the other entities to diverge as well).

You could, of course, also combine the alternatives above, e.g. by giving each entity two PRNG instances, one of which is only used to reset the other every frame.

Answer 3

Just a thought, and this might be completely invalid depending on how you want your NPCs to operate, but if you give the NPCs/world elements a repeating pattern to execute, you wouldn't have to actually store the data of their position. Rather, take the modulus of the time and interval over which the first iteration of the pattern is executed, and base the game entities position off of that.

And if you want those entities to respond to the player, you can have their reactions begin by triggering a boolean that says this entity is no longer part of the pattern, which in turn will trigger position recording.

I've never done something like this, but it sounds like this might work. I'd be happy to hear otherwise.