Also see Amit’s introduction to A*^{[1]}. The following was posted to Usenet in 1995:

Article 63291 of rec.games.programmer: Newsgroups: rec.games.programmer Path: nntp.Stanford.EDU!news.Stanford.EDU!bloom-beacon.mit.edu !spool.mu.edu!howland.reston.ans.net!news.sprintlink.net !news00.sunet.se!sunic!news99.sunet.se!umdac!cs.umu.se!christer From: christer@cs.umu.se (Christer Ericson) Subject: Re: Command & Conquer --> Shortest Path? Message-ID: <DHzp4B.BF7@cs.umu.se> Sender: news@cs.umu.se (News Administrator) Organization: Dept. of Computing Science, Umea Univ., 901 87 Umea, Sweden References: <476mnc$cv2@newsflash.concordia.ca> <Pine.ULT.3.91.951108164433.15443D-100000@ulke> <DHs94p.vM@undergrad.math.uwaterloo.ca> <47vpar$802@ulke.himolde.no> <DHxxHH.8wE@undergrad.math.uwaterloo.ca> Date: Mon, 13 Nov 1995 16:14:30 GMT Lines: 40 In <DHxxHH.8wE@undergrad.math.uwaterloo.ca> crpalmer@solo.uwaterloo.ca (Chris Palmer) writes: >[...] >If you really need a great deal of speed then you probably want to look >into the A* set of algorithms. They provide the ability to look for the >most likely solutions before trying the full range and will always find >a shortest path (if it exists). Not quite. The A* algorithm is optimal iff you have a heuristic function that is a lower bound on (underestimates) the actual cost from current position to a goal node. If this is indeed the case, the algorithm/function is said to be admissible. (In the strictest sense the algorithm should be called A*, "A-star", only when it is admissible, otherwise just A.) Zero is a guaranteed lower bound for all functions, but then you get a breadth-first search. For the type of search problem that you have been discussing here a better lower bound is dx+dy (ie the Manhattan distance) if the neighbourhood of the current position is N-S-E-W and perhaps some- thing like max(dx,dy) or max(dx,dy)+min(dx,dy)/2 if you have an eight-way movement neighbourhood. By selecting a heuristic function that is not a lower bound you are no longer guaranteed to find a shortest path, however you are likely to spend much less time in searching for a (longer) solution. I would definitely suggest that people look into the A* algorithm (if they haven't already) if they are interested in the shortest path problem. For gaming purposes it is often possible to use another non-optimal routine, but A* is still a contender in most cases. More info on the A* algorithm is found in any decent AI textbook. I've been using Ginsberg's "Essentials of Artificial Intelligence" in my class, but Russell's and Norvig's "Artificial Intelligence A Modern Approach" is possibly an even better general textbook (though harder to read). Nilsson's "Principles of Artificial Intelligence" has even more on A* (not surprisingly, since Nilsson came up with A*) but is otherwise rather dated. Christer Ericson <This space for hire!> http://www.cs.umu.se/~christer/ phone: +46-90-16 67 94, fax: +46-90-16 61 26, email: christer@cs.umu.se Department of Computing Science, Umea University, S-901 87 UMEA, SWEDEN