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, respectively, while the
“traverse” tunnel can be traversed if and only if the door is in
the open state. We prove that it is PSPACE-complete to decide whether an
agent can move from one location to another through a planar assembly
of such door gadgets, removing the traditional need for crossover gadgets and
thereby simplifying past PSPACE-hardness proofs of Lemmings and Nintendo games
Super Mario Bros., Legend of Zelda, and Donkey Kong Country. Our result holds
in all but one of the possible local planar embedding of the open, close, and
traverse tunnels within a door gadget; in the one remaining case, we prove
NP-hardness.
We also introduce and analyze a simpler type of door gadget, called the
self-closing door. This gadget has two states and only two tunnels,
similar to the “open” and “traverse” tunnels of doors,
except that traversing the traverse tunnel also closes the door. In a variant
called the symmetric self-closing door, the “open” tunnel
can be traversed if and only if the door is closed. We prove that it is
PSPACE-complete to decide whether an agent can move from one location to
another through a planar assembly of either type of self-closing door.
Then we apply this framework to prove new PSPACE-hardness results for several
3D Mario games and Sokobond.