HiveMindStudios

Creating great software, one line at a time

Blog

A deeper complexity to puzzle generation

 Posted by Rowan Powell on September 1, 2015 at 5:45 AM comments (0)

So in my most recent project I decided to make a puzzle game, but rather than just hard-code a whole ton of puzzles I decided to make the computer attempt it for me, with mixed results.

The algorithm that I built for this is fairly simple and is based of simulating a player 'solving' a puzzle that doesn't exist and building a solution to that effectively random wandering.

• Pick a direction to move (Ideally not where we just came from, but sometimes this can't be avoided if we get trapped in a corner)
• Move some random amount that way
• Try to put a rock down that would have stopped us at this point, if this wouldn't have been a viable stop point, keep moving until we hit an edge or we can put a rock in front of us
• Repeat this for a desired number of moves for this level
Ideally, this produces something that looks a little like this process;

but sadly, because the computer is walking somewhat randomly and because of the nature of ice sliding puzzles, it's very very easy for the algorithm to make solutions that either have the goal at an edge or that can be reached much more quickly than expected. Though this can be accounted for using While(isEdge(previousPoint)){keepMoving()}, but this solution can lead to infinite loops if the algorithm cannot find a new place to stop. So the process tends to end up looking a bit more like this;

A more well thought out algorithm could try to enforce that the next step is more steps away (Pathfinding) than the previous one by exploring a graph of nodes around potential stop points. This could be quite costly however, especially for bigger puzzles, and would take a more complex algorithm than a randomwalk approach does.

Ultimitely the result for this game was a sucess, the algorithm creates a huge amount of fairly simple 2-step to 6-step puzzles and the difficulty can be bumped up by asking the player to do some other puzzle solving alongside it. For example the extra modes in this game are Moon levels (Where each alternating step, the board is blacked out, so you need to memorise the next step) and by hiddenBlock levels (Where all the blocks are hidden until you bump into them) which extends the lifespan of the game somewhat.

Initial playtesting shows that people will play about 20-30 levels, but then will bore of the lack of difficulty and no new mechanics to learn.