The piece of code I wasted a chunk of yesterday writing was the most ludicrously over-engineered font engine I've ever heard of. If anyone thinks they can do better I'd be fascinated to hear it :-)

About eight years ago, I wrote a small PC game called Sumo. Last weekend I began the process of porting it to the Playstation 2, and realised that it was going to need a couple of configuration menu options that the PC version had got away without requiring. Therefore, it was going to need some more pieces of text, written in the same font I'd used for the original game. The only trouble was, I'd never designed a whole font for the original game; I'd sat down with Deluxe Paint and drawn the specific words and phrases I'd needed, by hand. Since I didn't feel much like firing up the Gimp and doing the same thing again for twice as many bits of text, I started wondering about automatically generating them.

What made this hard is that the font in question is context-sensitive. Each letter can be extended out of its character cell in a variety of ways; letters like H, N and Y, which have vertical strokes ending at the top or bottom of the character, can have those strokes extended upwards or downwards as flourishes, and many letters can be joined to the next letter by sideways extensions. At the start and end of words, letters like T and Z which have horizontal strokes ending at the edges of the word can be extended a little further as another type of flourish.

Of course it was easy enough to encode the core character shapes into a piece of code, and it wasn't that much harder to add annotations that told the font engine which stems it was allowed to extend and connect in which directions. My initial stab at a font engine just made random choices about what extensions to use; unfortunately this had a tendency to cluster extensions too close to one another, and leave other stretches without any, which looked wrong. Introducing blocking rules which disallowed extension clusters just made the extensions still more sparse. A better solution was required.

So I thought about it for a while, and I hit on a dynamic programming algorithm. I work along the string, and for each character I run through all the possible ways I could extend that character. Then I check each one against the possibilities I've stored from the previous character, and reject combinations that don't obey the ground rules (which outlaw overcrowding, and also obvious nonsense such as trying to connect a character to the top right corner of an L). Now, for each possibility for this character, I choose which of the possibilities for the previous character I should put it with to maximise the total number of extensions, and store that. Then I move on to the next character, and do the same for that.

The upshot of all this is that the algorithm, in O(N) time, ends up optimising globally - along the whole string - to find the largest possible number of extensions which obey the ground rules. It's important to realise that this is a true global optimiser: it's not an approximation technique such as you might use for an NP-complete problem, and it's not anything like a greedy algorithm which finds generally good solutions but might miss a really clever one that does better, and it never gets stuck in a locally maximal solution which isn't the absolute global optimum. This algorithm is perfect. Whatever possibility exists and has the highest score, it will find.

The beauty of it is, once I'd finished tweaking it it turned out practically identical to the rule set I must have been subconsciously obeying when I drew the original examples of the font. Several of the original game phrases, when run through this font engine, come out exactly the same as the versions I'd hand-drawn; and the others look if anything marginally better in their automated form.

I love playing with global optimisers. They feel somehow truly magical. Partly it's because so much of orthodox computer science teaches that most optimisation problems are NP-complete and the best you can practically hope for is to find 95% solutions, so it's always a breath of fresh air to come across a situation where that isn't true. Partly it's because the form of the code is so completely declarative: I don't have to do any mathematical mungings on the rules and scoring system to encode them into the program, I just write code which directly tells other parts of the optimiser "This combination is illegal" or "This combination is legal and scores 43 points" - and if I decide I got a rule wrong, I just rewrite it so it says what I wanted it to, and the whole optimiser will then uncomplainingly optimise according to the new rule instead. And partly it's because you really can see the behaviour being global; I can change something at one end of the text string, and extensions on the characters at the other end will flip into a different configuration as a result.

I'm sure that all this whizzy technology is massive overkill for a piece of code which will be used in Sumo to display perhaps ten or fifteen different pieces of text, and I'm sure I could have drawn those pieces of text by hand in a fraction of the time it took me to design and implement this optimising font engine. But dammit it was so much sheer fun, to design and to build and to play with, that I will absolutely refuse to admit having wasted my time on it.