Posted: Apr 11, 2014 One of the fundamentals of procedurally generated content is a convenient way to try a possible solution, then undo it should it fail.

I feel a little bit silly for writing this one. It's basic computer science 101. I was ready to just assume everybody knew this stuff, but looking at a few procedural generation conversations on the internet, I became aware that either it isn't as obvious as it seems, or some people just haven't thought to apply stacks to this particular problem.

I'm largely against the idea of procedurally generated content being an effort of guess and test. It drives me nuts that the current procedural generation environment is either guess and test or literally trying to find mountains in white noise. I spend a lot of my effort trying to devise ways in which you can get the results you want the first time. But computers are fast enough that the old guess and test approach could end up being quicker, conceptually simpler, and produce acceptable results with less code.

The framework here is essentially a slightly modified "undo" stack. The idea is that you present a potential solution to a problem and try it out. If it doesn't work, you "undo" it. The purpose of a stack is that you may attempt to do a process that takes multiple steps, and if one step doesn't work out, you'll want to return to the previous step and try again. In particularly unworkable solutions, you may "undo" all the way up to step 1 and basically try to complete the entire process from scratch, but starting from a different premise. The important thing is that you don't start from step 1 every time you hit a wall. You back up a little bit. You don't throw the baby out with the bathwater.

Some people rely on the implied stack of code recursion to reach the same results. While this is fine, for the most part, one of the drawbacks of recursion is that you can't pause it. Breaking a process up into pieces gives you control over when and how it runs, giving you the ability to break it up into multiple calls - perhaps running a lengthy process in the background preparing the next level while the player works his way through the current one.

Fig 202.1 - The Problem.

Here is a pretty basic scenario. You have a tree of rooms that you need to turn into a map. The simplest way to do this is to recursively go through the tree, and place each node adjacent to its parents. However, there are situations during which this may not succeed. The randomness may result in one long straight line that exceeds the map boundaries. Or perhaps the map is built so tightly together that there's no space next to a room to place its children.

Fig 202.2 - Place the first node.

The way to do this is to simply keep track of every action you perform with a stack. The first step is to place room A randomly on the map. This information is then pushed onto the stack. Then, starting with the children on the left, work your way through the tree. For each node, attempt to place it randomly next to its parent.

Fig 202.3 - The process works.

Here's what it looks like when the process works. There's enough room for everything, and the random positions of all the cells don't end up cornered. The stack is filled with all the rooms in the order the were placed down. This is the best case scenario. Now, here's what it looks like when guess and test doesn't work:

Fig 202.4 - Cornered.

The process gets all the way to 'K' just fine, but then when it is time to add 'M' off of room 'I', there's no room. This means that 'I' fails. Pop everything off the stack through 'I', and try placing it again. Unfortunately, there was only one place to put 'I' off of 'D'. There is no other way to place 'I', so 'D' fails. Pop everything off the stack up through 'D'.

Fig 202.5 - Not cornered.

Attempting to place 'D' into a different spot works out. In fact, now that map is more open from 'D' in its new position. When you hit a dead end, "undo" each step until you can redo a step that works.

The benefit of using a stack instead of just starting over every time is that it ultimately creates a search through the available spaces. It may be that there's only two or three configurations that work, and you could randomly try to place the tree a thousand times without finding those few solutions, and wasting untold effort for little result. However, the stack works as sort of a controlled flood-fill, filling in the spaces as best as it can, and backing up when it hits a wall to try again.

For this approach to work, there needs to be a fail case in which an attempt no longer works. In this map example, the fail case is that each of the four neighboring cells are either taken or tried (and failed). In more freeform guess-and-test, there could be an infinite number of guess you could try out - but it is better to cut your losses and try a new path after a number of failed attempts.

My one contribution to the guess and test stack is to point out that there are really two things going on at each step: the guess and the test. When the test fails, another guess is selected. When there are no more guesses, the guess fails, going back and failing the previous node's test.

This distinction is important because a test needs to know how to undo itself. If you place a room and it doesn't work, you need to remove that room for the next test. However, when a guess fails, it selects another guess, or failing that, gets popped off the stack. You can use different approaches to the guessing, from keeping a list of potential guesses to keeping a list only of the failed guess. Two different processes that have two different fail states.

Fig 202.6 - A better visualization of the guess and test stack.

Here is another way to visualize the stack: each entry is a pair. The blue parts are the guesses, with the current guess highlighted in the middle, the failed guesses darkened at the bottom, and guesses yet to try at the top. A has a list of potential starting positions, while the other letters simply point off in four directions from the current cell. The white letters are the successfully placed rooms. Those would fail if the guesses ended up pointing to an occupied cell or off the map boundaries.

By breaking this process into two distinct parts, it becomes more obvious what is happening, and allows you to code appropriately. Each room only has one fail states: can I place a room at the designated location? Placing A at a specific location on the map is different than placing B relative to A. In this way, the guesses do different things, but actually placing the rooms (or failing to) does not.