We prove PSPACE-completeness of the well-studied pushing-block puzzle Push-1F, a
theoretical abstraction of many video games (introduced in 1999). The proof also extends to …

A door gadget has two states and three tunnels that can be traversed by an agent (player,
robot, etc.): the" open" and" close" tunnel sets the gadget's state to open and closed …

Recent work has developed a theory of motion-planning gadgets, which are a useful tool for
proving hardness for a variety of problems that can be thought of in terms of an agent …

This thesis develops a framework for proving computational complexity results about motion
planning problems. The model captures reactive environments with local interaction. We …

In this paper, we explore how agent reachability problems from motion planning, games,
and puzzles can be generalized and analyzed from the perspective of block asynchronous …

Recursed is a 2D puzzle platform video game featuring treasure chests that, when jumped
into, instantiate a room that can later be exited (similar to function calls), optionally …

The computational complexity of agent-based boxpushing puzzles on grids is well-studied.
In particular, the video game Sokoban was shown to be NP-hard, and later PSPACE …

We consider the computational complexity of constant-area levels of games which allow an
unlimited number of objects in a fixed region. We discuss how to prove that such games are …

We examine the computational complexity of turnstile puzzles, which are grid-based tour
puzzles with walls and turnstiles. A turnstile is a wall that can be rotated in 90 increments …

We consider the problem of safely unstacking rectangular boxes through the lens of Megalit
(ASCII, 1991). In this Game Boy game, the player is confronted with a pile of 1-by-k and k-by …