The proof is not quite complete — the paper says, "given a path in the track we can check in polynomial time whether it completes the track." But this is only t

The proof is not quite complete — the paper says, "given a path in the track we can check in polynomial time whether it completes the track." But this is only true if the path has length that's polynomial in the length of the track. So there needs to be an argument showing that if there is any solution to a TrackMania level, then there is one that's polynomial in the length of the track. I think this is straightforward in the case of TrackMania but it needs to be spelled out. In other motion-planning games — for example, Sokoban — there can be levels that require an exponential number of moves. A quick sketch of how you might argue it. There are polynomially many states for the position, heading, velocity and other attributes of the car. Although there are exponentially many states for the n checkpoints, any given run can only visit n of them (because the checkpoints cannot be reset). Hence any given path can visit at most polynomially many different states, and so for every path there's a path of polynomial length that reaches the same end state (just cut out the portions of the path between identical states). Hence if there's any path that completes the level, there's a path of polynomial length that does so.