Can Horror-Based Escape/Room Be Computationally Hard?
Super Mario Brothers (SMB) is a 1985 platform game that features Mario and Luigi, two Italian plumbers, whose primary goal is to rescue Princess Toadstool (the original Western princess) from King Bowser. The game consists of various levels, which are traversed with walking and jumping functions. A variety of enemies must be avoided or defeated until the final boss, King Bowser is also defeated and the Princess is saved.
Although the gameplay is simple enough, its computational complexity has proven to be harder than initially thought. SMB was already proven to be NP-hard by Demaine et al in Classic Nintendo Games are (Computationally) Hard. However, the team has attempted to prove that SMB is also PSPACE-hard in their more recent paper, Super Mario Bros. is Harder/Easier than We Thought. In this article, I will discuss the proof(s) to their theorem(s), specifically how SMB is proven to be PSPACE-hard. Based on the use of their reduction, I then replicated a similar framework and reduction for horror escape house games. I will further explain my thought process on this takeaway, as well as any other evaluations, interpretations, and questions regarding the paper.
To prove SMB-General is PSPACE-hard, the following open-door framework is used.
This framework reduces from the PSPACE-complete problem, the True Qualified Boolean Formula. It assumes that there is at least one door and crossover gadget.
NP and PSPACE Hard Framework:
- Player-controlled avatar: usually the character of the game
- A starting and exit location: Spawning point of the avatar and the point at which a level ends
- Arbitrarily oriented traverse paths: paths that connect various locations and can be taken by the player
- Crossover gadgets: a way in which players can traverse from one path to another, without leakage
- Open-close door gadgets: open or closed state, however it can only be traversed if it is in the open state
Additional elements for PSPACE-hard:
- The screen does not move in a fixed direction
- Objects that go off screen are not reset
- The location of all enemies is known by the engine
For SMB General:
- Player-controlled avatar: Mario and Luigi (second character)
- Start and finishing point: Spawn point, Flag pole
- Crossover gadgets: walking, running, jumping, crouching
- Open-Closed door gadgets: monsters (i.e. spiny, koopa, goomba)
- Traverse paths: paths within the level, which also tend to make up the level
- Off screen objects aren’t reset.
- The location and movement of the enemies are always tracked/known by the engine.
- Screen direction and movement aren’t fixed.
Just as the elements of the generalized SMB game are matched up to the PSPACE-hard framework, I want to do the same for another type of game. Granny, Piggy, Pacify, and Play With Me are all horror video games in which your main goal is to avoid the villain and make it out of the house/building alive. In order to do so, you must search the house for a variety of tools and clues to help you along the way. There are specificities to each game that I am going to leave out of this evaluation, i.e. Granny is timed over 5 in-game days, Piggy has a multiplayer version, Pacify’s difficulty increases with time as the monster becomes faster, in Play With Me you have to turn the POV camera away from the monster in a timely manner to not “see” it, etc. Instead, I want to look at the generalized versions, which I intend to just include the basic functions and implementations that are mentioned below.
For Horror Escape Room/House:
- Player-controlled avatar: main FPOV character
- Start/finishing point: start room, escape the front door of the house
- Open-Closed door gadgets: monster/villain. Locked/closed doors, safes, cabinets, etc.
- Crossover gadgets: keys, tools, supplies, clues. Places to hide/run.
- Traverse paths: rooms, hallways, doors throughout the house (level)
- Off screen objects aren’t reset.
- The location and movement of the enemies are always tracked/known by the engine.
- Screen direction and movement aren’t fixed: first-person, 3D
Ultimately, it seems like the fundamentals of these types of games are able to fit into the PSPACE-hardness framework quite efficiently. I wonder if this could lead to valid reduction, therefore, proving and confirming that these types of games could also be computationally hard. I look forward to possibly looking more into this proposition or to study the work of someone else who has/will, as well as any look at more modern games that people are coming up with and playing currently.
Both papers were thorough in their explanations. The theorems and proofs are clearly proposed and laid out, including the elements that prove them and how the games correspond. The breakdown of the difference between SMB-Standard’s NP-hardness and SMB-General PSPACE-hardness was quite helpful in understanding how SMB-General takes the problem a little farther. It also improves and reinforces the general meaning of both outside of how it is being applied in the paper.
Overall, the papers were able to successfully answer the questions they set out to answer, including the one that I used: whether or not SMB is PSPACE-complete. The detailed presentation of the proof for this problem is what allowed me to then compare and substitute general horror escape room/house games into the framework. For me, it stirred the questions: if other games they proved to be only NP-hard could also be PSPACE hard and how well more modern single-player games are able to fit into this category despite the initial thought on the difference in theme, gameplay, genre, etc.
Despite the accomplishments in Super Mario Bros. is Harder/Easier than We Thought , the authors go on to talk about a few questions that they still have. One of the questions was if reaching the flagpole of run-length-encoded constant-height Super Mario Bros. weakly NP-hard and is it also NP-complete? One of the reductions done in Section 3 of the paper relies on the assumption that there are multiple levels so they posed the question of the complexity of a single level. Does theorem 4 hold if run-length encoding for sequences of levels is not allowed (except for blocks), and exactly 100 coins grant an extra life is another question brought up by the team regarding a change in implementing the number of coins for an extra life in section 3.7. Because the PSPACE-hardness of section 4 creates unlimited sized levels, they wonder if SMB is also PSPACE-complete for levels of constant height that do not contain any of the pipes. It is also mentioned that they speculate that their proofs can be adapted to SMB sequels, which would be interesting to see as they become more advanced.
Seeing some of their questions, actually brought on one of my own. Similarly to how the team questions the complexity of a single level in SMB, I wonder about the complexity of just a single escape room rather than the entire building as most of the horror games have. In addition, the majority, if not all, the games that are addressed in both papers are 2D platform games so I wonder if there comes any change/complication with 3D games (especially with 3D platformer games because the main difference there is the 3D aspect).