The conversation here is from comp.ai.games. You can read it on Google Groups.
|
Avoiding Obstacles to reach a destination | Index |
| From: | Tim Thomas |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 9 Apr 1996 21:26:29 GMT |
| Organization: | Motorola Computer Group, Urbana Design Center |
-Newsreader: NN version 6.5.0 #22 (NOV)
In <4k9k6v$a79@scratchy.mi.net> dmills@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
thomas@urbana.mcd.mot.com
| From: | Bjorn Reese |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Wed, 10 Apr 1996 11:07:25 GMT |
| Organization: | Dept. of Math. & Computer Science, Odense University, Denmark |
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.
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.
--
Bjorn Reese Email: breese@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
| From: | Jasper Phillips |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 11 Apr 1996 22:25:13 GMT |
| Organization: | Oregon State University, College of Engineering |
In article <2>,
Bjorn Reese <breese@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: breese@imada.ou.dk
-Jasper
--
/\ Jasper Phillips (Pit Fiend) ______,....----,
/VVVVVVVVVVVVVV|==================="""""""""""" ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""
\/ http://www.cs.orst.edu/~philljas/
| From: | Bjorn Reese |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Sat, 13 Apr 1996 12:56:37 GMT |
| Organization: | Dept. of Math. & Computer Science, Odense University, Denmark |
Jasper Phillips wrote:
> 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: breese@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
| From: | Sunir Shah |
| Subject: | Beacons (was: Avoiding Obstacles to reach a destination) |
| Date: | 14 Apr 1996 21:37:56 GMT |
| Organization: | Bell Global Solutions |
Subject: Beacons (was: Avoiding Obstacles to reach a destination)
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.
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 14 Apr 1996 05:40:20 GMT |
| Organization: | Bell Global Solutions |
To: Philljas@tx.engr.orst.edu
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. :)
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Darren Reid |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Mon, 15 Apr 1996 17:38:23 -0300 |
| Organization: | NBCC Miramichi |
sshah@intranet.ca wrote:
> 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
| From: | Robert A. Uhl |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 10 Apr 1996 15:14:44 GMT |
| Organization: | The Edgar Allan Poe Colouring Book Co. |
Steve Hodsdon <103365.656@compuserve.com> spake thusly:
>
>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 | evangelist@macway.com for information about the
Bolo Player (Spectre) | EvangeList, Guy Kawasaki's list for Mac advocates.
| From: | Steven Woodcock |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 11 Apr 1996 17:50:09 GMT |
| Organization: | Wyrdhaven Wyrks |
Robert A. Uhl (ruhl@odin.cair.du.edu) opined thusly:
: 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"
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: woodcock@escmail.orl.mmc.com (Work), swoodcoc@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 |
+=============================================================================+
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 11 Apr 1996 04:41:20 GMT |
| Organization: | Bell Global Solutions |
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?
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 (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Szu-Wen Huang |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 12 Apr 1996 14:38:07 GMT |
| Organization: | Monumental Network Systems |
sshah@intranet.ca wrote:
: 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?
:)
| From: | Dean Mills |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 13 Apr 1996 13:26:20 GMT |
| Organization: | MiNet |
:>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.
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
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 14 Apr 1996 05:40:43 GMT |
| Organization: | Bell Global Solutions |
To: Huang@mnsinc.com
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>).
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Szu-Wen Huang |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 15 Apr 1996 12:59:27 GMT |
| Organization: | Monumental Network Systems |
sshah@intranet.ca wrote:
: 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 :).
| From: | Bjorn Reese |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Sat, 13 Apr 1996 13:07:46 GMT |
| Organization: | Dept. of Math. & Computer Science, Odense University, Denmark |
sshah@intranet.ca wrote:
> 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.
--
Bjorn Reese Email: breese@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
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 14 Apr 1996 21:37:50 GMT |
| Organization: | Bell Global Solutions |
To: Breese@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?
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Bjorn Reese |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Mon, 15 Apr 1996 16:53:19 GMT |
| Organization: | Dept. of Math. & Computer Science, Odense University, Denmark |
sshah@intranet.ca wrote:
>
> > 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
--
Bjorn Reese Email: breese@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
| From: | Steven Woodcock |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 19 Apr 1996 04:20:31 GMT |
| Organization: | Wyrdhaven Wyrks |
sshah@intranet.ca opined thusly:
: To: Breese@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: woodcock@escmail.orl.mmc.com (Work), swoodcoc@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 |
+=============================================================================+
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 22 Apr 1996 03:29:19 GMT |
| Organization: | Bell Global Solutions |
To: Swoodcoc@cris.com
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. :-)
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Jasper Phillips |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 17 Apr 1996 22:24:05 GMT |
| Organization: | Oregon State University, College of Engineering |
In article <9>, <sshah@intranet.ca> wrote:
>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.
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 (sshah@intranet.ca) http://intranet.ca/~sshah/
-Jasper
--
/\ Jasper Phillips (Pit Fiend) ______,....----,
/VVVVVVVVVVVVVV|==================="""""""""""" ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""
\/ http://www.cs.orst.edu/~philljas/
| From: | Sunir Shah |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 20 Apr 1996 19:14:35 GMT |
| Organization: | Bell Global Solutions |
To: Philljas@tx.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> 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 (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Simon Slavin |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Fri, 12 Apr 1996 23:52:36 +0100 |
| Organization: | International Cocaine Importers, Ltd. |
In article <4k9k6v$a79@scratchy.mi.net>,
dmills@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.
--
slavins@hearsay.demon.co.uk -- the poster | "Sometimes a .sig is just
formerly known as slavins@entergrp.demon.co.uk. | a .sig." -- Sigmund Freud.
| From: | Darren Reid |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Sat, 13 Apr 1996 22:17:31 -0300 |
| Organization: | NBCC Miramichi |
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 ;)
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
| From: | Steven Woodcock |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 14 Apr 1996 17:15:48 GMT |
| Organization: | Wyrdhaven Wyrks |
Darren Reid (shokwave@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.
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....
Steven Woodcock
"The One and Only"
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Systems Group <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: woodcock@escmail.orl.mmc.com (Work), swoodcoc@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 |
+=============================================================================+
| From: | Eric Dybsand |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 15 Apr 1996 02:23:43 GMT |
| Organization: | Netcom |
In <23> Swoodcoc@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.
>
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
| From: | Bryan Stout |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 16 Apr 1996 17:28:11 GMT |
| Organization: | PSI Public Usenet Link |
In article <24>, edybs@ix.netcom.co says...
>>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?
>
>Eric Dybsand
>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
bstout@interramp.com
| From: | Tim Hardy |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Tue, 16 Apr 96 21:23:12 GMT |
| Organization: | Nortel |
>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
>bstout@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
| From: | Eric Dybsand |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 17 Apr 1996 14:44:46 GMT |
| Organization: | Netcom |
In <26> tim_hardy@nt.com (Tim Hardy)
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,
Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA
| From: | Steven Woodcock |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 19 Apr 1996 04:35:13 GMT |
| Organization: | Wyrdhaven Wyrks |
Eric Dybsand (edybs@ix.netcom.com) opined thusly:
: 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! ;)
Steven Woodcock
"The One and Only"
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Real3D <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: woodcock@escmail.orl.mmc.com (Work), swoodcoc@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 |
+=============================================================================+
| From: | Tim Hardy |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | Fri, 19 Apr 96 23:02:46 GMT |
| Organization: | Nortel |
> 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!
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
| From: | Amit Patel |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 19 Apr 1996 22:49:39 GMT |
| Organization: | Computer Science Department, Stanford University. |
In article <26>,
Tim Hardy <tim_hardy@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.
>
>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
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
| From: | Richard Wesson |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 19 Apr 1996 21:13:00 GMT |
| Organization: | Oregon Graduate Institute (OGI), Portland, Oregon |
If you're using a good search technique and it's taking 1-5 seconds
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
| From: | Steve Pavlina |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Tue, 16 Apr 1996 22:04:04 GMT |
| Organization: | Capital Area Internet Service, Inc. |
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. 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
| From: | Richard Gemmell |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Thu, 18 Apr 1996 12:55:48 -0700 |
| Organization: | Parallax Solutions Ltd, UK |
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 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
| From: | Tim Hardy |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Thu, 18 Apr 96 15:47:59 GMT |
| Organization: | Nortel |
In article <49>,
spavlina@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 remains static. A* works fine if you know in advance what
>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
| From: | Szu-Wen Huang |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 18 Apr 1996 19:28:20 GMT |
| Organization: | Monumental Network Systems |
Tim Hardy (tim_hardy@nt.com) wrote:
: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?
| From: | Kevin Kent |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Fri, 19 Apr 1996 00:04:43 GMT |
| Organization: | Student, CSc/B, University of Victoria |
> 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 (kkent@csc.uvic.ca)
Student, CSc/B, University of Victoria, Canada
| From: | Sunir Shah |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 22 Apr 1996 03:29:14 GMT |
| Organization: | Bell Global Solutions |
To: Kkent@gulf.uvic.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.
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Sunir Shah |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 22 Apr 1996 03:29:08 GMT |
| Organization: | Bell Global Solutions |
To: Huang@mnsinc.com
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.
--
Sunir Shah (sshah@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 . . .
___ Blue Wave/QWK v2.12
>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED
| From: | Darren Reid |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Fri, 19 Apr 1996 00:12:26 -0300 |
| Organization: | NBCC Miramichi |
Steve Pavlina wrote:
>
> 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
| From: | Amit Patel |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 19 Apr 1996 22:56:51 GMT |
| Organization: | Computer Science Department, Stanford University. |
In article <56>,
Darren Reid <shokwave@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
| From: | Steven Woodcock |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 20 Apr 1996 05:31:13 GMT |
| Organization: | Wyrdhaven Wyrks |
Amit Patel (amitp@Xenon.Stanford.EDU) opined thusly:
: In article <56>,
: Darren Reid <shokwave@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.
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.
Steven Woodcock
"The One and Only"
+=============================================================================+
| _ |
| Steven Woodcock _____C .._. |
| Senior Software Engineer, Gameware ____/ \___/ |
| Lockheed Martin Information Real3D <____/\_---\_\ "Ferretman" |
| Phone: 719-597-5413 |
| E-mail: woodcock@escmail.orl.mmc.com (Work), swoodcoc@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 |
+=============================================================================+
| From: | Amit Patel |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 19 Apr 1996 22:53:45 GMT |
| Organization: | Computer Science Department, Stanford University. |
In article <49>,
Steve Pavlina <spavlina@pacificnet.net> 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 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
| From: | Joe Bostic |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Sun, 21 Apr 1996 02:59:25 GMT |
| Organization: | Westwood Studios |
spavlina@pacificnet.net (Steve Pavlina) wrote:
<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?
>-- Steve
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.
| From: | Steve Pavlina |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Sat, 20 Apr 1996 20:04:58 GMT |
| Organization: | Capital Area Internet Service, Inc. |
joebwan@anv.net (Joe Bostic) wrote:
>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
| From: | Steve Atkins |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Sun, 21 Apr 1996 20:44:09 GMT |
| Organization: | Advanced Micro Devices, Austin, TX, USA |
>>>>> "Steve" == Steve Pavlina <spavlina@pacificnet.net> writes:
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.'
| From: | Richard Wesson |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | 22 Apr 1996 09:06:57 GMT |
| Organization: | Oregon Graduate Institute (OGI), Portland, Oregon |
[on getting peasant blockages resolved]
In article <61>,
Steve Pavlina <spavlina@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
(wesson@cse.ogi.edu)
| From: | Steve Pavlina |
| Subject: | Avoiding Other Units While Pathfinding |
| Date: | Sun, 21 Apr 1996 19:02:12 GMT |
| Organization: | Capital Area Internet Service, Inc. |
wesson@church.cse.ogi.edu (Richard Wesson) wrote:
>[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
| From: | Bryan Stout |
| Subject: | Avoiding Obstacles to reach a destination |
| Date: | 16 Apr 1996 17:24:27 GMT |
| Organization: | PSI Public Usenet Link |
In article <23>, Swoodcoc@cris.com says...
>
>Darren Reid (shokwave@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.
>
>
> That's Bryan Stout's presentation; he lurks around here too sometimes.
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