Paper by Erik D. Demaine

Reference:

Lily Chung and Erik D. Demaine, “Celeste is PSPACE-hard”, Thai Journal of Mathematics, volume 21, number 4, December 2023, pages 671–686.

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.

Comments:

The paper is also available as arXiv:2211.11839 and from the journal.

Availability:

The paper is available in PDF (844k).

See information on file formats.

[Google Scholar search]

Related papers:

Celeste_TJCDCGGG2021 (Celeste is PSPACE-hard)