I recently dug up my university dissertation and related code, and was surprised that it still runs and isn’t as bad as I feared. It was pretty interesting at the time so I thought I’d share. It was a good call to choose a project in the games/puzzle area, as I’m pretty sure that helped me get my job in the games industry a few months later!
Full report, and running the code
RollingBlock.pdf – this is the full dissertation I submitted, in case you’re interested in reading about this in more depth.
RollingBlock.zip – this is the full source and compiled code, written in Java. I’ve not recompiled it since 2002 and some of the formatting seems a bit messed up, but it still runs (please don’t judge the code quality, this was my first reasonable sized coding project!). There is the full editor program, plus a variant on the player for puzzles with multiple moveable blocks.
To run the Editor program you need the Java JRE installed. If java.exe is in your path then editor.bat should launch the program, otherwise you’ll need to put the full path in.
Rolling Block Puzzles
The idea of the ‘rolling block’ puzzle is to roll a non-cube block (2×1 in the simplest case) through a grid-based maze so it ends up exactly covering the goal. Because the block isn’t square it takes up more room in some orientations that others, and the puzzle involves shuffling the block into the right orientation to get to where you want to go.
Here is an example puzzle, where you need to roll the blue block so that it stands upright on the yellow goal square. So the only possible first move is up-left, because there isn’t enough room to roll in the other directions:
This is a type of multi-state, or concealed path, maze. Underneath you’re navigating a state graph of moves from the start point to the end point, but the shape of the block, and the moves it allows, means that the actual path to the solution can’t easily be seen. There are only 53 empty squares on the grid but there are 125 reachable maze states, and the shortest solution requires 32 moves (solution at the bottom).
Automatic maze generation
These types of puzzles are very hard to design unassisted, because each block added or removed impacts the state graph in many different places. Some clever people design these things by hand, but us mere mortals can use a computer.
The first thing we need is a solver. This does an exhaustive breadth-first search of the maze and builds a graph of all states and the transitions between them. In each state there are at most four legal moves so it checks if each destination state is a duplicate, add a new node if it isn’t, and add an edge between the two nodes. Here is a very small 5×5 maze:
And this is the state graph a solver will come up with:
The numbers are how many moves are required to reach each state, so zero is the start position and 18 is the goal position (the colour coding is based on branches and dead ends). So you can see that even a tiny 5×5 maze with three obstacle blocks has quite a complex state graph.
Measuring puzzle quality
To generate good new puzzles, we have to be able to tell the difference between a good puzzle and a bad one. What makes a puzzle ‘good’ is a hard thing to pin down, but we can pull out a few ideas such as it having a long solution, many dead ends, looking deceptively simple etc. For our purposes though we need to come up with a single score for the quality of a given puzzle, such that a higher score means the layout is ‘better’ in some sense.
One approach is to analyse the graph that the solver produced, and score it using a weighted set of criteria. The criteria I used are:
- Number of nodes – more states means a more complex puzzle
- Solution length – longer puzzles tend to be harder
- Number of branches – choices and dead ends are what make the puzzle interesting
- Number of blocks – give this a negative weight to prefer simpler looking puzzles with less obstacles
- Number of turns – requiring more direction changes can be a more interesting solution
- Average loop length – large loops in the graph make it less obvious when you’re on the right path
Different weights can be assigned here depending on what characteristics you want in your generated puzzle.
A more interesting block – 60 move solution
Genetic algorithms
So now we can give a score to a specific puzzle, but we need to use this to come up with the best puzzle possible. For this we can use a type of genetic algorithm.
Genetic algorithms are based on the same principles as evolution in the real world: using randomness to slowly evolve towards an optimal solution. The idea is to start with a solution (any solution), and then randomly modify it a bit. If the new solution is better than the old one, keep it, otherwise throw it away. Repeat this process many times, each time starting with the best solution you’ve found so far. To tell if a solution is better than the previous one we apply a fitness function to see if it survives to pass on its ‘genes’ (or instead gets eaten by bears). After a while, you can stop the process and take the best solution found so far as your result. Despite what creationists may tell you, order can result from randomness (plus a fitness function).
In the case of a rolling block puzzle we start with either an empty board, or one with a few random blocks, and a mutation rate (maybe 5%). Each iteration we check every grid square to see if it ‘mutates’ (toggles between obstacle and empty). The fitness function is the puzzle score described earlier. If the score is higher or equal we keep it. Then just keep going as long as you want.
And that’s pretty much all you need to generate new puzzles. The key is the fitness function – the better it fits our subjective opinion of “this is a good puzzle”, the better the generated results will be. I’m sure that there are much better fitness functions out there but this one works well enough.
Here’s a video of it in action.
References
Robert Abbott’s Logic Mazes page
A bunch of mobile games using a similar puzzle
Example solution (L is up-left): LURDRDRDDDLLLULDRRRRULDLLLUUULUU