Celeste is PSPACE-hard: Discrete and Computational Geometry, Graphs, and Games

Lily Chung; Erik D. Demaine

Celeste is PSPACE-hard

Discrete and Computational Geometry, Graphs, and Games

Authors

Lily Chung
Erik D. Demaine

Keywords:

video games, hardness, PSPACE

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.

Downloads

Published

2023-12-31

How to Cite

Chung, L., & Demaine, E. D. (2023). Celeste is PSPACE-hard: Discrete and Computational Geometry, Graphs, and Games. Thai Journal of Mathematics, 21(4), 671–686. Retrieved from https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/1538