Without having time to read the paper, this seems like a proof by obscurity. It's very conceivable that this problem is solvable in polynomial time with very high bounds. The problem is also so vaguely worded that it is practically meaningless, and the interpretation of "how the game designers intended" is also ambiguous.

The collection of games is also odd. Is Pitfall NP-complete? What about how Pitfall was designed to be played? Is Tetris NP-Hard? Is it even hard? ...

What about Minesweeper? Or Pong?

In particular, this article heading totally disregards the result from the first section:

> We can obtain some positive results if we bound the "memory" of the game. For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time: the state space is polynomial in size, so we can simply traverse the entire state space and check whether the goal is reachable. Similar results hold for the other games if we bound the screen size in Donkey Kong Country or the room size in Legend of Zelda, Metroid, and Pokemon. The screen-size bound is more realistic (though fairly large in practice), while there is no standard size for rooms in Metroid and Pokémon.

So already revising the definition of the games themselves.