A* question...
HAAVARD JAKOBSEN
Can anyone PLEASE help me with some silly question:
Is it common to use landscape cost when estimating the
cost to the goal using A*?
If so in an open lanscape (none tilebased) you have to pick
the cost for each pixel on the line to the goal.
This makes the estimating of the cost to the goal take
a serious amount of time...
If not do u just use the 'air distance' to the goal?
Thanks in advance,
Haavard
Dominic Byrne
Way out but,
if you have a base movement value of 1 and cacluate the path sum of
edge length * movement value, you get the value of the edge. Now put all
types of terrain in as regions, when an edge crosses a region boundary
put a node in. all edges are wholly contained in one type of region thus
a true path lenght can be calculated.
mail me for a fuller explaination. but this should be clear.
Dominic.
Randolph M. Jones
HAAVARD JAKOBSEN wrote:
>
> Can anyone PLEASE help me with some silly question:
> Is it common to use landscape cost when estimating the
> cost to the goal using A*?
> If so in an open lanscape (none tilebased) you have to pick
> the cost for each pixel on the line to the goal.
> This makes the estimating of the cost to the goal take
> a serious amount of time...
As with most everything, there are tradeoffs to either approach (damn
those tradeoffs). If you use actual landscape cost, each estimation
will be more expensive. If you use "air distance" (a common approach),
the inidividual evaluations will be cheaper, but the search will
potentially take longer. The wasted time you spend exploring
the "wrong" paths, will be directly proportional to how good an
estimate "air distance" is. How good an estimate it is depends
entirely on the particular application you are doing. If there are
lots of large, high-cost obstacles on the terrain, air distance is
not going to be a good estimator in general. But if there are
generally large expanses of terrain that have the same landscape
costs, air distance might work quite well.
Randy Jones
rjo...@eecs.umich.edu
Darren Reid
Try "chunking" the map up into squares...say 20x20. Determine a terrain
value for each of these...maybe by averaging areas somehow. Then run A*
on this map. When you have a path, chunk each tile you travelled over
into smaller tiles, and run A* on this higher-res map. Use the resulting
path as the basis for your path....some tweaking may need to be done,
but it should work quite fast & give a reasonable looking path.
-Darren
that's .com in disguise Christer Ericson
It's a nice idea, if only it would work too.
One obvious scenario where this would fail is where start and goal end
up in the same chunk, but it is impossible to find a path from A to B
within that chunk (ie. there's a separating wall between them).
In general, the problem is with the chunking; you cannot reliably map
the contents of a chunk into the set {wall, no wall} and guarantee that
you:
a) don't remove paths that were there to begin with, and
b) don't add paths that weren't there to begin with.
Still, you can always attempt to use the method suggested, and if
it does return a correct path then everything's fine, but if not,
then you have to rely on a different method to find your path
(e.g. doing an A* search on the complete area).
Darren Reid
Christer Ericson wrote:
> It's a nice idea, if only it would work too.
>
> One obvious scenario where this would fail is where start and goal end
> up in the same chunk, but it is impossible to find a path from A to B
> within that chunk (ie. there's a separating wall between them).
Yes, I see what you mean. I have been considering using this method for
a problem I have, but it almost worked fine for me: the map doesn't have
many "wall" areas, it's mostly just grass, swamp and trees at varying
elevations. Rivers and bridges will be a bitch, though. <sigh>. Back to
the drawing board.
> In general, the problem is with the chunking; you cannot reliably map
> the contents of a chunk into the set {wall, no wall} and guarantee that
> you:
>
> a) don't remove paths that were there to begin with, and
> b) don't add paths that weren't there to begin with.
>
> Still, you can always attempt to use the method suggested, and if
> it does return a correct path then everything's fine, but if not,
> then you have to rely on a different method to find your path
> (e.g. doing an A* search on the complete area).
So how do you do an A* on the complete area of a vector-based map? Just
chunk it into a zillion small pieces? <grin>
C'mon, someone....speak up. Enlighten us. Or do you really wind up
casting rays/calculating intersections/moving nodes along polygon edges
etc.
-Darren
-Darren
Szu-Wen Huang
Darren Reid (shok...@nbnet.nb.ca) wrote:
: Try "chunking" the map up into squares...say 20x20. Determine a terrain
: value for each of these...maybe by averaging areas somehow.
I'd suggest against a simple averaging. If the grid contains obstacles
like rivers or cliffs, averaging might mark that grid as "passable"
when in fact it isn't. I think, *without* any real experiment to back
up, that it might be better to take the worst terrain in that grid
instead.
Of course, this approach can lead to a map that look completely
unpassable to the algorithm, unless maybe the grids are sized properly.
: Then run A*
: on this map. When you have a path, chunk each tile you travelled over
: into smaller tiles, and run A* on this higher-res map. Use the resulting
: path as the basis for your path....some tweaking may need to be done,
: but it should work quite fast & give a reasonable looking path.
Another word of caution. As a casual wargamer I'm annoyed by units that
act *too* mathematical because it ruins my suspension of disbelief.
For example, if the unit moves backwards first to loop around a forest,
it actually gets to the objective first (because the SPA did work), but
it looked too computerish. Somehow I expect that when I say go from A
to B, the unit swerves left and right *somewhat* to avoid obstacles
smartly, but not "radical" things like go backwards.
Comments welcome.
Bryan Stout
In article <33268E08...@hig.no>, haa_...@hig.no says...
>
>Can anyone PLEASE help me with some silly question:
>Is it common to use landscape cost when estimating the
>cost to the goal using A*?
>If so in an open lanscape (none tilebased) you have to pick
>the cost for each pixel on the line to the goal.
>This makes the estimating of the cost to the goal take
>a serious amount of time...
>If not do u just use the 'air distance' to the goal?
>
>Haavard
The answer is yes, typically one takes into account the landscape cost. Using
A* for physical paths usually ends up with the estimate being something like:
(cost estimate) = (estimated distance) * (cost per distance)
so you don't need to look at each pixel, just use the 'air distance' to the
goal, but multiply it by a typical cost per unit distance.
The cost multiplier you pick can have a big effect. You can use the minimum
terrain cost in your game to guarantee the estimate is always a minimum, thus
guaranteeing the shortest path. But if most terrain is a lot more costly than
the minimum, then the search will be inefficient. But if the cost is too high,
the search will be very fast but the path it finds may be lousy.
This is discussed more in my article on path-finding in Game Developer
Magazine, Oct/Nov 96. If you can't get that back issue, wait a few months for
an expanded treatment in my book _Adding Intelligence to Computer Games_, to be
published by Addison-Wesley.
Regards,
Bryan
Bryan Stout
In article <332CA4...@nbnet.nb.ca>, shok...@nbnet.nb.ca says...
The 'chunking' idea is a very good one, if you can guarantee that the area in a
'chunk' is part of one contiguous space. This is easy if all the game maps are
designed ahead of time and come with the game; if they are generated
semi-randomly at game run time then you'd need a good algorithm for finding
contiguous areas, or remove those pesky walls from the game (a time-honored and
not shameful game design approach, if the time constraints are tight).
As far as path finding in a vector-based map, I quickly mention several
techniques for quantizing a continuous space at the end of my article on
path-finding in the Oct/Nov'96 Game Developer Magazine. (The same material
will appear in my book _Adding Intelligence to Compuer Games_ to appear in
several months from Addison-Wesley.) In brief, ways to break a smooth space
into a small amount of decision points include:
- slapping a grid atop the space
- assigning decision nodes near the corners of obstacles
- dividing the space into convex polygons, & go from center to center (or
from one edge middle to another)
- dividing the space into quadtrees
- dividing it into generalized cylinders, & look at points of intersection
of cylinder axes
Regards,
Bryan
Bryan Stout
>Another word of caution. As a casual wargamer I'm annoyed by units that
>act *too* mathematical because it ruins my suspension of disbelief.
>For example, if the unit moves backwards first to loop around a forest,
>it actually gets to the objective first (because the SPA did work), but
>it looked too computerish. Somehow I expect that when I say go from A
>to B, the unit swerves left and right *somewhat* to avoid obstacles
>smartly, but not "radical" things like go backwards.
>
>Comments welcome.
An easy way around this is to add cost factors that make reverse more expensive
than forward driving. The cost need not only include fuel expenditure or
movement speed, but also factors like the awkwardness of driving backwards, or
even programmer-enforced aesthetic factors which reduce unnatural behaviors.
The cost could even go up over time, so the longer one stays in reverse, the
more expensive it is.
Bryan
Daniel J Mitchell
On Sun, 16 Mar 1997 21:53:30 -0400, Darren Reid <shok...@nbnet.nb.ca> wrote:
>So how do you do an A* on the complete area of a vector-based map? Just
>chunk it into a zillion small pieces? <grin>
>
>C'mon, someone....speak up. Enlighten us. Or do you really wind up
>casting rays/calculating intersections/moving nodes along polygon edges
>etc.
Yup; look in most books on robot path planning. As far as I know, A* was
invented to work on graphs derived from the visibility graph of configuration
space around obstacles.
Typically, you take each point on each obstacle, and create a graph joining
each such point to all the other points that it can see; this gives you
a graph, which you then run A* on -- doing things this way guarantees you a
shortest path.
(except that it's a path that drives past corners more than tends to be
practical, even given configuration-space to sort that sort of problem out.
What I've ended up doing is hand-placing the nodes of the graph and working
out connectivity between them.)
All of which is completely non-grid-based. Personally, doing this sort of
thing on a grid sounds like an awful lot more work than doing it in an
environment made of polygonal obstacles..
(until you start to rotate your vehicle, at which point all heck breaks
loose.)
-- dan
Bjorn Reese
Bryan Stout wrote:
> several months from Addison-Wesley.) In brief, ways to break a smooth space
> into a small amount of decision points include:
> - dividing the space into convex polygons, & go from center to center (or
> from one edge middle to another)
Since the purpose of the convex segmentation is to be able to "see"
neighbouring decision points, you would have to use the edges rather
than the centers.
This is actually one of the subjects of my thesis.
Darren Reid
Daniel J Mitchell wrote:
> Typically, you take each point on each obstacle, and create a graph joining
> each such point to all the other points that it can see; this gives you
> a graph, which you then run A* on -- doing things this way guarantees you a
> shortest path.
>
> (except that it's a path that drives past corners more than tends to be
> practical, even given configuration-space to sort that sort of problem out.
> What I've ended up doing is hand-placing the nodes of the graph and working
> out connectivity between them.)
Duh! (slapping his forehead). Too easy...thanks. Maybe adding some extra
"spacer" nodes would round out the paths a little.
-Darren
Darren Reid
Hehehe...believe it or not, C&C had a similar behaviour programmed into
the units, although it probably wasn't "costed" in the infamous
brain-dead Bresenham SPA. Cars would do 3-point turns, various vehicles
had various turning radii. IIRC, management didn't care for it, so they
turned it off...but left the code in the game. If you put:
Rotation=Dancing
in the the CONQUER.INI file it will exhibit this behaviour. There are
some small bugs, but they could have been fixed if the idea had gotten a
green light.
-Darren
Jason Alan Nordwick
In article <333585...@nbnet.nb.ca>,
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.
Jason
--
Join the FreeBSD Revolution!
mailto:nord...@xcf.berkeley.edu
http://xcf.berkeley.edu/members.html
Amit J Patel
In article <5h5j8n$6...@scam.XCF.Berkeley.EDU> nord...@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
--
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 Alan Nordwick
In article <AMITP.97M...@Ghoti.Stanford.EDU>,
Amit J Patel <am...@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:nord...@xcf.berkeley.edu
Bryan Stout
>"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
bst...@mindspring.comm
Bryan Stout
In article <1997Mar20....@imada.ou.dk>, bre...@imada.ou.dk says...
Is your thesis available online, or through some other reasonably accessible
manner?
Bryan
bst...@mindspring.comm
Jason Alan Nordwick
In article <bfitz-ya02308000...@news.deltanet.com>,
Brian Fitzgerald <bf...@acm.org> wrote:
"If he is referring to what I know as Bandwidth search, that is as follows.
No, I will post pseudo code within the next day. I think that CLR might
actaully have a page on this, but I may be mistaken... its been a while.
Brian Fitzgerald
In article <5hfiin$s...@camel0.mindspring.com>, bst...@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
Jason Alan Nordwick
In article <5hfiin$s...@camel0.mindspring.com>,
Bryan Stout <bst...@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
"
"bst...@mindspring.comm
no, thanks for the comments; I have always wondered about this.
jason
Jason Alan Nordwick
In article <5hfhm0$s...@camel0.mindspring.com>,
Bryan Stout <bst...@mindspring.com> wrote:
How is this different than Vornoi ? Sounds like the same thing.
Jason
Bjorn Reese
Jason Alan Nordwick wrote:
> How is this different than Vornoi ? Sounds like the same thing.
There is a strong correlation between Voronoi diagrams and Delaunay
triangulations (which I use for the convex space partitioning.)
Using the vertices (meeting-points) of a Voronoi diagram is just as
good a solution. The reason why I chose to use Delaunay triangulation
instead was that it was easier to keep track of which subspace an object
was located in.
PS: I've had several requests for my thesis. It is not done yet so
please be patient :)
that's .com in disguise Christer Ericson
On 28 Mar 1997 04:48:23 GMT, bst...@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.
Chris Palmer
In article <5hf0l3$o...@scam.xcf.berkeley.edu>,
Jason Alan Nordwick <nord...@scam.XCF.Berkeley.EDU> wrote:
>In article <AMITP.97M...@Ghoti.Stanford.EDU>,
>Amit J Patel <am...@Ghoti.Stanford.EDU> wrote:
>"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: crpa...@undergrad.uwaterloo.ca
Homepage: http://www.undergrad.math.uwaterloo.ca/~crpalmer/
Bryan Stout
>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
Bryan Stout
>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
Bryan Stout
>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
Timothy R. T
On 29 Mar 1997 14:11:39 GMT, bst...@mindspring.com (Bryan Stout)
wrote:
>>However, most of the time we do not necessarily need a path that
I was wondering... anyone know where I could get a hold of the A*
algorithm? I made a path engine in pascal (converting it to C++), it
finds the shortest path in a directional network where all the
distances between the nodes have a weighting of 1. I was wondering if
there were any other algorithms that solve the problem.
I know Dijkstra's (learnt it in math this year) and i'm interested in
this A*.
Thanks
-Timothy
Ben Bennett
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
Marcus Alanen
On Mon, 31 Mar 1997, Ben Bennett wrote:
> 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:
> Issues:
> - Maintaining the web if routes are made unpassable (blowing up a
> bridge, enemy units building barricades, etc.)
A little thought... This could be a system of nodes connected like
this...
1 -------- 6
|\ |
| \ /
| --4---5
| /
2---3
So each node would know where to go (node 1 knows how to get
to nodes 2, 4 and 6). When e.g. a bridge (the link between nodes
1 and 4) is destroyed, all moves from nodes 1 to 4 are going
trough 1-2-3-4 or 1-6-5-4, whatever is closer. The paths
between the nodes wouldn't need to be _too_ straight since the
leaping trough the nodes could be done with A*.
This still has its problems. What if a building is destroyed, so
units can move on that terrain? What if the initial map is
unexplored, and one needs to build the web?
Marcus Alanen
maal...@abo.fi
GMMedia
>> 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.
<she...@ppv.com>
Eric Dybsand
Sean,
Your paper sounds very interesting! Please post the URL where it
can be obtained, if you can.
Thanks!
Eric
--
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
http://pw2.netcom.com/~edybs
email: ed...@ix.netcom.com
Steve Hodsdon
In article <19970402213...@ladder01.news.aol.com>,
gmm...@aol.com says...
> 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
[snip]
> 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.
I can't find it using HotBot, Altavista or Infoseek. Could you post a
URL or the paper itself?
Steve