2022/02/21 by Matthew Ferland, Ferland, Matthew, Vikram Kher +1
Computer Science · Psychology · Social Sciences · #Artificial Intelligence in Games #Computational Complexity (cs.CC) #Digital Games and Media #Educational Games and Gamification #F.1.3 #F.2 #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2202.10529
openalex publication_date 2022/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we give simple NP-hardness reductions for three popular video games. The first is Baba Is You, an award winning 2D block puzzle game with the key premise being the ability to rewrite the rules of the game. The second is Fez, a puzzle platformer whose main draw is the ability to swap between four different 2-dimensional views of the player's position. The final is Catherine, a 3-dimensional puzzle game where the player must climb a tower of rearrangeable blocks.