Boulder Dash

A single-player game in which the character digs through a rectangular grid to find diamonds within a time limit, while avoiding various dangers.

Screenshot of Boulder Dash

Description

Boulder Dash is a single-player game where a character (a man named Rockford) moves in a square grid, controlled by the player.

A level is a square grid of $n \times n$ tiles and a target number $d$ of diamonds to collect. When a level starts, each tile can either be empty or contain one of:

Time is discretized, and the game’s state updates at fixed intervals. At each time step:

Rockford can move through empty tiles, diamond tiles, or dig through dirt tiles, leaving them empty. If he moves into a diamond tiles, he collects the diamond (turning the tile into an empty tile). If he moves horizontally against a rock which has space on its other side, the rock is also pushed horizontally to allow Rockford to take its place. Enemies follow the borders of empty tiles in a clockwise pattern. This pattern is predictable, but not fixed: if a border that was blocking an enemy disappears, the enemy will go through it the next time it arrives there. If the player “frees” an enemy by digging through a tile that previously blocked its path, the enemy will go through it the next time it reaches that place. No entity can pass through or affect unbreakable rocks.

If a rock is in the tile above an enemy or Rockford, and has been falling for at least one time step, it “kills” the entity below: if the entity was an enemy, it is replaced with a diamond; if it was Rockford, Rockford dies.

Ending a level

When $d$ or more diamonds are collected, an exit door appears. Reaching this exit door wins the level.

Rockford dies (loses one life and starts over) if:

Initially Rockford has 3 lives, and more can be gained while playing. When no more lives are left the games is lost.

Computational complexity

The problem of deciding whether a level of Boulder Dash is winnable is NP-complete. This has first been proved by [2], then by [1] using a simpler method.

[1] shows that Boulder Dash levels implement single-use paths and location traversal (meaning that the player must visit a set of locations to win). This allows reduce the Hamiltonian cycle problem to a Boulder Dash instance in the following way: Choose any undirected $3$-regular graph $G$; choose a vertex $v$ of $G$, to which we attach a new vertex $u$. Starting from $G$, build a Boulder Dash level where:

An earlier proof was given in [2], based on Boulder Dash’s similarity with other block-pushing games without gravity. [2] shows that Boulder Dash levels can contain four constructions (one-way paths, forks, XOR crossings, and NAND crossings). This lets them apply [3]’s proof that block-pushing games featuring these constructions are NP-complete, which uses a reduction from $3$-coloring.

References

[1] Giovanni Viglietta, “Gaming is a hard job, but someone has to do it!”, Theory of Computing Systems, 2014.

[2] E. Friedman, “Pushing blocks in gravity is NP-hard”, 2002.

[3] E. D. Demaine, M. Hoffman, “Pushing blocks is NP-complete for non-crossing solution paths”, in CCCG 2001.

[4] M.R. Garey, D. S. Johnson, R. E. Tarjan, “The Planar Hamiltonian Circuit Problem is NP-Complete”, in SIAM Journal on Computing, 1976.

@misc{cog:boulder-dash,
    author = "{CoG contributors}",
    title  = "{Boulder Dash --- Complexity of Games}",
    year   = "2020",
    url    = "https://www.isnphard.com/i/boulder-dash/",
    note   = "[Online; accessed 2020-02-20]"
}