Thursday, November 04, 2004

A* Visualization

I've continued to make good progress on my game. One area that's been pretty fun is getting pieces to find a navigable path across the map. The algorithm I've used is called the A* algorithm .

A* is recursive and backtracking and as such it can be a bit tricky to debug. When I first implemented my version I made a small mistake that caused certain complex paths to be unresolved. The depth of the search and the number of backtracks made it very hard to analyze what was really going on. To help out I animated the search. As the search proceeded I drew the path being tested on the map (I added some sleep time to make it more watchable.) The results is that you can see the algorithm probing the nooks and crannies of the terrain trying to find a path from point A to B and from watching this behavior I was able to pinpoint the problem.

I'm certainly not the first to think of this, there are other examples of A* animation out there. But I like the effect so much I think I'll make it a configurable part of the game.

Post a Comment
The Out Campaign: Scarlet Letter of Atheism