A 'hints' button is probably the most requested new feature for Ancient Frog. Time spent on free updates for Frog is time not spent working on the next game, but since each update gives me a little bump in sales, I'm going ahead and adding this feature. Having hints will also mean I can put some harder levels in the demo without (I hope) alienating people - I'm hoping this will make the demo a more effective sales tool.

It's an interesting problem to tackle, though. I'll start with the technical, and move on to the presentation.

The first thing that's needed is for the game to be able to work out what the best move to make is. This turns out to be really hard. A typical puzzle takes about 20 steps, and each pose can typically reach about 16 other poses, so that makes about 10^24 possible moves to search through. If it takes one microsecond to check a move, it would take about three times the age of the universe to find a solution.

Now, real puzzles don't allow the full range of movement at every step (they wouldn't be very interesting if they did), and there's a whole bunch of optimisations and shortcuts you can take to discard obviously wrong solutions. During development I wrote a tool to check the solutions to every level, and on a fast dual-core machine with 4GB of RAM, I have to leave it running overnight to verify all 100 levels. Some of them it can solve in under a minute, others take over an hour.

Clearly, this isn't going to work on the iPhone.

So what can I do? Well, I can store the solution that was calculated during the build process, and lead the player through that. But that only works if they're at the home position, and if they're looking for hints it's probably because they've tried a load of stuff and got stuck. I could make the game insist that they reset to the start before getting a hint, but that's not very elegant.

A better solution is to search backwards through the cached solution, looking for poses which are reachable in a couple of moves from the current pose. If we find one, we pick up the solution from there. That's great, but it only works if the player is on pretty much the right track. If they've gone off down a dead end, this system won't be able to find a pose in the solution that's close enough to their current position, and we're back to requiring a reset.

Luckily, we have another useful list of valid moves - the undo buffer. Because Ancient Frog stores every move to allow the player to step backwards, the hint system can use that. It just needs to search backwards through the undo buffer, and for each pose, search back through the solution to see if it can step from the one to the other. In the worst case, it would move back through the undo buffer right to the start, and then forward through the cached solution to the end. In practice it can usually get onto the solution after just a few steps back.

As a final refinement, it looks for shortcuts in the undo buffer (the player may have spent some time going in circles, or taking several moves to reach a pose right next to an earlier position), and trims them out.

That's the stage I've just finished. I can press a button, and the game will show me the best next move. It's pretty effective too - I've tried tying it up in knots, and in my testing I haven't been able to create a situation where it seems to be taking longer to get back on track than I'd expect. It won't always get the perfect solution from a pose several moves in the wrong direction, but it does a pretty good job of it. And if you start from the beginning, it will always lead you down the optimum path.

So that's that problem solved. But the aim of the exercise is not simply to find a solution and lead the player through it - it's to provide a hint. What I want is to provide an intermediate goal for the player to aim at, which will help them on their way. One of the criticisms levelled against the game in some of the App Store reviews was that playing it is a matter of trial and error rather than problem solving. That's not the experience I want people to come away with - clearly I haven't done a very good job through the level progression of teaching the tricks of the game. The hint system gives me another shot at it.

In each level there is usually one (or more, in harder levels) core move that holds the key to solving the puzzle. One that I use a lot is the sidestep across a gap:

The key to solving this type of puzzle involves getting into a position such that the hands can plant on either side of the gap, with enough room to swing out of it on the far side.

What I want my hint system to do, then, is identify these core moves, and show them as the intermediate goal. I don't want to manually tag the move for each of the 100 levels (and not just out of laziness - if the player is coming from a position off the cached solution, their core move may be in a different position). So how do I automatically identify it?

I'm currently experimenting with this, and it seems that the foot moving a particularly long distance in one go is a good measure of a core move. But there's work left to do in balancing how many moves ahead to limit the hint to, against how important the core move is. I'm also undecided about whether I should be showing the pose immediately before or immediately after the core move.

The remaining tasks required by this feature become easier to implement technically, and harder to design from a useability standpoint. For instance, I need to decide when to show the hint button - should it always be visible, or only appear if the player is struggling? How do I define struggling? Resetting the level is a good indicator, but some players don't even realise they can do that. When the button does appear, where should it go? only the Daisy corner is in clear space - anywhere else, and I'm in danger of covering up a peg. How do I mark puzzles that were solved with hints? I don't want people to feel they're being penalised for using a feature they were offered, but I've also had emails from people who've been solving the game the hard way and don't like the thought of other players just being handed the solution on a plate.

These are all surmountable problems, and I look forward to fiddling around finding the most elegant solution. But I thought it might be interesting to show what goes into satisfying a request as simple as 'add a hint button'.

Alongside this work, I'm also knocking the PC version into shape for a slightly unusual potential platform - more details on that when it's not a secret any more!