Say hello to a scientific analysis of how mathematically hard some classic games are.|
Location traversal and single-use paths, ala Pac-Man, is NP-hard. Pressure plates, ala Prince of Persia or Portal, is PSPACE-hard if there are two pressure plates, and NP-hard if only one is required to open a door. In the case of switches, one switch is P-hard, two is NP-hard, and three or more is PSPACE-hard.Regrettably, they don't have categories for games like Ninja Gaiden 3 or the original Castlevania, which qualify simply as "throw your controller at the wall repeatedly in frustration, Nintendo Hard."
Viglietta then uses these characteristics to classify each of the 13 games. Boulder Dash, which involves traversing a map strewn with boulders, is NP-hard. Prince of Persia, thanks to its pressure plates, is PSPACE-complete. Doom, with its multiple switches, is PSPACE-hard (and Viglietta claims that most other FPSes and adventure games are the same).