Celeste is PSPACE-hard

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.

15 pages, 13 figures. Presented at 23rd Thailand-Japan Conference on Discrete and Computational Geometry, Graphs, and Games