Knapsack Problems

Also posted on my personal blog.

Some computer games draw a lot of ire because of what is sometimes called "Inventory Tetris"1. This is where the items the player is carrying are represented on a (finite) grid-like structure, and usually crops up in action/rpg games. It can quickly become fiddly and annoying to the player, trying to decide what to keep (given there isn't enough space for all the valuable doodads they may come across).

By SharkD - Own work, GPL, on wikipedia

It gets especially complicated when items are not a uniform size, going from "I can carry this many items" to "I can carry these items provided I can rearrange them to fit". Which just evokes all the joys of packing2.

Given that "Ugh!" is many people's initial reaction to this sort of puzzle, why do so many games include it? Well, some people's reaction to any puzzle is "Ugh!"; we need a more compelling reason for avoiding it. Solving a packing puzzle can be very satisfying—just ask anyone moving house/apartment/etc. who has (finally) managed to sort out their furniture in their new room(s). Any puzzle can be a worthwhile challenge to include in a game, provided it harmonises with other aspects of the game.

Limited inventory also adds realism3 to a game—a character is not able to carry a small village in their pockets. But realism is not the be-all-and-end-all when it comes to video games. All games abstract away details from the real world to try to capture the core of an experience (Does anyone ever run out of petrol in a racing game?). As such the relevant question to be asked is not "do I/my audience like this kind of puzzle?", but "does this fit with the game's core experience".

Let me give a couple of examples of where the "inventory tetris" mechanic fits, and where it doesn't.

Sir, You Are Being Hunted

From Rock, Paper, Shotgun

This is a game about sneaking around to collect parts for the MacGuffin that will allow you to escape. Armed robots attempt to stop you. Along the way, you scavenge necessary supplies, like food and weapons (and stuffed badgers).

The whole experience is about coping with limited resources, and a restricted inventory forces you to prioritise. If you choose to leave your majestic stuffed badger behind, you could potentially come back for it later, but just getting to where you left it can be difficult (i.e. having to fight/sneak your way past the robots).

Adventure Games

With the traditional "adventure game" genre (think "Colossal Cave", "The Secret of Monkey Island", "King's Quest", "Myst" etc.), the player's inventory is essentially unlimited. This may be because there are only a small number of collectible items in the game anyway, but of more relevance is that retracing your steps (in this type of game) is not interesting or challenging. If a player is at the front door and needs to open a parcel, a knife being in their inventory is essentially an abstraction for remembering seeing a knife in the kitchen and going to get it.

These games often induce a sort of kleptomania; experienced players will grab anything that isn't nailed down because it's bound to come in handy later, and it saves them backtracking.

Occasionally, a particular puzzle will require putting limits on what the player is able to carry, but these should be treated as exceptions, and not change the normal inventory mechanic. For example, in the text-adventure Hitchhiker's Guide to the Galaxy, solving a certain problem involves the player traversing a narrow space which gives an excuse for them to only take one item with them. In Broken Age, carrying a particular item (noted in-game as being exceptionally heavy) means the player cannot cross a particular surface without falling through.

So, as with all game mechanics, inventory tetris has a place, but can be very annoying if it is used somewhere it doesn't fit.

1 Or, more prosaically an Inventory Management Puzzle, but that just doesn't have the same pizzazz.

2 You may recognise this an example of the knapsack problem, one of many NP-complete problems which we have no efficient way of solving.

3 I use the term very loosely.

smiley