Working with puzzle design through state space visualization

In the beginning of 2014 I was interested in procedurally generating computer games puzzles with typical elements like toggles, gates that can be triggered to open, boxes or boulders that can be moved onto pressure plates, etc. Many games contain elements like these and I took inspiration in particular from the game Lara Croft and the Guardian of Light.

To better understand these puzzles, and understand what makes a puzzle interesting or boring, I started creating a tool for analyzing and visualizing the state space of the puzzle. In the Procedural Content Generation mailing list I discussed the approach here. I've worked on it on and off since, and while I still don't have an algorithm for procedurally generating the puzzles, the tool itself is interesting in its own right. It's called PuzzleGraph and I've just released it for free.
Get PuzzleGraph at itch.io

You can setup and connect puzzle elements like gates, toggles, pressure plates and boulders, and see the state space of the puzzle visualized, including solution paths, dead ends and fail states.

If you make some puzzles with PuzzleGraph, I'd love to see them!

The best demonstration is this video I made. If you already saw the video, skip down a bit for some new info and announcements. When I announced PuzzleGraph on Twitter, a lot of people seemed to be excited. Besides re-tweets, I also saw many people forwarding and CC'ing each other, particularly people in academia.

It makes sense. As a practical tool for everyday work, PuzzleGraph may only be useful to few people since it's tied to specific (although fairly common and generic) puzzle mechanics. However, as a fully implemented proof of concept and as a research project, it's showing an interesting way of thinking about and interacting with puzzle design that seems to capture the imagination of a lot of people.

Analysis and visualization of game state space is also a field already researched in academia from a bit different angles. Research-wise I may not have done anything groundbreaking with PuzzleGraph, but its polished and highly accessible form with no barriers to entry probably makes the idea of working with state space interesting and accessible to a wider audience.

This visualizer is pretty darn cool.

— StagPoint (@StagPointTools) March 30, 2016

Wouldn't it be grand to do this for interactive story generation? :) cc: @anneandkita @gillianmsmith

— R. E. Cardona-Rivera (@recardona) March 30, 2016

@runevision @jseakle Something like this could be really useful for general UX design (not just games).

— bob (@bobpoekert) March 30, 2016

MIND BLOWN! Almost exactly what I'm plannning for Streamline, but my ideas aren't as developed yet

— Francois van Niekerk (@francoisvn) March 31, 2016

@runevision nice! If it was a tad more abstract (e.g. like https://t.co/pMCZ8pZdFl) it'd be a really useful tool for puzzle/system design

— hessel (@besttoffer) March 31, 2016

An awesome tool/concept for anyone designing logic puzzles

— Anders Nissen (@andershnissen) March 31, 2016

PuzzleGraph is now open source

In order to maximize the usefulness that PuzzleGraph and it's approach may provide to others, I've decided to open-source it. This way people can adapt it to include specific mechanics of their choice, or pull out specific parts of it and integrate into other tools, or just have a look at the code structures and algorithms for reference.

If anyone want to make improvements that might be a good fit for the original version of the tool, I'll be happy to discuss including it there as well.

The code repository is located at https://hg.sr.ht/~runevision/puzzlegraph and is licensed under the Mozilla Public License version 2.0.

Puzzle elements in PuzzleGraph

Here's a list of all the puzzle elements in PuzzleGraph version 1.1. Some elements are in locations (nodes) while others are in connections (edges). Since the initial version was released and I made the video, I've added a few more features in version 1.1. All the node and edge types now have tooltips to make it more clear what exactly they do and there is a help screen with an overview like the above. I also added three new puzzle elements; the one way edge, the blockable hazard edge, and the ball track edge, as described above.

Further development

I'm not yet sure to what extent I'll keep developing PuzzleGraph. I've honestly had very little time to actually use it, and gathering more experience with it through my own usage or other people using it will probably be the focus at first.

So if you use PuzzleGraph - either purposefully or just messing around - please tell me about your experience. And I'd love to see puzzles you make with it, and potentially include them with the distribution if you want.

Apart from that, I guess I'll see if anything comes out of open sourcing it as well.

In the next section I'll go over the techniques used for the state space visualization that you might use if you want to implement it for your own tools.

The technology behind state space visualization

There's probably many ways of implementing state space analysis and visualization but I can tell a bit about the approach I used for PuzzleGraph. You can check out the source code for more details. I'll assume a rudimentary familiarity with terminology from graph theory in this section.

Suitability for state space analysis

Before you even begin implementing the state space representation you need to be sure your state space is succinct enough to be useful to visualize. What this means is that every change in state should be significant and correspond to a choice made by the player. Furthermore, the choices available at any given point should ideally be limited in number. If you have an exponential explosion, visualizations of the state space are not going to be of much help.

In PuzzleGraph I built this into the puzzle format itself. By building up the puzzles around discrete puzzle locations, I avoided a continuous or detailed representation of space. Most of the remaining simplicity in states followed directly from this, and I simply avoided supporting gameplay features highly tied to space or time, such as timer based mechanics or physically simulated interactions between objects.

In some cases it's possible to begin with a puzzle form with a somewhat richer state space and simplify or collapse it into fewer states by ignoring irrelevant details. For example, the game of Sokoban has a very high number of states if the states directly capture which grid cell the player is in. However, this can be abstracted away by only considering which grid cells the player currently have access to (without moving boxes) and recording that into states instead of the exact player position. It's conceivable that decent methods for state collapse can be employed for many cases of full 3D worlds as well. For example, there are methods to automatically generate navigation meshes (nav-meshes) from arbitrary 3D geometry, and the way walkable areas are split into convex polygons there might well in some cases be a useful abstraction of player locations for the purposes of state space analysis.

Separating state from statics

Once you have a state representation where every difference in state corresponds to a meaningful player choice, you can begin the implementation. The first step here is to separate the state that changes from anything that doesn't change.

This means a departure from normal object oriented design where you'd have a toggle object that contains its own state as a member variable. Instead you have two different main objects.

• One is the static puzzle design, that contains information about the nodes (type and location), edges (type and which nodes they connect), and the initial state of each dynamic object.
• The other is the puzzle state, which contains all data that can change while the puzzle is being played.

With this separation, to evaluate the current state of the toggle element, the puzzle state object is given to the toggle object, and the toggle knows how to find its own state. If the toggle is stored as the fourth element in the puzzle, it finds it state by looking at the fourth element in the array of bools in the puzzle state given to it.
While the current state is separated from the puzzle design, the initial state is encoded directly in the design. This is necessary since the dynamic state objects are highly reliant on a puzzle design that doesn't change. If the puzzle design is changed, things may no longer match up. So whenever the design is changed, any puzzle state objects must be discarded and new ones constructed from scratch based on the initial state properties of the elements in the puzzle design object.

You can test and verify your separation of puzzle design and puzzle state before doing any state space analysis or visualization. A first suitable step is implementing functionality to "play" the puzzle based on these separated states.

Searching the state space

Once you have your separate state objects, you need a way to evaluate which new states it's possible to go to from a given state, and you need to keep track of that and build up a graph of the ways that the different states are connected. If you already implemented play functionality, you are already part way there.

Before you can construct your graph, you need objects corresponding to nodes and edges in the graph. The puzzle state objects are not themselves nodes. The states should be entirely self contained, so we need wrapper state nodes that contain both the state of that nodes, and information about which other states it's connected to. The state nodes don't contain references directly to other state nodes, but rather to state edge objects. Besides having references to the state nodes it connects, the state edges also store which kind of action the edge corresponds to. This can't always be derived just by looking at a before-state and an after-state, so we need to store it explicitly.

To explore the state space you need these data structures:

• A dictionary with states as key and state nodes as value. This is needed to check if a new state is in fact the same as an existing state, and retrieve the state node of that existing state if so.
• A queue for state nodes to be processed.

You can then explore the state space according this this algorithm:

• Extract the initial state from the puzzle and create a state node for it. Add this state node to the dictionary and to the queue.
• Process state nodes according to the queue as long as it isn't empty. Let a state node popped from the queue be A.
• Look at the state of the state node A and figure out all the actions it's possible to perform. For each of those actions:
• Make a clone of the state of state node A.
• Perform the action on the cloned state such that it changes into a different state.
• Check in the dictionary if the new state is the same as an existing state in your graph.
• If so, let the state node of that existing state be B.
• Otherwise, create a new state node B, store the new state in it, and add B to the dictionary and to the queue.
• Connect state nodes A and B with a state edge that stores which kind of action was taken.

The state nodes in PuzzleGraph have both a list of outgoing and incoming state edges. Outgoing edges are the actions that can be taken to go from the current state to other states. Incoming are the actions that can be taken to go from other states to this state. Having both makes the state space visualization code simpler, and also helps when implementing e.g. undo for the play functionality of the puzzle.

Visualizing the graph

Now you have a graph data structure representing the puzzle state space, but no easy way to inspect it. All that's really needed here is figuring out at which position each state space node in the graph should be drawn. From there on it's easy to draw each node at its given position, and draw connections between connected nodes.

Figuring out the positions is the tricky part then. There are algorithms and even frameworks available for this, but in the end I ended up not using any of them and just go with my own implementation.

The overall trick is to do a little almost physical simulation where nodes have spring like connections between them, with each spring connection having an ideal distance it attempts to pull or push towards. The two main challenges here are:

• Figuring out the ideal distance between every pairs of nodes.
• Figuring out which force to apply to node pairs given the ideal distance between them.

The first of those is only done once when the state node graph layout is initialized. The ideal distance is calculated as the number of state changes required to go between the two nodes, either one way or the other. In PuzzleGraph every type of state change adds the same amount of distance, but this could be made different if some state changes are regarded as more significant than others.

The second part is done iteratively, stopping perhaps when the nodes don't seem to move much anymore. It took quite some experimentation to get something that worked reliably for a wide variety of graphs. I calculate an adjustment length as the difference between the current distance and the ideal distance, divided by the squared ideal distance. This is then multiplied with a constant of 0.1 which seemed to be about the highest value I could use that converges fast without causing oscillation, explosions, or other instabilities.

The division by ideal distance is because it's less important to maintain ideal distance to far off nodes than to close by one. And also because there are more far off nodes than close by ones, so they often have a large aggregate force. The reason to use exactly the squared ideal distance to divide with is largely experimentally arrived at. The graph will look a bit different dependent on which power is used.

Extra stuff

That's the basics! Some other things to do is marking state nodes that are part of shortest solutions paths, or which are fail states from which it isn't possible to reach a goal state. See the source code for more details. :)