The first week of the Stanford AI Class focused on route planning.  This is a pretty standard problem in computer science, with a number of well known solutions, including depth first and breadth first tree searching (it either means something to you or you really shouldn’t care).  Both of these have the drawback of taking a while to focus on the best route, so by simply applying a heuristic (a guess) to the remaining distance from each tested location, the algorithm should focus on the best path faster.

This slideshow requires JavaScript.

Here’s a few screenshots of the A* at work – blue is the starting point, pink the finish, yellow the tiles tested, and white the optimum path.

In this case there is a bug which means something is out of whack.  Unfortunately Processing (the language I’ve been using as a demo tool) doesn’t have much in the way of debugging, so I’m going to have to move to C++ or Java in XCode or Visual Studio.  It’ll take a while to transition this code, so I may as well head down the C++ route (in my opinion more useful as it allows me to easily port code to the iOS devices).

Advertisements