Talk:GSoC rewind

Rewinding SuperTuxKart

For network multiplayer it will be necessary to be able to 'restart' a race from a previously saved state (rewind). As a simple example take a client/server networking architecture. The server is at time t computing the next state at t+dt, then t+2*dt etc. At time t on a client the user presses a key. It will take some time before this information is received by the server - assume the information that the client pressed a key at time t is actually received at time t+3*dt. To correctly reproduce the result the server must now rewind to the state the race was in at time t, taking the new input from the client into account, and recompute the race till it reaches the current time t+3*dt again. The new state (e.g. new position of a kart) will then be sent to each client (which in turn will smoothly upgrade the graphics to avoid karts suddenly jumping to a new position).

To allow this kind of rewind the server has to take regular snapshots of the race state, from which it can recompute a part of the race.

This project is about adding this feature to STK. There should be a stack (or list, ...) that keeps track of the race states at various times.

The difficulty of this project is to identify the full state of a race that needs to be saved. It will include state information of:

  • karts, e.g. currently collected powerup, attached item (plus remaining time), if the kart is being rescued, ...
  • controller, especially the AI might keep track of state information like in which direction it is trying to overtake a kart, ...
  • items, e.g. if the item was collected or not, how long it might still be unavailable since it was collected earlier, ...
  • flyable, i.e. any additional item on the track like bowling ball, cake, ...
  • tracks, e.g. movable parts of the track (physical objects)
  • physics - which includes position, velocity, ... of all objects

This project needs a good design in order to make the data structures extendable. For example different game modes need different data:

  • battle mode would include number of lives,
  • follow-the-leader if a kart is eliminated or not (and the rewind might involve un-eliminating the kart)

Also the amount of data can change, for example more bubble gums can be dropped or be used up, a bowling ball can be thrown or be destroyed. Future features of SuperTuxKart might need additional information to be stored, so the design must be easy to extend. Memory management is very important (any memory leak here can easily make STK unplayable). It might be better to first determine the amount of data that needs to be stored and then to allocate one big block of memory instead of many many small allocates, which can impact performance.

Identifying the set of all state information to be saved requires studying a significant part of the code - bullet physics, kart, controller/AI, game modes, so programming experience is essential.

The actual networking is not part of this project (while we would welcome this it is too much work for the GSoC period). Instead a rewind will be simulated. Also things like smooth-moving of the graphics would be optional. Ideally some smart memory management should be implemented: store more states of (say) the last second. Older states should be gradually discarded, depending on some limit (e.g. we might not need more than 10 seconds rollback - if a delay that high occurs the client will likely be disconnected).

Yasin created a nice mind map for the replay code: http://goo.gl/Atk9A .