Three Hundred :: Mechanic #162 Sites:     Webcomics   |   Three Hundred Mechanics   |   Three Hundred Prototypes
 Three Hundred
   - Index Page
   - About...
   - By Year

   - Comp-Grid
   - Procedural
   - Tactics
   - Tiny Crawl
   - Misc

PreviousMechanic #162Next

  Mechanic #162 - PGC: Puzzle Tree Building - Glue
Posted: Oct 15, 2012

Glue puzzle tree nodes together in a more intelligent, useful way.

  Puzzle Tree Building - Glue

This entry is based on material published as a
Blind Mapmaker article on August 17, 2010.
I showed you what a [#158 - Puzzle Tree] is, and then I showed you how to build a simple one in [#159 - Puzzle Tree Building]. Then I showed you how to improve the the game world by combining the game world's zones to a puzzle tree in [#160 - Puzzle Tree Building - Zones]. At this point, you could create a fairly large, fairly diverse Zelda/Desktop Adventures type game. But there's still one glaring problem.

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.

Basically, you get a bunch of small, but obvious problems that come from the fact that items are purely random. This is the last major stumbling block on your way to procedurally generating an interesting game. You need to figure out a way tie the puzzle tree together in a logical manner, and that's where [#161 - Keyword Sets] comes into play.

  Static Input Sets

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.

  Keyworded Input Sets

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])]
This single line defines a set that has the attribute keywords ANCIENT INCAN and the type of MAP, TREASURE, or SHOVEL. Now you can add new maps and treasures all you want, and as long as they don't also have the keywords ANCIENT and INCAN, they won't be included in the set of potential inputs.

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.

  Providing Feedback

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.

  Multiple Solutions

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.

  Logical Puzzle Progression

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.

The first problem can be solved, once again, with our friends, keyword sets. Just like how the archeologist puzzle provided an automatic set for inputs, the blacksmith can provide an automatic set for outputs:
[[type: SHOVEL] [type: SWORD] [type: HOE]]
This allows the blacksmith puzzle to output any SHOVEL, any SWORD, and any HOE - even an ancient Incan shovel (let's assume the blacksmith is really good at emulating ancient Incan metalwork, because I don't want to create another hypothetical example at this point. I'm pretty committed to that archeologist, bless his little soul).

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.



Copyright 2007-2014 Sean Howard. All rights reserved.