From: benjohn@...
Date: 2006-10-14T00:17:32+09:00
Subject: Re: [QUIZ] A* (#98)

I wrote:
> Well, A* is a _dreadful_ algorithm for route finding, so there's plenty
> of scope for finding a way better approach :) Field Guidance, Ho!

If no one minds too much, I'd like to reject what I said about 20
minutes ago about A*. I said it from an uninformed position.

It sounds like it's more of a general search algorithm for finiding
optimal paths. It may be applied to route finding, but can be used for
other search problems. The huristic (in the quiz, the Manhaton distance
is suggested) is very important and has a great impact on its
performance (it can also break the algorithm if it over estimates cost).

It's discussed on wonderful wikipedia:
  http://en.wikipedia.org/wiki/A-star_search_algorithm

Field guidance is also a wonderful approach, and can give much more
"human" route planning. It's also great for allowing incomplete
knowledge to be handled, and it's nice at doing things like having a
unit of troops march in formation, but gracefully avoiding tree stumps,
and breaking formation near a wall, etc.

Cheers,
  Benjohn