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!
