Remember games such as Ninja Gaiden and Castlevania? Sure, they were great fun, but they were also responsible for those nights that had you rocking the foetal position in a corner, after spending way too much time just trying to clear that one perfect jump.
It’s an experience that most games have scrapped in the modern age, preferring to let players choose their own difficulty settings, from easy as pie, to nostalgic insanity challenge modes.
Belgian scientists sat down with a bunch of old games recently, such as Super Mario Bros., Donkey Kong and Metroid in order to study this, and (SURPRISE!) it turns out that older video games were indeed far more difficult than their contemporaries today.
Greg Aloupis, Erik D. Demaine and Alan Guo, from the Free University of Brussels, researched several of these classic games, eventually coming to the conclusion that most of them could be classified as “NP-Hard”, a scientific term that means that a problem cannot get any harder.
They’ve released a paper on their findings, which shows that a lot of effort went into the project. Here’s what they had to say about Pokémon;
The no-reverse gadget serves a similar function as the one-way gadget, except after traversing from a to b, the player cannot traverse it from B to A. This is implemented by the gadget in Figure 21. Clearly, the player cannot enter via b, because that lures the weak Trainer to block the passage.
Suppose the player enters through a. They can safely walk to b, because the weak Trainer is blocking the bottom strong Trainer’s line of sight. However, to reach B, the player must lure the weak Trainer out of the line of sight of the strong Trainer, hence the player may never return in the reverse direction.
And on those infamous sliding block puzzles from The Legend of Zelda;
Generalized Legend of Zelda is NP-hard by reduction from a puzzle similar to Push-1, because Legend of Zelda contains blocks which may be pushed according to the same rules as in Push-1 , except that in Zelda, each block may be pushed at most once.
Fortunately, all of the gadgets in the reduction for Push-1 found in  still function as intended when each block can be pushed at most once, with the possible exception of the Lock gadget. However, a simple modication to the Lock gadget (illustrated in Figure 11) suces. (Here we assume that Link has no items, in particular, no raft.)
I’m only pretending to understand what they’re talking about, but if you’re interested in reading more of their findings for yourself, while presumably nodding in silent agreement while stroking your chin to a fine point, then head on over to the Cornell University Library.
Last Updated: March 14, 2012