Just a level solver: Why my simple puzzle game took me over a year to complete

For my first serious attempt at creating and releasing a polished, professional looking game, I decided to go with what I thought was a simple concept: pull snakes out of the way and get the mouse to the exit.  Of course, as with most worth-while endeavors, things are never as simple as they seem.  I had issues with contractors, difficulty with a poorly documented game engine, and just general problems keeping myself motivated and on-task (being your own boss is both a blessing and a curse).  But one of the biggest time sinks was creating all 75 puzzles I needed.  And one of the biggest reasons for that was that my simple puzzle idea ended up being incredibly computationally expensive to solve. 

Pretty early on in the game's creation (before I even had an artist) I decided to make an in-game level editor for myself.  This was probably one of the best decisions I made during the whole crazy process.  I hooked it up to a Parse back end so that I could easily experiment with new ideas and when I was satisfied with a level, saved it to the cloud.  Then later I could grab that level on my computer, figure out its solution, estimate the difficulty, and integrate it into my game. 

It was taking me some time to find the minimum-move solutions, but it was kind of fun and I was confident in my own abilities.  Until one day one of my testers told me he beat the min-move score I had on a level I was SURE I had found the best solution for.  By two whole moves as well.  At that point I knew I needed to write a level solver.

Before I get into my solver, let me explain a bit about how Too Many Snakes works.  It's inspired by the classic sliding blocks puzzle game which has popular iterations under the name Rush Hour (the physical board game) and Unblock Me (the mobile game).  The goal of this game is to slide a special block out of a grid.  But there are other blocks in the way which must be rearranged to make a path for this special block. 

My unique (and literal) twist on the concept is to switch out rigid blocks for bendable snakes.  In Too Many Snakes, the player must pull and twist snakes out of the way so that they can move the mouse to the exit of each level.  And the objective is to do this in as few moves as possible.  Like so:

Note, a move is counted like a chess move: only once the player has lifted his or her finger.

The general strategy for programmatically solving this type of puzzle is simply brute force.  From the beginning game state, you first find all new states that can be reached with a single move.  From there, you find all additional states that can be reached with a second move.  And repeat for move three etc until you've found a winning state.  This is also known as a 'breadth-first' search.  The first iteration of this didn't take me too long to write.  I reused a bunch of my game code and was even hoping that I could implement the solver within the game as a hint system for the player.

However, I quickly realized a dynamic hint system wasn't going to be possible.  The solver was taking waaay too long and gobbling up memory even when running on my relatively powerful laptop.  So my first order of business was to re-write the solver outside of my lua-based game engine as a stand-alone C++ app.  It had been some time since I worked with C++, but I eventually got it working. 

Running as compiled C++ helped a lot.  But it was still too slow and memory intensive to solve many of my levels.  At first I thought there must be a bug in my code.  But after experimenting a bit, I realized that my mechanics just lead to a very large number of possibilities per move.  As an example, here's a small sample of all possible first moves of level 57:

Start state

Some possible first move states:

There are actually a total of 126 unique states that can be reached in the first move alone for this level.

Having determined the issue was probably not a bug, it was time to look for ways to optimize my code.  I started with looking at one of my most common operations: hash table access.  In order to keep track of all of my game states, I stored them all in one large hash table.  This way I could make sure the solver wasn't re-examining states that were already attainable with fewer moves. 

One of the most important parts of having an efficient hash table is making sure you're using an efficient hashing function.  And after a bit of research, I settled on the open source SpookyHash (http://burtleburtle.net/bob/hash/spooky.html).  It's apparently very fast and has a low collision rate.

So that helped a lot with my speed issues, but I was still having memory issues.  Again, the main culprit was my giant hash table of previously found game states.  I considered storing them in a database, but I figured that would add too much overhead to be constantly accessing.  So what I really needed to do was condense my saved states.  At the time I was storing each state as an array of 1 byte integers.  Each item represented the type of object occupying a space on my game grid.  I had 12 types in total:

       0. The empty space, represented by the '_' character in my string representation.

So as an example, this level state:                                          would be encoded like this:

Which, flattened out, looks like this:

Which is actually represented in the computer as a 25 item long array like this:

Each game state can be represented by a 200 bit long array.  But looking at it, I really didn't need all those bits.  Because there are only twelve possible values for each space, I could actually represent each occupant with just 4 bits instead of 8.  This would save me a bunch of memory (and should make my hashing even faster).  The only thing is, there isn't really a concept of a 4 bit integer in C++.  So what I ended up implementing was a way to pack two 4 bit values into one 8 bit int.  It wasn't pretty, but it works.  Here's the code for accessing this custom array type to demonstrate:

Finally I was able to solve even 12 move solutions on my computer.  In fact, this worked great for all the levels of my first two worlds where the grid is 5x5.  However, my final level set (levels 51 through 75) has a 6x6 grid.  By expanding the grid by just one space, it adds a whole order of magnitude more possible states.  My computer couldn't handle it.  The solver was eating through my 16 Gigs of memory in no time.

I was stumped.  Out of optimization ideas, I considered giving up.  Maybe I could just put in the best solutions I found on my own and make it a competition for my players to beat those scores?  I could even have real rewards for players who found better solutions... But I really didn't want to resort to that.  And then one day a new idea came to me.  I didn't have enough memory to solve my levels on my own computer.  But I could rent a computer that did.

Through my web job I'd become somewhat familiar with Amazon Web Services (AWS).  Basically Amazon has a service (EC2) where they rent out virtual computers and charge by the amount of time used.  Their most memory heavy instance, the r3.8xlarge, has 244 Gigs of memory to play with.  The cost wasn't too bad either.  About $3 an hour of use.  So I reserved a machine, uploaded my solver, ran it, and waited.  It was a bit stressful watching the memory consumption climb and climb, but it worked!  Some of the levels were taking over 100 G's of memory to get through, but I was getting solutions.  I actually managed to get solutions for all of my final 25 levels within a few hours.  At least, all except my last level.  That level actually ate through all 244 Gigs of memory and crashed the virtual computer.  Luckily I was watching at the time of the crash, and I saw it was evaluating move 20. I had already found a 20 move solution on my own. So I could be sure there wasn't a better answer out there.

I screen-capped a little bit of the memory devouring process:

So that's the story of one of my many small victories in bringing Too Many Snakes to market.  I'm pretty happy to have finished and released a game on my own (shameless plug, go get it on the app store now! :).  That said, I'm sure a bunch of you are thinking "Pshaw!  I could totally come up with something much more efficient."  And I'd actually love to see it!  I still have the nagging feeling that there's a much better optimization out there that I didn't think of.  So in that spirit, I'm releasing my level-solver code to the world here:

https://github.com/whalefood/TMS-Level-Solver

I cleaned it up a bit, but it's far from pretty.  And I'm sure someone more proficient in C++ will cringe at some of the things I'm doing.  But I've always thought one of the best way to learn is to be open and share your mistakes.