Saturday, January 18, 2014

So much for a friendly hint system

Most puzzle games on the app store these days have a hint system.  It makes sense.  It's an easy way to make a little bit more money and allow frustrated players to move past a level they are having issues with.  The typical setup is that the player is given a few hints for free, and when they run out, they can pay for more. 

Ideally I wanted my hint system to be able to look at the current state the player is in a immediately figure out what the next best move is to complete the level.  This meant that I needed to teach the game to play itself.  Which is easier said than done.

I attacked this issue through the use of a state machine.  Basically having the computer try every possible move (while making sure not to get in a loop) until the level is solved.  How this works is first every game state that is only a single move away is recorded on a queue.  Then, one by one, the states are popped from the queue and every new state that is a move away from that popped state is pushed onto the back of the queue.  This is repeated until either a solution is found or we run out of new states to explore (every state has a signature which is kept track of so that we don't get repeats).

While I did finally get this algorithm functional, it takes waaaaay too long.  The number of possible states from a simple 5x5 level turned out to be a lot larger than I anticipated.  I'm talking a possible over 100,000 states for something that can be completed in three moves.  So it looks like an imidiate hint system isn't really an option.  What I'll have to do is pre-calculate the optimal path for each level beforehand and if the player asks for a hint, I'll start them from the beginning and show them that path.  Not as friendly, but I don't think there are any other options. 

Now if the system would just finish figuring out the 9 move puzzle I started it on since before I started writing this...

No comments:

Post a Comment