There's a lot of different reasons for this, the most obvious one being the feeling of progress. You don't want the game to feel like Lost, where every problem solved yield two more in its place. There might be a rare occasion where something like that happens, but in general, you want the act of solving puzzles to reduce complexity, not increase it.

There's also the predictability aspect. Players can predict that solving this puzzle might yield a result which makes another puzzle solvable. Maybe it is because we haven't been trained in it, but it is very difficult to predict multiple outcomes from a single action. I just don't think you can easily communicate multiple outcomes easily without spending more time telling the player what he will get than hinting at how he will get it.

Finally, there's the issue of reward. One puzzle should ultimately yield one reward. If it has more than one, the effect of the reward is greatly diminished. Take World of Warcraft, for example. Finishing a quest will give you some experience, some money, and a piece of equipment. Generally speaking, the money and experience become almost invisible as the interesting reward takes center stage. In a game built around the transversal of a puzzle dependency graph, not giving full attention to each reward could end up making the game feel out of your control or random.

Leaf nodes are the exception, I think. These are the puzzles which have no requirement. Something like walking into the kitchen and finding a bottle of ketchup in an unlocked refrigerator. Even if it is something more complicated, like having to push a bunch of colored blocks around, it is something which requires no input and yields only output. It is not something that you encounter now and must remember later. You encounter now, solve now. You don't have to maintain a mental puzzle graph or its location within it. You see a locked door, you think, I have to find a key to open the door. You see a key, you think, now I have a key.

Similarly, in a game like Zelda, acquiring a new tool opens up new possibilities. Suddenly, a path that was once blocked is now open. Or a cracked wall can be blown up with your newly found bombs. Defeating a dungeon boss suddenly changes the weather to summer, causing all the ice blockades to melt. Defeating the evil wizard changes the nearby town from a depressing place to a happy celebration, where you can pick up party favors and nifty hats.

What is happening is that the world state is changing, and certain puzzles may depend on these changes in exactly the same way that they may depend on having a particular item. Finding the toothbrush in the bathroom has no explicit puzzle dependency (it's right there on the counter! pick it up!), but it is dependent on the bathroom being accessible. In general, these changes are more pronounced and far reaching than solving a typical puzzle. Unlocking a door opens up a new region, new leaf puzzles, and make previously unsolvable puzzles now solvable.

One place where the world state is not obvious is in a given task. For instance, in DeathSpank, your initial task is to find The Artifact. Upon doing so, your primary task then changes to finding a sword. After that, it is to find the half dozen orphans for the mayor. One could almost consider these chapter breaks, as each major accomplishment is achieved and you move on to the next major goal.

I bring this up particularly for the orphan example in which talking to the mayor sets up a multi-parallel task list. Each orphan is their own puzzle branch, but none of the orphans can be collected until the mayor gives you the orphan bag. Represented as a traditional puzzle tree, talking to the mayor would then branch out in a bunch of different branches, breaking the one-parent, many-child rule. However, if it is modeled as a world state change, this breaks it up into talking to the mayor unlocking the "collect the orphans" state, which now has a lot of leaf puzzles.

To the left is a puzzle tree in which unlocking a door to the bedroom allows you to solve three puzzles. One of the bedroom puzzles requires you to have an item from the first room (maybe you need a ruler to get the kazoo out from under the desk). Even with a simple example such as this, you can see that it makes the graph a bit complex. With something far more complicated, with far more state changes and dependencies, it could quickly make the chart unreadable.

With this chart on the right, I've modeled the world state change caused by unlocking the door as a zone. Every puzzle in the zone is assumed to have the same dependency - that is, the bedroom being accessible. This makes the simple puzzles like picking up pants off the floor into a leaf node instead of a major part of a complex dependency hierarchy.

As I've tried to show through my examples above, state changes are not strictly related to opening new regions on the map. However, if you were designing an RPG or something that was highly dependent on opening new regions, that may be all that it is. In fact, it could be nothing more than a series of separate regions where each puzzle tree simply leads to unlocking the next one.

In this more elaborate, but not quite thought through example, I attempted to show how these dependency zones can help modularize a game's puzzle tree. As you can see, the series puzzles required to unlock the swamp are separate completely from the major quest line - itself little more than an excuse to unlock the final dungeon. The benefit of this approach is that you can break each dependency zone into its own thing. You can design the dungeon separate than the swamp. Designing the swamp, you need to be aware of the two puzzle paths that cross zone lines, but it is easier to think in terms of a couple dependencies than a giant interrelated chart filled with dozens of them.

The first thing that I want to point out is that dependency zones are themselves dependent as well. If all the quests needed to unlock the swamp are located in the forest zone, you have to assume that the dependencies stack. Everything in the forest zone requires the forest dependencies, while everything in the swamp zone can be said to require the swamp zone dependencies and the forest zone dependencies. The dungeon requires all three. You can't get into the dungeon unless both the forest and swamp have been unlocked.

In general, games go through these major state changes in a linear order. You aren't going to get to the swamp until you've done the forest. Period. Procedurally generating a game with such a linear progression is as easy as keeping a stack of dependency zones and building the tree from the bottom us. Each time you create a puzzle in a particular zone, simply factor in all the dependencies for the zones above it.

One way this works out is if your puzzles are tied to a particular landmass, and each landmass is tied to a particular stratum. Since you can assume that all strata meet the requirements for the previous ones, you can reliably use any puzzle from a landmass higher up. For instance, you can put a forest puzzle in the swamp zone. It may require access to the swamp and solving a puzzle there then traveling back to the forest to solve the puzzle, but you can't accidentally create a situation where a key is behind the door it needs to unlock.

Much like the environment tree concept I wrote about in the Three Hundred, dependency zones are self checking for unwinnable situations. As long as you build from the bottom up and use puzzles for areas from the current stratum or earlier, you can't screw up the puzzle tree. Since my goal is a Desktop Adventures type game, which is a hybrid RPG and adventure game, this sort of stack would probably be more than enough to suit my needs for some time to come.

My main problem with dependency zones, at the moment, is that they are in a dependency graph themselves. If it is just a linear series of unlocking - which, it should be said, are what 99% of the games out there employ - then it is simple, obvious, and easy to implement. However, once you start entering more complex dependencies, especially parallel states, it can get rather complicated.

For instance, I put the dungeon in the above example as being wholly contained by the swamp zone. Really, it is such a linear path that the dungeon zone could've been the third stratum, such that it is a stack of three zones, all dependent on the previous ones. I was thinking that by making it interior, you could have multiple dungeons run parallel. You can do them in any order, so long as you did them all before moving to the next landmass.

With dungeons, that's probably not a very complicated thing. However, if you use dependency zones to model tool unlocks for something like Zelda or Metroid, you could run into complexity quickly. For instance, say that there are three tools that you can collect in parallel. That's three zones for each tool, side by side. But then you need the puzzles that require two tools, so you've got three more zones for tool combinations AB, AC, and BC. If the third tool is optional for a greater length of time (you don't need to discover the ice wand until the fifth dungeon, but the shovel and grappling hook are required by the third), you end up with dependency zones that don't graph together all that politely.

Perhaps one solution is to model tool zones with explicit dependencies. Rather than relying on the existence of previous zones, each zone is considered self contained with their requirements explicit. Thus tool zones A, B, C, AB, AC, BC, and ABC are all separate. If you have a puzzle sequence which moves through multiple zones (you can do puzzle X with tool A, puzzle Y with tools AB, and puzzle z with tools ABC), you can just put that entire subtree as part of the highest dependency zone (zone ABC). Even though you can solve parts of the puzzle earlier, they don't actually affect the greater puzzle tree until the last puzzle in the sequence is complete.

Building on that, perhaps it is worthwhile to make multiple dependency zone charts, like one for tools and one for landmass unlocks or plot progression. Maybe these multiple graphs can be cross referenced in some way. You might build the greater plot progression tree based largely on landmass unlocks - for that it might be important to keep track of which tools are required to get to each dungeon or area, but each area could potentially contain puzzles that cannot be completed until much later in the game. Using the tool dependency graph, you can then organize these puzzles based on where in the game you might be able to open them up, and scale the rewards accordingly.

Some people take great pleasure in sequence breaking a puzzle tree, especially in something like Zelda or Metroid. How would you model something like that? Would it require making two representations, one where you get the axe and then the double jump and one where you get the double jump and then the axe? That seems excessive to me, but for complex sequence breaking, maybe it is the only way to model it.

Of course, this is assume you want to model it. Most sequence breaking represents a failure or at least a willful ignorance of maintaining puzzle tree integrity. It's likely that if you procedurally generated an adventure, without proper precautions, sequence breaking may just be a side effect of not paying close enough attention. Of course, care must be taken care, at least somewhat, as it could be possible for sequence breaking to be purely accidental and for it to make your game completely unwinnable.