Mystery Tower is Computationally Hard

We investigate the computational complexity of “Mystery Tower, ” which is a 2D-platform action puzzle video game released by Namco in 1986 in Japan. First, we formalize Mystery Tower as a decision problem that asks whether or not, in a given level, the goal is reachable from the start. Our contributions are as follows. (1) We show the NP-hardness of the problem without an enemy character. (2) In the same problem setting as (1), we show that there exists an instance such that the length of its shortest solution is exponential. (3) If the use of enemy characters is allowed, the problem is PSPACE-complete.