My thrashing around trying to pin down the details of project Blue Comb continues. I have decided on an art style, which is helping to frame the rest of it. Ancient Frog started with a very simple and clear premise, but this new project is just a collection of obsessions which I haven't yet managed to glue together. I suspect something will need to get cut before I'm able to finish it.

I just received an email from Jef Armstrong, whose game Mondrian was recently released. Jef emailed me last year, shortly after Ancient Frog was released, saying words to the effect that he liked my puzzle game, he was writing his own puzzle game, so let's talk about puzzle games. Flicking back through the emails, there's some blogworthy stuff about how I created the levels in Ancient Frog:

Creating the puzzles was one of the big challenges with Ancient Frog. I've been thinking about writing a blog article about it, because it's something I personally find fascinating. A large proportion of all the code written for Frog (possibly the majority - I should check) went into the tools for creating the puzzles. However, I'm a bit wary about talking too much about it in public because I suspect that some people would be disappointed to learn that it's not all lovingly hand crafted by some sort of puzzle making master craftsman.

Seems a bit silly now. Let's hear the details!

The most important part of the toolset is the solver. This has two levels - a quick pass to determine whether a particular layout has any solution at all, and a slow pass to exhaustively determine the optimum solution. (In this context, 'quick' means anything up to 15 seconds, and 'slow' can be up to 6 hours). There's nothing clever about the way it works. It uses brute force and a fast computer to walk down the tree of possible moves. There's some interesting optimisation, and stuff like exploiting symmetry, early-out, loop detection and so on, but essentially it uses the approach that computer scientists say is impossible. But that's because it's their job to come up with general solutions which work for the worst cases in the biggest data sets. I'm able to limit the problem space to something which is achievable by brute force, and just skip puzzles which are taking too long to check.

So the process for generating a puzzle goes like this:

* I choose a start point and an end point, and a set of pegs from which it can choose its route (this lets me put a particular move into a puzzle, but often I'll just leave it to choose from all pegs)

* I press the magic button

* It goes through a loop where it removes a random peg and tests whether a solution exists. If there is no solution, it replaces the peg and flags it as required. This process is repeated until no peg can be removed without creating an impossible puzzle.

* It checks the result against all the previously generated puzzles to ensure it's not a duplicate (taking into account simple translation, rotation and mirroring)

* If I like the look of the result, I press magic button #2 and generate the optimum solution for it

* I quickly step through the solution to see if I like the look of it. I tend to reject puzzles that require too much walking backwards, or that push the frog's head off the side of the screen or have the legs passing over the fly.

I like to generate a whole bunch in one sitting, then try to put them in order based on how difficult I think they look, and how difficult the solver reckoned they were (that's a bit of code that needs some work by the way - some of my rankings are quite a bit off). Then I leave them for a day or so while I get on with other stuff, so I can play them through without knowing how they're solved. In my playthrough, I log how long it takes me to solve, how many dead ends I go down, how many undos etc, all of which information also goes into the difficulty ranking. Each time I play through, I'll generally shuffle levels around a bit to improve the progression, but I also like having runs of very similar layouts with increasingly difficult solutions.

The tools also include stuff for applying backgrounds, frog species, fine-tuning of board position, rotation & translation of the whole puzzle and so on.

Interesting stuff!

Happy new year.