# Ghost replay - storage and timing

I am working on a car race game and just implemented a ghost sprite for replaying past races. I use a physics engine and after much reading I came to the conclusion that the best way to store the ghost data for replay would be to record the car's position and rotation at given timepoints, as for example described here: https://gamedev.stackexchange.com/a/8380/26261.

But what would be a good way to find those timepoints during replay? An example would be a record with this data:

time: +3.19932 (seconds since race start)
position:  180,40 (position at that time)
rotation: 30.4 (rotation at that time)


But I have several problems with that:

1. When I replay, it's unlikely that I reach the exact timepoint at 3.19932 again - more likely, I will have a timepoint around 3.1 and have to find the closest matching record. When interpolating, even the closest matching above and below. This sounds very inefficient and time consuming?

2. In which list structure could I store these records for a later replay? An array? Doesn't that mean that search time for records matching a certain time will increase the longer the race is?

3. Which frequency should I use for timepoints? Each frame would be -I guess- overkill, rather I should save i.e. every nth frame and interpolate in between, which makes the storage questions in 2. even more difficult.

So is this idea even the right approach? If yes, how could I efficiently store and retrieve the data? Please note that I generally would like to go with using the data structure above, not deterministic gamestates and recording user input etc.

Thanks for any help!

EDIT: I realise I should describe the environment I use: Cocos2D for iPhone. There is a method update:(ccTime)delta. Ideally, this method would be called every 1/60 seconds, but there is no guarantee - delta is the actual time passed since the last gametick and could be a lot more or less than 1/60. It is in this method where I would like to store the current gamestate.

• Excellent question. As this shows, a precise replay is more complex than you might think at first, and I'm curious to see what solutions people have come up with here. – Christian Feb 13 '13 at 10:40

Doesn't that mean that search time for records matching a certain time will increase the longer the race is?

Nope :)

Say you store it as an array (note the snapshots are in chronological order, but not evenly spaced):

snapshots = [
{time: 0.0, position: {x,y,z}},
{time: 0.41,    position: {x,y,z}},
{time: 0.57,    position: {x,y,z}},
{time: 1.10,    position: {x,y,z}},
{time: 1.67,    position: {x,y,z}},
{time: 2.05,    position: {x,y,z}},
{time: 3.24,    position: {x,y,z}},
{time: 3.86,    position: {x,y,z}},
{time: 3.91,    position: {x,y,z}},
{time: 5.42,    position: {x,y,z}},
...]


Then, when the replay/game starts, you get the first and second element from the array:

nextIdx = 1
previousSnapshot = snapshots[nextIdx-1]
nextSnapshot = snapshots[nextIdx]


Then in each frame (currentTime is the current time in this new game):

if currentTime > nextSnapshot.time
nextIdx++
previousSnapshot = snapshots[nextIdx-1]
nextSnapshot = snapshots[nextIdx]

# Do your magic here, e.g.:
snapshotPairGap = nextSnapshot.time - previousSnapshot.time
ratio = (currentTime - previousSnapshot.time) / snapshotPairGap
ghostPosition = {
x: previousSnapshot.position.x + ratio*(nextSnapshot.position.x - previousSnapshot.position.x)
y: previousSnapshot.position.y + ratio*(nextSnapshot.position.y - previousSnapshot.position.y)
z: previousSnapshot.position.z + ratio*(nextSnapshot.position.z - previousSnapshot.position.z)
}


Of course this could be optimized by caching some of the calculations. There's no searching through the array, just looking up specific indices.

• YES! I have to try this out later, but this seems to be what I was looking for. Thanks!! – marimba Feb 13 '13 at 15:16

It's not too hard. You can store your data at arbitrary points in time (the more, the better), and you can interpolate the values of the data based on the timestamp you're looking for and the data from two closest recorded timestamps, e.g.:

N | Time | Position | Rotation
1 | 0.05 | 1, 1, 1  | 0
2 | 0.15 | 1, 2, 1  | 0
3 | 0.25 | 1, 3, 2  | 30


Now imagine you want to get position and rotation at time 0.10. As 0.10 is between points '1' (meaning 0.05 time) and '2' (meaning 0.15 time), you need to interpolate these.

timestamp = 0.10
factor = (timestamp - Time[1]) / (Time[2] - Time[1])
position = Lerp(Position[1], Position[2], factor)
rotation = Lerp(Rotation[1], Rotation[2], factor)


Lerp is just linear interpolation.

So let's fill the gaps with some examples (*).

N | Time  | Position    | Rotation
1 | 0.05  | 1, 1,    1  | 0
* | 0.075 | 1, 1.25, 1  | 0
* | 0.10  | 1, 1.5,  1  | 0
2 | 0.15  | 1, 2,    1  | 0
* | 0.20  | 1, 2.5,  2  | 15
3 | 0.25  | 1, 3,    2  | 30


HTH.

• +1. Interpolation is the simple and effective answer here. It might be true that cubic interpolation might give slightly better results when the vehicle is turning but linear will work well if the intervals are small enough. – Kylotan Feb 13 '13 at 12:56
• Thanks for showing how to interpolate! This will be very useful for my game. But let's say I would like to retrieve at time 41.15, deep inside the array. Would you start searching through the entire array until you found a record > 41.15? – marimba Feb 13 '13 at 13:18
• A simple linear search could work for you, but binary search is better, when you have a sorted array: en.wikipedia.org/wiki/Binary_search_algorithm – Marcin Seredynski Feb 13 '13 at 13:33