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