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:
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:
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.