Knapsack problems

Some computer games draw a lot of ire because of what is sometimes called “Inventory Tetris1. 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. I may burble more on this distinction in a later musing, if anyone is interested.

3 I use the term very loosely. 🙂

Advertisements

What’s the point?

Players of video games—particularly role-playing games (RPGs)—will often lament the problem of grinding (I suspect named in reference to “the daily grind”, but it is also sometimes referred to as “treadmilling”). The commonly-accepted definition of grinding is having to complete tedious and/or repetitive tasks. It often arises in the context of “leveling up” a character (essentially training to improve abilities).

Various workarounds have been proposed and/or implemented (see some examples). Completely removing the potential for grind would mean completely changing the leveling systems (which are otherwise tried, true, and effective), which would have significant consequences, so the approach de rigueur is to include some sort of payoff; a gold star for having defeated 100 swamp rats. This is applying an extrinsic reward to either motivate the player to grind, or placate them after a period of grinding.

While some aspects of game design—like the diminishing returns of experience points/leveling, and the random reinforcement of loot drops—are heavily informed by psychological findings, similar findings about the poor motivational effects of extrinsic rewards seem to have been passed over. Of course, it may also be that figuring out how to tap into intrinsic motivators is not only difficult, but getting back into the “overhaul the whole system” approach, which isn’t what we want.

I find myself wondering, though, if this is a case where the old adage “you never understand the solution until you understand the problem” applies. We have a definition of what grinding is, but maybe we need to consider why grinding is off-putting to so many players. Think of an RPG—whether it’s Ultima, Diablo, World of Warcraft, or even Pokémon—the parts of the game that are perceived as “grinding” aren’t mechanically different to the rest, they’re when your goals are different. You need to get stronger before you can overcome the next challenge. Your character still gains experience and levels while completing quests, but it’s a side-effect. “Grinding” is when leveling up becomes the main goal. And that’s just not very interesting*.

We can see something similar in the world of sports. The equivalent would be playing a match that has no impact on which team wins the trophy, so the only advantage to the players is the potential for improving their stats (though there’s still ticket sales, broadcast revenue, etc. to entice the higher-ups). For example, the fifth match of a best-of-five final when the score is 3-1; such a match is referred to as a “dead rubber”, and in some cases is abandoned.

Maybe this perspective can help. Grinding doesn’t seem like grinding if there’s another reason for doing it besides boosting stats**. Earning a gold star doesn’t help, unless it makes a difference to later gameplay. Perhaps other characters could start referring to your character as “Bane of Swamp Rats”. Perhaps swamp rats become more likely to flee rather than attack. But something beneficial—give them a reason, not an arbitrary number.


* For most players, anyway. For some, it’s the main attraction, and that’s fine, but I don’t believe that’s the case for the majority.

** Partly because I was feeling the lack of footnote, but also because this is a genuine side-issue: granularity. Sometimes the problem isn’t that there’s no other reason to kill all those swamp rats, but that you have to kill so many before it matters. It comes down to the same thing though: if you make the player’s actions feel meaningful, they’re less likely to get bored/frustrated with their progress. This is sometimes called “breadcrumbing”—leaving a trail of small markers/rewards to lead the player onward.