Wednesday, 30 January 2008

When games programming experience becomes valuable for solving other problems.

As part of the large multimillion pound project I'm working on at work, there are lots of little tools that I've had to build to aid content authors and the technical team in the development process.

One of those tools is an automatic menu generator. We have a slight problem where, as part of the resources we're building, there are going to be about forty HTML pages with content that we don't know about and a structure that hasn't been decided yet and they need to be ready (with everything else for the next delivery) in only a couple of weeks. To top it off, the design hasn't been implemented yet either.

Developing a tool to help us to cope with a situation like this is obviously not that easy, but having some application that you can throw a template at (for the design), an XML file (for the navigation) and have it spit out the resulting transformed HTML is tremendously useful. It allows us to move quickly and meet the deadline even if the content authors are extremely late at bringing all the assets to the table. So that's what I've been working on for the past few days and brings us up to scratch with where I'm at.

I have the tool working and generating the navigation menu, which needs to show the detail for the level you are at within the structure, as well as menu options for the levels above. I use recursion for parsing the navigation XML and have it spit out the final HTML based on this; but it turns out this wasn't enough.

As each navigation branch in the structure tree could potentially contain the current page that the user is on, it suddenly occured to me that this was in essence, a pathing problem. Only the path through the resource that the user has taken to get to any particular page should be "open" on the menu. Other paths should remain closed, as only the sections that a user has gone through to get to the page they are on should be shown. I realised pretty quickly that I could bring my A Star programming experience to this problem in order to solve it. I was right. A Star is a famous algorythm used for finding a way around a map by opening and closing nodes. It normally involves a heuristic to optimise the pathing but I didn't need it for this; the navigation is not in 2D space, so that simlpified matters somewhat.

Ten minutes later, I had implemented a slight variant of A Star and fixed my menu transformation so that it produced the correct data. Bringing my games programming experience to bear on this specific problem was a huge benefit. I wonder if there are other problems I could use A Star to solve that are not game related?

No comments: