June 15, 2004

Algorithm for constructing locked room puzzles – [musings]

Just thinking out loud here, with no real context.

The player is confronted by a locked door. How does he open it?

A common construction for this puzzle is the paper-under-the-door skeleton key setup: the key is in the opposite side of the lock, and can be pushed out of the lock with a small pointed object, to land on a sheet of paper which can then be pulled back under the door. This is a slightly sophisticated puzzle, because it requires the interaction of three objects: the door, the small pointed object, and the flat object. (The key is not part of the interaction, it is the reward for solving the puzzle.)

Step 1: operate the flat object on the door
Step 2: operate the pointed object on the door
Step 3 (obvious): retrieve the flat object

Hidden in these steps is a potential losing state: if the player operates the pointed object on the door without first operating the flat object on the door, then they key will become unreachable. It isn't this losing state that makes this puzzle what I called "slightly sophisticated", the sophistication comes from having to operate the two objects independently. One object does not "produce" the other, the player must have both at once.

Other than that, this situation can be defined as a sequence of states, allowed actions, and results:

state / allowed action / result
key-in-lock / operate(flat object, door) / go to state key-in-lock-can-be-pushed
key-in-lock-can-be-pushed / operate(pointed object, door) / go to state key-on-flat-object
key-on-flat-object / operate(flat object) / go to state have-key

Player actions are simply motivated by the need to discover the next state-changing operation.

Forgoing any losing states, it should be relatively easy to construct an endless series of locked room puzzles. Start with the pointed object, the flat object, and the locked door, and create a state that is one operation removed, then create another state from there, and so on.

I want to be able to create these puzzles with a step parameter, so if steps = 5 then it will take 5 operations (opening things, unlocking things) to complete the puzzle.

Every object must have a location. This location may be a room, or some relationship with another object. For example, the flat object might be located under a piece of furniture. Now the flat object has a location, but the addition of the piece of furniture means that it too needs a location.

Finding a object that is not in an obvious location (in plain sight) counts as a puzzle step.

Some objects can be locked, such that their concealing relationship cannot be explored unless they are unlocked. For example, a desk might have a locked drawer. The player must find the desk key to unlock the desk (1 step), and then open the desk (1 step).

Concealing locations that cannot themselves be concealed are called rooms. Rooms can be locked. The key-in-lock door is in room alpha. All other rooms must connect to room alpha in some way.

There is a design decision to be made here: does the player start in room alpha, or must he find it just as he must find the flat object and the pointed object? If he has to find it, the overall motivation for getting out of the room/unlocking the door will be hidden. Without this motivation, the player will be solving arbitrary puzzles without knowing why -- of course the locked room is itself arbitrary, but it functions as a ground, a central setting for other player interactions.

First thing to do is build a library of objects. Each object can be queried for potential state paths, and their corresponding step costs. These paths are: is contained (1 step), is locked (1 step), has a location (0 steps).

Building the puzzle

Place the sharp object and the flat object into a list. We'll say the sharp object is a pin and the flat object is a newspaper.

[pin, newspaper]

Now, querying the list, we have these possible paths: pin is contained (1), pin is located (0) newspaper is contained (1), newspaper is located (0). Choose a path, make the appropriate changes, and repeat.

Say we choose "pin is contained", now we pick a container: a desk. Since the pin is now contained, it has a location. Since it has no more possible paths, it could be removed from the list for efficiency. Add the desk to the list.

[newspaper, desk]

Possible paths: newspaper is contained (1), newspaper is located (0), desk is locked (1), desk is located (0).

Choose "desk is located". We need a room, "room 1". This room will go on the list.

[newspaper, desk, "room 1"]

Possible paths: newspaper is contained (1), newspaper is located (0), desk is locked (1),
"room 1" is locked (1).

Choose "desk is locked".

And so on.

Once the puzzle has the required number of steps, any objects without a location can be resolved. This has to be done with some care, to make sure objects are accessible when they are needed. One way to do this is to record the associated step number for any step with the object, and also with rooms.


step t - 0: look under bed, find newspaper
step t - 1: unlock "room 1" with door combination (access to bed)
step t - 2: find door combination in book
step t - 3: look in desk, find pin
step t - 4: unlock desk with desk key

rooms: room alpha (max), room 1 (t - 0)
unlocated objects: desk key (t - 4), desk (t - 4), book (t - 2)

Objects must go into rooms that can be reached at or before the object step, so the book cannot be located in room 1.

Here the three objects could all go into room alpha, or a new room can be created for some of the objects. It depends on the visual design for rooms, how many objects can be fit into one room location.

Note: because there are two objects involved in the master solution, getting to those two objects results in two parallel paths of action, and the constructed path is a variant from a set of combinatorial solution paths.

Finally, once all the objects are located in rooms, we need to connect the rooms. Starting with rooms with step t - 4 (the max value), connect these rooms together. Then lower the value to t - 3, t - 2, and so on, adding rooms to the existing network of rooms. This insures that each room can be reached in time.

That's it. Now it should be possible to explore the set of rooms, opening and unlocking objects to solve the puzzle.

Some thoughts on "sophistication"

The different types of operations can be classified by the number of objects they consume. Some of the consumed objects may be inventory items, while others are location specific.

Opening a container - this operation consumes one object, the container. Whether it is opening a small box (in the inventory) or opening a desk drawer (in the location), one object is consumed. There is no net change in the number of objects in the world, because an object is created for the object consumed.

Unlocking a container - this operation consumes two objects: the key, and the container. The container is consumed because it must then be opened. Any puzzle where a key, a code, a tool, &c is needed is an unlocking operation. There is a net loss of one object, because one object is created and two are consumed. (One can argue, particularly from the technical point of view, that two objects are created, when you account for the creation of the unlocked container. This is also more in line with the operation/state change construction of these puzzles.)

Unlocking a "sophisticated" container - unlocking the skeleton key door requires three objects: the door, a flat object, and a sharp object. There is a net loss of two objects.

By this classification, the "sophisticated" container is an expensive puzzle to create, because it needs to consume more objects. Even more sophisticated containers (requiring three keys, four jewels, and so on) consume more objects. And, from the technical perspective, there is truly a net loss of objects, if no intermediate objects (a partially unlocked container?) are created.

Another way to think of "sophisticated" containers is to look at them as critical junctures. These are operations that will turn a bunch of objects into a smaller number of more important objects. I'm thinking of Viridian Room, which has two such critical junctures: building the "soul box" and the final puzzle. The other puzzles are just the exchange of one object for another: the diary key for the thing, the red blanket for another thing.

Posted by B Rickman at June 15, 2004 01:22 AM | TrackBack