The most efficient way to roll back data. To get the time back

Question

So, I have a 3d platformer. And I want to have a button that, if you hold it, makes you "go back in time." Fortunately, the game is quite simple and has only one essence, so the only thing that needs to be saved for each frame is this.

struct Coord { float x; float y; float z; } structure Bool6 { bool front; bool back; bool left; bool right; bool top; bool bottom; } struct Player { Coord Pos; Coord Vel; Bool6 Col; } 

But I'm afraid that this is a lot of data, especially because my game theoretically goes somewhere around 60 frames per second, and it would be nice to have 5 seconds or so (300 frames) of data that could be obtained by reverse viewing . I reviewed every frame doing something like this

 Player Data[300]; for (int i = 299; i > 0; i--) { Data[i] = Data[(i-1)]; } Data[0] = "THIS FRAMES DATA"; 

However, it seems that this means that an outrageous amount of processing power occurs only when each frame is saved.

Is it a more efficient way to store this data, keeping all the data in order?

Also their way I can tell the array slot is that it has nothing? So what their problems arent if the player tries to rollback before all the slots of the array are full or after rollback? I believe in C #, I would set it to NULL ... but this does not work in C ++, probably because im uses structures.

Thanks a lot!

Answer 1

However, it sounds like it means an outrageous amount of processing power

Before making such a statement, it is useful to do the math. It seems that the data you are worried about is about 40 bytes, so 40 * 300 = 12 kB. It fits easily into memory and is far from the "outrageous amount of computing power" on modern computers.

Is it a more efficient way to store this data, keeping all the data in order?

Yes. If your game is deterministic, all you need to save is the player’s input and one game state 5 seconds ago. When rolling back, reset the game state and play user inputs to recalculate the data of each frame.

See this question for an interesting discussion of how to create your own play system in gamedev stackexchange.

Answer 2

I don’t think that an array of 300 relatively small elements will slow you down at all, have you tried to profile it?

However, you can save it in a vector and save the iterator in the “current” and update it.

Answer 3

If you think that you can store 300 a lot, store less, for example, you can store 1/5 frames:

....|....|....|....|..*

 * is your position, `/` the frames you will store and `....` other frames 

and you don’t need to copy all the saved data every time ... just delete the first one and add one to the end, you can use std :: list, you don’t have to copy any data

In every 5 frames, you call myList.pop_front(); oldest frame and myList.push_back(); the newest

Answer 4

I don’t think the storage requirement is extremely harsh - even with 300 frames this small object will take up much less memory than your average texture.

I suggest that you avoid using an raw array and look at using std :: vector, which will be almost as efficient and will automatically resize as you need more buffer space (so if you suddenly need 8 seconds or fps reaches 100 you will not suddenly run out of buffer space). It also eliminates your difficulties with empty slots, since the vector has a known size with which you can effectively access.

I can also assume that you do not need to store every frame - games like Prince of Persia that do this trick, if you keep a close eye on them, are much less smooth when time runs back, indicating that they, perhaps they only store a few frames or something like twice a second, unlike every frame.

Answer 5

• If you don’t work on the MCU, the data size (given the structures provided) will be small compared to the rest of your game (~ 10K, if I calculated it correctly, nothing for a modern PC).

• The processor, moving the data in the way that you specified, and on each frame, MAY be suboptimal (it will move around 10K 60 times per second or 600K per second, which MAY, although it probably will not be noticeable). IF this is a concern, I would go for a circular buffer (like in boost :: circle_buffer) or for std :: deque or std :: list (with deque probably being my first choice); they all have O (1) insertion / deletion time, and insertion / deletion is what you need most of the time. Theoretically, there is also the option to use memmove () to speed things up without significant changes, but it is quite error prone and still has O (N) complexity, so I would prefer not to.

Answer 6

Indeed, you can do fewer operations for each frame to maintain state.

You can use std::vector . Then in each frame push_back() new state and if(vector.size() > 300) , then do pop_front() .

If you think this is not enough, just save less often (every half second). When you roll back your information, you can interpolate between the values.

---

Edit:

you're damn right Otman, the vector does not have pop_front, so you can use vector.erase (vector.begin ()) :) So you do not need to use linked lists.