RE: [Algorithms] RTS Dynamic obstacles path-finding

[Richard S. <Ric...@ei...>]

To avoid the 'approach then turn' type of ugly behaviour,
you can calculate the path ahead, then do a quick line-of-sight
optimisation, removing all nodes you can currently see directly
except the last one. This should give you a more sensible journey=20
start though it does have a memory overhead and a spike in=20
processing rather than a continuous tiny overhead.

Another possible solution at this level might be repulsion,
a specialised version of Reynolds' flocking behaviours. It's
a little tricky to balance and you can still get stuck in local
minimas, like your situation below, but this can also be handled
intelligently.

The problem is that to go beyond this kind of reactive behaviour
you start moving into the arena of graph solving. Graph solving
(notably A*) is a very powerful way of making extremely intelligent
looking paths which use terrain features very well. But this kind
of thing needs to be built into your AI architecture and data
production pipeline ffrom the beginning - bolting it on later
is painful and nothing like as effective. Also has a high data
production overhead or a nasty algorithm problem, depending on
whether you create your search space by hand or in code.

There are good discussion of these methods in "Game Programming
Wisdom 1&2", also some good A* articles in the "Game Programming=20
Gems" series. Every games dev company should own these books.

Which solution you actually use depends very much on the specifics=20
of the situation. This is one of the most complex AI problems you
will face in an RTS and also one of the most important to get right.
A genius AI will still look bad if the units move in a stupid way.
Spend the time researching, it will stand you in good stead later.

Rich


> A quick navigation method is "wall hugging" - the unit plans=20
> to go straight
> for the target. If/when it hits something, it traces around=20
> the edge of the
> obstacle both ways until it can head directly for the target=20
> again, then it
> picks the way that takes the least time before it can go direct again
> (though there might still be things in the way of course).
>=20
> This does not produce the best path by any means, but it is=20
> pretty robust,
> gets good results, and is pretty quick to run. Bear in mind that when
> talking about "intelligent" units, perfect routes are not only
> computationally expensive, they are also unrealistic - that's=20
> why we have
> maze puzzles :-) So anything that is quite good and robust is=20
> all you really
> need.
>=20
> TomF.
>=20
> > -----Original Message-----
> > From: gda...@li...=20
> > [mailto:gda...@li...] On=20
> > Behalf Of Wessam Bahnassi
> > Sent: 09 February 2004 08:40
> > To: gda...@li...
> > Subject: [Algorithms] RTS Dynamic obstacles path-finding
> >=20
> >=20
> > In an RTS game, based on a Points-of-View path-finding algorithm for
> > static obstacles, we're stuck in the following scenario:
> >=20
> > ----------------------
> >=20
> >          SSSSS
> > Start      SS     Goal
> >           SS SS
> >=20
> > ----------------------
> >=20
> > A unit has to make its path from "Start" to "Goal", while there is a
> > group of units (marked by "S") in standing state blocking the=20
> > way (as in
> > the diagram above).
> > What would be the best method to detect the shortest path=20
> that doesn't
> > collide with those existing units?
> >=20
> > While observing Warcraft3, I noticed that the unit tries to=20
> > go directly
> > to the goal until it collides with a standing unit, then it=20
> > changes its
> > path to get around. Such behavior is good for me, but I=20
> don't know the
> > best way to implement it. My Points-of-View algo didn't work here
> > (performance reasons), so I'll have to make some special algo for
> > dynamic obstacle path finding. I have a grid representation=20
> of the map
> > that I plan to utilize for this problem.
> > Any thoughts on how this can be implemented?
> >=20
> > Wessam Bahnassi
> > Microsoft DirectX MVP
> > Lead Programmer
> > In|Framez
>=20
>=20
>=20
>=20
>=20
> -------------------------------------------------------
> The SF.Net email is sponsored by EclipseCon 2004
> Premiere Conference on Open Tools Development and Integration
> See the breadth of Eclipse activity. February 3-5 in Anaheim, CA.
> http://www.eclipsecon.org/osdn
> _______________________________________________
> GDAlgorithms-list mailing list
> GDA...@li...
> https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
> Archives:
> http://sourceforge.net/mailarchive/forum.php?forum_ida88
>=20