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

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

PreviousMechanic #004Next

  Mechanic #004 - Environment Tree

Category: Random
Posted: 05/12/07

A method for generating puzzles and locked doors without worrying about unwinnable situations based on modelling the environment as a tree.


Procedurally generated content (like random dungeons) is something of a holy grail for game design. The ability to instantly generate any and as much content as you'd like with infinite variety represents a game that could be played forever. Even games with the most rudimentary procedural content, like Diablo II or NetHack, represent some of the most popular and replayable games available.

Unfortunately, procedural generation is at best simplistic and obvious right now, used almost exclusively to design dungeon layouts - and even then, it rarely surpassed the quality of a kid with a level editor. I believe that procedural content could be used to design full games, beginning, middle, and end to a quality at least above the average game designer's. That day is far, far off.

This idea is less an gameplay mechanic and more of a gameplay design mechanic. In simple terms, by describing the game world in a tree structure, it becomes very easy to intelligently place puzzles without worrying about creating an unwinnable situation.



This is the map I'll be using as an example. It consists of two floors and the roof. The blue doors are simple doors that can be closed or open, while the light gray doors are invisible doors - seemless divisions between two rooms. We can close and lock regular doors, but there's nothing there to close seemless doors. We can still block off the seemless doors, but we have to place an obstacle there, like a fire or barrade. The difference is mostly cosmetic (ie what kind of barrier is required).


This is the spatial tree that represents the logical spaces within this building and you'll notice that they follow the same order that you would encounter them. This is a very simple tree as there's no loop backs, one way doors, or multiple points of entry (ie stairs and elevator), but you get the point.

Here's where the magic happens. Let's say we want three puzzles total, and for the sake of simplicity, they will be simple key/door puzzles - they could be anything that requires X and rewards Y. In this case, the puzzle requires X (a key) to access a new area, which will either contain a key or victory.

You'll notice in the above tree that each of the blue lines corresponds directly with a doorway, and if we lock one of those connections, than all nodes below are equally locked. That is, we cannot get to any room through that door and the tree makes it really easy to tell which rooms those are. For instance, say we wanted the final victory to be in the shed on the roof. If we were to lock the roof, it would look like this:


This tells us one very, very important thing. All white nodes are a valid location for the key to the red area. So long as we keep this in mind, we can build the puzzle tree backwards, and always have a valid and solvable experience. Let's place the key on the second floor, then lock the second floor, putting the key to that in the back room. Then we'll lock the back room, and put the key to that in one of the rooms off the hallway.



See? It's a very simple algorithm to implement and understand, even if you include criteria for where to place locked doors (ie don't lock off an empty area, don't lock too large an area, etc). We can even make it a little more interesting by changing the keys into puzzles. For instance, a room could have a boss monster in it that you have to defeat to get the key, or there could be a safe that requires a combination from another room (at equal or lesser locked level) to open. Each puzzle requires a number of inputs (even zero, such as finding a key on the floor) and yields a number of outputs. The puzzle tree can be created (again, backwards) be using the environment tree as reference.

Hopefully, it should be obvious that defining the world environment in this tree format could also be used to generate an environment. If you created a rule set which defined what kind of nodes can be children of each other, it could be a relatively simple process that could create very logical and usable spaces that could far exceed the potential of traditional random generated areas.


  • This is a very simplistic version of the system that requires exploration to be multi-linear. This version does not include, for example, the ability to enter a room from two different directions. Most adventure games are not really that wide open in practice. For instance, a game like Silent Hill only allows you to enter a zone from one entrance, but may open a one-way locked door back to a previous zone to shorten the trip. Something like that would be trivial to add and work in a manner similar to the puzzle locking.

  • A strictly non-linear zone would probably be a single node in the graph, but could still benefit from it. For instance, the path you take through the oil refinery may be open pathed, but you will still do the oil refinery after the sewers. Or perhaps a large open area may be broken into smaller zones, such that a node doesn't refer to a single room but a collection of rooms that are all unlocked simultaneously upon entering.

  • One could probably take a pre-created floorplan and build a tree from it. Based on the assumptions made (for instance, you start by going in the back door instead of the front), it could generate a very different looking tree. Perhaps there could be a method for creating a union of multiple trees to factor in multiple points of entry. For example, there could be a hallway and adjacent rooms that can only be entered from one entrance no matter how many door enter the floor - thus it can be assumed to be a single subtree, shared between the two different versions of the world. Or if you locked an area in one tree, how the changes are reflected in the other tree could tell you whether it was a good idea.

  • Multiple points of entry is definitely a tricky subject. Luckily, most adventure games have absolutely no use for it. It can be faked, ignored, or carefully avoided in most cases. Coming up with a good solution to multiple points of entry is more a subject of pride and curiosity than a pragmatic solution to a desperate problem.



  • Copyright 2007-2014 Sean Howard. All rights reserved.