Exact Finishing Time

The Exact Finishing Time algorithm is the algorithm used by Mario Kart Wii to compute the player's finishing time accurate to 1 millisecond. Mario Kart Wii's physics runs at 59.94 frames per second which means the player's position is only calculated every 16.683... milliseconds of game time. In order to calculate the final time of a player in a race or time trial, the game then applies the algorithm described in this article. The algorithm runs whenever any player's lap count increases.

Algorithm

The game computes the player's position each physics frame. On the final frame of a player's lap, the game will notice that the player is now in the first Checkpoint of the next lap, having not been just in it in the previous frame. This implies the player crossed the finish line between that frame and the previous one. The game then computes how far the player moved in the frame of 16.683... milliseconds and then divides this distance by 16.683... to compute the distance the player travels in 1 millisecond. Finally it repeatedly adds the distance the player moved in 1 millisecond to the player's position on the previous frame to work out the first millisecond at which the player was beyond the finish line. The game does this computation based on the line, not on the checkpoint quadilateral. The game considers the final time of the lap to be the first millisecond at which the player was beyond the finish line. This means if the player's exact finishing time was 1:43.6871 the game would report the final time as 1:43.688, because this is the first point at which the player is beyond the finish line.

The method which does this computation is located at 80511ec8 PAL. This corresponds to the following pseudocode, which maintains the exact floating point operations of the game's code. All operations are performed using single precision floating point representation.

# The player's position last frame (track coordinates).
input vector2d oldPosition;
# The player's position this frame (track coordinates).
input vector2d newPosition;
# The finish line's centre (track coordinates).
input vector2d lineCentre;
# Normal vector of the line's direction (perpendicular to the checkpoint line).
input vector2d lineDirection;

# Player's movement per millisecond.
vector2d velocity = (newPosition - oldPosition) / 16.683350017;
# Displacement to the line.
vector2d displacement = oldPosition - lineCentre;

for milliseconds = 1 to 16
    # Compute position at millisecond.
    displacement += velocity;

    # dot computes the dot product; distance in a given direction.
    if (dot(displacement, lineDirection) >= 0) then
        return milliseconds;
    end
end

return 17;

Criticism

There are three bugs/problems with the above algorithm. Firstly, the game will always round times up to the nearest whole millisecond. Based on the position and speed of travel, the exact finish time could be computed to infinite precision. Thus, a situation where the game rounds the time up may be possible, but the closest representable time would be rounding down. For example, if the player crosses the line at 1 nanosecond after 0:59.999, the game will round the time up to 1:00.000.

The second problem is that this algorithm is subject to a compound rounding error. Like most processors, the Wii's processor uses IEEE 754 floating point representation to store decimal numbers. This is not infinitely precise, instead offering around 7 significant figures of precision. This means that every operation in the code will round the result. Because the code operates by repeated addition, it is theoretically possible for a compound rounding error to cause the wrong answer to be reached. That is to say, the player may accurately cross the line at 0:59.999999999... which ought to be represented as 1:00.000, but due to compound rounding error the game would represent it as 1:00.001.

The third problem is that this code does not consider the start line checkpoint to be a quadrilateral; instead only counting it as an (infinite) line. This is not accurate to the rest of the game's logic. This means if the start line quadrilateral is entered from the side, the algorithm will bug out and return 1 or 17. This situation frequently occurs on Coconut Mall in the glitch time trial on lap 2.

CTGP Revolution

CTGP Revolution contains a workaround for this bug in its time trial mode. The game's original code is run and reported as normal, but additionally, a simple distance based division is run to calculate the 'true' finishing time. This divides the distance to the start line by the player's velocity in that direction to produce an exact time difference. This is also subject to rounding error, so is not infinitely accurate, but is accurate to around 12 significant figures. This algorithm still suffers from the problem caused by checkpoints being quadrilaterals.