Avoiding Obstacles to reach a destination
Avi Pilosof
One of the problems within it is to navigate a robot such that it
picks up objects and arranges them in a given pattern, avoiding
obstacles in its way. The destination point is known in advance.
This problem is not a gaming problem for me, but it certainly
seems to belong in this group, since I can easily see it applying
in a game situation.
I have alot of time before this is due, and I want to get it working
using a good method.
Meanwhile, we have had two methods hinted at (to avoid obstacles):
a) Brute force: If you hit a wall, turn a little, and keep
going. This will eventually work, but is less than
inspiring.
b) Find a good path, THEN follow it.
I don't want to use (a) unless I really have to, since it's very
el-cheapo.
I would much rather find a good way to do (b), but I'm not sure how
to go about it.
I have briefly considered 2 methods:
i) Ray casting - backwards. I'm not sure exactly how I
would do this, but I was thinking to start from the
destination, and try casting towards the robot. Upon
failure, try to offset the angle of casting a little,
until you've gone full circle (increment both +ive
and -ive with each cycle). This gives me the first
ray, but I then have to cast more rays (recursively)
until the robot is hit. But once the initial ray finds
a "way out" around the obstacles, where does the next
ray begin, etc?
ii)Graph algorithms. I was thinking to define a graph
of randomly (??) distributed vertices around the
destination, and where there is no obstacle from one
vertex to another, an edge exists. This would lend
itself to a shortest-route algo. I'm VERY vague about
this method, since it doesn't seem very concrete.
Anyway, my request is for hints and pointers and algorithm
names.
I'm **NOT** asking for a solution, I would just like some direction,
and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...
I would really appreciate any response (especially via e-mail).
TIA.
###################################################################
Avi Pilosof - av...@cse.unsw.edu.au
- http://www.cse.unsw.edu.au/~avip/
> You cannot propel yourself forward by patting yourself on the back.
Edward Montgomery
>One of the problems within it is to navigate a robot such that it
>picks up objects and arranges them in a given pattern, avoiding
>obstacles in its way. The destination point is known in advance.
>
>Meanwhile, we have had two methods hinted at (to avoid obstacles):
>
> a) Brute force:
> b) Find a good path, THEN follow it.
b)
>
>I don't want to use (a) unless I really have to, since it's very
>el-cheapo.
agreed.
>
>I would much rather find a good way to do (b), but I'm not sure how
>to go about it.
>
>I have briefly considered 2 methods:
>
> ii)Graph algorithms. I was thinking to define a graph
> of randomly (??) distributed vertices around the
> destination, and where there is no obstacle from one
> vertex to another, an edge exists. This would lend
> itself to a shortest-route algo. I'm VERY vague about
> this method, since it doesn't seem very concrete.
Then try a grid of squares (coordinate space, 2D I presume?). Easy to code,
handles infinite better.
>
>Anyway, my request is for hints and pointers and algorithm
>names.
Build a grid or a graph, depending on the coordinate space appropriate to your
objects, obstacles and robot. Add obstacles to the graph/grid as they are
encountered. Use a breadth-first search from the robot until the destination
is encountered. Rerun it after each obstacle is added.
If you want to optimize, save the graph/grid info between obstacle encounters,
instead of regenerating it. But on small grids, the search is very fast.
Bjorn Reese
> One of the problems within it is to navigate a robot such that it
> picks up objects and arranges them in a given pattern, avoiding
> obstacles in its way. The destination point is known in advance.
You could use Potential Field as suggested by Jean-Claude Latombe
("Robot Motion Planning", ISBN 0-7923-9129-2)
Make your goal an attractive force, and obstacles to be avoided
repulsive forces. Imagine a marble rolling down towards the goal.
All obstacles are hills which the marble will roll around. This
approach has been applied to commercial robot controllers. The
disadvantage of this method is that it easily gets trapped in
local minima.
> This problem is not a gaming problem for me, but it certainly
> seems to belong in this group, since I can easily see it applying
> in a game situation.
Indeed. I'm experimenting with the above mentioned method, and
it seems to do very well for arcade type of games - very smooth
motions.
--
Bjorn Reese Email: bre...@imada.ou.dk
Odense University, Denmark URL: http://www.imada.ou.dk/~breese
"It's getting late in the game to show any pride or shame" - Marillion
Tim Hardy
path algorithm (a tried and true algorithm for doing exactly what you
want). We desperately need to put this in a faq. Read the thread I
started "Best Path Algorithm" if you want to know about A* and see
some C++ source code.
Somebody please help out with the faq!!!! I can't. I'm writing a
game and building up a nice collection of C++ code to put in the faq.
Tim
John Christian Lonningdal
>I'm studying AI, and we just got our final assignment.
>One of the problems within it is to navigate a robot such that it
>picks up objects and arranges them in a given pattern, avoiding
>obstacles in its way. The destination point is known in advance.
>This problem is not a gaming problem for me, but it certainly
>seems to belong in this group, since I can easily see it applying
>in a game situation.
Try some shortest path algorithms. Take a look at my web page for some
solutions, including a description of the A* algorithm.
http://www.lis.pitt.edu/~john/shorpath.htm
Regards,
John
------------------------------------------------------------------------------
John Christian Lonningdal - Web: http://www.lis.pitt.edu/~john
jo...@lis.pitt.edu - (412) 521-9386 - 6611 Wilkins Ave, Pittsburgh, PA 15217
------------------------------------------------------------------------------
Get JOBE 1.5 a sprite editor @ http://www.lis.pitt.edu/~john/jobe/jobe.htm
Try out FUSECUTTER! @ http://www.lis.pitt.edu/~john/fusecut/fusecut.htm
Avi Pilosof
: You could use Potential Field as suggested by Jean-Claude Latombe
: ("Robot Motion Planning", ISBN 0-7923-9129-2)
: Make your goal an attractive force, and obstacles to be avoided
: repulsive forces. Imagine a marble rolling down towards the goal.
: All obstacles are hills which the marble will roll around. This
: approach has been applied to commercial robot controllers. The
: disadvantage of this method is that it easily gets trapped in
: local minima.
This sounds like what one uses in flocking algorithms: At each "frame",
the destination contributes a vector, and the obstacle(s) contributes a
vector.
However, as you say, I'm not guaranteed to reach my destination. If
there's an obstacle lying between me and my target, such that it is
perpendicular to the line created between me and my target, I will
eventually come to a stop as the forces balance...
Is this correct?
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Ti> Somebody please help out with the faq!!!! I can't. I'm writing a
I'll read the FAQ on FAQs and take it over seeing as I'm the only one ('side
from you) who cares. Now to tell Steve Furlong that he no longer has to care.
:-)
--
Sunir Shah (ss...@intranet.ca) http://intranet.ca/~sshah/
BBS: The Open Fire BBS +1(613)584-1606 Fidonet: 1:241/11
The Programmers' Booklist : http://intranet.ca/~sshah/booklist.html
Synapsis Entertainment : http://intranet.ca/~sshah/synapsis.html
WASTE (Wargame AI Contest): http://intranet.ca/~sshah/waste/waste.html
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
Steven Woodcock
: Make your goal an attractive force, and obstacles to be avoided
: repulsive forces. Imagine a marble rolling down towards the goal.
: All obstacles are hills which the marble will roll around. This
: approach has been applied to commercial robot controllers. The
: disadvantage of this method is that it easily gets trapped in
: local minima.
Aces of the Deep used this very same method for handling their
destroyer/convoy/submarine AI. It works like a charm.
Steve
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: wood...@escmail.orl.mmc.com (Work), swoo...@cris.com (Home) |
| Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) |
| http://www.cris.com/~swoodcoc/ai.html (Game AI page) |
| Disclaimer: My opinions in NO way reflect the opinions of |
| the Lockheed Martin Information Systems Group |
+=============================================================================+
Dean Mills
:>: local minima.
I found, in my implementation using the above technique, it was very easy to
trap an AI player, such as...
T
XXXXX
X X
X X
X
A
Using a slightly modified A* search, the AI player would end up in the U,
trapped for all intents and purposes. Anyone have any ideas on this, as I
really don't want to redo this approach, as the rest of it works well! :)
D.Mills
______________________________________________________________
Dean Mills - Savage SoftWare Company
Team OS/2 Member
E-Mail - dmi...@mi.net - data...@ftcnet.com
Savage SoftWare, a division of Savage Online Services Inc.
______________________________________________________________
Jasper Phillips
Just modify your maps so that all blocking terrain is convex. ;-)
Seriously though, I'm guessing that this situation while comman and
stiffling, isn't the usual one, and that this kind of "springy" AI
normally works fairly well.
If this is the case, couldn't you just put in a special case if the AI
get stuck? So if your AI can't go where it wants, you can switch to some
other AI for a while. The problem naturally is when to switch back to
the springy AI, but I'd guess you could start with something simple like
returning as soon as you had direct line of sight.
Another option might be to combine this with some sort of pre computed
"best path routes" between general areas, and let that kick in if you really
got stuck.
Just some ideas,
-Jasper
--
/\ Jasper Phillips (Pit Fiend) ______,....----,
/VVVVVVVVVVVVVV|==================="""""""""""" ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""
\/ http://www.cs.orst.edu/~philljas/
Stephane Bessette
>:>: The disadvantage of this method is that it easily gets trapped in
>:>: local minima.
>
>I found, in my implementation using the above technique, it was very easy to
>trap an AI player, such as...
>
> T
>
> XXXXX
> X X
> X X
> X
>
> A
>
>Using a slightly modified A* search, the AI player would end up in the U,
>trapped for all intents and purposes. Anyone have any ideas on this, as I
>really don't want to redo this approach, as the rest of it works well! :)
If you have a way of determining when the AI player is trapped (can't
find novel movements, consumes too much time, ...), then you could switch
the AI governing the computer player. For example, in the situation
presented above, the AI/strategy of always turning left or always turning
right would easily solve the problem.
Now that I think about it, it seems as though I am suggesting that you
implement a superAI, in the sense that this AI would select the most
appropriate AI to use when faced with a certain environment. In the
current scenario, the superAI would utilise your AI until the computer
player is trapped. When this situation arises, the superAI would now
utilise the TurnLeft/TurnRight AI until either the destination is reached
or the computer player is once again moving in the direction of the goal.
--
Stephane [TEAM OS/2]
Steve Hodsdon
Mills), the following was written:
> Using a slightly modified A* search, the AI player would end up in the
> U, trapped for all intents and purposes. Anyone have any ideas on
> this, as
Simple. Remove the 'U' from the map.
Instead of exerting more effort in making the movement algorithm smarter
you just make the map simpler.
Steve
Tim Thomas
In <4k9k6v$a...@scratchy.mi.net> dmi...@mi.net (Dean Mills) writes:
>:>: The disadvantage of this method is that it easily gets trapped in
>:>: local minima.
>I found, in my implementation using the above technique, it was very easy to
>trap an AI player, such as...
> T
> XXXXX
> X X
> X X
> X
> A
>Using a slightly modified A* search, the AI player would end up in the U,
>trapped for all intents and purposes. Anyone have any ideas on this, as I
>really don't want to redo this approach, as the rest of it works well! :)
How about using a hierarchical method for determining the path?
Organize the terrain into something similar to a quad tree. Take your pick
how you construct it. The weighting of each "quad" is the average of
all those within. (Storing min and max might be useful as well...)
Now this is how the algorithm would work. At the highest level of granularity
pick the path to your destination which requires the least amount of "effort".
Now enter the first "quad" that is on the path. Bump down to the next level
of granularity, recursively applying the same algorithm. The trick here is,
if you encounter a position where you can't go anywhere, bump back up to the
previous level of granularity and select a path which requires a little more
effort.
Such an algorithm, or one similar to it, would at the very least allow you to
"back out" of corners like the one you described above. Add a little bit of
lookahead before moving and you're set.
Tim Thomas
tho...@urbana.mcd.mot.com
Bjorn Reese
>
> :>: The disadvantage of this method is that it easily gets trapped in
> :>: local minima.
>
> I found, in my implementation using the above technique, it was very easy to
> trap an AI player, such as...
You basicly have two options. Either avoid the local minima, or escape
it trapped.
The former is the preferred option, but it can be somewhat tricky.
One possibility is to use "beacons" -- well-placed attractive
points. Let the object travel from one beacon to the next until its
destination is within sight.
If you choose the latter option, you could try something like this:
1) Detect a dead-end (if the object doesn't reach its destination
within a specified time, or if it stays too long in a small
area)
2) Pick a random location which is reachable from the current
location, and go there first.
3) When you reach the random location, go to the desired location.
There are plenty of other methods for both options though.
Robert A. Uhl
>
>Simple. Remove the 'U' from the map.
>
>Instead of exerting more effort in making the movement algorithm smarter
>you just make the map simpler.
You cannot do this if writing an AI for a game like Bolo. Players
just olug in AI brains and use their own maps. You have no control
(nor should you, really).
That said, at one time I gave a lot of thought to various movement
algorithms. I came up with one whose one requirement is that LOS must
be cheap to calculate. I'll post it if anyone's interested.
--
Robert Uhl | Save the Ales! Homebrewer Since 1995
Orthodox Christian | If you like the Macintosh, send mail to
Macintosh Programmer | evang...@macway.com for information about the
Bolo Player (Spectre) | EvangeList, Guy Kawasaki's list for Mac advocates.
Darren Reid
>
> In article <4k9k6v$a...@scratchy.mi.net>, Dean Mills <dmi...@mi.net> wrote:
> >trapped for all intents and purposes. Anyone have any ideas on this, as I
> >really don't want to redo this approach, as the rest of it works well! :)
> Just modify your maps so that all blocking terrain is convex. ;-)
Chris Crawford once spent a long time on just this exact problem...and finally realized
that the best solution was removing concave areas from the map. A* should fix this
problem, so that slight modification must be breaking it.
> Seriously though, I'm guessing that this situation while comman and
> stiffling, isn't the usual one, and that this kind of "springy" AI
> normally works fairly well.
>
> If this is the case, couldn't you just put in a special case if the AI
> get stuck? So if your AI can't go where it wants, you can switch to some
> other AI for a while. The problem naturally is when to switch back to
> the springy AI, but I'd guess you could start with something simple like
> returning as soon as you had direct line of sight.
Yup. If your attractor/repulsor AI is breaking A*, just detect for stuck or "dancing"
units and drop back to a real A* or Djykstra's (sp?) for a few turns.
>
> Another option might be to combine this with some sort of pre computed
> "best path routes" between general areas, and let that kick in if you really
> got stuck.
This adds an extra benefit to the AI...pre-planned tactics ala pincer moves etc.
I would use attractor/repulsor to determine targets, then use Djykstra's to compute a
true shortest path that avoids heavy repulsor (defended) areas and follow that path. If
the target is moving, you can re-evaluate or choose to follow the attack path for a few
turns anyway...
Jasper Phillips
Steve Hodsdon <10336...@compuserve.com> wrote:
>In article <4k9k6v$a...@scratchy.mi.net>, From dmi...@mi.net (Dean
>Mills), the following was written:
>
>> U, trapped for all intents and purposes. Anyone have any ideas on
>> this, as
>
>
>Instead of exerting more effort in making the movement algorithm smarter
>you just make the map simpler.
>
>
Better yet, just remove all terrain...
This should do wonders in simplifying your AI. ;-)
Steven Woodcock
: You cannot do this if writing an AI for a game like Bolo. Players
: just olug in AI brains and use their own maps. You have no control
: (nor should you, really).
Well said Robert!
: That said, at one time I gave a lot of thought to various movement
: algorithms. I came up with one whose one requirement is that LOS must
: be cheap to calculate. I'll post it if anyone's interested.
Hey, I'd like to see it. I'm always looking for fast code that I
won't have to write myself...... ;)
Steven Woodcock
"The One and Only"
Jasper Phillips
Bjorn Reese <bre...@imada.ou.dk> wrote:
>Dean Mills wrote:
>>
>> :>: The disadvantage of this method is that it easily gets trapped in
>> :>: local minima.
>>
>> I found, in my implementation using the above technique, it was very easy to
>> trap an AI player, such as...
>
>You basicly have two options. Either avoid the local minima, or escape
>it trapped.
>
>The former is the preferred option, but it can be somewhat tricky.
>One possibility is to use "beacons" -- well-placed attractive
>points. Let the object travel from one beacon to the next until its
>destination is within sight.
The main problem with this is that you have to setup beacons for all maps
by hand... Although most games have premade terrain anyway. You could also
just make concave areas more powerfull repulsors than other blocking terrain.
Ideally the same terrain could be attractive or repulsive in different
strengths for different types of units (e.g. ground as opposed to naval).
I'm wondering how effective writing code to try to figure out how to place
attractors and repulsors would be... Any ideas?
[second option snipped]
>
>--
>Bjorn Reese Email: bre...@imada.ou.dk
-Jasper
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Ph> Just modify your maps so that all blocking terrain is convex. ;-)
Seriously, that is a viable solution.
Ph> If this is the case, couldn't you just put in a special case if the AI
Ph> get stuck? So if your AI can't go where it wants, you can switch to
Question: How does it tell when it is stuck?
Ph> Another option might be to combine this with some sort of pre computed
Ph> "best path routes" between general areas, and let that kick in if you
Ph> really got stuck.
It'd get stuck because of those too if the map is modifiable.
--
Sunir Shah (ss...@intranet.ca) http://intranet.ca/~sshah/
BBS: The Open Fire BBS +1(613)584-1606 Fidonet: 1:241/11
The Programmers' Booklist : http://intranet.ca/~sshah/booklist.html
Synapsis Entertainment : http://intranet.ca/~sshah/synapsis.html
WASTE (Wargame AI Contest): http://intranet.ca/~sshah/waste/waste.html
*NEWSFLASH*
-GAMEDEV, The Game Development Echo, is now on the Zone 1 Backbone (Fido)
-Stay tuned for the release of the *new* comp.ai.games FAQ . . .
Szu-Wen Huang
: To: PhilljasUnknownx.engr.orst.edu
: Subject: Re: Avoiding Obstacles to
: Ph> Just modify your maps so that all blocking terrain is convex. ;-)
: Seriously, that is a viable solution.
: Ph> If this is the case, couldn't you just put in a special case if the AI
: Ph> get stuck? So if your AI can't go where it wants, you can switch to
: Question: How does it tell when it is stuck?
Alternatively, why not just define your terrain as not having obstacles
your units can *never* cross? Replace those with "expensive" terrain
that take long to cross, but not impossible, and your convex/concave
problem goes away as well.
: Ph> Another option might be to combine this with some sort of pre computed
: Ph> "best path routes" between general areas, and let that kick in if you
: Ph> really got stuck.
: It'd get stuck because of those too if the map is modifiable.
How's WASTED coming along, Sunir? :) Oh, I'm sorry, was it WASTE instead?
:)
Simon Slavin
dmi...@mi.net (Dean Mills) wrote:
> :>: The disadvantage of this method is that it easily gets trapped in
> :>: local minima.
>
> I found, in my implementation using the above technique, it was very easy to
> trap an AI player, such as...
>
> T
>
> XXXXX
> X X
> X X
> X
>
> A
When the piece gets trapped, take a note of the cells occupied by the
obstacle. Follow the left-hand wall until no part of the obstacle lies
between the piece and the target, then continue. [Simple algorithm.]
If you've got the processing power and storage space free then precompute
the path before you start out on any journey. [Extra marks.]
Point to ponder: what governs whether you should follow the left-hand or
right-hand wall ? [You can take a *good* guess from the 'Simple' alg.]
Simon.
--
sla...@hearsay.demon.co.uk -- the poster | "Sometimes a .sig is just
formerly known as sla...@entergrp.demon.co.uk. | a .sig." -- Sigmund Freud.
Richard Wesson
Avi Pilosof <av...@cse.unsw.edu.au> wrote:
>I'm studying AI, and we just got our final assignment.
>
>One of the problems within it is to navigate a robot such that it
>picks up objects and arranges them in a given pattern, avoiding
>obstacles in its way. The destination point is known in advance.
>
>
>I have alot of time before this is due, and I want to get it working
>using a good method.
>
>
> going. This will eventually work, but is less than
> inspiring.
>
>el-cheapo.
>
>to go about it.
>
>I'm **NOT** asking for a solution, I would just like some direction,
>and perhaps a reference. Are my ideas worthwhile? Are they junk? etc...
>
>I would really appreciate any response (especially via e-mail).
>
>TIA.
>
OK, here are two ideas.
As someone already mentioned, a quad-tree.
Take a big square. If it is completely free, mark it as clear. If it
is completely blocked, mark it as blocked. If it is partially clear,
give this square 4 children (in effect dividing it into 2x2) and repeat
this procedure for all of the children.
At the end of this, you'll have a number of squares in this tree-structure,
all the leaves will be either impassable or clear.
Search recursively for a path from free square to free square.
Once you have such a path, proceed from the center of each free square
to the next.
This should be pretty fast. It will work especially well for a large
board that is mostly free space. Since you are stepping from the center
of one square to another, you will have a slightly jagged looking path.
Once you have the quad-tree in place it will work for going from anywhere
to anywhere.
Here's another idea, rather like a breadth-first search but using the board
itself to store things. It's a modified flood-fill.
-- WARNING -- THE FOLLOWING MAY BE CONSIDERED A 'SOLUTION'
I call it "Ant Races".
Have a list of ants, starting out at the start. Each ant knows how many
moves it took to get where it is. Each turn, each ant moves into a free
space and 'colors' that space with the current number of ticks elapsed. If
there is more than 1 free space the ant can get to, it spawns a child
(to be added to the list of ants) for each extra free space. Ants that
cannot get to a free space will die and be removed from the list of ants.
Start with one ant at your destination.
Once you arrive at the start, you can trace your path back by
always going down the gradient.
This should be much faster than the typical breadth-first search, because
you don't have to check an open or a closed list -- just look at the
board. The algorithm is O(size of board) -- every square on the board
is looked at some constant factor of times, maybe 2.5 times or so.
It's simple to implement and will give you a very close to optimal
path. The drawback is that you have to repeat all that work for every
different start/destination, so it isn't the best if you have to do a bunch
of paths from/to different places. For that, I would suggest the quad-tree.
-- Richard Wesson
(wes...@cse.ogi.edu)
Bjorn Reese
> The main problem with this is that you have to setup beacons for all maps
> by hand... Although most games have premade terrain anyway. You could also
> just make concave areas more powerfull repulsors than other blocking terrain.
This could be a problem if your target is within the concavity at some
stage.
> I'm wondering how effective writing code to try to figure out how to place
> attractors and repulsors would be... Any ideas?
I think selecting the "beacons" from the meeting points (vertices) of
a Voronoi diagram could be pretty effective.
NB: I've quoted the word "beacons" because it usually has a slightly
different meaning in robotics.
--
Bjorn Reese Email: bre...@imada.ou.dk
Bjorn Reese
> Question: How does it tell when it is stuck?
The easy way out would be to use time. The object could be considered
stuck either if it hasn't reached its destination within a reasonable
time, or if it stays in the same area for too long.
Dean Mills
:>
:> Ph> Just modify your maps so that all blocking terrain is convex. ;-)
:>
:>Seriously, that is a viable solution.
Actually, in this case Sunir, it is not.
:> Ph> If this is the case, couldn't you just put in a special case if the AI
:> Ph> get stuck? So if your AI can't go where it wants, you can switch to
:>
:>Question: How does it tell when it is stuck?
That was the point of my original post! :)
:>It'd get stuck because of those too if the map is modifiable.
It is, and thus, I don't have any real control over the obstacles.
D.Mills
Dean Mills
:>your units can *never* cross? Replace those with "expensive" terrain
:>that take long to cross, but not impossible, and your convex/concave
:>problem goes away as well.
Well, since the whole idea of the game is to be as realistic as possible, this
is not a viable solution. Ships going overland, tanks traversing mountain
ranges, etc, wouldn't look to hot in the game at all! :)
D.Mills
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Ph> Better yet, just remove all terrain...
Ph> This should do wonders in simplifying your AI. ;-)
And then give the computer a *really* big gun and the player a stick.
Guaranteed win every time. :-)
Darren Reid
> When the piece gets trapped, take a note of the cells occupied by the
> obstacle. Follow the left-hand wall until no part of the obstacle lies
> between the piece and the target, then continue. [Simple algorithm.]
Only works if the non-traversable terrain is only slightly concave. If the concavity
bends beyond a tangent to the line drawn to the target, you will start back towards the
target while still trapped within the cavity. Been there, done that ;)
Seriously, am I missing something here? DO you really want a path algorithm as stupid as
the C&C one? What's wrong with a true A* or Dijkstra's? Check out:
http://www.lis.pitt.edu/~john/shorpath.htm
for lots of good stuff.
There is a nice white-paper on shortest path algorithms in the 1996 CGDA proceedings, on
page 439.
An interesting point that I just realized: A* is faster than Dijkstra, but not always as
good...it uses heuristics, and tries to go towards the target and around obstacles. This
can lead to it finding a more direct but possibly more expensive (in movement points)
path than Dijkstra...and this side-effect might be actually useful to someone who is
trying to simulate "realistic" unit movement over "perfect" unit movement.
-Darren Reid
Steven Woodcock
: Seriously, am I missing something here? DO you really want a path algorithm
: out: http://www.lis.pitt.edu/~john/shorpath.htm for lots of good stuff.
I'd just like to second Darren about this page; it's a good one.
: There is a nice white-paper on shortest path algorithms in the 1996 CGDA
: proceedings, on page 439.
That's Bryan Stout's presentation; he lurks around here too sometimes.
Bryan did a great job of covering all the major pathing algorithms and
approaches, and had a little tool that demostrated each. You could watch
how (normal) Djkstra's "spirals" out looking for a solution vs. A*'s
"searchlight" method. It was very cool and easily one of the best
presentations at the CGDC.
: An interesting point that I just realized: A* is faster than Dijkstra, but
: not always as good...it uses heuristics, and tries to go towards the target
: and around obstacles. This can lead to it finding a more direct but
: possibly more expensive (in movement points) path than Dijkstra...and this
: side-effect might be actually useful to someone who is trying to simulate
: "realistic" unit movement over "perfect" unit movement.
Agreed, although Bryan did demonstrate a nasty concavity situation
which A* took a *lot* longer to solve the Dijkstra. Six of one, half dozen
of the other....
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
[Beacon method]
Ph> The main problem with this is that you have to setup beacons for all
Ph> maps by hand... Although most games have premade terrain anyway. You
With large, complex maps that could be a lot of fun. Oh yeah. :)
Ph> blocking terrain. Ideally the same terrain could be attractive or
Ph> repulsive in different strengths for different types of units (e.g.
Ph> ground as opposed to naval).
The more complex it gets, the more evil it becomes. :)
Ph> I'm wondering how effective writing code to try to figure out how to
Ph> place attractors and repulsors would be... Any ideas?
Just one... you could leave this run over night. Have the unit start at a
random location and go to a random destination and trace its path in a data
element (well, it'd be best to use an array the same size as the map and add
one to wherever the unit goes). Then, after it gets there or some sort of
time elapses, you located the areas with the largest concentration of movement
and put a beacon there that is proportional to the concentration of movement.
As for determining where high concentrations are (keep in this is over an
area), I'm sure there is a simple way as colour quantinization techniques do
similar things in 3D.
P.S. Yeah, I know I've been pushing this add-one-to-the-map idea over the edge
lately. :)
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Hey, Steven! How ya been? Or do you prefer to go by your given name now??
Hu> : Question: How does it tell when it is stuck?
Hu> Alternatively, why not just define your terrain as not having
Hu> obstacles your units can *never* cross? Replace those with "expensive"
Hu> terrain that take long to cross, but not impossible, and your
Hu> convex/concave problem goes away as well.
True, but that might look ridiculous depending on the game. Suppose a game is
in a city ... how do you cross a solid wall? :)
But, that *would* work brilliantly in games that are set in the great
outdoors.
Hu> How's WASTED coming along, Sunir? :) Oh, I'm sorry, was it WASTE
Hu> instead? :)
WASTE is having troubles avoiding obstacles as well.
It's moving along, but all of a sudden, it slowed down a lot. Fortunately, a
lot was done before we hit the wall (so to speak <G>).
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
:> Ph> Just modify your maps so that all blocking terrain is convex. ;-)
:>Seriously, that is a viable solution.
Dm> Actually, in this case Sunir, it is not.
Not in this *particular* case, no. In general, it may be. Sue me for looking
beyond this instance. L:) (Sunir with an axe in his head)
:>Question: How does it tell when it is stuck?
Dm> That was the point of my original post! :)
I know.
:>It'd get stuck because of those too if the map is modifiable.
Dm> It is, and thus, I don't have any real control over the obstacles.
The beacon method is also out.
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
> Question: How does it tell when it is stuck?
Br> The easy way out would be to use time. The object could be considered
It wouldn't be accurate. Suppose a complex, maze-like map where the unit has
to go back and forth. The time would have to be equivalent to the area *
velocity (kind of.. velocity is 1D, area is 2D.. but just screw that and use
the numbers).
Br> time, or if it stays in the same area for too long.
That's what I mean.. how do you figure that out cheaply?
ss...@intranet.ca
Br> NB: I've quoted the word "beacons" because it usually has a slightly
Br> different meaning in robotics.
Are you referring to the method where each robot is a beacon for the others?
Then you go out until you get to the end of beacon range at which point the
next robot comes down the line.
Anyway, the reminded me of the last time (first time) I had heard about
beacons. I had an idea about the effects of that.
You send out units until they are no longer in visible sight of another units.
If it is, keep it moving. Then send out other units.
In this way, the units should spread out over the map and therefore be able to
cover the most area for recon. It also makes them go out in an expanding
area. It also creates a border/front which you can use to detect incoming
enemies or push them back.
Just a thought.
Andrew Searls
>
> :>: The disadvantage of this method is that it easily gets trapped in
> :>: local minima.
>
> I found, in my implementation using the above technique, it was very easy to
> trap an AI player, such as...
>
> T
>
> XXXXX
> X X
> X X
> X
>
> A
Someone earlier (perhaps a different thread) mentioned a wave propogation
approach. You could start at A, and pick all squares within, say 45 degrees
to line AT. Then take each of those squares and do the same. Some easy
optimisations of this would be: Keeping track of squares visited to
avoid duplication. Carefully adjusting the angle through which you sweep
your search. Picking lower cost squares over higher cost squares.
Keep in mind also that if your terrain has verying costs, that the shortest
route this way may not necessarily be the cheapest one. You might want to
pick all current points within a certain radius once one point reaches the
target, or something along those lines (pick the five closest points and
try a line of sight shot or something.
--
-Andy Searls
graduate, Borg Institute of Technology
Late Enhancements: unrecognized requirements due to lack of proper analysis.
/********************************************
Are you surfing, or just treading bits?
********************************************/
http://gaia.ecs.csus.edu/~searlsa
"Proof of Murphy's Law:
Murphy's Law cannot be proven, yet is correct, as when you try to
prove Murphy's Law, you will see that the proof is incorrect.
This is obviously due to Murphy's Law, therefore
one can only conclude that Murphy's Law is correct."
"If you're looking for a 'Hello, world' OS,
DOS will fit the bill perfectly"
Eric Dybsand
Woodcock) writes:
>
>
>Bryan did a great job of covering all the major pathing algorithms
>and approaches, and had a little tool that demostrated each. You
>could watch how (normal) Djkstra's "spirals" out looking for a
>solution vs. A*'s "searchlight" method. It was very cool and easily
>one of the best presentations at the CGDC.
>
Yes it was, perhaps, the best pathing presentation that has been
done at CGDC.
Did you get Bryan to upload his little pathing demo to your web page?
>: An interesting point that I just realized: A* is faster than
>: Dijkstra, but not always as good...it uses heuristics, and tries
>: to go towards the target and around obstacles. This can lead to it
>:
>: [snip]
>
>Agreed, although Bryan did demonstrate a nasty concavity situation
>which A* took a *lot* longer to solve the Dijkstra. Six of one,
>half dozen of the other....
>
Yes, that surprised me too. I've not seen a modified A* do that.
Regards,
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
Eric Dybsand
writes:
>
>An interesting point that I just realized: A* is faster than
>Dijkstra, but not always as good...it uses heuristics, and tries
>to go towards the target and around obstacles. This can lead to
>points) path than Dijkstra...and this side-effect might be actually
>useful to someone who is trying to simulate "realistic" unit
>movement over "perfect" unit movement.
>
>
>
This has been my experience too Darren, that with a modified A*,
the unit often found the kind of path I might have taken as a
driver (especially with an off road type vehicle) but not necessarily
the most efficient path.
I also found that pathfinding during real time, created some
interesting artifacts in the data as a longer path was calculated.
Peter Schaefer
How about this: You can have any type of obstacle, but you place
convex 'shadow obstacles' over those that aren't convex.
This means you will have to tag every map tile with an obstacle area
identifier.
<sigh>
All those ingenious Algorithms waiting to be written by you & me !
--
Peter Schaefer
"office":
scha...@malaga.math.uni-augsburg.de
http://wwwhoppe.math.uni-augsburg.de/schaefer
"leisure":
scha...@mathpool.uni-augsburg.de
http://www.mathpool.uni-augsburg.de/~schaefer
Chant this Mantra 1024 times a day
to become a happy usenet user:
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Deedledee Deedledee Deedledee
Szu-Wen Huang
: Hey, Steven! How ya been? Or do you prefer to go by your given name now??
Quite fine... 'Steven' will be just fine ;)
: True, but that might look ridiculous depending on the game. Suppose a game is
: in a city ... how do you cross a solid wall? :)
A tank or APC can ram the wall, while infantry can climb it ;). In any
case, a simplistic "go left" might work for non-continuous obstacles.
: But, that *would* work brilliantly in games that are set in the great
: outdoors.
Except when (as somebody else pointed out) the scale is large and you have
marine and land units. Something of the scale of Empire would obviously
not work, because ships would climb on land ;).
: Hu> How's WASTED coming along, Sunir? :) Oh, I'm sorry, was it WASTE
: Hu> instead? :)
: WASTE is having troubles avoiding obstacles as well.
: It's moving along, but all of a sudden, it slowed down a lot. Fortunately, a
: lot was done before we hit the wall (so to speak <G>).
Equip the unit with a terrain-blaster :).
Bjorn Reese
>
> > Question: How does it tell when it is stuck?
> Br> The easy way out would be to use time. The object could be considered
>
> It wouldn't be accurate. Suppose a complex, maze-like map where the unit has
Which is why I said "the easy way out" ;) I didn't intend to make
some general solution applicable to every possible scenario.
> Br> time, or if it stays in the same area for too long.
>
> That's what I mean.. how do you figure that out cheaply?
I've stumbled upon a similar technique, where they use a local
spatial memory, which may be more suitable. Try
http://www.cc.gatech.edu/grads/b/Tucker.Balch/papers/avoid_past.ps.Z
Darren Reid
> Ph> I'm wondering how effective writing code to try to figure out how to
> Ph> place attractors and repulsors would be... Any ideas?
>
> Just one... you could leave this run over night. Have the unit start at a
> random location and go to a random destination and trace its path in a data
> element (well, it'd be best to use an array the same size as the map and add
> one to wherever the unit goes). Then, after it gets there or some sort of
> time elapses, you located the areas with the largest concentration of movement
> and put a beacon there that is proportional to the concentration of movement.
>
> As for determining where high concentrations are (keep in this is over an
> area), I'm sure there is a simple way as colour quantinization techniques do
> similar things in 3D.
>
> P.S. Yeah, I know I've been pushing this add-one-to-the-map idea over the edge
> lately. :)
Hmm...might not have to run over night. Imagine this:
The user makes a map (may even be random generated). When it is selected to be played,
your program initializes an equal size array to 0 and then charts shortest paths from
each edge to opposing edges (on a 64x64 map, 128 paths are calculated). It adds 1 to
each cell crossed each time. This could be calculated real quick on loading the map, and
would give you some good info on Hotspots (passes, roads, etc) and ambush points (a
hotspot with dead zones next to it would be an obvious place to look).
Hey! Sunir! This is sounding interesting. Anyone have any ideas on evaluating the data
generated by this system?
This could be performed recursively as well....calculate a second pass from the edges to
the biggest hotspots, to show where the enemy is liable to be while on his way to the
hotspots, and where to suspect ambushes, and where to lay them...of course, depending on
your game system/map design, edges might not be the best starting points for this second
pass. Other hotspots might be, or cities, or whatever.
This map could be used as a bias adjustment for burnt circles, too.
There must be a big flaw in this somewhere...it sounds too easy <g>.
-Darren Reid
Darren Reid
> That's Bryan Stout's presentation; he lurks around here too sometimes.
>
> Bryan did a great job of covering all the major pathing algorithms and
> approaches, and had a little tool that demostrated each. You could watch
> how (normal) Djkstra's "spirals" out looking for a solution vs. A*'s
> "searchlight" method. It was very cool and easily one of the best
> presentations at the CGDC.
Cool! I didn't go to that seminar, as I had other things to do...Bryan was very visible
in a few of the roundtables that I attended, and introduced himself to me eventually
(guesse I was visible too <g>). I would love to look at that tool...I'll have to email
him and see if he'll share it.
mari...@nwoasis.wa.com
>
>> The main problem with this is that you have to setup beacons for all
seems similar to the project I am working on and currently trying to
figure out.
For my application, I am trying to plot a course on a globe, where I
know the position and destination points, but can only travel in water
and must navigate around all land masses. The globe is configured in a
geodesic pattern so that any point could be land or water (but that all
water would be somehow connected for travelling purposes). If I could
make a straight course, I know an easy way to figure the straightest
course, but if the land masses get very convoluted between my position
and destination, the time necessary to find a good course could go up
dramatically (especially if an exhaustive search was necessary).
I saw mention of the beacons to place, and thought of determining
something like major navigation lanes (where many courses tend to
follow)... and if I have a hard time finding a course to a destination,
I can try finding a course to part of the navigation lane, and finding
my destination from there. Does this sound reasonable? I don't see it
generally finding the best route to another place, but I guess I am
thinking of it as getting out of the convolution into a place where I
know I can plot an easier course...
I haven't thought of any other way as yet to get out of whatever place
without potentially needing an exhaustive search to find the only outlet
from a large "ocean" which spans numerous points of the globe.
Any ideas? Thanks...
Marianna
Mail sent with Portico for Excalibur
Jason Kester
> Bryan did a great job of covering all the major pathing algorithms and
>approaches, and had a little tool that demostrated each. You could watch
>how (normal) Djkstra's "spirals" out looking for a solution vs. A*'s
>"searchlight" method. It was very cool and easily one of the best
>presentations at the CGDC.
What's wrong with a simple recursive algorithm to solve the shortest path thing? I did one
up in a couple hours after work one day (in QBasic, no less!), and it seems to find paths
plenty fast in any semi-open landscape.
I can only assume that A* uses some other method, or it wouldn't get stuck. Is it really
all that good?
Bryan Stout
>
>Darren Reid (shok...@nbnet.nb.ca) opined thusly:
>: Seriously, am I missing something here? DO you really want a path algorithm
>: as stupid as the C&C one? What's wrong with a true A* or Dijkstra's? Check
>: out: http://www.lis.pitt.edu/~john/shorpath.htm for lots of good stuff.
>
> I'd just like to second Darren about this page; it's a good one.
>
>: There is a nice white-paper on shortest path algorithms in the 1996 CGDA
>: proceedings, on page 439.
>
>
Here I am, poking out of lurking. (My mom's in town to see the new baby;
sometimes things like that keep me away from even lurking.)
I also like that web page.
> Bryan did a great job of covering all the major pathing algorithms and
>approaches, and had a little tool that demostrated each. You could watch
>how (normal) Djkstra's "spirals" out looking for a solution vs. A*'s
>"searchlight" method. It was very cool and easily one of the best
>presentations at the CGDC.
Thank you.
>: An interesting point that I just realized: A* is faster than Dijkstra, but
>: not always as good...it uses heuristics, and tries to go towards the target
>: and around obstacles. This can lead to it finding a more direct but
>: possibly more expensive (in movement points) path than Dijkstra...and this
>: side-effect might be actually useful to someone who is trying to simulate
>: "realistic" unit movement over "perfect" unit movement.
>
> Agreed, although Bryan did demonstrate a nasty concavity situation
>which A* took a *lot* longer to solve the Dijkstra. Six of one, half dozen
>of the other....
I guess I didn't explain some things well enough. [Terminology: A* sorts the
candidate nodes based on the lowest f(n) = g(n) + h(n). g(n) is the (shortest)
cost from start to n, h(n) the estimate of the shortest cost from n to goal.]
As long as h(n) is never greater than the true cost from n to the goal, A* will
*always* find a shortest path. (I say "a", not "the", because several paths
may have the same cost.)
Now, A* is not a single search, but a class of searches, depending on the type
of heuristic function h(n) being used. If h(n) is always zero, we have
Dijkstra's algorithm, which counts the cost from start but makes no estimate of
the remaining cost. IOW, Dijkstra's *is* an A* search.
I think Darren is referring to the Best-First search, which does the opposite,
namely sorting only on h(n), ignoring the actual cost of the search. It can be
a lot faster than the A* searches, but can end up with a lousy path.
If the h(n) function is no longer guaranteed to be an underestimate, then the
search is not truly "A*", but only "A" (a bit of nomenclature I didn't mention
in the lecture or proceedings). The weightier h(n) is, the more A performs
like a best-first search; the lighter, the more like Dijkstra's. How one
weights h(n) would depend on the tradeoff between time of search and quality of
path that is best for the game.
Steve, I can't think of anything I did which showed A* being slower than
Dijkstra's, since A* at its worst was exactly Dijkstra's; while with a high
h(n) it went even faster. Can you describe what you remember better?
Bryan Stout
bst...@interramp.com
Bryan Stout
>>Bryan did a great job of covering all the major pathing algorithms
>>and approaches, and had a little tool that demostrated each. You
>>could watch how (normal) Djkstra's "spirals" out looking for a
>>solution vs. A*'s "searchlight" method. It was very cool and easily
>>one of the best presentations at the CGDC.
>>
>
>done at CGDC.
>
>Did you get Bryan to upload his little pathing demo to your web page?
>
>Glacier Edge Technology
>Glendale, Colorado, USA
>
Hi Eric,
I'm tinkering with the program -- adding some features I didn't have time to do
before the lecture -- and I'll probably post it somewhere when I'm done.
Are there any requests for features people would like to see? I don't promise
what I'll have time to do, but I'll consider all suggestions.
Regards,
Bryan Stout
bst...@interramp.com
Tim Hardy
do
>before the lecture -- and I'll probably post it somewhere when I'm done.
>
>Are there any requests for features people would like to see? I don't
promise
>what I'll have time to do, but I'll consider all suggestions.
>
>Regards,
>
>Bryan Stout
>bst...@interramp.com
>
Hi Bryan,
Thanks for your help with my A* problems earlier (you gave me some pointers
in the thread Best Path Algorithm). I would like to request you include in
your tool the option to see A* work on a relatively large (100x100) map with
no "forbidden" squares and varying terrain costs with lots of terrain on the
map. This is the scenario that took so long in my implementation. I am eager
to see if you can get decent speeds using the "default" algorithm (no major
tweaking) given the scenario above in Windows95.
I reduced my path finding speed (it was taking 5-30 seconds on p100) by using
an array for the x,y searches and a linked list sorted wrt f for the f
searches. It now takes <1-5 seconds, and I can still speed it up with
"mechanical" modifications like assembler, etc.
For everyone else:
Someone already said this, but the original poster of this thread should
simply use A* to find his paths (the real thing, not "slightly modified" aka
doesn't work). If the posters to this thread would spend some time speeding
up the A* code by otimizing it to death and making it freely available, a lot
of people will be happy. I posted my entire C++ A* solution to this newsgroup
for people to comment on but I guess nobody likes to read code (except Chris
Palmer - thanks a lot Chris). Oh well, I will optimize my solution and
probably make it available anyway.
The basic algorithm needs tons of optimizing for anyone who hasn't tried it.
Tim
Steve Pavlina
pathfinding calculation works fairly well in real-time -- as long as
the terrain remains static. A* works fine if you know in advance what
the terrain looks like, but how do you account for dynamic terrain
changes?
Taking an example from Warcraft II (a real-time strategy game), let's
say I want to have a peasant walk from one spot to another, avoiding
obstacles as he goes. When does this path calculation take place? Do
you precalculate and then follow it exactly? Do you re-calculate it
after some fixed interval? In Warcraft, it can take a peasant 45
seconds to go from one end of the map to the other. In that time, new
structures may have been built that render the initially calculated
path invalid, or trees may have been chopped down that make the
original path a very poor choice.
Another thing that Warcraft does nicely is that units avoid each other
(i.e. no two ever occupy the same 32x32 tile, even when moving).
Sometimes you notice rare glitches, but for the most part it works
well. In Command & Conquer, units will often overlap each other when
they move, but if they do, they still spread out again when reaching
their destination. The problem with Warcraft's method is that units
will often block each other. I have played many a scenario where the
computer's peasants all get stuck while mining gold. Units heading to
the mine will block units returning from the mine, and they can't get
around each other since the only path for each group is blocked by the
other group.
So my basic question is: How do you implement pathfinding when your
units have to avoid other units, both stationary and moving, as well
as new structures that might be built shortly after they start moving?
I can think of many ways to potentially solve this problem, but I'd
like to know if anyone here has had experience with it as well?
-- Steve
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Ma> and must navigate around all land masses. The globe is configured in a
Ma> geodesic pattern so that any point could be land or water (but that
What? At the vertices of the triangles or just any point on the surface?
Ma> course, but if the land masses get very convoluted between my position
Ma> and destination, the time necessary to find a good course could go up
Ma> dramatically (especially if an exhaustive search was necessary).
Maybe. It's more like the more water you have free the longer it'll take.
But then again, it depends.
Ma> I saw mention of the beacons to place, and thought of determining
Ma> something like major navigation lanes (where many courses tend to
Ma> follow)... and if I have a hard time finding a course to a
Ma> destination,
This is just like the precalculated shortest path discussed in the command and
conquer thread. This system breaks when the player recognizes the
precalculated shortest paths and then lies in ambush. If it's possible, the
player can even block off your path.
Ma> I can try finding a course to part of the navigation lane, and finding
Ma> my destination from there. Does this sound reasonable? I don't see
That would work.
Ma> I haven't thought of any other way as yet to get out of whatever place
Ma> without potentially needing an exhaustive search to find the only
Have you looked at the A* algorithm?
Jasper Phillips
>To: PhilljasUnknownx.engr.orst.edu
>Subject: Re: Avoiding Obstacles to
>
>
>Seriously, that is a viable solution.
True, it's not very general though. Not allowing concavity removes most
of the more complex terrain.
>
> Ph> If this is the case, couldn't you just put in a special case if the AI
> Ph> get stuck? So if your AI can't go where it wants, you can switch to
>
>Question: How does it tell when it is stuck?
*Shrug* I didn't have anything particular in mind. Such things as the amount
of time spent in the same area, or the sum of your attractors and repulsors
returning you to where you just were might work. Obviously an imortant
question, but one that I felt was a little off topic. (There are lots of
possiblities, and this part of the ai is itself an issue...)
>
> Ph> Another option might be to combine this with some sort of pre computed
> Ph> "best path routes" between general areas, and let that kick in if you
> Ph> really got stuck.
>
>It'd get stuck because of those too if the map is modifiable.
True enough. Most of the games that let you modify the map do so with
destroyable barriers though; you could try to detect this and then clear
the obstruction rather than go around it (or get stuck). The most commonly
touted example of this is Command and Conquer (although I've never played
this one) where people comment that all the computer would need to do
to get out of the "sandbag deadend" would be to destroy it.
>--
>Sunir Shah (ss...@intranet.ca) http://intranet.ca/~sshah/
-Jasper
--
/\ Jasper Phillips (Pit Fiend) ______,....----,
/VVVVVVVVVVVVVV|==================="""""""""""" ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""
\/ http://www.cs.orst.edu/~philljas/
Jasper Phillips
Peter Schaefer <schaefer> wrote:
>I think having only convex obstacles is a good starting idea;
>How about this: You can have any type of obstacle, but you place
>convex 'shadow obstacles' over those that aren't convex.
>This means you will have to tag every map tile with an obstacle area
>identifier.
This would work fairly well when obstacles are small... I'm guessing pretty
much so long as sighting ranges can cover the concavity, so that a player
couldn't just hide everything in a little cave. Big rings of mountains would
cause even more problems...
>Peter Schaefer
Jasper Phillips
Darren Reid <shok...@nbnet.nb.ca> wrote:
>Simon Slavin wrote:
>> When the piece gets trapped, take a note of the cells occupied by the
>> obstacle. Follow the left-hand wall until no part of the obstacle lies
>> between the piece and the target, then continue. [Simple algorithm.]
>
>Only works if the non-traversable terrain is only slightly concave. If the concavity
>bends beyond a tangent to the line drawn to the target, you will start back towards the
>target while still trapped within the cavity. Been there, done that ;)
I don't follow you here. If the concavity is as you describe, you keep
following the wall... don't return start back towards the target while the
the "current obstacle" blocks LOS. I don't know if this is a great alogorithm,
but I don't see why it wouldn't work.
>-Darren Reid
Eric Dybsand
writes:
>For everyone else:
>Someone already said this, but the original poster of this
>thread should simply use A* to find his paths (the real thing,
>not "slightly modified" aka doesn't work). If the posters to this
>thread would spend some time speeding up the A* code by otimizing
>it to death and making it freely available, a lot of people will be
>happy. I posted my entire C++ A* solution to this newsgroup for
>people to comment on but I guess nobody likes to read code (except
>Chris Palmer - thanks a lot Chris). Oh well, I will optimize my
>solution and probably make it available anyway.
Hi Tim,
I for one would like to see your code, and I do remember you
posting the news that you would post it, but I never saw the
posting with the actual code. Probably, it got lost by my ISP
or something.
If I may suggest, that you send it to Steve Woodcock, and let
him put it up on his web page. Steve is always around comp.ai.games
and has developed one of the best collections of info and links on
computer game AI, and pathing is definitely an appropriate topic
for it.
Regards,
Richard Gemmell
>
> I've been working on a game similar to Warcraft II, and the
> pathfinding calculation works fairly well in real-time -- as long as
> the terrain remains static.
One option is to pre-calculate the path when you specify the
destination. At the beginning of each turn check that the path is still
clear. If it isn't, find a new path.
Richard
Ralph Scott
Jasper Phillips <phil...@tx.ENGR.ORST.EDU> wrote:
>In article <317052...@nbnet.nb.ca>,
>Darren Reid <shok...@nbnet.nb.ca> wrote:
>>Simon Slavin wrote:
>>> When the piece gets trapped, take a note of the cells occupied by the
>>> obstacle. Follow the left-hand wall until no part of the obstacle lies
>>> between the piece and the target, then continue. [Simple algorithm.]
>>
>>Only works if the non-traversable terrain is only slightly concave. If the concavity
>>bends beyond a tangent to the line drawn to the target, you will start back towards the
>>target while still trapped within the cavity. Been there, done that ;)
>
>I don't follow you here. If the concavity is as you describe, you keep
>following the wall... don't return start back towards the target while the
>the "current obstacle" blocks LOS. I don't know if this is a great alogorithm,
>but I don't see why it wouldn't work.
>
I believe it works fine. I used it in the game omega. I was going
to post a solution but it is easy enough to do on your own. Your way
could be simplified by just remembering the direction you wanted to
go in and just circling around until you hit that. You may have
to keep track of how many circles you've taken but it does work.
---ralph
Tim Hardy
spav...@pacificnet.net (Steve Pavlina) wrote:
>I've been working on a game similar to Warcraft II, and the
>pathfinding calculation works fairly well in real-time -- as long as
>the terrain looks like, but how do you account for dynamic terrain
>changes?
For starters, Warcraft 2 doesn't really have a decent path algorithm. The
armies just seem to head straight for their destination going left or right
when they hit something, then giving up after a while. Command&Conquer
doesn't find true shortest path either (any game where the guys get stuck or
you find yourself saying - "WHY THE HECK ARE THEY GOING THAT WAY!" doesn't use
a true shortest path from start to destination).
For your game, since you are using true shortest path finding, just separate
the path finding from the movement. Calculate the path and store it. When
the army moves, he just asks the path which direction he's supposed to go next
(the path is just a collection of bytes indicating compass directions (you can
actually use just 3 bits for 8 compass directions) and the army tries to move
there. You need to have some communication between the army and the map for
movement (can I go here?, will going here cause me to explode or take damage?
- you'd think you'd avoid this when finding the path, but you may have no
choice or something may have changed, etc.) This allows the map to change
after the path is calculated. If something comes up that would cause you to
re-calculate (impassibility, instant death, etc) just re-calculate the path.
To sum up, separate the path calulation from the actual movement.
Tim
Szu-Wen Huang
:For starters, Warcraft 2 doesn't really have a decent path algorithm. The
:armies just seem to head straight for their destination going left or right
:when they hit something, then giving up after a while. Command&Conquer
:doesn't find true shortest path either (any game where the guys get stuck or
:you find yourself saying - "WHY THE HECK ARE THEY GOING THAT WAY!" doesn't use
:a true shortest path from start to destination).
[snip]
On the other hand, a true shortest path algorithm can be immensely
annoying to gameplay. IIRC The Perfect General (or somesuch) has
such a feature and I'm not at all satisfied with it. For instance,
I advance my forces performing a sweep of the flanks - a common and
useful maneuver. When my platoons reach a forest, I intend for them
to sweep it, not run a weird circle and skip around it! While
theoretically sound, a true shortest-path following unit tends to
look mathematical and stupid. That's a pitfall the game designer
must take into consideration when picking an algorithm. In other
words, I would expect my unit to take the same general direction I
told it to go, avoiding some obstacles (especially unpassable ones)
along the way, but suffer some speed loss if I, their commander,
happened to have ordered them to wade through a swamp.
This has to do with human perception, I think. When I click my mouse
to tell my unit to "go here", I'm giving it a point, implicitly forming
a ray with its present location. If your frame of mind treats "go here"
as simply "get here, I don't care what path you take", then my irks
will not bother you. It might be interesting to know what people
expect of that command. Thoughts?
Avi Pilosof
: As someone already mentioned, a quad-tree.
: Take a big square. If it is completely free, mark it as clear. If it
: is completely blocked, mark it as blocked. If it is partially clear,
: give this square 4 children (in effect dividing it into 2x2) and repeat
: this procedure for all of the children.
: At the end of this, you'll have a number of squares in this tree-structure,
: all the leaves will be either impassable or clear.
: Search recursively for a path from free square to free square.
This is quite brilliant. I'd used quadtrees before in my graphics programs,
but it didn't cross my mind to use them here.
On e question: Once I have a quadtree, and I wanna search for a path,
I then use something like A*, right?
I mean - I COULD do a rat-maze type of thing and try all solutions, but
it's not elegant.
###################################################################
Avi Pilosof - av...@cse.unsw.edu.au
- http://www.cse.unsw.edu.au/~avip/
> Bigamy is having one wife too many. Monogamy is the same thing. -- Anon
Kevin Kent
> This has to do with human perception, I think. When I click my mouse
> to tell my unit to "go here", I'm giving it a point, implicitly forming
> a ray with its present location. If your frame of mind treats "go here"
> as simply "get here, I don't care what path you take", then my irks
> will not bother you. It might be interesting to know what people
> expect of that command. Thoughts?
Personally, I think that units should take the shortest possible route,
while giving a wide berth to hostile units. This would prevent units from
taking a short-cut back to base that brings past the front of an enemy
base. I'm constantly amazed at how units in some games have no common
sense, and will blithely go where no unit with a survival instinct would
go.
Perhaps that's what each unit needs - a survival instinct. That way, units
which are nearly dead would make a run for it, defenceless units would
stay away from hostile units, etc. Hmm, there's possibilities there...
K.
--
Kevin Kent (kk...@csc.uvic.ca)
Student, CSc/B, University of Victoria, Canada
Darren Reid
>
> I've been working on a game similar to Warcraft II, and the
Jeez, there's going to be 5000 of THOSE fighting for shelf space Christmas '97 :)
> So my basic question is: How do you implement pathfinding when your
> units have to avoid other units, both stationary and moving, as well
> as new structures that might be built shortly after they start moving?
> I can think of many ways to potentially solve this problem, but I'd
> like to know if anyone here has had experience with it as well?
Well, one answer to part of the problem is to store your path, then follow it until you
can't anymore, then calculate a new one. That won't answer to "they cut down a tree, so
now there is a better path", but that's normally not such a big thing in a fast-action
real-time game. You could recalculate all paths being followed by all units when a
terrian cell changes type...if you had the CPU/brain-dead simple SPA. <-note extraneous
use of stupid acronym.
For an OK effect, you might just recalculate paths for units close to the changed cell,
up to x# of units max. Hell, it might be better than OK...if you saw the computer change
direction a few times under circumstances like that, you'd probably be real impressed. I
would be...for now.
As for multiple stuck units in confined spaces...you could keep count of all "stuck,
can't follow my pre-calced path this frame" units, and if>1 check for adjacent units in
same difficulty....then back off units using what could be a slower, more rule-based
function, until some units can get on their way.
-Darren Reid
Darren Reid
> >Only works if the non-traversable terrain is only slightly concave. If the concavity
> >bends beyond a tangent to the line drawn to the target, you will start back towards the
> >target while still trapped within the cavity. Been there, done that ;)
>
> I don't follow you here. If the concavity is as you describe, you keep
> following the wall... don't return start back towards the target while the
> the "current obstacle" blocks LOS. I don't know if this is a great alogorithm,
> but I don't see why it wouldn't work.
oops.hehe...I read that post a wee bit too fast. I thought it was the old "move left
until there's a free cell between you and your target" method. Yes, move left along
wall until LOS does work. It is ALMOST the ultimate trade-off of nice path vs speed of
calculation <big grin>. C&C found the ultimate trade off winner in that division:
Bresenham's for a path algo, follow obstacle wall until all the way back around to a
point on original plotted line, then continue on our way. About as fast as you could ask
for...and so stupid a potato would plot a better path. Guesse they needed speed REAL
bad.
Steven Woodcock
: To: Bre...@imada.ou.dk
: Subject: Re: Avoiding Obstacles to
: > Question: How does it tell when it is stuck?
: Br> The easy way out would be to use time. The object could be considered
: It wouldn't be accurate. Suppose a complex, maze-like map where the unit has
: to go back and forth. The time would have to be equivalent to the area *
: velocity (kind of.. velocity is 1D, area is 2D.. but just screw that and use
: the numbers).
: Br> time, or if it stays in the same area for too long.
: That's what I mean.. how do you figure that out cheaply?
Figuring out if a given unit has been in one area too long is relatively
cheap, actually. Time in area = time now - time arrived. Use a delta
movement trigger to start the countdown; if a unit hasn't moved more than
some arbitrary value (presumably small), then start the countdown. When
you exceed the threshold, do something else (go the other way, blow up
the wall, whatever).
Steven Woodcock
"The One and Only"
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Real3D <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: wood...@escmail.orl.mmc.com (Work), swoo...@cris.com (Home) |
| Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) |
| http://www.cris.com/~swoodcoc/ai.html (Game AI page) |
| Disclaimer: My opinions in NO way reflect the opinions of |
| the Lockheed Martin Information Real3D |
+=============================================================================+
Steven Woodcock
: I saw mention of the beacons to place, and thought of determining
: something like major navigation lanes (where many courses tend to
: follow)... and if I have a hard time finding a course to a destination,
: I can try finding a course to part of the navigation lane, and finding
: my destination from there. Does this sound reasonable? I don't see it
: generally finding the best route to another place, but I guess I am
: thinking of it as getting out of the convolution into a place where I
: know I can plot an easier course...
Personally I think using beacons for a case such as this is perfect,
and frankly it's not too far off from the way the ancient mariners did
it. Once they found a safe, fairly straight sea lane they didn't like
to muck around! ;)
: I haven't thought of any other way as yet to get out of whatever place
: without potentially needing an exhaustive search to find the only outlet
: from a large "ocean" which spans numerous points of the globe.
Since you're dealing with a globe and a relatively huge number of
potential "tiles", if you will, any of the classic algorithsm are
going to be time-eaters. You could subdivide the problem into finding
the best path within an individual ocean basin, and use natural causeways
and straits between the oceans as "beacons". This is somewhat similar
to the way we (think) C&C does its pathfinding.
Good luck!
Steven Woodcock
: Yes it was, perhaps, the best pathing presentation that has been
: done at CGDC.
: Did you get Bryan to upload his little pathing demo to your web page?
Not yet, but I've pinged him for it twice now....
Well, this makes THREE times...you out there Bryan? ;)
Steven Woodcock
: If I may suggest, that you send it to Steve Woodcock, and let
: him put it up on his web page. Steve is always around comp.ai.games
: and has developed one of the best collections of info and links on
: computer game AI, and pathing is definitely an appropriate topic
: for it.
Thanks Eric. <blush>
Tim, I'd *love* to post you algorithm on my page. I've been thinking
about adding a "Practical Code" section for a while now, and it's definitely
time to get started.
In fact, let me make this public to All Whom Lurk Here: Send me your
code! Code to solve Line-of-Sight, code for pathing problems, code for
whatever falls within the general field of Game AI. I'll post it up on
my page in one easy-to-reach place so everybody can share the wealth.
I'll get that page started this weekend (the 20th), so send me your
code today!
(Thanks a *lot* Eric. As if I already didn't have enough hours in
the day! ;)
Richard Wesson
on a P5/100, you must be doing something wrong in the implementation.
I implemented 'ant races' (floodfill) for a 100x100, with highly
variable terrain, and I'm getting (on a 486-80) traversal times
less than a second -- always. I think I can squeeze down the times
a lot more, too, down to a hundred milliseconds or so. (This is in
DOS/C++ btw).
I suspect a sorted linked-list is a pretty bad idea, and that may
be what's killing you. If you need it sorted, use a heap or
a B-tree. Sorting the linked-list is probably putting you up
to O(n^2) or worse.
A minimum graph traversal should be O(E+V) log V worst-case. So
for a 100x100 that should be about 10,000+10,000 * 10 -- 200,000
operations. But your machine is doing 150,000,000 instructions
per second. Say 500 instructions per graph operation (generous!)
and you get 100,000,000 operations -- it should be doable in less
than a second. Without resorting to assembly, either, since with
assembly you would be cutting down the instructions executed to
100 or so per graph operation.
Heck, I bet I can implement ant races in Java and find a path in less
than two seconds on your P5/100.
-- Rich Wesson
Amit Patel
Steve Pavlina <spav...@pacificnet.net> wrote:
>I've been working on a game similar to Warcraft II, and the
>the terrain remains static. A* works fine if you know in advance what
>the terrain looks like, but how do you account for dynamic terrain
>changes?
[example deleted]
>So my basic question is: How do you implement pathfinding when your
>units have to avoid other units, both stationary and moving, as well
>as new structures that might be built shortly after they start moving?
>I can think of many ways to potentially solve this problem, but I'd
>like to know if anyone here has had experience with it as well?
Okay, there are two issues I tackle in my game:
1. What if the map changes and your path is no longer
optimal (or possible)?
2. What if another unit's in your way?
I haven't implemented either yet; they are in the design and I'm not
yet done coding them.
For (1), I have a background thread that recalculates paths in idle
time. Also, every unit only takes the first N steps of the calculated
path; when it's done with those N steps, it recalculates. It also
recalculates if it encounters an obstacle.
For (2), I wait some amount of time for the obstacle to go away. If
it doesn't go away, then I recalculate the path. This keeps me from
recalculating when there's a guy in the way who's going to move away
soon.
- Amit
Amit Patel
Tim Hardy <tim_...@nt.com> wrote:
>Hi Bryan,
> Thanks for your help with my A* problems earlier (you gave me some pointers
>in the thread Best Path Algorithm). I would like to request you include in
>your tool the option to see A* work on a relatively large (100x100) map with
>no "forbidden" squares and varying terrain costs with lots of terrain on the
>map. This is the scenario that took so long in my implementation. I am eager
>to see if you can get decent speeds using the "default" algorithm (no major
>tweaking) given the scenario above in Windows95.
>
>
>I reduced my path finding speed (it was taking 5-30 seconds on p100) by using
>an array for the x,y searches and a linked list sorted wrt f for the f
>searches. It now takes <1-5 seconds, and I can still speed it up with
>"mechanical" modifications like assembler, etc.
>
>Someone already said this, but the original poster of this thread should
>simply use A* to find his paths (the real thing, not "slightly modified" aka
>doesn't work). If the posters to this thread would spend some time speeding
>up the A* code by otimizing it to death and making it freely available, a lot
>of people will be happy. I posted my entire C++ A* solution to this newsgroup
>for people to comment on but I guess nobody likes to read code (except Chris
>Palmer - thanks a lot Chris). Oh well, I will optimize my solution and
>probably make it available anyway.
>
>
>Tim
Tim, can you be more specific about what needs to be optimized? What
distance function did you use? Did you try using a priority queue
data structure (like a heap) instead of a sorted linked list (for the
f searches)?
I'm planning to put my code up on the net once I optimize and document
it. A* seems to work fairly well on my small map (hexagonal; 32x24):
30 milliseconds to find a path from one corner to a random point
(averaged over 100 random points all over the map). I tried a
different distance function, which gives me paths in 4 milliseconds,
but it gives slightly worse paths, and it doesn't work in the "U"
obstacle case.
- Amit
Amit Patel
Darren Reid <shok...@nbnet.nb.ca> wrote:
>For an OK effect, you might just recalculate paths for units close to the changed cell,
>up to x# of units max. Hell, it might be better than OK...if you saw the computer change
>direction a few times under circumstances like that, you'd probably be real impressed. I
>would be...for now.
This sounds great!
Have you tried this or seen this in any games?
I'm using an idle-time background thread to recalculate paths.
Whenever someone changes part of the map, I could move nearby units to
the front of the queue of units that need their paths recalculated ..
it sounds easy to implement.
- Amit
Tim Hardy
>code! Code to solve Line-of-Sight, code for pathing problems, code for
>whatever falls within the general field of Game AI. I'll post it up on
>my page in one easy-to-reach place so everybody can share the wealth.
>
> I'll get that page started this weekend (the 20th), so send me your
>code today!
My code fragments (all one needs to implement A* in C++) are on their way in
an email to you Steve. Thanks for making your page available.
Tim
Steven Woodcock
: In article <317704...@nbnet.nb.ca>,
: This sounds great!
This *does* sound like a nice refinement of the whole algorithm.
I also have a background task in my current game which will recalculate
and refine paths on an "as available" basis. I don't get *much* CPU
time doing it that way, but I get my "normal" share plus a little
extra every once in a while, which (so far) seems like enough.
mari...@nwoasis.wa.com
> Ma> and must navigate around all land masses. The globe is configured
in a
> Ma> geodesic pattern so that any point could be land or water (but
that
>
>What? At the vertices of the triangles or just any point on the
surface?
triangles meet. But it is also much more complex than that... See,
every edge of the geodesic globe is a direction (link or path) between
one point and another, and if there is land in that direction, then
another course is necessary... therefore, effectively, every edge of the
globe can be land or water, as well as every point (although any one
point can be land only if all connected edges are land) Get confusing
yet? I think this lends itself to a much more realistic-looking map.
> Ma> course, but if the land masses get very convoluted between my
position
> Ma> and destination, the time necessary to find a good course could go
up
> Ma> dramatically (especially if an exhaustive search was necessary).
>
>Maybe. It's more like the more water you have free the longer it'll
take.
>
>But then again, it depends.
>
> Ma> something like major navigation lanes (where many courses tend to
> Ma> follow)... and if I have a hard time finding a course to a
>
>This is just like the precalculated shortest path discussed in the
command and
>conquer thread. This system breaks when the player recognizes the
>precalculated shortest paths and then lies in ambush. If it's
possible, the
>player can even block off your path.
something else. I have noticed another thread about A* and Djikstra's
pathing algorithms, and like the mention about the breadth-first search
that follows whatever course is currently the shortest (when adding the
amount gone so far and the estimated amount left to go). This sounds
like something that could get through a complex maze of land pretty
well if necessary... and if the destination was in a dead-end type of
area, all I'd need to do there is find the closest outlet and plot to
there... then follow my dead-end course back to the destination.
By the way... are there any available copies of this algorithm?
Thanks,
Marianna
Mail sent with Portico for Excalibur
Steve Pavlina
>If the traveler was blocked by another friendly traveler that isn't
>going anywhere (a squatter?), then you can do two things. Recalculate
>the path all over again, but from this new position or tell the
>squatter to move out of the way. The latter makes sense if the terrain
>is somewhat restricted (a bridge) and the former makes more sense if
>the terrain is wide open.
That's a good idea, and I thought it was really cool in C&C to see my
tanks politely move out of the way to let my newly manufactured units
take the field. But what do you do when the squatter is trapped as
well. An example from Warcraft 2: If you have peasants mining an
area with only one way in or out, through a narrow pass that is only 1
unit's width, the peasants will often get stuck. In fact, on a
certain built-in scenario ("Mine the Center," I think), if a computer
player starts in the bottom left corner, his peasants will always get
completely stuck fairly early in the game. The problem is that you
have several peasants going to the gold mine and several returning.
If two peasants going opposite directions enter the narrow pass
(between two farms, for instance) at roughly the same time, they will
block each other, and their friends will pile up behind them on each
side of the blockage. Now the two peasants that initiated the
blockage are completely unable to move in *any* direction because they
are blocked from behind by the others. For both middle peasants, the
squatter is also unable to move. The original assumption is that this
narrow pass is the *only* path to or from the gold mine.
One solution is to get some of the outer peasants on one side to back
up, then move the squatter on that side, and let the other side
proceed. This can be difficult to implement with a large number of
peasants (which the computer players in WC2 are prone to produce),
since there is a great deal of coordination that must occur. I.e. you
must identify which side of the blockage a peasant is on, and whether
he should back up or proceed through the pass. This problem is bound
to recur.
It may also be possible to prevent this from happening. I.e. you can
search ahead a little and see if the next few steps will create a
blockage.
Preventing the terrain from allowing this type of problem is not a
good general solution if you wish to include a scenario editor.
Any ideas for a good solution to this problem?
-- Steve
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
> Ph> Just modify your maps so that all blocking terrain is convex. ;-)
>Seriously, that is a viable solution.
Ph> True, it's not very general though. Not allowing concavity removes
No, not at all. But you do what you have to do to get it out, eh? :)
>Question: How does it tell when it is stuck?
Ph> *Shrug* I didn't have anything particular in mind. Such things as the
I think using a 2D version of the median-cut algorithm might work. I think
this would be like the quad-tree algorithm outlined in here a couple days ago.
Then, you'd have boxes around places with a lot of ones..
You'd need some sort of threshold for the minimum number of numbers in a
region though, or it may go down to too fine a resolution.
>It'd get stuck because of those too if the map is modifiable.
Ph> True enough. Most of the games that let you modify the map do so with
Ph> destroyable barriers though; you could try to detect this and then
That's when you start modifying game rules to plug holes in your AI... and you
gave me an idea.
:-)
--
Sunir Shah (ss...@intranet.ca) http://intranet.ca/~sshah/
Joe Bostic
<snip>
>
>So my basic question is: How do you implement pathfinding when your
>units have to avoid other units, both stationary and moving, as well
>as new structures that might be built shortly after they start moving?
>I can think of many ways to potentially solve this problem, but I'd
>like to know if anyone here has had experience with it as well?
If the traveler was blocked by another traveler that is moving, just
wait a bit and then try again. The other traveler will probably not be
blocking then.
If the traveler was blocked by another friendly traveler that isn't
going anywhere (a squatter?), then you can do two things. Recalculate
the path all over again, but from this new position or tell the
squatter to move out of the way. The latter makes sense if the terrain
is somewhat restricted (a bridge) and the former makes more sense if
the terrain is wide open.
If the surprise blocking terrain is truly static (a building for
example), then there is no choice but to recalculate the path all over
again. However, if the traveler has weapons of destruction, you have
another option -- blow up the blockage and proceed as if nothing had
happened. This also becomes an option if the squatter blockage is an
enemy.
Joe B.
Steven Woodcock
: True... I just hadn't thought of anything better... and I wanted to find
: something else. I have noticed another thread about A* and Djikstra's
: pathing algorithms, and like the mention about the breadth-first search
: that follows whatever course is currently the shortest (when adding the
: amount gone so far and the estimated amount left to go). This sounds
: like something that could get through a complex maze of land pretty
: well if necessary... and if the destination was in a dead-end type of
: area, all I'd need to do there is find the closest outlet and plot to
: there... then follow my dead-end course back to the destination.
: By the way... are there any available copies of this algorithm?
Marianna:
If you hop over to my web page (address below) I have several links
to various pathing algorithm pages, some with code. I also hope this
weekend to post some A* code solutions from various folks from this
very newsgroup; I'm trying to start an "AI Solutions" page so folks like
you don't have to run all over creation looking to solve problems that
have been solved a million times already. ;)
As to your specific problem, I still think you may want to go with
some kind of beacon approach. Maybe have several to represent multiple
routes. I don't know how many areas you've got the globe divided into,
but if it's a lot (i.e., several tens of thousands) A* and Djikstra's
are going to take forever to run unless you reduce the problem.
Multiple beacons would avoid the overhead of computing all of this while
providing multiple, hopefully-harder-to-recognize routes for your units
to follow.
Steve Atkins
Steve> do when the squatter is trapped as well. An example from
Steve> Warcraft 2: If you have peasants mining an area with only
Steve> one way in or out, through a narrow pass that is only 1
Steve> unit's width, the peasants will often get stuck. In fact,
Steve> on a certain built-in scenario ("Mine the Center," I
Steve> think), if a computer player starts in the bottom left
Steve> corner, his peasants will always get completely stuck
Steve> fairly early in the game. The problem is that you have
Steve> several peasants going to the gold mine and several
Steve> returning. If two peasants going opposite directions enter
Steve> the narrow pass (between two farms, for instance) at
Steve> roughly the same time, they will block each other, and
Steve> their friends will pile up behind them on each side of the
Steve> blockage. Now the two peasants that initiated the blockage
Steve> are completely unable to move in *any* direction because
Steve> they are blocked from behind by the others. For both
Steve> middle peasants, the squatter is also unable to move. The
Steve> original assumption is that this narrow pass is the *only*
Steve> path to or from the gold mine.
[Snip]
Steve> Any ideas for a good solution to this problem?
One quick & dirty hack might be to mark regions where this could
happen on the map (either by hand in the terrain editor, or automatically)
then to use a 'Railway Rivals' type of algorithm - a set of traffic lights
at each end of the area that will
o Wait until the region is empty of units
o Allow some units in from one end
o Wait until it's empty
o Allow some units in from the other end
and so on. It's cheating a little, but might give a usable behaviour.
If there are huge swarms of units there'd still be the problem of them
clogging up one end or the other. But if the map were marked like so:
AAABBB
AABB
AB
X
X
X
AB
AABB
AAABBB
AAAABBBB
and units going NE were allowed on A squares, units going SW were allowed
on B squares and the X squares were traffic light controlled the units
would behave like well behaved pedestrians, always keeping to the left and
queuing politely until the corridor is free.
Cheers,
Steve
--
'The best book on programming for the layman is "Alice in Wonderland";
but that's because it's the best book on anything for the layman.'
Steve Pavlina
>[on getting peasant blockages resolved]
>I don't know why you can't just get the peasants to move out
>of the way. Keep all peasants ranked by priority. Try-to move
>them in order of descending priority. A peasant who is blocked
>will 'tell' an unmoved blocker to get out of the way.
>If the blocker cannot move, mark him, and have him tell somebody
>unmarked to get out of his way, and so on. If/when you will find
>somebody who can get out of the way, then walk back up the
>chain of marked peasants, moving them all as they were told to
>move. If you can't find anybody who is capable of moving away
>for you (either by getting somebody else to move first or just
>moving directly himself) then return that you can't move. But this
>way, at least one peasant always makes progress.
The solution you suggested would work well for getting the peasants to
move out of the way. What concerns me is the amount of time the
peasants would spend being blocked. Even if they move out of the way
quickly, the blockage could recur every 5-10 seconds. That may seem a
little odd to the player, whose peasants seem to be doing a little
jig. I like the idea of using some kind of stoplight approach, to
prevent the peasants from blocking in the first place. Unfortunately,
it's also possible in Warcraft for the peasants to get stuck in passes
that are 2 peasants wide. It doesn't happen very often, but it does
seem to plague computer opponents with dozens of peasants. In this
case, yor approach would still work, and the stoplight method might be
modified into a rule that says you always walk on the right side
(relative to the direction you are walking).
>But the Warcraft programmers didn't seem to implement much pathfinding
>anyhow. The ships seem especially feebleminded in this respect. Oh
>well. C&C was refreshingly good that way, except for harvesters
>locking horns on bridges now and then.
Agreed. But I do have to credit the WC2 programmers for implementing
an AI that would work with the scenario editor. It doesn't do too
well on complex terrain, but it usually builds up a nice little
village to destroy. :) One thing I didn't like about C&C is that on
a few scenarios (depending on where you built your base), your units
might employ a variation of the shortest path algorithm know as the
stupidest path algorithm. I remember on the 13th mission of the GDI
side, the shortest, simplest path for my harvesters to return to base
would bring them straight home w/o encountering any enemy troops.
Unfortunately, my harvesters would casually stroll past two NOD
turrets and then take an extended detour inside a U-shaped enemy base,
finally to return home with about 1/3 of their original strength.
They wouldn't take this path getting *to* the Tiberium, only
returning. I couldn't stand micromanaging my harvesters to tell them
which way to return to base, so I just restarted the scenario and
built my base in a spot where the harvesters wouldn't have to think as
much. They still took paths that led them to meander throw the enemy
camp, so I restarted a third time, and finally the harvesters would
take decent paths. The solution was to build my base at the first
available spot, like the testers seemed to intend.
One thing I noticed about WC2's AI is that when it fails to find a
path, the units will get stuck. In C&C, however, your units will
brave any hazards to get to their destinations, even if there is a
safer, shorter, more direct path that you might reasonably expect them
to follow. C&C pathfinding appears to hug the walls a lot, and that
too often leads them into problems along the way. As a player, I
prefer to have my units get stuck than to have them sacrifice
themselves. But as a programmer, I'd like to avoid either situation
if at all possible.
-- Steve
Richard Wesson
Steve Pavlina <spav...@pacificnet.net> wrote:
[...]
-One solution is to get some of the outer peasants on one side to back
-up, then move the squatter on that side, and let the other side
-proceed. This can be difficult to implement with a large number of
-peasants (which the computer players in WC2 are prone to produce),
-since there is a great deal of coordination that must occur. I.e. you
-must identify which side of the blockage a peasant is on, and whether
-he should back up or proceed through the pass. This problem is bound
-to recur.
-
-It may also be possible to prevent this from happening. I.e. you can
-search ahead a little and see if the next few steps will create a
-blockage.
-
-Preventing the terrain from allowing this type of problem is not a
-good general solution if you wish to include a scenario editor.
-
-Any ideas for a good solution to this problem?
-
--- Steve
-
I don't know why you can't just get the peasants to move out
of the way. Keep all peasants ranked by priority. Try-to move
them in order of descending priority. A peasant who is blocked
will 'tell' an unmoved blocker to get out of the way.
If the blocker cannot move, mark him, and have him tell somebody
unmarked to get out of his way, and so on. If/when you will find
somebody who can get out of the way, then walk back up the
chain of marked peasants, moving them all as they were told to
move. If you can't find anybody who is capable of moving away
for you (either by getting somebody else to move first or just
moving directly himself) then return that you can't move. But this
way, at least one peasant always makes progress.
Worst case:
XXXXXXXXXXX
135-><-642 (numbers = priority of peasants)
XXXXXXXXXXX
That case would be inefficient, but at least not a permanent
blockage.
Keep all your units organized in a consistent way for determining
who gets priority when moving/unblocking. Randomly reassigned
priorities will result in do-si-do's in narrow corridors. I
would suggest that military units always get priority over peasants,
and gold/lumber carrying peasants get priority over unburdened
peasants. Other than that, perhaps age before beauty?
But the Warcraft programmers didn't seem to implement much pathfinding
anyhow. The ships seem especially feebleminded in this respect. Oh
well. C&C was refreshingly good that way, except for harvesters
locking horns on bridges now and then.
-- Richard Wesson
(wes...@cse.ogi.edu)
Bryan Stout
>: done at CGDC.
>
>: Did you get Bryan to upload his little pathing demo to your web page?
>
> Not yet, but I've pinged him for it twice now....
>
> Well, this makes THREE times...you out there Bryan? ;)
>
>"The One and Only"
I'm here. I'm tweaking with the program in my spare time (while trying to find
gainful work). It'll probably be a month or two before I can send it to you.
Regards,
Bryan
bst...@interramp.com
mari...@nwoasis.wa.com
>: I haven't thought of any other way as yet to get out of whatever
place
>: without potentially needing an exhaustive search to find the only
outlet
>: from a large "ocean" which spans numerous points of the globe.
>
>> Since you're dealing with a globe and a relatively huge number of
>>potential "tiles", if you will, any of the classic algorithsm are
>>going to be time-eaters. You could subdivide the problem into finding
>>causeways and straits between the oceans as "beacons". This is
how convoluted the terrain will be, and so in some setups, I'll have
anywhere from large continents and oceans to quite convoluted land
masses, possibly like a maze. So, it would be hard to determine beacons
as such for any type of game setup. What seems to be best is (I think
it is called Djykstra's algorithm) where the breadth-first search is
determined by the effort expended plus the estimated effort still to go.
The algorithm that I envision (since all I've seen are descriptions of
it) would pick a direct course straight to the target if there were no
obstacles, and if there were, it would pursue only the course that at
any one time would seem to be the best... and that algorithm seems that
it would be the best for me in either situation.
I have not seen it in action or anything, but it sounds as if it would
do what I want pretty well.
Eric Dybsand
writes:
>
>In article <4krbs4$d...@tribune.concentric.net> Swoo...@cris.com
(Steven Woodcock) writes:
>> Bryan did a great job of covering all the major pathing
>> algorithms and approaches, and had a little tool that
>> demostrated each. You could watch how (normal) Djkstra's
>> "spirals" out looking for a solution vs. A*'s "searchlight"
>> method. It was very cool and easily one of the best
>> presentations at the CGDC.
>
>What's wrong with a simple recursive algorithm to solve the
>shortest path thing? I did one up in a couple hours after
>work one day (in QBasic, no less!), and it seems to find paths
>plenty fast in any semi-open landscape.
>
There is absolutely nothing wrong with any solution to the shortest
path problem, as long as the algorithm provides a decent solution
within a decent timeframe, and all within the design constraints
of the game.
Having myself developed a recursive version of A* years ago, I'm
really curious about what you did with your "simple recursive
algorithm ... in a couple of hours". Could you elaborate on
what your algorithm actually does?
Regards,
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Sw> Figuring out if a given unit has been in one area too long is
Sw> relatively cheap, actually. Time in area = time now - time arrived.
Sw> Use a delta movement trigger to start the countdown; if a unit hasn't
Sw> moved more than some arbitrary value (presumably small), then start the
Sw> countdown. When you exceed the threshold, do something else (go the
Sw> other way, blow up the wall, whatever).
The only problem is that you'd have to either have a sufficiently large
threshold or start new counters for various positions because after you've
exceeded the treshold 1 you may still be stuck in reference to the point you
were at t'=t/4 (1/4 the counter value).
Or you'll just to wait a bit longer for the AI to figure it out. :-)
ss...@intranet.ca
Subject: Re: Avoiding Other Units
Hu> On the other hand, a true shortest path algorithm can be immensely
Hu> annoying to gameplay.
[...]
Hu> theoretically sound, a true shortest-path following unit tends to
Hu> look mathematical and stupid. That's a pitfall the game designer
Good point. Humans don't do that. Humans make a list of way-points based on
lines (don't have to be straight. e.g. go around this cylindrical tower
staying close to the edge) in their head and follow them.
Talking about our own species in the third-person is a bit odd. It's like I'm
saying I'm not human... and please, no jokes. :)
Hu> must take into consideration when picking an algorithm. In other
Hu> words, I would expect my unit to take the same general direction I
Hu> told it to go, avoiding some obstacles (especially unpassable ones)
Hu> along the way, but suffer some speed loss if I, their commander,
Hu> happened to have ordered them to wade through a swamp.
The problem is with big obstacles like mountain ranges. Sometimes it's easier
to go around instead of climbing up there. Humans would.
How about this.. if an AI comes up against a big obstacle and it can't find a
path around within a certain distance (by precalculating both left and right)
it can scream at the player and ask if it can can change course.
Ofc, this is a problem for computer units because complaining to their
controlling software is impossible (kinda).
Hu> This has to do with human perception, I think. When I click my mouse
Hu> to tell my unit to "go here", I'm giving it a point, implicitly
Hu> forming a ray with its present location. If your frame of mind treats
This sounds like the bending-line, waypoint SPA would work here.
ss...@intranet.ca
Subject: Re: Avoiding Other Units
Kk> Personally, I think that units should take the shortest possible
Kk> route, while giving a wide berth to hostile units. This would prevent
That's easy. Running an influence map algorithm over the map and then use
that information to weight terrain values in your SPA.
Steven Woodcock
: What's wrong with a simple recursive algorithm to solve the shortest path thing? I did one
: up in a couple hours after work one day (in QBasic, no less!), and it seems to find paths
: plenty fast in any semi-open landscape.
: I can only assume that A* uses some other method, or it wouldn't get stuck. Is it really
: all that good?
Nothing's wrong with a simple recursive approach, and in fact that
was suggested at one point in this thread (a long, long time ago).
The problem with recursion is pretty much what you yourself pointed
out...it's pretty good in relatively open terrain but bogs down in
more cluttered surroundings. Plus, there are some straightforward
system issues to deal with--how deep can you recurse on a given piece
of hardware with a particular compiler? There's only so much register
and stack space....
A* is good for its relative robustness and its ability to find a
pretty darn good solution, if not the absolute best.
Steven Woodcock
"The One and Only"
+=============================================================================+
Steven Woodcock
: Well, another concern is that the set up of any one game will determine
: anywhere from large continents and oceans to quite convoluted land
: masses, possibly like a maze. So, it would be hard to determine beacons
: as such for any type of game setup. What seems to be best is (I think
: it is called Djykstra's algorithm) where the breadth-first search is
: determined by the effort expended plus the estimated effort still to go.
Agreed. Djikstra's is *guaranteed* to find you the best path, but
it can take longer due to its breadth-first approach. Sometimes it's
faster *if* a comparable alternative algorithm stands a good chance of
thrashing around in a cul-de-sac.
: I have not seen it in action or anything, but it sounds as if it would
: do what I want pretty well.
You can find sample A* code on my web page (address below), kindly
donated by Tim Hardy. It looks pretty good and his timing numbers
are solid.
Tony Schroeder
In Article<4lfi7h$6...@reuter.cse.ogi.edu>, <wes...@church.cse.ogi.edu> writes:
> Path: nmb-news!psinntp!psinntp!psinntp!howland.reston.ans.net!vixen.cso.uiuc.edu!uwm.edu!reuter.cse.ogi.edu!church!wesson
> From: wes...@church.cse.ogi.edu (Richard Wesson)
> Newsgroups: comp.ai.games
> Subject: Re: Avoiding Other Units While Pathfinding
> Date: 22 Apr 1996 09:06:57 GMT
> Organization: Oregon Graduate Institute (OGI), Portland, Oregon
> Lines: 62
> Message-ID: <4lfi7h$6...@reuter.cse.ogi.edu>
> References: <4jn4f2$f...@mirv.unsw.edu.au> <4l3ptm$5...@news2.cais.com> <3179a326....@news.accessnv.com> <4le4ee$q...@news2.cais.com>
> NNTP-Posting-Host: cse.ogi.edu
several aspects I would see it the other way because the workers give you the
ability to build troops. I have destroyed the computer by pulling a peon
warfare tactic. Basically I go into an area with peasants and that is all I
will kill unless I have a large group. Then I will use two or three military
units as guards to protect the troops that go for the workers. It works well,
not only they have to build new peasants, but they are losing production. But
please expand on your statement.
Cpt. Picard
Richard Wesson
Avi Pilosof <av...@cse.unsw.edu.au> wrote:
[on quadtrees for quick pathfinding]
-On e question: Once I have a quadtree, and I wanna search for a path,
-I then use something like A*, right?
-
-I mean - I COULD do a rat-maze type of thing and try all solutions, but
-it's not elegant.
-
-
-###################################################################
-
-Avi Pilosof - av...@cse.unsw.edu.au
- - http://www.cse.unsw.edu.au/~avip/
-
Yeah, it wouldn't be too hard to flatten out the quadtree, and
make a graph out of it, and it probably would be worthwhile,
just so you don't have to chase up and down levels in the quadtree
continuously while looking at paths.
Your right neighbor(s) is/are:
your right sibling, if clear
or, the leftmost leaves of your right sibling, if clear
Or if you have no right sibling with a common parent, then your
right neighbor(s) is your parent's right neighbor(s) such that share
any edge with you. I.e. any clear ones closer the root (bigger),
and any smaller ones sharing your vertical right edge.
etc etc. Sort of a pain in the butt, but doable.
A path from any square in the quadtree to any other is a path
from one square's center to another. You can make your graph thus.
Once you have a graph, then you can easily use a standard graph
traversal algorithm. If you have rather large squares that will be
a somewhat jagged path (as mentioned), but oh well.
(You can fix the path up somewhat by heading towards your next
destination immediately once you enter some rectangle, as long as you
keep within your current rectangle in the meantime.)
A slightly more efficient variation of the quadtree (in terms of
number of leaves) would be to start anywhere. Expand a rectangle
by adding rows and columns until you can't maintain purity-of-
essence (would be no longer unmixed clear or unmixed blocked).
For all the spots on its edge, do the same thing until they are
in some rectangle. For each of those rectangles, grow rectangles
for all the un-taken spots on _their_ edges. and so on.
For better traversals, you might stop the rectangle growth before it
got too disproportionate (i.e. too skinny in some direction.)
-- Rich Wesson
(wes...@cse.ogi.edu)
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
[Units can be at ...]
Ma> Yes, by points I mean all the points of the geodesic globe, where the
Ma> triangles meet. But it is also much more complex than that... See,
[...]
Ma> another course is necessary... therefore, effectively, every edge of the
Ma> globe can be land or water, as well as every point (although any one
Ma> point can be land only if all connected edges are land) Get confusing
Ok. I understand.
[precalc'd shortest path + objections from C&C thread]
Ma> True... I just hadn't thought of anything better... and I wanted to
How many vertices are there in your dome? If there aren't a lot
then you can do A* or dual-direction breadth-first or something similar.
Otherwise, you'll have to cheat a little. Presumably, the land
masses aren't truly painful along the coast. What you could do
is rubber-tape them to begin with and just avoid crossing land
masses' tape lines.
To rubber tape a continent, it's best to start with a point
furthermost from the centroid of its edges, but there's a faster
way. Theoretically you can guesstimate the centroid's general
location. Scan a bit of the coast and look for a point where
you've been going farther away from the centroid until you pass
the point, at which time you are getting closer to the centroid.
Start from that point.
From that point, continue to scan around the coast doing the same
thing. Draw lines from point to point. Eventually you'll come
up with a polygon around the continent that should be convex
enough to deal with. If you want perfection, check for concavity
at each edge. If it's concave at some point, delete the two
lines going to that vertex and replace it with one solid line
between the vertex's neighbour.
Now, in some other version of the map, polygon fill the
rubber-taped areas with a non-passable terrain type. Store this
map somewhere. I don't think this is a particularly lengthy
algorithm, but you might want to precalculate this and store it
off as a file of somesort. It should be supercompressable too.
Unless you have to go somewhere within a rubber-taped area, just
avoid those polygons altogether, thereby keeping you from getting
stuck in bays.
Now, for your map, because each continent is an island now, you
can just use the way-point SPA technique. To do that, draw a
line to the destination from the starting point. When it
collides with a rubber-taped polygon (or any other object), scan
left and scan right along the edge of that object until the line
no longer collides with something on its next iteration. Mark
both those points. Keep doing this for each polygon,
recursively, from the left and right branches, adding up the
distances as you go along. Take the shortest set of waypoints.
[Hands up; how many realized I made all that up just now? :)]
BTW, to guesstimate the centroid of a polygon, just draw a quick horizontal
line across it and take the centre of that line. This should work in most
cases. Or find a few points and average those.
Ma> By the way... are there any available copies of this algorithm?
A* can now be found from Steve Woodcock's pages:
http://www.cris.com/~swoodcoc/ai.html
I also recommend you read this page:
http://www.lis.pitt.edu/~john/shorpath.htm
ss...@intranet.ca
Subject: Re: Avoiding Obstacles to
Jk> What's wrong with a simple recursive algorithm to solve the shortest
Jk> path thing? I did one up in a couple hours after work one day (in
That could crunch some serious stack space with a big enough map.
ss...@intranet.ca
Subject: Re: Avoiding Other Units
Sp> take the field. But what do you do when the squatter is trapped as
Sp> well. An example from Warcraft 2: If you have peasants mining an
Sp> area with only one way in or out, through a narrow pass that is only 1
Sp> unit's width, the peasants will often get stuck. In fact, on a
[...]
Sp> Any ideas for a good solution to this problem?
Enter emergent behaviour.
Imagine this situation, where each letter is a unit:
\ABC/
|D|
/EFG\
F wants to go up, but D is blocked. However, if F puts a message on the
global message queue telling D to move out of the way, D will select a
direction (say in the direction of A). Now D is blocked by A. D puts a
message on the global message queue for A to move, and it will. Then D moves,
so F can move. And all this gets repeated for B.
Problems: A may choose to move behind B. You may also want to communicate
directions not to move to in the message. In this case, you'd tell A not to
go to B or behind B or you'd restrict D to moving beside F.
Eric Dybsand
>
>To: Kk...@gulf.uvic.ca
>Subject: Re: Avoiding Other Units
>
> Kk> route, while giving a wide berth to hostile units. This would >
>
>That's easy. Running an influence map algorithm over the map and
>then use that information to weight terrain values in your SPA.
Nice idea Sunir, if this is occuring in a turn-based game with a
low unit density.
However if it is in a real-time game, with a dynamically changing
map (buildings being built or blown up, bridges being constructed
or destroyed and units in motion) with a high unit density (100+
units) on a large map (1024x1024) then how could most home systems
(where games are played) be able to provide enough power to run an
influence map algorighm over the map for each path finding request?
Steven Woodcock
: Otherwise, you'll have to cheat a little. Presumably, the land
: masses aren't truly painful along the coast. What you could do
: is rubber-tape them to begin with and just avoid crossing land
: masses' tape lines.
:
: <Sunir's rubber tape algorithm deleted>
:
Well, you *did* disclaim it before you dumped it all out, but
my goodness that seems like a roundabout way to figure out the
lines enclosing an irregular polygon (i.e., a continent). For gosh
sakes man--a simple bounding box is *much* simpler, isn't it?
;)
: [Hands up; how many realized I made all that up just now? :)]
__
:) (Steve with his hand over his head)
: BTW, to guesstimate the centroid of a polygon, just draw a quick horizontal
: line across it and take the centre of that line. This should work in most
: cases. Or find a few points and average those.
Much, much, much, much, much, much, much better. If she has any
*hope* of doing a realtime game, this is the way to go. It's far simpler
to refine this case than to simplify the other.
: A* can now be found from Steve Woodcock's pages:
: http://www.cris.com/~swoodcoc/ai.html
Thanks much. Just a note that Tim Hardy provided the original source
posting; there will shortly be a Java implementation as well.
Steven Woodcock
: To: Swoo...@cris.com
: Sw> Figuring out if a given unit has been in one area too long is
: Sw> relatively cheap, actually. Time in area = time now - time arrived.
: Sw> Use a delta movement trigger to start the countdown; if a unit hasn't
: Sw> moved more than some arbitrary value (presumably small), then start the
: Sw> countdown. When you exceed the threshold, do something else (go the
: Sw> other way, blow up the wall, whatever).
: The only problem is that you'd have to either have a sufficiently large
: threshold or start new counters for various positions because after you've
: exceeded the treshold 1 you may still be stuck in reference to the point you
: were at t'=t/4 (1/4 the counter value).
Well, maybe, but normally this type of situation is (or should be)
relatively rare. Hence, when it does happen you can probably take a little
bit more time to figure it out. Plus, I would presume that you'd do
some tuning of the game ahead of time.
I would make the threshold some obvious multiple of the terrain cost
and the movement capability of the unit in question. This would
somewhat "tailor" the threshold such that a unit with a low movement
capability (i.e., an infantry) could hang around for a bit before
figuring out he's stuck while a tank might figure it out faster. That
would make sense, look realistic, and "feel" right.
Steven Woodcock
: That's easy. Running an influence map algorithm over the map and then use
: that information to weight terrain values in your SPA.
Or set up the enemy units as repulsors, your waypoints as attractors,
and use those values to "draw" or "push" your units along. That's what
they do in Aces of the Deep II for the wolfpacks, and it works pretty
well.
Steve
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Real3D <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: wood...@escmail.orl.mmc.com (Work), swoo...@cris.com (Home) |
| Web: http://www.cris.com/~swoodcoc/wyrdhaven.html (Top level page) |
| http://www.cris.com/~swoodcoc/ai.html (Game AI page) |
| http://www.cris.com/~swoodcoc/software.html (AI Software page) |
Andrew D. Myers
Swoo...@cris.com (Steven Woodcock) wrote:
>ss...@intranet.ca opined thusly:
>: That's easy. Running an influence map algorithm over the map and then use
>: that information to weight terrain values in your SPA.
> Or set up the enemy units as repulsors, your waypoints as attractors,
>and use those values to "draw" or "push" your units along. That's what
>they do in Aces of the Deep II for the wolfpacks, and it works pretty
>well.
[lurk mode off]
Whups, my acronym-tracking module seems to have gone kaput. What's
SPA stand for in this context again? I forgot.
(btw, I _really_ enjoy reading this group, and may actually take a
more active role if I ever get around to trying my hand at coding some
strategy AI; I've almost started a couple times, but other
distractions keep cropping up, like Civ2 most recently :)
[lurk mode on]
---
Andrew D. Myers : (k) All Rites Reversed
andrew...@pobox.com : Reprint what you like!
Steven Woodcock
Andrew D. Myers (andrew...@pobox.com) opined thusly:
: Swoo...@cris.com (Steven Woodcock) wrote:
: >ss...@intranet.ca opined thusly:
: >: That's easy. Running an influence map algorithm over the map and then use
: >: that information to weight terrain values in your SPA.
: > Or set up the enemy units as repulsors, your waypoints as attractors,
: >and use those values to "draw" or "push" your units along. That's what
: >they do in Aces of the Deep II for the wolfpacks, and it works pretty
: >well.
: [lurk mode off]
: Whups, my acronym-tracking module seems to have gone kaput. What's
: SPA stand for in this context again? I forgot.
SPA = Shortest Path Algorithm
Sunir likes to speak in acronym. He's gonna do great if he
ever joins the Army or Air Force....
: (btw, I _really_ enjoy reading this group, and may actually take a
: more active role if I ever get around to trying my hand at coding some
: strategy AI; I've almost started a couple times, but other
: distractions keep cropping up, like Civ2 most recently :)
We'd love to have your input Andrew. We're a mix of folks here.
Some of us (such as Eric and myself) are developers-for-a-living,
others (such as Sunir) run net game AI contests, others dabble.
Steven Woodcock
Eric Dybsand
In <4lppvd$r...@news.cs.hope.edu> andrew...@pobox.com (Andrew D.
Myers) asks:
>
>[lurk mode off]
>
>Whups, my acronym-tracking module seems to have gone kaput. What's
>SPA stand for in this context again? I forgot.
>
SPA = Shortest Path Algorithm
Eric Dybsand