Pathfinding Archive

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

• Tim Thomas
• Bjorn Reese
  • Jasper Phillips
    • Bjorn Reese

      • Sunir Shah

        Beacons (was: Avoiding Obstacles to reach a destination)

    • Sunir Shah
      • Darren Reid
• Robert A. Uhl
  • Steven Woodcock
• Sunir Shah
  • Szu-Wen Huang
    • Dean Mills
    • Sunir Shah
      • Szu-Wen Huang
  • Bjorn Reese
    • Sunir Shah
      • Bjorn Reese
      • Steven Woodcock
        • Sunir Shah
  • Jasper Phillips
    • Sunir Shah
• Simon Slavin
  • Darren Reid
    • Steven Woodcock
      • Eric Dybsand
        • Bryan Stout
          • Tim Hardy
            • Eric Dybsand
              • Steven Woodcock
                • Tim Hardy
            • Amit Patel
            • Richard Wesson

          • Steve Pavlina

            Avoiding Other Units While Pathfinding

            • Richard Gemmell
            • Tim Hardy
              • Szu-Wen Huang
                • Kevin Kent
                  • Sunir Shah
                • Sunir Shah
            • Darren Reid
              • Amit Patel
                • Steven Woodcock
            • Amit Patel
            • Joe Bostic
              • Steve Pavlina
                • Steve Atkins
                • Richard Wesson
                  • Steve Pavlina
      • Bryan Stout
    • Eric Dybsand
    • Jasper Phillips
      • Ralph Scott
      • Darren Reid
• Richard Wesson
  • Avi Pilosof
    • Richard Wesson

• Peter Schaefer

  Avoiding Obstacles to reach a destinationRe: Avoiding Obstacles to

  • Jasper Phillips

• Andrew Searls

  Avoiding Obstacles to reach a destination

• Andrew R. Southwick

  Command and Conquer AI

  • Sunir Shah
  • Joe Bostic
    • Steven Woodcock
      • Joe Bostic
      • Sunir Shah
    • Andrew R. Southwick

• Jason Kester

  Avoiding Obstacles to reach a destination

  • Steven Woodcock
  • Eric Dybsand
• Steven Woodcock
• Sunir Shah

• Richard Wesson

  Command and Conquer AI

  • Sunir Shah
    • Richard Wesson

• Tony Schroeder

  Avoiding Other Units While Pathfinding

  • Brian
  • Sunir Shah

    • Richard Wesson

      Ideal pathfinding

      • Sunir Shah

• Simon Slavin

  Sparse array for storage of shortest-path routes ?

• Bryan Stout

  Maneuver based shortest path

• david

  Avoiding Other Units While Pathfinding

  • Eric Dybsand
    • Sunir Shah
      • Eric Dybsand
        • John Christian Lonningdal
        • Steve 'GryMor' Metke
          • Eric Dybsand
            • Sunir Shah
              • Steven Woodcock
        • Sunir Shah
  • Sunir Shah
• John Christian Lonningdal
  • Eric Dybsand

-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

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

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/

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

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

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

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

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.

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                   |
+=============================================================================+

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

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?
:)

:>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

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

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 :).

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

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

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

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                          |
+=============================================================================+

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

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/

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

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.

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

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                   |
+=============================================================================+

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

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

>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

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

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                          |
+=============================================================================+

>   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

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

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

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

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

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

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?

> 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

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

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

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

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

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                          |
+=============================================================================+

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

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.

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

>>>>> "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.'

[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)

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

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 
>: 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
bstout@interramp.com

In <22> Darren Reid <shokwave@nbnet.nb.ca>
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 
>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
>
>

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.

Regards,

Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA

In article <22>,
Darren Reid  <shokwave@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

-Jasper
-- 
              /\  Jasper Phillips (Pit Fiend)  ______,....----,
/VVVVVVVVVVVVVV|===================""""""""""""       ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""        
              \/  http://www.cs.orst.edu/~philljas/

In article <34>,
Jasper Phillips <philljas@tx.ENGR.ORST.EDU> wrote:
>In article <22>,
>Darren Reid  <shokwave@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

Jasper Phillips wrote:

> >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.

In article <4jn4f2$f45@mirv.unsw.edu.au>,
Avi Pilosof <avip@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.
>
>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'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      -       avip@cse.unsw.edu.au
>		 -	 http://www.cse.unsw.edu.au/~avip/

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
(wesson@cse.ogi.edu)

Richard Wesson (wesson@church.cse.ogi.edu) wrote:

: 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      -       avip@cse.unsw.edu.au
		 -	 http://www.cse.unsw.edu.au/~avip/

> Bigamy is having one wife too many. Monogamy is the same thing. -- Anon

In article <38>,
Avi Pilosof <avip@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      -       avip@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
(wesson@cse.ogi.edu)

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. 
<sigh>
All those ingenious Algorithms waiting to be written by you & me !
-- 
Peter Schaefer

"office":
schaefer@malaga.math.uni-augsburg.de
http://wwwhoppe.math.uni-augsburg.de/schaefer

"leisure":
schaefer@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

In article <39>,
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

-- 
              /\  Jasper Phillips (Pit Fiend)  ______,....----,
/VVVVVVVVVVVVVV|===================""""""""""""       ___,..-'
`^^^^^^^^^^^^^^|======================----------""""""        
              \/  http://www.cs.orst.edu/~philljas/

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
> [snip]

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"

Caskey Dickson <caskey@CitySearch.com> writes:
>Steven Woodcock wrote:
>> Glenn Corpes (glennc@cix.compulink.co.uk) opined thusly:
>> : I think it shows that the shortest path algorithm is pre-calculated for
>> : each map, which is a very sensible thing to do until the player modifies
>> : it. This is not a simple problem to fix.

>>    Lessee, to store the cheapest routes from every point to every other
>> point on a 100x100 square grid map, with, say 10 waypoints per "path", would
>> be a lot of memory.....

>>            100 x 100 x 10 x 4 = 400,000 bytes

Actually it is
  100x100 source squares x 100x100 dest squares x 10 waypoints x 4 bytes
   == 4000000000 (4GB).

400k is spare change, if it makes your AI a lot smarter.  But 4GB is far
too much memory.  Only Avid users have that much.  By why waste that
much memory?  Store paths for each 4x4 or 8x8 square area.  Warcraft II has
some 128x128 maps.  So, approximately 512 source locations:
  512 source x 512 dist x 2 bytes for closest marker == 512k.

Still a huge amount.  This is easy enough to test out (assuming you're
using an OS that easily supports such sizes).

But, waypoints are only useful if your map is convoluted enough to demand
complex waypointing.  Roads, rough terrain, and other features that make
some squares more difficult to cross than others complicates it.  If you
are NOT using such features, the only this you have to worry about is
large bodies of water, stands of trees, mountain ranges, and the like.
These features, however, are large enough (relative to the total size of
the map) that you should only need 60 or so waypoints.  And, you can store
links my merely indicating the next waypoint a unit should progress to.
For example, to get from A to B:
   .........**.........
   .....C...**.........
   .A...*...**.........
   .....*..............
   .....*....***.......
   ....**....*...***...
   ..***.....*..**...B.
   ..........*.........

First work your way to C.  Then your problem is: how to get from
C to B.

>I believe what we are witnessing is the fact that the game stores a
>`desired' route from it's home base to `your' base.  It attempts to
>maintain the state that existed at the beginning of the game and
>follows a strategy script so long as it is at it's `desired state'.
>There would be, perhaps, 5 routes along which it sends different
>groupings of troops and merely repeats this until you quit.

More strategic wargames, if they are precalculating, store slightly
different information about the map, like good defensive or offensive
positions.  Then they just try to move from strong-point to strong-point.

>The problem with the sandbag trap is an artifact of their maze
>algorithm.

I am assuming that they store some previous state, which Warcraft appears
to do as well.  i.e. What squares have I already visited?  If a unit
tries to cross a river (where there isn't a bridge: this is Warcraft I),
it walks straight to the river, and then holds out its right hand and
tries to find its way around the obstacle.  Units don't back up
because (I am guessing) they know they have tried the shortest distance
>from the area behind them, and hence won't re-enter those squares.  OF
course, keeping an entire game map full of bits for each unit isn't
cost effective, so the units probably only store the last 10 or so squares.
Units in C&C might sense that the last ten squares leave an opening at the
far end they haven't checked yet.

More likely, I think, they hold out their left hand until they think they
are heading too far in the wrong direction.  When blocked, set counter
to 20.  For each step around obstacle, decrease counter by 1.  While this
counter is > 0, moving away from the target is ok.

Also note: flood fill search algorithms are fast on PowerMacs and Pentiums.
Flood, trim, waypoint-ize the resulting map, store, and march.  Or, flood-
fill the entire map every once in a while, and update the waypoint map from
that.


Andrew R Southwick          -={C++/OO Programmer}=-     asouthwick@vnet.ibm.com
#include <stddisclaimer.h>                                 I speak not for IBM.
            -= Freedom by permission is a contradiction in terms =-

To: Asouthwick@vnet.ibm.com
Subject: Re: Command and Conquer A

 >>            100 x 100 x 10 x 4 = 400,000 bytes
 As> Actually it is
 As> 100x100 source squares x 100x100 dest squares x 10 waypoints x 4
 As> bytes == 4000000000 (4GB).

Beat ya too it. :-)

 As> locations: 512 source x 512 dist x 2 bytes for closest marker ==
 As> 512k.

I proposed a solution that was something like (n)(n-1) bytes a while back.
I forget exactly.  Oh, I found it.  It basically works on the theory that if
you you want the shortest path from A to C that goes through B, that would be
the sum of the shortest paths from A to B and B to C.  And it does that
recursively for all the waypoints to C.

Yeah, that's only 255.5kb.  I'll send it to you if you want.
 
 As> But, waypoints are only useful if your map is convoluted enough to
 As> demand complex waypointing.  Roads, rough terrain, and other features

The other problem is blocking the waypoints.  Dynamic paths can be a problem.
Ofc, this has be hashed and rehashed about a hundred times in the last week.

 As> different information about the map, like good defensive or offensive
 As> positions.  Then they just try to move from strong-point to
 As> strong-point.

That's probably a much better solution.
--
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

>Steven Woodcock wrote:
>> Glenn Corpes (glennc@cix.compulink.co.uk) opined thusly:
>> : I think it shows that the shortest path algorithm is pre-calculated for
>> : each map, which is a very sensible thing to do until the player modifies
>> : it. This is not a simple problem to fix.
>
<major snip>

Pre storing paths is not a reasonable solution (on the face of it)
when dealing with a large map that changes passability characteristics
frequently (e.g., Command & Conquer and Warcraft). There are just too
many possible starting and ending destinations. RAM limits storing the
path vectors and CPU resources limit calculating the paths (most
potential path vectors won't be used). When the map changes
characteristics, the pre computed paths would have to be recalculated
to reflect that. However there are several options to address this.

The map can be broken up into regions (say 3x3 or 5x5). Then all
possible paths calculated between the center points of these regions.
A traveler would merely have to move to the center point of the region
it is currently in. Then it would use the precalculated path vector to
the closest region center point to its desired destination. This has
the same problems as before, but to a much lesser degree. It also has
an additional problem where a blockage might bisect a region.

Alternatively, the path to the destination can be calculated (using
edge following algorithm) and then the path vector remembered. The
traveler would follow the vector until it reached the destination or a
surprise blockage interfered. At that point the traveler could either
recalculate an entire full path to destination or calculate a short
path to get back onto the original precalculated path.

Yet another solution is to not calculate a path at all unless it is
necessary. The traveler would head toward its destination in a direct
path (veering up to 45 degrees to either side if there is a minor
blockage). If it cannot get closer to its desired destination using
this method would it then go into 'full blown path finding' mode.

To add even more complexity to the problem, sometimes blocked terrain
isn't immutable. What if the terrain can be destroyed by the traveler,
but at the cost of some finite amount of time. In addition, some
'terrain blockage' may actually another traveler. In such a case it
might make sense to detect if the other traveler is moving and thus
the path algorithm should pretend it isn't there on the assumption
that it would have moved out of the way by the time the traveler gets
there.

Joe B. (the programmer of C&C)

Joe Bostic (joebwan@anv.net) opined thusly:

Hello Joe!


   I'm not sure if we met at the CGDC or not, but hello anyway.

: Pre storing paths is not a reasonable solution (on the face of it)
: when dealing with a large map that changes passability characteristics
: frequently (e.g., Command & Conquer and Warcraft). There are just too
: many possible starting and ending destinations. RAM limits storing the
: path vectors and CPU resources limit calculating the paths (most
: potential path vectors won't be used). When the map changes
: characteristics, the pre computed paths would have to be recalculated
: to reflect that. However there are several options to address this.


   Agreed.  When this was suggested as a solution, we quickly came up
with various estimates for memory size (ranging from 400K to 4GB) that
this might require.  I don't think any of us liked it much.

: The map can be broken up into regions (say 3x3 or 5x5). Then all
: possible paths calculated between the center points of these regions.
: A traveler would merely have to move to the center point of the region
: it is currently in. Then it would use the precalculated path vector to
: the closest region center point to its desired destination. This has
: the same problems as before, but to a much lesser degree. It also has
: an additional problem where a blockage might bisect a region.

   Indeed.  It is probably the "winning theory" right now that this is
pretty much what you guys did in C&C.  Can you confirm?  ;)

: Alternatively, the path to the destination can be calculated (using
: edge following algorithm) and then the path vector remembered. The
: traveler would follow the vector until it reached the destination or a
: surprise blockage interfered. At that point the traveler could either
: recalculate an entire full path to destination or calculate a short
: path to get back onto the original precalculated path.

   This works but could lead to some odd looking paths.  I would imagine
that in the class "U-shaped obstacle" case a unit following this algorithm
would walk smack into the center of the U, then follow one edge around
until he got out.

: Yet another solution is to not calculate a path at all unless it is
: necessary. The traveler would head toward its destination in a direct
: path (veering up to 45 degrees to either side if there is a minor
: blockage). If it cannot get closer to its desired destination using
: this method would it then go into 'full blown path finding' mode.


   This is the approach I'm using in my game.  I try not to even compute
a path if it's not needed, if the unit is moving only a relatively short
distance, etc.  I don't like to crank up the full pather unless I
have to.

: To add even more complexity to the problem, sometimes blocked terrain
: isn't immutable. What if the terrain can be destroyed by the traveler,
: but at the cost of some finite amount of time. In addition, some
: 'terrain blockage' may actually another traveler. In such a case it
: might make sense to detect if the other traveler is moving and thus
: the path algorithm should pretend it isn't there on the assumption
: that it would have moved out of the way by the time the traveler gets
: there.


   Indeed, which is yet another reason not to plan *too* far ahead in
such games.  Taking the path in small steps a.) is faster b.) helps to
account for changes in terrain and c.) is perhaps more intuitively
correct.

   Since you brought it up, though, it's been noted that the C&C AI
isn't smart enough to blow away sandbag obstacles.  Obviously you
gave it some thought, as your above post indicates.  Were you just
unable to implement that logic branch before the Doom of the Shipping
Date loomed?  (I can understand that, believe me!)

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                          |
+=============================================================================+

Swoodcoc@cris.com (Steven Woodcock) wrote:
<big snip>
>   Since you brought it up, though, it's been noted that the C&C AI
>isn't smart enough to blow away sandbag obstacles.  Obviously you
>gave it some thought, as your above post indicates.  Were you just
>unable to implement that logic branch before the Doom of the Shipping
>Date loomed?  (I can understand that, believe me!)
>
>Steven Woodcock
>"The One and Only"

Early on, during play balancing, the computer units would blow through
walls quite handily. The testers were complaining that the game was
too tough, so this was disabled. As ship day neared, the question of
reactivating this was raised. Management decided that all of the
recent balancing adjustments would be moot if the computer units were
to be allowed to blow through walls again. Leaving it the way it was
(computer doesn't blow through walls) was considered the lesser of two
evils. This was fixed for the internal version of the game. However,
the patches for C&C were explicitly directed to change only the
minimum necessary to address the most major bugs. The wall blockage
problem was considered not major enough. Oh well.

Joe B.

To: Swoodcoc@cris.com
Subject: Re: Command and Conquer A

[precalc SPA]
 Sw> Agreed.  When this was suggested as a solution, we quickly came up
 Sw> with various estimates for memory size (ranging from 400K to 4GB) that

Blphssst...  Thanks for remembering me, Steve.

I came up with a 9900b solution for a 100x100 map (with 10x10 regions).  Or
Regions * (Regions - 1) bytes solution.  Certainly nowhere near 400kb.
At 5x5 region resolution it was something like 155kb.  At 3x5 it comes out to
be 433kb.  3x3 is 1.2MB.

:-(

:-)  No hard feelings.  Not at 1:30am anyhow.

[And you said (unnamed author guy of a certain famous game book who you knew
>from college) had a bigger ego than me! :)  Then again, I'm in a sour mood.]

 Sw> This is the approach I'm using in my game.  I try not to even
 Sw> compute a path if it's not needed, if the unit is moving only a
 Sw> relatively short distance, etc.  I don't like to crank up the full
 Sw> pather unless I have to.

That is perfectly reasonable with open maps.  With city-type maps, there is no
such thing as close except for one tile away, and even then, if tiles have
variable elevation (and therefore can be stepped), maybe not.

Ofc, I know how much you hate 'tiles.'  Just for the 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

joebwan@anv.net (Joe Bostic) writes:
>The map can be broken up into regions (say 3x3 or 5x5). Then all
>possible paths calculated between the center points of these regions.
>A traveler would merely have to move to the center point of the region
>it is currently in. Then it would use the precalculated path vector to
>the closest region center point to its desired destination. This has
>the same problems as before, but to a much lesser degree. It also has
>an additional problem where a blockage might bisect a region.

Actually, I'm starting to like this more.

Units blindly follow region waypoints to their destination until forced
to do otherwise.  C&C, Warcraft I, and Warcraft II all point out cases
where waypoints are useful: there are (sometimes huge) blockages in the
maps, like rivers or mountains, that can not be crossed.  Instead of
forcing units to feel along the edge of the blockage, just send them to
the bridge!

If a unit needs to get from A to B:
  Compute a path using current waypoints.  Store this.  Head to the first
  waypoint.
If, in getting from waypoint to waypoint, the unit is blocked:
  Update the waypoint map.  Find a short-term way around the blockage,
  and feed this workaround into the waypoint map.

This has advantages of:
 (1) This keeps analysis local: units will never look at more than a
     (say) 16x16 square area;
 (2) Units can handle dynamic world changes, by updating the waypoint
     map when a blockage is found
 (3) Waypoints allow units to quickly find out how to travel long distances
 (4) Random, infrequent searches of nearby terrain can point out terrain
     changes that don't directly affect the unit, but DO allow other units
     to take advantage of the changes.

>Yet another solution is to not calculate a path at all unless it is
>necessary. The traveler would head toward its destination in a direct
>path (veering up to 45 degrees to either side if there is a minor
>blockage). If it cannot get closer to its desired destination using
>this method would it then go into 'full blown path finding' mode.

Units in Warcraft I do this, and sometimes it is the most frustrating thing.
They'll decide to head the long way around a barrier, when they could just
move two steps to the left and cross the bridge there.

I think not calculating a path unless necessary is a good thing.  I think
waypoints fit into this by giving units a quick way of deciding a large-scale
path.

>In addition, some
>'terrain blockage' may actually another traveler.

Warcraft is 'smart' by being 'dumb'.  A bunch of units can enter a long
corridor, and they'll just follow each other through to the other side.
So long as no-one tries to go the other way, all is fine.  Units just
ignore other units, unless they find themselves 'stuck,' at which point
they will either think hard and find a good solution, or just stop.
Which tells me that they'll think only SO hard.

The solution isn't perfect, but it is cheap and works most of the time.

>Joe B. (the programmer of C&C)


Andrew R Southwick          -={C++/OO Programmer}=-     asouthwick@vnet.ibm.com
#include <stddisclaimer.h>                                 I speak not for IBM.
            -= Freedom by permission is a contradiction in terms =-

In article <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.

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?

Jason Kester (jkester@pdx.ms.ch2m.com) opined thusly:

: 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                                     _____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                          |
+=============================================================================+

In <65> Jason Kester <jkester@pdx.ms.ch2m.com>
writes: 
>
>In article <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.
>
>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

marianna@nwoasis.wa.com opined thusly:
: Well, another concern is that the set up of any one game will determine 
: 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.


   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.

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                          |
+=============================================================================+

To: Marianna@nwoasis.wa.com
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
--
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

In article <4ltorc$fno@news.bellglobal.com>,  <sshah@intranet.ca> wrote:
>To: Swoodcoc@cris.com
>Subject: Re: Command and Conquer A
>
> Sw> : I came up with a 9900b solution for a 100x100 map (with 10x10
> Sw> regions).  Or : Regions * (Regions - 1) bytes solution.  Certainly
>
> Sw> Sorry.  I forgot about your proposed solution, probably (no offense)
> Sw> I thought it was way too coarse.  I think you'd get very "chunky"
> Sw> motion breaking the map up into 10x10 regions.
>
>The 10x10 region wasn't the kicker though.  It was the n(n-1) bytes of memory
>required (where n = # of regions).  I mean, Most solutions used 400kb for 5x5
>where mine only uses 155kb.
>
[...]
>Sunir Shah (sshah@intranet.ca)     http://intranet.ca/~sshah/

You should be able to do a lot better than N x N-1 bytes.

First, for every of N squares keep N-1 directions; each direction being
"To Square X, the best path involves moving in direction D".  Maybe that's
what Sunir already did.  But each direction only needs 3 bits (0->7) so
it's down to N x N-1 x 3/8 bytes.

Next, use a run-length encoding.  There will be a huge amount of redundancy
in these directions.  Each direction in a square, compressed with run-length
encoding, will look like "For destinations 576-1145, take direction D."
And so on.  Each square will now have not N-1 path instructions associated
with it, but more like sqrt(N).  N x sqrt(N) total.

Then, run-length encoding is linear, and a quadratic encoding might work
better.  I.e. in a square, the pathfinding instructions would look like,
"For destinations in rectangle(x1,y1,x2,y2) take direction D."  I would
expect something like (number of directions) rectangles to be generated
per square.  For N=10,000 regions (100 x 100 map), maybe 500K bytes used.
(N x some smallish constant.)  Traversals are still easy.

Last, there is _still_ a good deal of redundancy that can be squashed
out.  Many adjacent squares could have the same direction given for the 
same destination rectangle.  Squish all those together in a start rectangle.

Now, what you have is a database of rules
"If starting in rectangle(w,x,y,z) and heading to destination in
 rectangle(a,b,c,d) take direction D."

That could be a lot _less_ than N bytes.   But traversals have gotten
difficult ...  Don't ask me to figure out right now how one would quickly 
find which rule to use.  Building that database could be a headache, 
too.


-- Richard Wesson

To: Wesson@church.cse.ogi.edu
Subject: Re: Command and Conquer A

 We> You should be able to do a lot better than N x N-1 bytes.
[...]
 We> Maybe that's what Sunir already did.  But each direction only needs 3
 We> bits (0->7) so it's down to N x N-1 x 3/8 bytes.

Hmm.  I can buy that.  The program knows its current location anyway.  So
after moving in the direction, you can rip the current location again.

To save time reading it, you may only want to use nybbles instead of packets
of 3 bits.  So, that would afford

[Keeping in mind it was previously 2 bytes per entry ...]

n(n-1)
------ bytes.  Still
  4

3n(n-1)
------- bytes is better.
  16

Anyway, that would mean 3x3 tile regions (on a 100x100 map) are a comfy 300kb
or so, and 3x3 is pretty tight.

 We> Next, use a run-length encoding.  There will be a huge amount of

Ugh... that would take far too long.  You want random access here, not
sequential.

 We> Then, run-length encoding is linear, and a quadratic encoding might
 We> work better.  I.e. in a square, the pathfinding instructions would look
 We> like, "For destinations in rectangle(x1,y1,x2,y2) take direction D."  I

That's the entire point of using regions.  n is the number of regions, not
squares.

 We> generated per square.  For N=10,000 regions (100 x 100 map), maybe 500K

Each tile is a 1x1 region. :)

Without using RLE (which would require decompressing anyway ... disk space is
cheap, memory is not), that would be ...

10000(9999)
----------- bytes = 25MB
     4

Or

(10000)(9999)(3)
---------------- = a cool 19MB
       16

:-)

 We> Last, there is _still_ a good deal of redundancy that can be squashed

Definitely.  That was part of my solution... the shortest path from A to C, if
it passes through B, is the sum of the shortest paths from A to B and B to C.
So just store the path from A to B and then the path from B to C instead of
all three.

 We> Now, what you have is a database of rules
 We> "If starting in rectangle(w,x,y,z) and heading to destination in
 We> rectangle(a,b,c,d) take direction D."

Yes.... Dynamic regions!  Yeah! :)  (Too many marshmellows..)

 We> That could be a lot _less_ than N bytes.   But traversals have gotten
 We> difficult ...  Don't ask me to figure out right now how one would
 We> quickly  find which rule to use.  Building that database could be a
 We> headache,  too.

True and true.  The latter isn't so much a problem as the former.  Hmm..

Well, you'd start with an index destination bounding boxes that point to their
respective source box list.  That's only two lists to traverse with a simple
bounding box algorithm.  You can even sort the boxes based on one of their
corners to speed things up..

Pick a sort direction opposite to the direction of traversing.  If you were
scanning from the "top of the map down" (i.e. you'd check if your point's Y
coordinate was less than the boxes' Y coordinates, assuming standard computer
indexing methods), you should sort one of the top Y (lowest one) of the boxes,
>from highest to lowest.  That way you can quickly traverse the list checking
for a < match on the boxes before doing the more lengthy bounding box
calculation.

HOWEVER, the same problem exists:  dynamic maps.  Those would break severely
with this dynamic region solution.  With fixed regions, you can always recalc
the shortest path.

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

In article <73>,  <sshah@intranet.ca> wrote:
Sh>To: Wesson@church.cse.ogi.edu
Sh>Subject: Re: Command and Conquer A
Sh>
Sh> We> You should be able to do a lot better than N x N-1 bytes.
Sh>[...]
Sh> We> Maybe that's what Sunir already did.  But each direction only needs 3
Sh> We> bits (0->7) so it's down to N x N-1 x 3/8 bytes.
Sh>
Sh>
[...]
Sh> We> Next, use a run-length encoding.  There will be a huge amount of
Sh>
Sh>Ugh... that would take far too long.  You want random access here, not
Sh>sequential.

Hmm, think so?  We're encoding _which direction_ here ... it's not
unreasonable to think that a long row to the north will represent 
only 3 different directions in re getting to our destination in that
row.  500 entries, (considering a 100x100 board with 100 rows)
if searched linearly won't be at all bad.  If you use a binary search
(remember that we can order the row-destinations) then average search
time thru that list is log-2(500) is 10 accesses to the list.

What I mean is, each point will have a list of a span of destinations
ie. for 
...
destination: 300-513 go direction 7.
destination: 514-899 go direction 5.
destination: 900-1015 go direction 4
...
Such a list will _not_ need to be decompressed, and can be searched in
a binary fashion.  (Go to middle, then go to up-half or down-half of
two sides of list, depending.  Recurse until you find item containing
your destination.)

That's what I meant by RLE.

SShS>Without using RLE (which would require decompressing anyway ... disk space is
Sh>cheap, memory is not), that would be ...

Humph.  See above.  Still, quadratic is better.

Sh> We> Last, there is _still_ a good deal of redundancy that can be squashed
Sh>
Sh>Definitely.  That was part of my solution... the shortest path from A to C, if
Sh>it passes through B, is the sum of the shortest paths from A to B and B to C.
Sh>So just store the path from A to B and then the path from B to C instead of
Sh>all three.
Sh>
Sh> We> Now, what you have is a database of rules
Sh> We> "If starting in rectangle(w,x,y,z) and heading to destination in
Sh> We> rectangle(a,b,c,d) take direction D."
Sh>
Sh>Yes.... Dynamic regions!  Yeah! :)  (Too many marshmellows..)

Right, I ended up at a similar point to you, but circuitously.  I'd also
like a solution that didn't throw away any information on the map, that 
would work just as well for gnarly 'city' terrain as for countryside.  Hence
dynamic regions, regions that have a commonality of path(start,dest)=dirX.

Sh> We> That could be a lot _less_ than N bytes.   But traversals have gotten
Sh> We> difficult ...  Don't ask me to figure out right now how one would
Sh> We> quickly  find which rule to use.  Building that database could be a
Sh> We> headache,  too.
Sh>
Sh>True and true.  The latter isn't so much a problem as the former.  Hmm..
[..]
Hmm ... nothing really elegant can be done, anyhow ...

Sh>HOWEVER, the same problem exists:  dynamic maps.  Those would break severely
Sh>with this dynamic region solution.  With fixed regions, you can always recalc
Sh>the shortest path.
Sh>

alas, true.  Until we get computers that are fast enough to examine
nearly every space on the board, we're stuck with some suboptimal
solution.


>'                  Sunir Shah (sshah@intranet.ca)                   '

-- Richard Wesson
(wesson@cse.ogi.edu)

In Article<DqIxDo.G7v@actcom.co.il>, <bruck@actcom.co.il> writes:
> sshah@intranet.ca wrote:
> 
> >To: Spavlina@pacificnet.net
> >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.
> >--
> If you the units are posting these global messagea, might it not be
> better to sepcify which spot they want to be cleared, rather than
> which unit? 
> They should also post in the same message their current location, so
> we won't get one unit posting about a spot where it wants to go and
> the unit that stands in that spot, responding by asking to clear the
> spot where the first unit is. 
> 
> Uri
> 
> 
> 
Well one way to avoid that is to not have an area that close, I have not seen 
any maps that have it set up that way either. The only objects that could be 
in the way would be tree's, rocks, and buildings, if it is tree's you can cut 
them down or blow them up with a demolition squad, if it is rock then you can 
blow that up as well. As far as the building, don't build close to a mine.

Tony Schroeder wrote:
> 
> Well one way to avoid that is to not have an area that close, I have not seen
> any maps that have it set up that way either. The only objects that could be
> in the way would be tree's, rocks, and buildings, if it is tree's you can cut
> them down or blow them up with a demolition squad, if it is rock then you can
> blow that up as well. As far as the building, don't build close to a mine.

How about restricting the building of maps (random or otherwise) to a 
higher level than the players.  That didn't come out right, but what I 
mean, is if a player takes one "square", build the maps in blocks of 4 
"squares" (which connect normally, not at angles).  If you restrict 
the level editor this way too, the player can't do any tricky stuff.

Map:
AABBCCDD 
AABBCCDD
EEFFGGHH
EEFFGGHH
IIJJKKLL
IIJXKKLL
MMNNOOPP
MMNNOOPP

Key:
X - size of map square, player
AA - size of map block of squares
AA

And you can have rules with path following since the 4-blocks are 
guaranteed to have the same terrain characteristics:

If goal is up, stay to the right along the path.
If goal is down, stay to the left along the path.
If goal is left, stay to the top along the path.
If goal is right, stay to the bottom along the path.

(or "drive" on the left hand side if you come from one of THOSE 
countries ;-) )

Just some thoughts.  Might still need messages for intersections, 
player-player collision detection etc...

-- 
---------------------------------------------------------------
Brian Offermann   CS Student, University of Minnesota - Duluth
E-mail:  mailto:bofferma@d.umn.edu  Phone Extension: 6459
WWW:     http://www.d.umn.edu/~bofferma/index.html         =VH=
---------------------------------------------------------------

To: Tony.schroeder@netmanage.com
Subject: Re: Avoiding Other Units

[one-tile wide enclosured blocked off by units on either side]
 To> Well one way to avoid that is to not have an area that close, I have

Doesn't work too well with dynamic or user-made maps.

Which has basically been the problem this entire series of SPA threads...

*sigh*

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

In article <77>,  <sshah@intranet.ca> wrote:
~To: Tony.schroeder@netmanage.com
~Subject: Re: Avoiding Other Units
~
~[one-tile wide enclosured blocked off by units on either side]
~ To> Well one way to avoid that is to not have an area that close, I have
~
~Doesn't work too well with dynamic or user-made maps.
~
~Which has basically been the problem this entire series of SPA threads...
~
~*sigh*
~
~'                  Sunir Shah (sshah@intranet.ca)                   '

You know what, something to think about:

Our perfect pathfinding solution would involve converting the map into
vectorized polygons, and then navigating that vectorized map.

Most tile maps (with no terrain differentiation besides passable/impassable)
would be easy to convert into polygons.  A set of polygons representing a
tile map would have much, much fewer bits than the tile map.  Thus, it's
practical to actually examine all the map info every time you want to set
a path.  (I note that any pathfinding algorithm for a large number of tiles
is impractical to run constantly, simply because you _must_ examine most
of the information on the map to create a path.  Hence, for a tiled map
you have to give up something -- you have to give up resolution or the
ability to make new paths at will, or something.)

A completely dynamic map will be practical.  Just add/remove polygons
as needed, and recompute your path.

(Vectorization will not work for a map that actually really does have 
a ton of information in it, i.e. a map with lots of mixed variable terrain.)

Next question: what algorithms will work for navigating a vectorized map?

A search of the literature would be in order at this point.  I have some
ideas myself, but I have no idea if they're workable.

One idea:  Consider the map as a rubber sheet.  Distort the rubber sheet
until you have a clear path (straight line) between you and your
destination.  Then undistort the rubber sheet, which will distort your
straight-line path into the path around obstacles that you need.

-- Richard Wesson
(wesson@cse.ogi.edu)

To: Wesson@church.cse.ogi.edu
Subject: Ideal pathfinding

[Polygonizing, or geometricizing, maps]
 We> (Vectorization will not work for a map that actually really does have 
 We> a ton of information in it, i.e. a map with lots of mixed variable
 We> terrain.)

That's a big problem, but for things like city maps ... hmm.
 
 We> Next question: what algorithms will work for navigating a vectorized
 We> map?

How about a bending-line, way-point SPA?  I think one is outlined on the Smart
Unit Navigation page.

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

Okay, I've seen a lot of discussion on storage of shortest-path
routes.  I wondered if sparse arrays could be used to decrease
the space required to store the results.  Given the following:

1) The map is formed (by a human or randomly), then made available
   for analysis for shortest-path selection.
2) Since humans are allowed to design the map, one must allow
   concave obstructions, mountains which totally divide the map, etc..
3) Different terrains may take different amounts of time to cross.
4) There may be a time-penalty associated with changing from one
   type of terrain to another (e.g. must get in a boat to cross
   water, and out again when you're at the other side).
5) The possibility that a route may be blocked by an opponent's
   War-God with +4 backscratcher is ignored: we're only worrying
   about terrain here.  [Though see note A.]

it is possible to spend a lot of CPU time and calculate the best
possible path from A to B.  You can precalculate (for scenarios)
or calculate in the background (doing immediately any paths required
which haven't been calculated yet).  All one needs to store for
each (start-point, end-point) pair is the direction of the next
square, i.e. eight directions (= 3 bits). [See notes B & C.]
You'd probably use 4 bits so you can use the extra bit to mark
the 'last move' of a route and not have to align bits in memory.

By working backwards from the destination cell it's possible to
work-out the required movements quite efficiently.  (But then
the readers of this group know that already !)

One could use a sparse array to prevent the necessity for storing
these results.  You'd also not have to make space for situations where
   a) the start is the destination,
   b) the start or the destination point are inaccessable (e.g. swamp)
   c) the start or the destination point are 'blocks' themselves.
   d) there is no path from the start to the destination.
      (e.g. a range of uncrossable mountains separates them,
       or a river in games with no boats or flight.)

Now given a list of the eight semi-ordinal directions, we can
divide 360 degrees into eight giving 45 degrees.  A large number
of the movements generated by the algorithm are going to be in
the 'obvious' direction, given the direction of the vector from
the start-point and the end-point, i.e. if the destination is to
the east of the start, then you should go east.  This gives us
   e) The 'obvious' direction should be taken.

Conditions (a) to (e) can represent a large proportion of routes.
Does anyone have any figures on how efficient this would be ?
I'm sorry but since I don't write games (or write papers
describing how to write games) for a living I don't have the time
to develop a decent investigation of this.

With a 50x50 grid and just simple 'clear' or 'blocked' tiles I
get a much smaller resulting array for anything but a really
crowded map: one resembling a maze.  Much of the saving is made
because if a map has a large number of obstacles, then a large
number of cells are, themselves, part of obstacles, so you don't
need to store directions for them.

Notes:
   A. You could cause the computer to recalculate given the
      current position of the pieces in play.  The pieces would
      be assigned 'costs' associated with how much effort it
      takes to destroy them.  This would yield a different 'map'
      for each player, of course.
   B: Or hexagon, with six directions (= 2.6 bits).  Or more bits
      if you count a change of direction as a 'turn'.  Or whatever.
   C: This leads, for simple maps with no terrain variations, to
      pieces taking a diagonal until they're in-line with the
      destination, and then a horizontal or vertical line.  This
      may look a little boring.

Simon.
-- 
Simon Slavin -- Computing | "We are /all/ lying in the gutter, but /some/
  Contractor Ordinaire    |  of us are looking at the stars." -- Oscar Wilde

In article <4loce4$iuc@tribune.concentric.net>, Jonesja@cris.com says...
>  What is a method for computing the shortest path for units that can't
>chose to move into any arbitrary square?
>
> For example, say a unit always faces one direction , and can only change
>its heading by one unit per move taken:
>
>                    B
>     *************** *******************
>                    A
>
>  If the unit is at A heading south and is trying to get to B, it would
>have to spend some number of turns turning around and then two turns
>moving ahead to reach B. 
>
>  What if that same unit could not chose to simply turn in place? If the
>only moves it can make are move, or move & turn, this problem becomes even
>more complicated.
>
>  
>  Does anyone have any thoughts on this problem?
>
>
>Jeff Jones
>jones@ca.metsci.com


To express something similar to what Messrs. Woodcock and Jones posted:

1. Make the structure representing the state include not only the location, but 
also the orientation (which way it is facing), and even the velocity if it 
matters.

2. The routine which then finds all neighboring states (or nodes) to the 
current state, will then generate only those accessible states.  Hence, it 
won't generate impossible moves, like turning in place, moving sideways, etc.

3. The evaluation of the goal state may only care about the final location, or 
may consider the orientation, depending on the application.

Note: Since A* depends on being able to check on whether a generated node is 
already on the Open and Closed lists, you will need to look for it based on 
both the position and orientation.  Since you will also need to pop nodes from 
the Open list based on their score, this will probably effect how you try to 
implement a data structure for those lists.  

Joe Bostic's method sounds like a faster approach for some situations, even if 
it may not find the best path.

Regards,
Bryan Stout
bstout@interramp.com

In article <4m0h89$bs5@news.bellglobal.com>, sshah@intranet.ca wrote:
>To: Edybs@ix.netcom.com
>Subject: Re: Avoiding Other Units
>
> >That's easy.  Running an influence map algorithm over the map and 
> >then use that information to weight terrain values in your SPA.
> Ed> Nice idea Sunir, if this is occuring in a turn-based game with a
> Ed> low unit density.
>
>No need to be sarcastic.  'Twas just an idea.
>
> Ed> units) on a large map (1024x1024) then how could most home systems
> Ed> (where games are played) be able to provide enough power to run an
> Ed> influence map algorighm over the map for each path finding request?
>
>They can't.  Oh well.

What about using a simple alg. to calc a Sphere-of-Influence for a unit,
let's say something like 
    Strenght-ABS(Distance) 
or just a precalced array like
    00100
    01210
    12321
    01210
    00100
and just add/sub it when moving a unit. You'd have to store a whole second 
map, but I think that wouldn't take that much time. 

Any suggestions?

Regards, 

  David

------------------------------------------------------

David Schmitt (david@edvzbb2.ben-fh.tuwien.ac.at)

Don't tell me I didn't think about it.
On the other hand ...

------------------------------------------------------

In <80> david@edvzbb2.ben-fh.tuwien.ac.at
(david) writes: 
>

[snipped Sunir's and Eric's comments about using an influenec map]

>
>What about using a simple alg. to calc a Sphere-of-Influence for 
a unit, let's say something like 
>    Strenght-ABS(Distance) 
>or just a precalced array like
>    00100
>    01210
>    12321
>    01210
>    00100
>and just add/sub it when moving a unit. You'd have to store a 
>whole second map, but I think that wouldn't take that much time. 
>
>Any suggestions?
>

David,

Assuming that this is in a real-time game, and there is more than
one unit involved in the game, then it seems a Sphere-of-Influence
(SoI) approach would provide the 'influence' one could obtain from
influence mapping, however it also seems to me, that the processing
requirements resulting from just a single move by a single unit 
would still make this approach difficult to use effectively.

Consider in your example above, that a move of a single step to the
right would involve the recalculation of the influence of 25 cells.
Further consider that there was another unit located within the radius
of the influence that was impacted by the move, which would require
the calculation of possibly another 25 cells.  Then further consider
that there are even more units that are located within the radius of
the influence of the moving unit, and hence there could be another
X times 25 cells that require recalculation.  So thus, the movement
of a single unit, of one step, could result in the need to recalculate
the SoI rating for upwards of hundreds of cells.

This seems like too much processing to ask of the computer in use by
most people who buy computer games, especially when the additional
processing demands of real-time, animation, 24bit color graphics and
sound and music are added in.

Just my 2 cents worth ...

Regards,

Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA

To: Edybs@ix.netcom.com
Subject: Re: Avoiding Other Units

[SoI algy del'd]
 Ed> Consider in your example above, that a move of a single step to the
 Ed> right would involve the recalculation of the influence of 25 cells.

I see you've never had to do digital sound processing (ok, I haven't either,
but I know how it works).  This is peanuts.  25 subs + 25 adds.  Oh no.

 Ed> Further consider that there was another unit located within the radius
 Ed> of the influence that was impacted by the move, which would require

So what?  Think about it.. you have a zeroed map at the beginning.  Now, for
each unit on your side, add the array.  For their side, subtract the array.

Every time computer unit X moves, subtract its array from its current position
and add it to its destination.  That's all that's needed.  Flip the signs for
the player.

[Actually, I think it'd be more beneficial to make the player positive and the
computer negative, but that's just an opinion]

 Ed> the calculation of possibly another 25 cells.  Then further consider
 Ed> that there are even more units that are located within the radius of
 Ed> the influence of the moving unit, and hence there could be another
 Ed> X times 25 cells that require recalculation.  So thus, the movement

Why?  They aren't moving.  They still have the same influence.

 Ed> of a single unit, of one step, could result in the need to recalculate
 Ed> the SoI rating for upwards of hundreds of cells.

Still, that's peanuts.  Nuttin' at all. (Don't hit me <G>)

 Ed> This seems like too much processing to ask of the computer in use by
 Ed> most people who buy computer games, especially when the additional

[Although I don't want to admit to listening to MODs, ever, I'll bring 'em up]
For MOD playing, on my box, you can get away with 11kHz, or 11000 bytes/s, for
a four channel MOD in Windows.  That's 33000 adds and 11000 shifts by 2.  In
Windows no less. [the last time I listened to a MOD in Windows was early
1994.]

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

In <82> sshah@intranet.ca writes: 
>
>To: Edybs@ix.netcom.com
>Subject: Re: Avoiding Other Units
>
> Ed> Further consider that there was another unit located 
> Ed> within the radius
> Ed> of the influence that was impacted by the move, which 
> Ed> would require
>
>So what?  Think about it.. you have a zeroed map at the beginning. 
>Now, for each unit on your side, add the array.  For their side,
>subtract the array.
>

Then you suggest, that every time a single unit moves, to recalculate
the entire influence map?  That's even more processing intense than
the worst case I suggested.


>
> Ed> the calculation of possibly another 25 cells.  Then 
> Ed> further consider
> Ed> that there are even more units that are located within 
> Ed> the radius of
> Ed> the influence of the moving unit, and hence there could 
> Ed> be another
> Ed> X times 25 cells that require recalculation.  So thus, 
> Ed> the movement
>
>Why?  They aren't moving.  They still have the same influence.
>

I think you are missing the point.  That is, that every time a
single unit moves, the influences generated by that single unit,
as applied with neighboring units, is changed.  And once changed
that influence needs to be applied as far as it is felt.  And,
then that application of influence means significant processing.

Of course, you might be thinking of a very simplied influence map, 
such as you described above. <g>


> Ed> of a single unit, of one step, could result in the need 
> Ed> to recalculate
> Ed> the SoI rating for upwards of hundreds of cells.
>
>Still, that's peanuts.  Nuttin' at all. (Don't hit me <G>)
>

I'm not going to hit you <g>, but I am going to suggest you must
be considering this is going to run on a P166 with 32MB of memory
and a much more efficient OS than something like Win95.  When you
need to manage 100s of moving units, and support 24fps, and drive
sound and music, and still make other decisions for upwards of 6
AI players, *** all in the same game ***, then even a single add
that is not necessary is to be avoided.  So, my point to you is 
that all this additional processing that an influence map would
need, *** for each step taken ***, makes the use of SoI to be,
IMO, processing prohibitive.

I have not seen anything in your comments to suggest otherwise, 
in fact, IMO you seem to be suggesting increasing the processing 
needs of the influence map or SoI.


> Ed> This seems like too much processing to ask of the computer 
> Ed> in use by
> Ed> most people who buy computer games, especially when the > 
> Ed> additional
>
>[Although I don't want to admit to listening to MODs, ever, I'll 
>bring 'em up]
>For MOD playing, on my box, you can get away with 11kHz, or 11000
>bytes/s, for
>a four channel MOD in Windows.  That's 33000 adds and 11000 shifts 
>by 2.  In
>Windows no less. [the last time I listened to a MOD in Windows was
>early 1994.]
>

IMO, playing sounds and doing something else is trivial compared to
what must happen in a real-time strategy game, by today's gaming 
standards.  Over the last year, we have been working on such a game,
and pityfully few cycles that are left over for the AI to do something
like influence mapping (after each step by any unit) is simply, IMO,
not enough to do the job.  Of course, take away the support for 24fps
and animations and user interface, and just leave playing sounds as
you suggest, and force it to run on a P166, then, well, maybe .... <g>

Regards,

Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA

edybs@ix.netcom.com(Eric Dybsand) wrote:

>>So what?  Think about it.. you have a zeroed map at the beginning. 
>>Now, for each unit on your side, add the array.  For their side,
>>subtract the array.
>>

>Then you suggest, that every time a single unit moves, to recalculate
>the entire influence map?  That's even more processing intense than
>the worst case I suggested.

This sounds like the radar map I use in my (now getting too old) POW
project. Every unit has a X*X radar area (actually images formed like
circular areas) that is subtracted from the map whenever a unit leaves
a tile and added again with the new offsett. Running 256 units with
lots of other calculations, including graphics, works fine with 70 fps
on a 486-66 CPU. Although the radar area is a max of 15*15 (7 tiles in
each direction) it is not that time consuming. By using this I get an
effective "fog of war" effect that looks great.

BTW, the radar scanning for other units around another unit takes at
least 4 times as much CPU time and that runs along fine as well. The
scanning works a bit differently as it has to scan in a spiral from
the unit and outwards. The scanning is done more often than the radar
map update also, as a unit takes at least 16 frames to move from one
tile to another one.

Just to let you all know this is not time consuming at all. In my
case, updating the small overview map takes the most time. I know that
I can speed it up by a factor of at least 5, just haven't found the
time to do the optimizations.

Regards,
John


------------------------------------------------------------------------------
   John Christian Lonningdal    -    Web: http://www.lis.pitt.edu/~john
 john@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

In article <83> edybs@ix.netcom.com(Eric Dybsand) writes:
>Then you suggest, that every time a single unit moves, to recalculate
>the entire influence map?  That's even more processing intense than
>the worst case I suggested.
No, you do a fix and a blit. You know by how much the unit modified each 
tile in it's influence so you do the inverse adjustment (1 add per tile 
within it's influence, say 100 max) move it and then make the 
modification again (another 100 add/subs).

>>Why?  They aren't moving.  They still have the same influence.
>>
>
>I think you are missing the point.  That is, that every time a
>single unit moves, the influences generated by that single unit,
>as applied with neighboring units, is changed.  And once changed
>that influence needs to be applied as far as it is felt.  And,
>then that application of influence means significant processing.
Not with the definition of influence the influence map he stated,
and given extra memory and some precalculation, you can make a new set of 
maps with only 100 adds (Just precalc what the delta influence would be 
for moveing in each non rotateable direction (a hex map would require 
one, a square with diaganol movement would need 2)


>I'm not going to hit you <g>, but I am going to suggest you must
>be considering this is going to run on a P166 with 32MB of memory
>and a much more efficient OS than something like Win95.  When you
>need to manage 100s of moving units, and support 24fps, and drive
>sound and music, and still make other decisions for upwards of 6
>AI players, *** all in the same game ***, then even a single add
>that is not necessary is to be avoided.  So, my point to you is 
>that all this additional processing that an influence map would
>need, *** for each step taken ***, makes the use of SoI to be,
>IMO, processing prohibitive.

Well, lets do some math, assumeing that we can get 10% of the processor 
(since you declared music, sound a graphics trivail, it's a fair estimate)
that still leaves us with 16600000 adds per second (before you disagree, 
remember add is a one tick operation on the pentium, and we have two 
pipes). Divide that up into 30 fps and we have 553333 adds *just for 
this) per frame. Now assumeing 250 units moveing per turn we get 226 adds 
per unit that moved, and most units won't move every frame (unless they 
are all bloody fast) in fact, if a large portion of them don't move, it 
is considerably easier, also, if you precalc some info for grouped 
movements, you can cut the number of effective units in half a few times, 
thus allowing either more units, or more other stuff. Even with a worst 
case of 1% of the CPU, we still have enough for almost 50 units moveing 
per turn, wich would give an average speed (for 300 units) of 7 tiles a 
second, and most of the time, most player units will be idle (in most 
stratagies).

Anyways, his method is doable with the space and time available, even 
assuming very pour conditions. Oh, and one other thing, I don't think 
Graphics, Music and Sound effects are trivial, you just happened to state it.

\--/-\--/                GryMor, Tan-Istar of the Istari Council
 \/   \/  / \            [Corespondence: n9545138@cc.wwu.edu   ]
  \___/  /\ /\           "When someone asks if you're a god"
   \ /  /  |  \                     "YOU SAY YES!"
       /___|___\  \/irtual /\depts, because reality's just a bunch of bits

In <87> n9545138@waldorf.cc.wwu.edu (Steve
'GryMor' Metke) writes: 
>
>
>Well, lets do some math, assumeing that we can get 10% of 
>the processor (since you declared music, sound a graphics 
>trivail, it's a fair estimate)

Please do not misrepresent my words.  Here is what I stated:

"IMO, playing sounds and doing something else is trivial compared to
what must happen in a real-time strategy game, by today's gaming 
standards.  Over the last year, we have been working on such a game,
and pityfully few cycles that are left over for the AI to do something
like influence mapping (after each step by any unit) is simply, IMO,
not enough to do the job.  Of course, take away the support for 24fps
and animations and user interface, and just leave playing sounds as
you suggest, and force it to run on a P166, then, well, maybe .... <g>"

The "playing sounds and doing something else is trivial" referred
to Sunir's suggestion that adding the workload of playing a sound
while calculating influence represented a typical game workload.

It does not.

The "Of course, take away the support for 24fps and animations and 
user interface, and just leave playing sounds as you suggest, and force
it to run on a P166, then, well, maybe .... <g>" seems to me to be an
acknowledgement that all this work, if removed, would free up enough
time to do the influence calculating in the manner Sunir suggeested.


>Oh, and one other thing, I don't think Graphics, Music and Sound
>effects are trivial, you just happened to state it.

Neither do I.  Nor did I state such.  That is the point.  With all that
additional work going on in a real-time strategy game, then there is a
need for the AI to be as efficient as possible.  I do not believe that
using influence maps for pathing, which was the point of this thread,
is very efficient.


>that still leaves us with 16600000 adds per second (before 
>you disagree, remember add is a one tick operation on the pentium, 
>and we have two pipes). Divide that up into 30 fps and we have 553333
>adds *just for this) per frame. Now assumeing 250 units moveing per
>turn we get 226 adds per unit that moved, and most units won't move
>every frame (unless they are all bloody fast) in fact, 

Running numbers out here is one thing.  Actually doing it with a cpu,
a real game and a user, is totally different.  Often, IMO, the best
in theory, must be proven in application.

Have you actually implemented your suggestions in a real-time strategy
game?  If so, please tell us where we can buy a copy to study.


>assumeing that we can get 10% of the processor

In actually testing Enemy Nations, during its year long development,
my experience has been that each AI Player (there can be up to 6) is
getting less than 1% of the cycles.  Although, this is skewed due to
our testing processes that eat up some of what each AI gets, IMO your
assumption of 10% is very generous indeed.

>
>Anyways, his method is doable with the space and time available, even 
>assuming very pour conditions.
>

Have you done it?  Has Sunir?

Regards,

Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA

To: Edybs@ix.netcom.com
Subject: Re: Avoiding Other Units

 Ed> Please do not misrepresent my words.  Here is what I stated:

*sigh*  Ditto.

 Ed> The "playing sounds and doing something else is trivial" referred
 Ed> to Sunir's suggestion that adding the workload of playing a sound
 Ed> while calculating influence represented a typical game workload.
 Ed> It does not.

Eric, I let that one go last time because I figured you'd figure it out
eventually.  I guess you didn't. I was commenting on the fact that it is
easily possible to do 33000 adds in one second while mucking around with
several applications in Windows, which is slow enough, even on my cancer box
(which I failed to point out is a 486SX25 w/ 4MB RAM).  That practical example
(failing actually writing the code, which I don't care to do as any game
programmer could by themselves) indicates that you *can* handle, what?  50
adds/subs per unit per turn max if you use a simple 5x5..  It's actually less
(about 25 or so) because you'd use a transparent 'blat.'

Let's quantify... there are, say, 30 cycles per second (which is the standard
fps target for most games).  So, for each unit, if its going max out for 30
cycles, that's 30 * 25 adds/subs/s/unit = 750 operations/s/unit

How many units do you have?  Let's say 25 (medium theatre ... I'll get back to
this later).. that's 18750 operations/s, which *is* possible.

However, it's stupid.  Onto optimizations.

Naturally, no unit is going to get far in one second, so why recalculate it
every turn?  Why not recalculate it once a second?  So, that's only 25 * 25 =
625 operations per second.  This is pretty low, allowing more units in the
game, if you want.

Of course, who's going to move every unit every turn?  But that's the worst
case scenario.

Anyway, this allows you to calculate _fast_ *influence maps*... screw
pathfinding for now.  Influence maps are useful in some cases.

[removing CPU heavy sections of a game]
 Ed> be an acknowledgement that all this work, if removed, would free up
 Ed> enough time to do the influence calculating in the manner Sunir
 Ed> suggeested.

No, that would allow one *real* influence map a second.  And I didn't propose
this technique.  I just understand it and I think would work.  I don't think
it's the only solution, though.  Perhaps other people have better ideas.  I
had another idea that involved messaging queues and emergent behaviour.

Besides, now I'm just thinking about neat ways to determine influences.

 Ed> is a need for the AI to be as efficient as possible.  I do not believe
 Ed> that using influence maps for pathing, which was the point of this
 Ed> thread, is very efficient.

Probably not.  No need to get in a huff over it, though.  There are better
ways to shoot my ideas down:

    Sunir, boy that was dumb ... you know how slow an influence mapper is?
    Oi, magonnager... try again, Sunny. ;-)

Happy, cheerful, feeds into my neuroses (the plural of 'neurosis' for you
English majors).. perfect.
 
 Ed> Running numbers out here is one thing.  Actually doing it with a cpu,
 Ed> a real game and a user, is totally different.  Often, IMO, the best
 Ed> in theory, must be proven in application.

Maybe, but you still need the theory first.

 Ed> Have you actually implemented your suggestions in a real-time strategy
 Ed> game?  If so, please tell us where we can buy a copy to study.

That was uncalled for.  Bouncing an idea around is the point of newsgroups.

[Ok, I remember what I originally wrote to start of this infl.mapping thread,
but if it was a real solution, I'd be writing a book about it.]

 >assumeing that we can get 10% of the processor
 Ed> In actually testing Enemy Nations, during its year long development,
 Ed> my experience has been that each AI Player (there can be up to 6) is
 Ed> getting less than 1% of the cycles.  Although, this is skewed due to

The difference, here, is that you don't make AI as high as a priority as some
other people. 'Tis your style.

I mean, you could kill things like 24-bit graphics if you wanted good AI.

 Ed> Have you done it?  Has Sunir?

Wasn't my idea.  Wasn't his idea.  I suggest you scan backwards because you've
seem to have missed a few key things.  I can send you the URL of the archive
if you want.

[BTW, if you've been to Steve's pages lately, you'll notice that someone is
actually making an influence mapper so we can guage the time then.]

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

   Sorry I've been unable to hop onto this thread earlier.  My ISP's
news server was down.

sshah@intranet.ca opined thusly:
: To: Edybs@ix.netcom.com
: Subject: Re: Avoiding Other Units

:  Ed> Please do not misrepresent my words.  Here is what I stated:

: *sigh*  Ditto.


   Geez guys... let's not let this get out of hand.


: Eric, I let that one go last time because I figured you'd figure it out
: eventually.  I guess you didn't. I was commenting on the fact that it is
: easily possible to do 33000 adds in one second while mucking around with
: several applications in Windows, which is slow enough, even on my cancer box
: (which I failed to point out is a 486SX25 w/ 4MB RAM).  That practical example
: (failing actually writing the code, which I don't care to do as any game
: programmer could by themselves) indicates that you *can* handle, what?  50
: adds/subs per unit per turn max if you use a simple 5x5..  It's actually less
: (about 25 or so) because you'd use a transparent 'blat.'

: Let's quantify... there are, say, 30 cycles per second (which is the standard
: fps target for most games).  So, for each unit, if its going max out for 30
: cycles, that's 30 * 25 adds/subs/s/unit = 750 operations/s/unit

: How many units do you have?  Let's say 25 (medium theatre ... I'll get back to
: this later).. that's 18750 operations/s, which *is* possible.


   Sure, it's possible, but you don't *get* all those adds to yourself.
The AI gets more like 5% of the CPU time in a typical realtime environment,
so tha's more like 1600 adds *available* *period*.  That ain't much when you've
got pathfinding, production decisions, movement, firing solutions, etc.
to calculate.

   I think I tend to side with Eric....even this "simplified" Influence
Mapping technique is going to end up costing more than I think you
will get out of it in a realtime game.  Now, for a turn-based game
I'd do it in a sec, but that's a different beastie altogether.


: No, that would allow one *real* influence map a second.  And I didn't propose
: this technique.  I just understand it and I think would work.  I don't think
: it's the only solution, though.  Perhaps other people have better ideas.  I
: had another idea that involved messaging queues and emergent behaviour.


   I think an Influence Map for a realtime game might work if it was 
calculated only once a second or so.  That might not be too big a hit and
would provide reasonably good information to the AI.  Eric and I discussed
this briefly at the recent Colorado Computer Game Developer's meeting up
in Denver, but unfortunately didn't get to finish kicking it around.

:  
:  Ed> Running numbers out here is one thing.  Actually doing it with a cpu,
:  Ed> a real game and a user, is totally different.  Often, IMO, the best
:  Ed> in theory, must be proven in application.

: Maybe, but you still need the theory first.


   Again I'll side with Eric on this one.  Theory is all well and good, 
but when something like this runs smack into hard practice the theory
has got to give.

:  Ed> Have you actually implemented your suggestions in a real-time strategy
:  Ed> game?  If so, please tell us where we can buy a copy to study.

: That was uncalled for.  Bouncing an idea around is the point of newsgroups.


   Well he *does* have a point.  The proof is in the implementation.

:  Ed> In actually testing Enemy Nations, during its year long development,
:  Ed> my experience has been that each AI Player (there can be up to 6) is
:  Ed> getting less than 1% of the cycles.  Although, this is skewed due to

: The difference, here, is that you don't make AI as high as a priority as some
: other people. 'Tis your style.


   Not his style as much as the piece he got.  In my current project,
I'm officially allotted 5% of the CPU and 100K of memory.  Today they
asked if they could take some of my CPU cycles away.  *sigh*

: I mean, you could kill things like 24-bit graphics if you wanted good AI.


: [BTW, if you've been to Steve's pages lately, you'll notice that someone is
: actually making an influence mapper so we can guage the time then.]

  Actually I need to ping that guy again for that.  He was cleaning up the
code and planned to get it to me as soon as he'd done that.


Steve
+=============================================================================+
|                                                           _                 |
| 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)     |
|             http://www.cris.com/~swoodcoc/software.html  (AI Software page) |
| Disclaimer: My opinions in NO way reflect the opinions of                   |
|             the Lockheed Martin Information Real3D                          |
+=============================================================================+

To: Edybs@ix.netcom.com
Subject: Re: Avoiding Other Units

 >So what?  Think about it.. you have a zeroed map at the beginning. 
 >Now, for each unit on your side, add the array.  For their side,
 >subtract the array.
 Ed> Then you suggest, that every time a single unit moves, to recalculate
 Ed> the entire influence map?  That's even more processing intense than

No.. at the beginning of the game calc it.  Then you can adjust it as needed.

 >Why?  They aren't moving.  They still have the same influence.
 Ed> I think you are missing the point.  That is, that every time a
 Ed> single unit moves, the influences generated by that single unit,
 Ed> as applied with neighboring units, is changed.  And once changed

I think where we aren't meshing is that you are talking about the real
influencing mapping technique and this technique just quick jimmies one
that'll work.

 Ed> Of course, you might be thinking of a very simplied influence map,

Exactement.

 Ed> I'm not going to hit you <g>, but I am going to suggest you must
 Ed> be considering this is going to run on a P166 with 32MB of memory
 Ed> and a much more efficient OS than something like Win95.  When you

Sure, with a real infl map algy... with this 'SoI' algy, it's much less
intense by several orders of magnitude.

Anyway, you'd use this simple blit technique to determine places of high
intensity instead of true influence mapping.  It's not necessarily accurate,
but it's good enough.

[SoI, infl map prohibitive cuz of speed ...]
 Ed> I have not seen anything in your comments to suggest otherwise,

Well, I don't think this simple blat (block arithmetic transfer... just made
that term up too <G>) will take up too much time.
 
 Ed> and pityfully few cycles that are left over for the AI to do something

That's typical.  Generally, I wouldn't care about infl. mapping or SoI if AI
isn't a high priority.  This stuff is for *really* good opponents... it's all
a matter of choices.  AI, unf, doesn't sell games as well as graphics and
sound.

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

To: David@edvzbb2.ben-fh.tuwien.ac.at
Subject: Re: Avoiding Other Units

 Da> What about using a simple alg. to calc a Sphere-of-Influence for a
 Da> unit, let's say something like Strenght-ABS(Distance) or just a
 Da> precalced array like
[...]
 Da> and just add/sub it when moving a unit. You'd have to store a whole

Hmm.. yeah, I could see this.  It's just like blitting sprites, just a bit
slower.  You'd add it for each unit at the beginning and each time it moves
you'd subtract it from its currect position and add it at its destination.

I like it! :)

'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
'                  Sunir Shah (sshah@intranet.ca)                   '
'  http://intranet.ca/~sshah    ftp://ftp.intranet.ca/usr/synapsis  '
'   Fidonet: 1:241/11   BBS: The Open Fire BBS  +1 (613) 584-1606   '
'                                                                   '
'  By the WEB:  Vanity: http://intranet.ca/~sshah/                  '
'               The Programmers' Booklist         booklist.html     '
'  ~`-,._.,-'~  Synapsis Entertainment            synapsis.html     '
'  _.,-`~'-,._  WASTE (Warfare AI Contest)        waste/waste.html  '
'                                                                   '
' comp.ai.games FAQ: ftp://ftp.intranet.ca/usr/synapsis/cagfaq?.txt '
' The Game Development Echo:  Areafix GAMEDEV from Zone 1 (Fido)    '
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''

___ Blue Wave/QWK v2.12

>> Slipstream Jet - The QWK solution for Usenets #UNREGISTERED

edybs@ix.netcom.com(Eric Dybsand) wrote:

>Where can we see this running John?  I have 486DX250 I can test it
>on.  I'd love to see 70 fps AND a sophisticated AI running on it!

Well, who knows. I just picked up the project again and added some
more features (multiselecting units and adding buildings).

BTW, it needs a local bus computer. It wont run too good on an ISA bus
computer. On my P133 I actually only use 1/3 of the CPU time running
at 70fps (so actually I get 210 fps). And I spot all sorts of
optimization that can be done. Still I wont do any since I will
probably need to redo a lot of the routines to fit new code.

The AI is very very very sparse at the moment. I have to figure out a
good way of keeping track of everything. I've been thinking of setting
up lists of the computer players goals and subgoals. The problem is
that I don't quite yet know what will be implemented in the game so I
have to think out some very general routine for handling AI. This is
not easy at all. 

My idea was to use something like a list of priorities with each
having a value. When the computer recognizes that it needs to produce,
move or other things it adds some value to that list element. Every
n'th ticks I could pick the one with the highest number and execute
that plan (and then subtract some value from the list element).

Somehow I feel that each unit should have a small AI as well so that
the computer don't have to prioritize between all the units movement.
Instead based on some higher level goal, like "move units into area
X", some units will pick up the task and move there. It will be sort
of a bunch of small intelligent agents.

I have to fit some parameters into the AI as well so that I can adjust
it for different gameplay. Some parameters might be: Aggresiveness,
Exploring, Building/Research, Randomness.... I'm trying to work out a
list of the typical progress a human player would do on the game and
use that for finding appropriate parameters.

Just for fun, I actually planned to add a small neural network that
learns about situations on the board. Sort of a pattern recognition
thing where each pattern is the status of the map and an outcome of
some action. Based on this the computer might learn better approaches
to attack the enemy (different angles/weapons).

Well, the list of things to do is huge, and the game engine is getting
pretty good now. Pretty soon I'll be at the point where I can play a
simple game. Adding two player network (IPX) support won't be too
hard, it's obviously the AI that needs the heavy work.... 

Best regards,
John

BTW, I'm a bit embarrased to say this, but I still haven't added any
good pathfinder to the game yet. I need to optimize some of them for
speed... I can't have the pathfinder stalling the game totally. The
one I'm using now is an "enhanced" crash'n turn algorithm (doesn't
handle U-shaped terrain).

------------------------------------------------------------------------------
   John Christian Lonningdal    -    Web: http://www.lis.pitt.edu/~john
 john@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

In <85> john@lis.pitt.edu (John
Christian Lonningdal) writes: 
>
>edybs@ix.netcom.com(Eric Dybsand) wrote:
>
>
>>Where can we see this running John?  I have 486DX250 I can test it
>>on.  I'd love to see 70 fps AND a sophisticated AI running on it!
>
>Well, who knows. I just picked up the project again and added some
>more features (multiselecting units and adding buildings).
>
>BTW, it needs a local bus computer. It wont run too good on an ISA bus
>computer. On my P133 I actually only use 1/3 of the CPU time running
>at 70fps (so actually I get 210 fps). And I spot all sorts of
>optimization that can be done. Still I wont do any since I will
>probably need to redo a lot of the routines to fit new code.
>

Wait a minute! <g>

I thought you posted you got the 70fps on a 486DX266?  Now, with a P133
and maybe 32MB and a single player game with moderate music and sound
and only a single AI player, then yes, there is time to do all sorts
of neat stuff.


>The AI is very very very sparse at the moment. I have to figure out a
>good way of keeping track of everything. I've been thinking of setting
>up lists of the computer players goals and subgoals. The problem is
>that I don't quite yet know what will be implemented in the game so I
>have to think out some very general routine for handling AI. This is
>not easy at all. 
>
>My idea was to use something like a list of priorities with each
>having a value. When the computer recognizes that it needs to produce,
>move or other things it adds some value to that list element. Every
>n'th ticks I could pick the one with the highest number and execute
>that plan (and then subtract some value from the list element).
>
>Somehow I feel that each unit should have a small AI as well so that
>the computer don't have to prioritize between all the units movement.
>Instead based on some higher level goal, like "move units into area
>X", some units will pick up the task and move there. It will be sort
>of a bunch of small intelligent agents.
>
>I have to fit some parameters into the AI as well so that I can adjust
>it for different gameplay. Some parameters might be: Aggresiveness,
>Exploring, Building/Research, Randomness.... I'm trying to work out a
>list of the typical progress a human player would do on the game and
>use that for finding appropriate parameters.
>

You might want to stop by Steve Woodcocks Web page (see his sig) and
check out the description of Enemy Nations AI.  I've implemented what
you have described above, in a multi-player, multi-threaded (which is
part of the problem) environment.

Also, you may want to get ahold of a copy of the proceedings from
the last CGDC this last April.  In there is the lecture notes from
Dr. Walter Tackett, Neuromedia Inc., who presented a 2-part lecture
on "modern AI in games" (what you described and I have implemented).


>Just for fun, I actually planned to add a small neural network that
>learns about situations on the board. Sort of a pattern recognition
>thing where each pattern is the status of the map and an outcome of
>some action. Based on this the computer might learn better approaches
>to attack the enemy (different angles/weapons).
>

I did a neural net for "Parachutes at Kanev" (1988 - World Wide
Wargames) for which I had attempted to determine the best strategic
movement options.  I found that it took simply too long to converge
and for a usefull pattern to emerge.  That was implemented in C code
on a 286/12 with 1MB and EGA graphics.


>Well, the list of things to do is huge, and the game engine is getting
>pretty good now. Pretty soon I'll be at the point where I can play a
>simple game. Adding two player network (IPX) support won't be too
>hard, it's obviously the AI that needs the heavy work.... 
>

Sounds like you're making progress.  I've got to show EN at E3 next
week with the publisher (Viacom) and then it is going to be crunch 
time to ship this summer.

Regards,

Eric Dybsand
Glacier Edge Technology
Glendale, Colorado, USA

>
>BTW, I'm a bit embarrased to say this, but I still haven't added any
>good pathfinder to the game yet. I need to optimize some of them for
>speed... I can't have the pathfinder stalling the game totally. The
>one I'm using now is an "enhanced" crash'n turn algorithm (doesn't
>handle U-shaped terrain).
>

Have you looked at using an A* algorithm?  It and the Dykstra's (Steve
Woodcock is doing some impressive stuff with his modified version of
it) are definitely worth considering for both speed (takes some mods
to the classical approaches to get the speed) and accuracy.