Lemmings

A puzzle game where the player guides a sequence of characters to safety by assigning them skills.

Game screenshot

Description

Lemmings is a single-player platform and puzzle game.

At the beginning of a level, several identical characters (“lemmings”) appear in sequence in a predefined place. The goal is to help at least some threshold percentage of these characters reach a target location alive. The number of lemmings that appear and the threshold survival percentage are fixed and depend on the level.

A Lemmings level is two-dimensional and can contain various elements, the most important ones being:

Although the positions of characters and game elements are actually discrete (pixel coordinates), and the game advances at fixed intervals, the time and position values are fine enough that they can be assumed continuous for our purposes. Lemmings always walk and climb at the same pace. Likewise, the time taken by each action is fixed.

Lemmings initially wander aimlessly in one direction, falling off any cliffs they encounter, climbing any stairs on their path, and changing directions when they hit a wall.

A lemming can die by falling from a height above some threshold, or disappearing through the upper or lower boudaries of the level. If a lemming dies, it simply disappears and will not count towards the percentage of saved lemmings. If a lemming reaches an exit portal, it also disappears, but counts towards the threshold.

The player has a set of 8 skills that can be assigned to each lemming separately:

There is a limit to the number of times a skill can be assigned. A lemming that is assigned a skill will act accordingly as long as possible, then start wandering aimlessly again. For example, if a lemming is assigned the Digger skill, it will dig down until reaching an obstacle it cannot cross, or empty space. At this point, it will go back to its walking state, and won’t start digging again, even if it reaches a place where it can (unless the player assigns it another digging skill).

At any point, the player has the option to apply the Bomber skill to all remaining lemmings, though this is mainly useful to end a level early when the outcome has become obvious (threshold reached or unwinnable situation).

Ending a level

A Lemmings level ends when there is no lemming left, i.e when all lemmings have either died or reached an exit portal. At this point, the percentage of lemmings that reached an exit portal is calculated. If this percentage is above the threshold, the player wins.

Computational complexity

[1] proves the NP-completeness of deciding whether a Lemmings level is solvable, via a reduction from the Hamiltonian cycle problem in a directed planar graph where each vertex has either indegree 2 and outdegree 1, or indegree 1 and outdegree 2. The latter problem is NP-complete [2].

NP-hardness proof of [1]

The proof is as follows. Let $G$ be any $n$-node graph with the above property. Choose a vertex $v$ with indegree 2, and attach to it a new vertex $u$. Embed this graph in a plane, and construct a Lemmings level from this embedding.

The level construction step uses a specific game construct detailed in [1]. It contains:

The trapped lemming can only be freed by another lemming with a Basher skill coming in through the entrance. The level is constructed from the graph with:

The starting location contains a trapdoor releasing one lemming (called the avatar), and the exit location ($u$) with an exit portal. The player is given $2n+2$ Basher skills, where $n$ is the number of vertices in $G$.

Solving the level requires to free all $n+1$ lemmings. In order to do that, the avatar has to go through all locations, each time using one Basher skill to release the trapped lemming, then another to go on to the next location. The last two Basher skills are used to reach the exit portal in $u$. This is equivalent to finding a Hamiltonian cycle in G, starting and ending in $v$.

References

[1] Giovanni Viglietta. “Gaming is a hard job, but someone has to do it!” In: Theory of Computing Systems 54.4 (2014), pp. 595–621.

[2] J. Plesnik. The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two. Information Processing Letters, 8:199-201, 1979.

[3] Cormode, Graham. “The Hardness of the Lemmings Game, or “Oh no, more NP-Completeness Proofs”.” (2004).

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