Keep in mind that relativity doesn't just change where things appear to be, but also how fast they're moving, how big they are, and how much mass they have. As your speed increases,
so does your mass. Additionally, you get
contracted lengthwise along the direction of travel, and your clocks appear to
run slower. This is all from the perspective of people watching you, of course; to you, the effects apply to everyone else (as they appear to be moving relative to your fixed position).
So I think that a game of relativistic Mario would need to be done from an observer's standpoint, so we can apply all these neat effects to Mario himself. :)
I seem to recall once seeing a Linux game that basically looked like a Mario clone with a penguin subbing in for Mario. This would've been a good five-six years ago, though, and I don't remember what it was called.