TrackMania is NP-complete
  We prove that completing an untimed, unbounded track in TrackMania Nations Forever is NP-complete by using a reduction from 3-SAT and showing that a solution can be checked in polynomial time. 
Franck Dernoncourt
cs.CC