I'm writing a version of that boring-lecture classic Vector Racer (if you don't know what I mean have a look here: http://vectorracer.boschloo.net/ I have the game working for hot-seat multi-player but I'm looking to add AI bots for humans to race against. I'm looking for the bots to be able to move round the track without augmenting the track with any AI-only information. In my version of the game there is no penalty for moving onto the same space as a another player and you're immediately eliminated if you cross a wall (or there's another mode where your car is halted, vector reset to 0 and you suffer a turn penalty instead). Anyway, I thought that this would be a simple case of coming up with a heuristic for A* but I find myself stumped, I simply can't come up with an admissible heuristic, nor can I work out how to get the search to search for an entire path round the track. I suppose if I think of distance to checkpoints rather than number of turns taken that might get me something workable. So is A* the right approach to take here and if so anyone have any idea about a heuristic to use?

A* would definitely work. Remember that the current velocity is also part of the description of the node.

A constant 0 is always an admissible heuristic, in which case A* degenerates into breath-first search. I'm sure you can do better than that, but if you can't think of anything you can finish the rest of the program for now.

So it turns out A* is a good fit as I can't come up with a decent heuristic involving turns taken.

However, greedy search using combined distance to all checkpoints not yet passed works a treat. Yet again I should have started with the simplest solution and increased the complexity rather than yelling 'Eureka!' when I hadn't fully grasped the problem.