Celeste is PSPACE-hard

2022/11/21 by Lily Chung, Erik D. Demaine, Chung, Lily +1 · 1 citation
Computer Science · Social Sciences · Psychology · #Artificial Intelligence in Games #Digital Games and Media #Educational Games and Gamification

paper · pdf · doi:10.48550/arxiv.2211.11839

Abstract

We investigate the complexity of the platform video game Celeste. We prove that navigating Celeste is PSPACE-hard in five different ways, corresponding to different subsets of the game mechanics. In particular, we prove the game PSPACE-hard even without player input.

Cited by

• Push-1 is PSPACE-complete, and the automated verification of motion planning gadgets

Related

• PSPACE-Hard 2D Super Mario Games: Thirteen Doors
• The Legend of Zelda: The Complexity of Mechanics
• Dots & Boxes is PSPACE-complete
• 2048 is (PSPACE) Hard, but Sometimes Easy
• Defying Gravity: The Complexity of the Hanano Puzzle