Lemmings

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:

• Platforms, surfaces on which lemmings can walk horizontally.
• Stairs that can be climbed by lemmings to reach a higher platform. A lemming starts climbing stairs if it reaches their bottom and is walking in the right direction.
• A trapdoor that will release the lemmings one by one at fixed intervals, until the total amount of lemmings has been released.
• Exit portals through which lemmings can leave the level.

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 boundaries 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:

• Climber enables a lemming to climb a vertical wall (instead of turning around when reaching it).
• Floater enables a lemming to fall slowly with a parachute, removing the risk of dying in the fall.
• Bomber kills the lemming and destroys any obstacles around it after a five-second delay. Other lemmings and some game elements are not destructible in this way.
• Blocker will make other lemmings reaching the blocker turn around, as if they had hit a wall without the climbing skill. A blocker lemming will stop moving.
• Builder makes the lemming build a stairway, enabling other lemmings to climb it. The builder will stop after 12 steps.
• Basher enables digging through soil in a horizontal line.
• Miner makes the lemming dig downwards at a 45° angle.
• Digger makes the lemming dig downwards in a straight vertical line.

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:

• an entrance at the top of the construct,
• a lemming trapped in a “cage”, that forces it to walk in a loop,
• an exit portal.

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:

• each vertex corresponding to a copy of the game construct mentioned above,
• each edge corresponding to a one-way path between two locations, as described in [3].

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   = "2024",
    url    = "https://www.isnphard.com/i/lemmings/",
    note   = "[Online; accessed 2024-04-13]"
}