A* Archive

The conversation here is from comp.ai.games. You can read it on Google Groups.

• William Uther
  • William Uther
• William Uther
  • William Uther

• Amit J Patel

  Prim's v.s A* (was Re: A* question...)

  • Jason Alan Nordwick

    Dykstra v. A* (Was Re: Prim's v.s A*)

    • Bryan Stout
      • Brian Fitzgerald
      • Jason Alan Nordwick
        • Bryan Stout
      • Christer Ericson
        • Bryan Stout

• Chris Palmer

  Dykstra v. A* (Was Re: Prim's v.s A*)

  • Bryan Stout
    • Ben Bennett

• GMMedia

  Something new 'n something old (Re: Dykstra v. A*)

In article <54qhea$qg8@freenet-news.carleton.ca>, aq834@FreeNet.Carleton.CA
(Daniel Royer) wrote:

>  About the A* search algorythm, I notice that the routine takes all the
>best nodes of the same f value, where 
>
> f = g + h
>
>and
>
> g = 1
> h = distance from current(x,y) to goal(x,y)
>
>I find that on most maps this can create a lot of extra work.  Worst case
>scenario would be starting point and ending point parallel, divided by a 
>vertical line.  What I was wondering is:  would it be better to simply take
>the best node of the PREVIOUS best node?  I'm hip deep in code at the moment
>and don't have time to test this, so I thought I'd post.  Thanks,

There are a few interesting points here.  Firstly, in a discrete world you
can often end up with a large number of 'optimal' paths.  Some A*
implementations will explore all of them.

Comsider all those paths that are equally best in the priority queue.  If
you take one, and it has a child of the same value (heading along the same
path, you move some value from h to g but don't modify the total), then
that will be inserted into the queue.  BUT, A* doesn't specify how to
handle ties.  Considering only those equally optimal entries are the front
of the queue, our new entry could be added to the front of this list, or to
the end of this list. (or anywhere in between).  Adding to the end of the
list (as a naieve heap would do) leads to an A* search that does Breadth
first search amongst the optimal paths.  Adding to the front of this list
of 'optimal' elements leads to an A* that does Depth first search amongst
optimal paths.  This second is probably better.

Basically, when you're moving the element down through the heap, move it
down if it's <= it's parent, rather than just <.

There is a related algorithm called Approximate A*.  It relies on the same
observation as above, but, whereas the above only really helps with perfect
heuristics and/or coarse grained discrete spaces, this one works in more
places.

This variant or A* is only approximate, but the amount of error is bounded
by a fixed, user-definable value; and the algorithm works well even if that
value is small (when it's 0 it reverts to something like the above).

Assume we have second heuristic s, which is an estimate of the number of
steps to the goal (this does not have to be admissable - always an
underestimate).  We also know e which is our bound on the maximum allowable
error.  Now, instead of selecting the node with the smallest f (= g + h) to
expand, we look at all those nodes which are within e of the smalled f;
>from amoungst these nodes we pick the node that has the smallest estimate
s.  i.e. we find the node that has the smallest f - say f'.  we then look
at sll the nodes which have f < f' + e, and pick the one of these that has
the smallest s to expand (i.e. we estimate is closest to the goal).

This algorithm is guaranteed to find a path that's within e of optimal.  It
can be much faster than A*.  Often h and s are the same function.

Have fun,

\x/ill      :-}

-- 
William Uther          "Give me the strength to change those things I can
change,
will@cs.cmu.edu             The patience to accept those things I can't change,
Dept. of Computer Science,       And the wisdom to know the difference."
Carnegie Mellon University         http://www.cs.cmu.edu/~will/

In email, Daniel Royer (aq834@freenet.carleton.ca) wrote:

>Thanks for the info.  I'm new to the AI part of gaming, so please, forgive
>my ignorance.

Not a problem - everyone has to start sometime :).

>Can you name a few good books on AI logic (ie smarter enemy
>"generals")?

I don't know any AI books that I like.  I don't know of any at all on ai
gaming.  Look at the stuff on the web though.  The FAQ for this groups has
pointers to it.

>  One other thing:  I'm not sure I understand this S value thing.  How does
>it relate to f'?

OK.  Normal A* searches to find an OPTIMAL path - i.e. a shortest path. 
this means that if there are 6 paths that at all close to optimal, A* might
have to search along them all to find out which one is best.  Often this is
not the behavious you want - you don't care if the path is exactly
shortest, as long as it's close.

In normal A* I believe the formula is f = g + h.  g is the actual distance
travelled so far, and h is the heuristic estimate of the distance to the
goal.  In other words, f is your estimate so far of the total length of the
path that goes through this point.  At each step in A* you expand the node
that has the shortest estimated total path length.

If you have 6 paths that are very close to each other the one with the
current shortest estimate path length might keep changing.  Or, they might
have equal estimate path lengths, but you break the equality differently
each time.  In this case you are doing alot of work finding the OPTIMAL
path.

In Approximate A*, you don't select the path that has shortest estimated
length.  Instead, you look at all paths with reasonable estimated length
(their estimated length, f, is within e of the best estimated length), and
pick the one that is closest to complete.  To do this you need an estimate
of how far the path has to go before it's complete - this is the 's' I
talked about.  Often each step in a problem has equal cost, and in this
case 's' will be the same as 'h', although they are used in different ways.

  So, you go through your current list of nodes.  You find the one with the
shortest estimated total path length (f).  You then look at every one with
an estimated path length not too far from that (you still want a reasonable
path), say every one with an estimated path length less than the best f +
e.  Of these paths, you choose the node that is closest to finishing (has
the smallest s value) and expand it.

Hopefully, by expanding the 'reasonable' path that's closest to completion
you'll finish quickly.  Note, s doesn't get included in f anywhere.  s is
just how you pick amongst the 'reasonably good' paths.

\x/ill           :-}

-- 
William Uther                 It's you and me against the world
will@cs.cmu.edu                  When do we attack?
Dept. of Computer Science,
Carnegie Mellon University         http://www.cs.cmu.edu/~will/

In article <54qhea$qg8@freenet-news.carleton.ca>, aq834@FreeNet.Carleton.CA
(Daniel Royer) wrote:

>  Worst case
>scenario would be starting point and ending point parallel, divided by a 
>vertical line.

Just one quick point.  If you have the right representation of the problem,
this can be really easy.  For instance if you have a 'line drawing', put
each 'point' in the line drawing (each position where two lines meet, a
line ends, the start point and the end point) in as a node.  Each node's
children are those points it can 'see'.

In your example this means 4 points, s, a, b and g.  s connects to a and b. 
a and b both connect to g.  a and b might also be connected.  Almost any
algorithm can solve this really fast.

In doing this change, you move the work from searching through lots of
squares, to checking which points are visible from which other points. 
This can be a huge win in a sparce space.

\x/ill        :-}

-- 
William Uther
will@cs.cmu.edu          "The beatings will continue until morale improves."
Dept. of Computer Science,
Carnegie Mellon University         http://www.cs.cmu.edu/~will/

Hi,
  I'm posting this reply to comp.ai.games as well as mailing it becuase I
think it's quite a important point to do with A* and problem solving in
general.

In an email reply, Dan wrote:
>In article <3>,
>will+sp@cs.cmu.edu (William Uther) wrote:
>>In article <54qhea$qg8@freenet-news.carleton.ca>, aq834@FreeNet.Carleton.CA
>>(Daniel Royer) wrote:
>>>  Worst case
>>>scenario would be starting point and ending point parallel, divided by a 
>>>vertical line.
>>
>>Just one quick point.  If you have the right representation of the problem,
>>this can be really easy.  For instance if you have a 'line drawing', put
>>each 'point' in the line drawing (each position where two lines meet, a
>>line ends, the start point and the end point) in as a node.  Each node's
>>children are those points it can 'see'.
>>
>>In your example this means 4 points, s, a, b and g.  s connects to a and b. 
>>a and b both connect to g.  a and b might also be connected.  Almost any
>>algorithm can solve this really fast.
>>
>>In doing this change, you move the work from searching through lots of
>>squares, to checking which points are visible from which other points. 
>>This can be a huge win in a sparce space.
>>
>I'm not denying that this can be done very quickly, but it does so much 
>unnecessary work that it's crazy.

Well, did you see my other post?  Where I explained approximate A*?  The
main point here is that by changing representation it doesn't have to do
all the extra work.  With the representation change above, you can solve
the problem in four steps.  With the representation change, it's not doing
all that extra work.

>Basically there's the main line that
>travels from start to the wall, then up one side and continues in a straight
>line to the goal.  However, every point on the line start->wall will at
>some point have the same value as the main line.  What you get is a
>semicircle with a line extending from one edge.  Waste waste waste.

Well, firstly its not a semicircle, it's a triangle with the wall as one of
its edges, and the start as the opposite point. :)  But aside from that,
the approximate A* algorithm I gave will find the path you suggest (the
main line) if e is high enough.

It's important to note that (if you're using straight line distances) the
'main path' you suggest is NOT optimal.  If A* were to return it THAT WOULD
BE A BUG.  It's interesting to note that optimal (shortest) isn't always
optimal (least work to find a 'reasonable' solution).  Going to the wall
then up and around it is going out of your way.  The optimal path goes
directly from the start to the end of the line, and then to the goal.

I should also note that in finding that optimal path you are making use of
information you havn't given A*.  In fact, it has been shown that A* is as
efficient (expandes the fewest nodes) as you can get (on average) given the
information it uses - if only used the hueristic you gave it you couldn't
do better.  The extra information you are using is embodied in the the fact
that you just decide to go around the wall, and so your eyes flick straight
to one of it's endpoints.  This is identical to the representation change I
described.  Give A* that information and this it's fast.  You could also
code that information up as a heuristic rather than a representation change
- A* would make use of it then too.

\x/ill           :-}

-- 
William Uther          "Give me the strength to change those things I can
change,
will@cs.cmu.edu             The patience to accept those things I can't change,
Dept. of Computer Science,       And the wisdom to know the difference."
Carnegie Mellon University         http://www.cs.cmu.edu/~will/

In article <5h5j8n$6sc@scam.XCF.Berkeley.EDU> nordwick@scam.XCF.Berkeley.EDU (Jason Alan Nordwick) writes:
> Does anybody know of any tests done to compare A* with Prim's for
> single-pair shortest path ?  It would really like to know if there is
> a theoretical and/or actual cross-over to these, when dealing with
> path finding.  And if anybody has tried to implement any good
> improvements to Prim's (or Kruskal's) similar to the one's used
> in the TSP-USA problem (who did this... Cook ?).  I was thinking the
> other day about this, and was wondering if an efficient
> epsilon-approximation in n^3 time would be possible.

Hi Jason,

I don't know of any tests to compare A* with Prim's algorithm, but
isn't Prim's algorithm for minimum spanning trees rather than shortest
paths?

In general, A* "should" have an advantage because it has extra
knowledge of the graph, while the usual graph algorithms do not.  For
example, if you are trying to travel from London to Paris, A* will
tend to spend more time looking to the south, while most graph
algorithms look equally in all directions.

Also, I believe that A* has O(n) average behavior (assuming few
obstacles) on grid-maps, although I'm not sure about this.  O(n^3)
would be far too expensive for my game.  :(


	- Amit

--
Amit J Patel, Computer Science Department, Stanford University 
       ``A language based on point and click is like a 
         human language based on point and grunt.'' -- me

In article <5>,
Amit J Patel <amitp@Ghoti.Stanford.EDU> wrote:
"
"I don't know of any tests to compare A* with Prim's algorithm, but
"isn't Prim's algorithm for minimum spanning trees rather than shortest
"paths?

Yeahm after I posted, I realized that I made referrence to the wrong
algorythm... what I really meant was Dykstra... I always confuse the
names... ohh.. well...

"In general, A* "should" have an advantage because it has extra
"knowledge of the graph, while the usual graph algorithms do not.  For
"example, if you are trying to travel from London to Paris, A* will
"tend to spend more time looking to the south, while most graph
"algorithms look equally in all directions.

However, it also has a larger overhead associated with it, and it
horrible when the graphs are strongly connected, b/c it is a good
tree-walking algorithm, but chunks on graphs.

"Also, I believe that A* has O(n) average behavior (assuming few
"obstacles) on grid-maps, although I'm not sure about this.  O(n^3)
"would be far too expensive for my game.  :(

Where n is what ? the length of the solution path ? then that would
be optimal.  the number of nodes ?  I find that very hard to believe.

Remember,  n^3 is worst time always, and you can provide tweaks that
will move the speed to super-linear but also sacrifice precision.

There is a good variant that will find a path that is a 1+epsilon
approximation in n^(lg epsilon) time.  This has to be better than
A*, unless I am missing some thing.

Do you use A* to find the optimal or just close to optimal ?

"	- Amit
"
"--
"Amit J Patel, Computer Science Department, Stanford University 
"       ``A language based on point and click is like a 
"         human language based on point and grunt.'' -- me

Jason
-- 
Join the FreeBSD Revolution!
mailto:nordwick@xcf.berkeley.edu
http://xcf.berkeley.edu/~nordwick

>"In general, A* "should" have an advantage because it has extra
>"knowledge of the graph, while the usual graph algorithms do not.  For
>"example, if you are trying to travel from London to Paris, A* will
>"tend to spend more time looking to the south, while most graph
>"algorithms look equally in all directions.
>
>However, it also has a larger overhead associated with it, and it
>horrible when the graphs are strongly connected, b/c it is a good
>tree-walking algorithm, but chunks on graphs.

This all depends on how you implement the Open and Closed lists, in 
particular how efficiently they search to see if a candidate new node exists 
already.  

Dijkstra's search -- at least how I have understood and implemented it -- 
*is* an A* search, whose heuristic estimate 'g' is always zero.  It 
therefore cannot be better than A*.  My experience with A* in the games 
domain, for finding paths in a 2D space, is that having a good 'g' estimate 
improves A*'s efficiency tremendously.  See my 'PathDemo' program which can 
be downloaded from Game Developer Magazine's website at 
http://www.gdmag.com, from vol. 3 no. 5 (Oct/Nov 96).

>There is a good variant that will find a path that is a 1+epsilon
>approximation in n^(lg epsilon) time.  This has to be better than
>A*, unless I am missing some thing.
>
>Jason

Could you please elaborate on that variant?

Thanks,
Bryan

bstout@mindspring.comm

In article <11>, bstout@mindspring.com (Bryan
Stout) wrote:

> 
> >There is a good variant that will find a path that is a 1+epsilon
> >approximation in n^(lg epsilon) time.  This has to be better than
> >A*, unless I am missing some thing.
> >
> >Jason
> 
> Could you please elaborate on that variant?

If he is referring to what I know as Bandwidth search, that is as follows.

Normally, for A*, we have, for any node x,

    h(x) <= h*(x)

Suppose we overestimate h(x) by some amount e at the most; that is, for any
node x,

    h(x) - h*(x) <= e

The cost of the solution found by the search will not exceed the cost of
the cheapest solution by more than e (proof left as an exercise for the
reader).

*However*, we now have an inadmissible search strategy, that is one that is
not guaranteed to find the solution. In "real world" cases, it will usually
find the solution. But, best to have a fall-back when it fails.

P.S. It's Dijkstra.

-- 
Brian Fitzgerald
Future Point

In article <11>,
Bryan Stout <bstout@mindspring.com> wrote:

"Dijkstra's search -- at least how I have understood and implemented it -- 
"*is* an A* search, whose heuristic estimate 'g' is always zero.  It 
"therefore cannot be better than A*.  My experience with A* in the games 
"domain, for finding paths in a 2D space, is that having a good 'g' estimate 
"improves A*'s efficiency tremendously.  See my 'PathDemo' program which can 
"be downloaded from Game Developer Magazine's website at 
"http://www.gdmag.com, from vol. 3 no. 5 (Oct/Nov 96).

First, when you say g-estimate, do you mean h-estimate ?  'g' is supposed
to be the cost, while 'h' is an estimate.

Second, I don't think that your characterization of Dykstra is at all
true.  Dykstra searches nodes and then relaxes is a better path is found:
a-star attempts to look at all nodes in the next level of the current tree,
and thinks of them as a new path, thus forgetting about the inherent
structure of a graph.

"Could you please elaborate on that variant?

I will post 1+epsilon approximation of shortest path in a day or so.
Sorry, for the vagueness.

"Thanks,
"Bryan
"
"bstout@mindspring.comm

no, thanks for the comments; I have always wondered about this.

jason
-- 
Join the FreeBSD Revolution!
mailto:nordwick@xcf.berkeley.edu
http://xcf.berkeley.edu/~nordwick

>First, when you say g-estimate, do you mean h-estimate ?  'g' is supposed
>to be the cost, while 'h' is an estimate.

You're right.  Late-night fuzziness, I guess.

>Second, I don't think that your characterization of Dykstra is at all
>true.  Dykstra searches nodes and then relaxes is a better path is found:
>a-star attempts to look at all nodes in the next level of the current tree,
>and thinks of them as a new path, thus forgetting about the inherent
>structure of a graph.

I'm not sure what you mean by either characterization, but I'll try responding. 
A* and Dykstra correspond exactly.  Where Dijkstra assigns a temporary (finite) 
distance label to a node, A* pushes it on the Open list, with a current f=g+h 
value. Where Dijkstra assigns a permanent label (or colors it, depending on the 
algorithm description), A* pushes it on the Closed list, again with its current 
f value.  Where Dijkstra initializes the nodes with a label of infinity, A* 
just leaves unallocated, waiting to be pushed onto Open.  Where Dijkstra ends 
when the goal node is assigned a final label (or is colored), A* ends when a 
goal state's node is popped off Open.  Where Dijkstra chooses the next node to 
consider by picking the one with the smallest label, A* pops off Open the node 
with the smallest f.

The basic difference is that Dijkstra picks the node with the smallest g, and 
A* picks the node with the smallest g+h.  This does lead to another difference: 
since the h estimate can be wrong, it may cause a node N to be popped off Open 
early and pushed on Closed, but then another, shorter, path to N is found, so 
it has to moved back to Open again; once Dijkstra has assigned a permanent 
label, there's no fear of that, since the 'h' is uniformly zero, and will not 
cause nodes to be popped early.  (Again, Dijkstra is an A* search, whose 'h' 
underestimate is zero.)

I was wondering how you came to think that A* forgets the structure of the 
graph. Looking over several books that describe A*, I saw that they tended, in 
their discussions of the A* algorithm, to ignore the possibility of repeated 
states arrived at through different paths.  I looked again, and saw that most 
of them did discuss this somewhere.  Nilsson's _Principles of Artificial 
Intelligence_, if I remember correctly, explicitly discusses moving nodes from 
Open to Closed, and reassigning their pointer to the parent state while doing 
so. It is these pointers to the parent state that keep track of the structure 
of the graph.

>I will post 1+epsilon approximation of shortest path in a day or so.
>Sorry, for the vagueness.

Good.  I'm always willing to learn to new algorithms.

Regards,
Bryan

On 28 Mar 1997 04:48:23 GMT, bstout@mindspring.com (Bryan Stout) wrote:

>It [Dijkstra's algorithm] therefore cannot be better than A*.

This is indeed true, since A* is optimal in the sense that there
is no algorithm (searching from the root) that is guaranteed to
expand fewer nodes than A*. (And obviously, with an admissible
heuristic we are guaranteed a shortest solution, if one exists).

However, most of the time we do not necessarily need a path that
is provably best, only one that is 'good enough'; so, yes, there
might be algorithms that are better than A* for gaming purposes,
but Dijkstra's is not one of them.

>However, most of the time we do not necessarily need a path that
>is provably best, only one that is 'good enough'; so, yes, there
>might be algorithms that are better than A* for gaming purposes,
>but Dijkstra's is not one of them.

I definitely agree that often we do not need the best path, just a reasonable 
one. But we can use the same algorithm, just use an inadmissible heuristic, an 
'h' which is not guaranteed to be an underestimate.  (In Nils Nilsson's 
terminology, I think this made the algorithm 'A', not 'A*'.)  A huge value for 
'h' (compared to 'g') will find a path very quickly, but may end up with a 
direct path through very costly terrain.  It depends on the game in question 
how to balance the need for a good path versus the need to find some path 
quickly.

Bryan

In article <5hf0l3$o1l@scam.xcf.berkeley.edu>,
Jason Alan Nordwick <nordwick@scam.XCF.Berkeley.EDU> wrote:
>In article <5>,
>Amit J Patel <amitp@Ghoti.Stanford.EDU> wrote:
>"In general, A* "should" have an advantage because it has extra
>"knowledge of the graph, while the usual graph algorithms do not.  For
>"example, if you are trying to travel from London to Paris, A* will
>"tend to spend more time looking to the south, while most graph
>"algorithms look equally in all directions.
>
>However, it also has a larger overhead associated with it, and it
>horrible when the graphs are strongly connected, b/c it is a good
>tree-walking algorithm, but chunks on graphs.

It's trivial to add the same heuristic function to Djikstra's algorithm
to get a goal directed search.  I have yet to try an in depth comparison
between the two searching techniques but I'd expect them to explore
almost identical areas of the graph given the same function.

The real advantage in the A* algorithm is the fact that it works on
very large search domains.  For Djikstra's algorithm, you require a
table with size proportional to the graph you are searching.  

Cheers,
Chris.
-- 
Mail: crpalmer@undergrad.uwaterloo.ca
Homepage: http://www.undergrad.math.uwaterloo.ca/~crpalmer/

>The real advantage in the A* algorithm is the fact that it works on
>very large search domains.  For Djikstra's algorithm, you require a
>table with size proportional to the graph you are searching.  
>
>Cheers,
>Chris.

For some algorithms, the data structure used is essential -- for example, a 
heap is necessary for heap sorting.  I don't consider a lookup distance table 
essential to Dijkstra's path algorithm.  What's needed is some means of getting 
the cost between two nodes.  In most game path situations, that can be gotten 
by looking at the game map and calculating the cost between two adjacent areas 
-- no additional structure beyond the map is needed.

Regards,
Bryan

Bryan Stout wrote:
> 
> >The real advantage in the A* algorithm is the fact that it works on
> >very large search domains.  For Djikstra's algorithm, you require a
> >table with size proportional to the graph you are searching.
> >
> >Cheers,
> >Chris.
> 
> For some algorithms, the data structure used is essential -- for example, a
> heap is necessary for heap sorting.  I don't consider a lookup distance table
> essential to Dijkstra's path algorithm.  What's needed is some means of getting
> the cost between two nodes.  In most game path situations, that can be gotten
> by looking at the game map and calculating the cost between two adjacent areas
> -- no additional structure beyond the map is needed.

	Okay, here is an odd idea.  Has anyone considered superimposing a graph
over the game's terrain and optimizing that once (possibly when the map
is saved from the map editor), then for subsequent lookups you could use
a simple algorithm to find the nearest node of the network, and
similarly locate the nearest node of the destination, then use the
simplified network to find the route quickly (making sure that costs of
enemy unit presence is added to the static terrain cost).  This route
will probably have to be smoothed a little to make sure that the units
don't actually go to the first and last nodes, but to the second nodes
(so that the units don't go backwards to the start node, then re-trace
their steps to the second node).

	For generating the initial web you could cast a grid over the area then
work out which nodes are superfluous by checking that there are no
obstacles between the node and the surrounding nodes (i.e. plains do not
need many nodes since you should be able to go in a straight line across
them).

	Issues:
		- Maintaining the web if routes are made unpassable (blowing up a 
			bridge, enemy units building barricades, etc.)
		- Building the web if all terrain is not initially visible

	Or has this idea been tried and proven bad, or is it currently in use?

			-ben

>> 	Okay, here is an odd idea.  Has anyone considered superimposing a
graph
>> over the game's terrain and optimizing that once (possibly when the map
>> is saved from the map editor), then for subsequent lookups you could
use
>> a simple algorithm to find the nearest node of the network, and
>> similarly locate the nearest node of the destination, then use the
>> simplified network to find the route quickly (making sure that costs of
>> enemy unit presence is added to the static terrain cost).  This route
>> will probably have to be smoothed a little to make sure that the units
>> don't actually go to the first and last nodes, but to the second nodes
>> (so that the units don't go backwards to the start node, then re-trace
>> their steps to the second node).

>	Hi! I actually thought of that very same idea about a year ago,
>	but didn't do any coding or further investigation in the subject.
>	:( This was due to the simple fact that I couldn't come up
>	with a solution for maintaining the web:

I came up with an algorithm in my paper "Using Heirarchies of Macro Cells
to
Linearize Search Costs for Real Time Route Planning" (_Proceedings of the
Ninth Florida Artificial Intelligence Research Symposium_, ISBN
0-9620-1738-8) that does this.  The problem was routing on city streets. 
If D^2 is your map size and 'd' is the distance between your start and
goal state, the cost of Dijkstra will be O(D^2), A* will cost you O(d^2)
and an A* using my "heirarchy of macro cells" will cost you just O(d)  
(all three methods are complete and admissable).

My method uses a systematic pre-exploration of the search space to create
a set of "macro cells" (your "grids"). The macro cells contain the cost
and path for every traversal of the cell.  In a sense, an A* search
"forgets" all the information that it aquires in running a search on the
graph; adding the cell structure gives the
A* search a "memory" that it can refer to in future searches.  The search
cost savings can be immense.

If you are running a lot of shortest paths on a (mostly) static complex
graph,
then you'll find that my method works like butter. The paper should be
posted on one of Johns Hopkin's University's web pages, if not, I have a
postscript copy around here somewhere.

Sean Henry
Dir Scheduling/Planning
Viewer's Choice/PPV, Inc.
<shenry@ppv.com>