Improve replay files

[MichaelHoste]

NOW

Currently the replays are saved with :

1. positions of left_wheel, right_wheel, body, torso, upper_leg, lower_leg, upper_arm, lower_arm. And also an information about moto direction (left or right).
2. Each position is represented by x, y and angle (we only keep 2 decimals precision (1 cm) to create smaller files and smaller network communications. And separators are needed to separate all the numbers.)
3. 10 frames par second for replays are a good compromise (one frame every six). The other frames are interpolated when the replays are run.

Size : So, for every minute of replay, we need about 9 moto parts x 3 values x 6 chars ("00.00" + separator) x 10 frames x 60 seconds = **~ 100ko** of disk space.

We save about half of this size by compressing with lz-string but it's not enough if we want to have millions of saved replays

And while it works fine, we may have a problem when we'll introduce physics elements in the level because each of the "movable" element will need to have all its positions saved as well !

Pros:

• It's already working.
• It's really fast to run a replay (no physics recalculations).

Cons:

• Heavy replay files (100ko/min)
• Cheat-friendly (No really easy way to know if a replay if legit)
• Doesn't work if other physics objects in the level (boxes, elastic bridges, etc.).

Improved solution?

Since the physics of the game is created so that it doesn't depend AT ALL on the framerate and is always fixed as 60 steps/second, we should be able to re-create every replay with only the player's inputs (up, down, left, right, space).

Pros:

• Light replay files.
• More difficult to cheat (replays are legit since the physics are computed again each time).
• Work well with other physics objects in the level (boxes, elastic bridges, etc.).

Cons:

• Slower to run replays (but don't seem critical)

Solution 1

We know that each input is either true or false, at anytime (a key is pressed or it is not). So we could consider storing inputs in binary format with a small library like bitview.js.

We'll need only 6 bits per physics step : up, down, left, right, space and another bit for a potential future input (like a boost). In this situation, we must save each one of the 60 steps per second.

Size : 6 bits x 60 steps x 60 seconds = 21600 bits = 2700 octets = 2.6ko. About 40 times less than the previous format !

And with this solution, we can introduce movable physics elements without even thinking about saving them since the physics engine will reproduce exactly the same behaviour without any additional information.

The only counterpart is that it will need more CPU power to re-generate the new positions of the ghosts. But Box2D is fast and the drawings are much more CPU intensive.

Solution 2

Instead of keeping the "true" or "false" information of every input at each step, we could try keeping only the changes of these inputs.

If the player start pressing "up" at step 100 and stop at step 120, and then press again at 159 and stop at 201, we could only save :

{ 
  up_pressed: [100, 159], 
  up_released: [120, 201]
}

It could be interesting since there will have far less actions than steps. According to my tests, there are about 200 input changes every 60 seconds. A rate of about 3 or 4 by second.

If we store the replays like this 100,159|120,201,... and supposing replays are shorter than 3 minutes (so steps of less than 4 digits) with a separator.

Size: (4 digits + 1 separator) x 200 = 1000 octets = 1ko. Even less than the previous format without even using binary representation!

And we still can compress with lz-string to save about 50% of the final size. We get to a point where we could store the replays in the DOM of the web pages and not getting them by additional HTTP requests.

Solution 3

Same as solution 2 but instead of storing up_pressed: [950, 1010] where the up key is pressed at step 950 and then 1010, we could store as up_pressed: [950, 60] for the same behaviour, where each number represents the delta since the last action.

In this simple example we gain 2 digits/octets on the final representation.

[MichaelHoste]

Non-deterministic behaviour

The solution 2 was implemented but we had a serious issue: Box2D is non-deterministic [1, 2, 3] and some very small differences between simulations created situations where the moto crashed at random different places before finishing the level (usually after about 30 seconds on complicated levels)

[1] http://box2d.org/forum/viewtopic.php?f=3&t=5453
[2] http://www.box2d.org/forum/viewtopic.php?f=3&t=4489
[3] http://www.box2d.org/forum/viewtopic.php?f=3&t=4614

It worked each time only in one specific situation : when creating a replay on Chrome on the first try, saving the replay on its textual representation, and then passing it in params to XMoto. The replay then worked correctly but only on the first run. If the replay was restarted using "ENTER", then the moto crashed.

On Firefox it failed almost each time (except on short-simple levels of course).

The reason is quite simple : Box2D is only deterministic for "one binary, on a specific system and if the action is taken at the exact same moment of the simulation".

In our case, it could be interpreted as "in one browser, on a specific system and only for the first run".

Solution (key-steps)

We implemented the following solution : Every x steps, we save a key-steps containing the following informations of each part of the moto and the rider :

  position:
    x:              object.GetPosition().x
    y:              object.GetPosition().y
  angle:            object.GetAngle()
  linear_velocity:
    x:              object.GetLinearVelocity().x
    y:              object.GetLinearVelocity().y
  angular_velocity: object.GetAngularVelocity()

These informations are concatenated to the inputs informations of the solution 2 and when the replay is run, each part of the moto and rider are positioned manually in the world. This solution prevents moto parts to drift off their original path because of the non-deterministic behavior.

Size: Of course the replay size increases a little bit because of this trick. But it still manageable since the key-steps can be saved with low-frequency like one time every second (60 steps). The total size of the replay (input + key-steps) is about 20ko/minute.