Posted: Oct 15, 2012 Glue puzzle tree nodes together in a more intelligent, useful way.

This entry is based on material published as a
Blind Mapmaker article on August 17, 2010.

So far, the only glue that has been used to glue one puzzle node to the next has been a randomly chosen item. This creates a less than ideal experience for many reasons:

Because the item is random, it is unpredictable. The item must be explicitly told to the player before he knows where it is supposed to go. This reduces all puzzles to glorified fetch quests. Similarly, you can not provide feedback for offering the wrong item, as all items are equally valid wrong answers.

Because the item is random, it almost assuredly won't be thematically correct. An archeologist needs a sailboat and will give you a flounder. You solve a block pushing puzzle and open the chest at the end to find... Han Solo.

Because the item is known, there is no need to discover a use for the item. If you see a rope leading to an island, you won't need to figure out that the chicken with the pulley in the middle will get you across. You will be told outright.

Because the puzzles cannot communicate with each other, there is no plot progression. Instead of an archeologist discovering a secret passage leading to the tomb of Mummy Jim, he gives you a shoebox which you then give to the police man somewhere else entirely.

Let's start with the first problem: puzzle items are random and thus limit how puzzles can use them. Rather than an archeologist asking for a sailboat, it would be much more appropriate if he were looking for something archeologist-related, like a map, a shovel, a piece of treasure, or Han Solo. Okay, maybe not Han Solo.

The obvious solution is to just keep track of what puzzle items are acceptable for this puzzle. Thus, this puzzle will only accept a map, shovel, or piece of treasure. When gluing this puzzle to the previous one, simply select from one of those three items when deciding on the puzzle item. And this will work and it will make a huge qualitative difference.

For instance, if the puzzle knows that a map is needed, then it does not need to be explicit about it. The archeologist can simply state that he is lost and the player will need to figure out that he is looking for the map. Now, the item needed is not only thematically correct, but it can be used to improve the puzzle from "FIND A" to "FIND ITEM WHICH CAN PERFORM A". In other words, I have a chicken with the pulley in the middle... what do I do with it?

The problem is this approach is static and does not scale well. What happens if you add a bunch of new items to the game? What if these items conflict with the puzzle solutions? For instance, what if you add a GPS to the game? It's a map-like object which appears to solve the archeologist's problem, and yet the archeologist doesn't know that it exists and can provide no better feedback than "I don't think that will work".

Or what if more treasure is added to the game. The archeologist is looking for a piece of treasure, but now the puzzle tree contains four or five treasures that work now. This could royally screw up your tree if you use the wrong treasure to solve the puzzles out of order.

Enter [#161 - Keyword Sets]. Instead of defining the inputs to the puzzle in terms of absolutes, you can define it in terms of a set of keywords. For instance, you can define the above puzzle using this automatic set:

        [[attr: ANCIENT INCAN] (unionSet [type: MAP] 
                                         [type: TREASURE]
                                         [type: SHOVEL])]

A small addition to the Keyword Sets format is that you can have different groupings of keywords, like "attr" or "type". This is designated in the set notation with a simple type followed by a colon and then the keywords. Each automatic set works with a single type, so [attr: ANCIENT INCAN] will only look at the keywords ANCIENT and INCAN of the "attr" group.

The first thing that this does is it future proofs your input sets. If you add in additional maps or treasures, the puzzle will automatically include them into their calculations. The puzzle will know that the pirate map isn't an ancient Incan map, and thus is not a valid solution. Perhaps just as importantly, it allows the puzzle to give some item-specific feedback based on the keywords associated with it.

If the player attempts to give the archeologist a pirate map, the puzzle will see that it has the keyword [type: MAP], but not [attr: ANCIENT INCAN]. The archeologist can use this information to tell the player, "That's a great map, but I'm specifically looking for something older, having to do with the Incan civilization". If the player provides an item that is neither ANCIENT nor INCAN nor a MAP, the archeologist can say, "That's very interesting and all, but I'm really lost right now and that's not going to be very useful for me if I die before I can leave this place!"

This also allows the puzzle to customize itself to the item it requires. A map, treasure, and shovel are not really all that similar, but it can affect what the archeologist talks about. If a map is needed, the archeologist can tell the player that he is lost. If the treasure was selected, the archeologist admits that he is looking for a specific treasure but has become frustrated that he couldn't find it. If the shovel is required, the archeologist could mention that his trowel broke and that he believes something good is buried under the sand nearby.

In short, the keywords allow the puzzle to customize its solution and its hints based on what keywords the needed item has and what keywords the item a player provides has.

What happens if you have multiple items that fit the basic criteria, like if you were to have multiple ANCIENT INCAN TREASURES added to the game. Perhaps you have golden goblet and a small idol. If these items have additional keywords (such as [type: GOBLET] or [type: STATUE]), the puzzle could use that explain why one item won't work as well as another ("Sorry, I was looking for a goblet"). But this runs into the same problem as before, in that it does not factor in the possibility that more items will be added to the game. If you add a golden sun mask to the game, the archeologist will have to say something like, "I have no idea what that is, but I don't want it" - which exposes the joints in the procedural generation algorithm a little too clearly.

Instead, the best solution is to, once you have selected the item from the set of candidates, to then invalidate the rest of the candidates. In other words, once you've selected the goblet, the idol and sun mask will not be used with any further puzzles. Now there can only be one solution ever, at the cost of reducing the size of potential candidates for the next puzzle node. If you have many different puzzles and many different puzzle items, this is not as damaging as it may initially seem - especially if you are more specific with your keyword sets (make sure you invalidate ANCIENT INCAN TREASURE rather than all TREASURE).

One thing to watch out for is when you use multiple different types of items in your keyword set. For instance, the above will end up invalidating all the ANCIENT INCAN MAPs, TREASURE, and SHOVELs. If the puzzle only cares about the TREASURE, then there's absolutely no reason why the MAPs and SHOVELs need to be invalidated as well. One solution to this is to provide a set made up of smaller sets (i.e. a set that contains a set of MAPs, a set of TREASURE, and a set of SHOVELs), and only invalidate whichever smaller set is chosen from.

Last but not least, we want to provide some manner for puzzle nodes to communicate with each other in order to have some sort of logical connection to each other. For instance, perhaps there is a blacksmith who can create any manner of tools for the player. Knowing that the archeologist needs a shovel, the player could then ask the blacksmith to create a shovel (after the player retrieves his smithing hammer, etc). There's really two things at play here:

1. The blacksmith can only create tools. Therefore it can only be paired with puzzles that accept tools as inputs.

2. The player asks for the shovel, so some game state is required for the blacksmith to know whether the player is aware of the shovel before offering the dialogue option to create one.

[[type: SHOVEL] [type: SWORD] [type: HOE]]

Whether or not two puzzles will fit together is largely about taking the intersection of the input set with the output set (and subtracting the invalid set). If the resulting set is non-empty, then the two puzzles can fit together. So, when selecting puzzles to join together, simply test the input sets against the output set. Also, though unused inputs are invalidated, unused outputs don't need to be.

The second problem is about world state and there's a bunch of ways to solve it. Perhaps the easiest way to do it is to maintain a state for each puzzle node. Already, they keep track of whether they are solved or not. You could extend this state to whether a puzzle is active, inactive, visited, or whatever. Then in the dialogue tree with the archeologist, simply set the puzzle state to active once the archeologist mentions that he is looking for a shovel. In the blacksmith puzzle, only offer the option to create a shovel if the parent puzzle node is active.

Puzzle states, mixed with controlling the glue between each puzzle, provide a simple but effective way to control the flow of puzzles. They open up a lot of possibilities for more complex and connected puzzles and should generally create a superior experience for the player.