📄 unitavoid.htm
字号:
<!--Header-->
<HTML>
<HEAD>
<TITLE>GPMega - Advanced Section - Avoiding Units & Path Recalculation</TITLE>
<META NAME="DESCRIPTION" CONTENT="An important feature of any pathfinding system is it's ability to compensate for moving object and blocked paths. This article covers the techniques needed to handle those events and the methods needed to recalculate your paths quickly.">
</HEAD>
<BODY BGCOLOR=#000000 TEXT=#FFFFFF LINK=#00FF00 VLINK=#00FF00 ALINK=#0000FF>
<!--End Header-->
<!--Advertiser-->
<CENTER>
<TABLE>
<TR>
<TD>
<A HREF="http://www.ugo.com/">
<IMG SRC="/GPMega/ugologo120.gif" BORDER=0 WIDTH=120 HEIGHT=60></A>
</TD>
<TD>
<IMG SRC="/GPMega/sponsored.gif" WIDTH=468 HEIGHT=10><br><br>
<SCRIPT LANGUAGE= "JavaScript">
<!--
var now = new Date();
var random_num = now.getSeconds();
document.write("<A HREF='http://www.ugo.net/RealMedia/ads/click_nx.cgi/www.perplexed.com/GPMega/advanced/unitavoid.htm/" + random_num + "/@Top'>");
document.write("<IMG SRC='http://www.ugo.net/RealMedia/ads/adstream_nx.cgi/www.perplexed.com/GPMega/advanced/unitavoid.htm/" + random_num + "/@Top' BORDER='0' WIDTH='468' HEIGHT='60'></A>");
//-->
</SCRIPT>
</TD>
</TR>
</TABLE>
</CENTER>
<!--End Advertiser-->
<!--Splitter-->
<BR>
<!--End Splitter-->
<!--Body-->
<FONT SIZE=2 FACE=Helvetica>
<STRONG>
<!--Top Navigation-->
<A NAME="top"></A>
<CENTER>
<TABLE WIDTH=75%>
<TR VALIGN=MIDDLE>
<TD ALIGN=LEFT>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1><BR><BR>
<A HREF="http://www.perplexed.com/GPMega/"><IMG SRC="logo.jpg" BORDER=0 ALT="Home" WIDTH=80 HEIGHT=47 ALIGN=CENTER></A>
<FONT COLOR=#666666 FACE=HELVETICA SIZE=-1><I>
This Article Is Taken From <A HREF="http://www.perplexed.com/GPMega/">The Game Programming MegaSite</A>, A Definitive Resource For Game Developers!
</I></FONT><BR>
<IMG SRC="gradsplit2.jpg" WIDTH=100% HEIGHT=1>
</TD>
</TR>
</TABLE>
</CENTER>
<BR><!--End Top Navigation-->
<!--Title-->
<H3 ALIGN=CENTER><font color="#FFF800">A</font><font color="#FFF100">v</font><font color="#FFEA00">o</font><font color="#FFE300">i</font><font color="#FFDC00">d</font><font color="#FFD500">i</font><font color="#FFCE00">n</font><font color="#FFC700">g</font><font color="#FFC000"> </font><font color="#FFB900">U</font><font color="#FFB200">n</font><font color="#FFAB00">i</font><font color="#FFA400">t</font><font color="#FF9D00">s</font><font color="#FF9600"> </font><font color="#FF8F00">&</font><font color="#FF8800"> </font><font color="#FF8100">P</font><font color="#FF7A00">a</font><font color="#FF7300">t</font><font color="#FF6C00">h</font><font color="#FF6500"> </font><font color="#FF5E00">R</font><font color="#FF5700">e</font><font color="#FF5000">c</font><font color="#FF4900">a</font><font color="#FF4200">l</font><font color="#FF3B00">c</font><font color="#FF3400">u</font><font color="#FF2D00">l</font><font color="#FF2600">a</font><font color="#FF1F00">t</font><font color="#FF1800">i</font><font color="#FF1100">o</font><font color="#FF0A00">n</font><BR><FONT SIZE=-2>By: <A HREF="mailto: john@lis.pitt.edu">john@lis.pitt.edu</A></FONT></H3>
<!--End Title-->
<P>In a real time environment avoiding other units can be a hard
nut to crack. Generally considering dynamic modifications on the
map can bog down a pathfinder. Important issues like when do
we really want to recalculate a units path has to be answered.
For example, what should we do when some earlier blocking terrain
is blown away and this makes a possible path much shorter for a unit.
A unit that has already evaluated a path before this modification and
started moving will un-intelligently continue on its long path around
the obstacle. Recalculating all moving units paths after a modification
comes to mind, but in a realtime environment this will be extremely
timeconsuming. Unfortunately there is no good solution to all the problems
that come up. Still, small additions to the pathfinder can help a lot.
<P>When is a unit an obstacle? Imagine some unit trying to find a path
from A to B and has to avoid lots of other units. We could make some
assumptions on what units really are obstacles. First we could drop
all moving units as obstacles as the chance of them stopping exactly
in the path is minimal. Units standing still should however be considered
obstacles and avoided.
<P>Still, some units that are moving will probably stop in the units path
so that some quick pathfinding should be done when something new is
in the units way. An easy way would be to try to find an immediately
connecting position that will take the unit to the second next
position in its path. The unit 1 below is trying to move along the
"asterisked" line but unit 2 is blocking:
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
1*2*** -> 12*** -> 12***
*
unit moving - obstructed - found connecting tile
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER>
<p>The above algorithm should be pretty easy to implement and
will avoid a lot of recalculation.
<P>When you are using a path defined by waypoints like the ones
found in the direct line pathfinder you have an advantage when
recalculating paths. If e.g. the unit couldn't find an immediately
connecting tile because it was blocked by several units, it could
try to just recalculate a new path to the next waypoint instead
of the whole path. This will reduce the distance of the recalculation.
You should however have some kind of timeout feature that if the
pathfinder didn't reach the waypoint after some steps relative to the
distance to the waypoint, you should continue the pathfinding a
all the way to the units end. This will ensure that the unit is not
using a lot of time finding a path to a waypoint when it maybe has
a much better path available. You could however keep the old waypoints,
and if any of these are reached in the new path you just keep old ones
from there and the new path is found.
<P>To avoid a lot of recalculation of paths when changes are done
to the terrain (e.g. a wall is blown away) you could eliminate
all those units moving away from the change. This is easily done
by calculating the angle between the lines from the unit to its
goal and from the unit to the change of terrain. You can then choose
e.g. that for angles lower than 90 degrees that units path is totally
recalculated.
<P>To make units behave more intelligent you should often think of real
world examples. An example is when a wall is blown away by friendly
units, it is often to make some of its own units pass. This event could
be notified to all friendly units (if they have some sort of communication
that is) so that they will find a new path. Another example of such
real world AI is to inform a friendly unit that it should move away if
it blocks from another friendly unit. This is common sense and should be
pretty easy to implement. Together with the immediately-connecting-tile
scheme above, much more intelligent movement is generated. Also making
a lot of pathfinder flags for each unit can limit the amount of
recalculation. These flags can then represent concepts that had to be
taken into consideration when the pathfinder was evaluating. E.g. the
concept "a wall was obstructing" could be set for that particular unit
and when a wall is blown away all those units with this flag set will
be evaluated.
<P>All these additions will make the unit behave a bit more intelligently
but each of them will steal some more CPU time. It might be that one
should rather concentrate on optimizing the pathfinder so that
reevaluation isn't that costly. A combination will probably produce
the best results.</P>
<!--Bottom Navigation-->
<A NAME="bottom"></A>
<!--End Bottom Navigation-->
</STRONG>
</FONT>
<!--End Body-->
<!--Bottom-->
<BR>
<IMG SRC="gradbar.jpg">
<BR>
<FONT SIZE=2 COLOR=#8B8B8B FACE=Helvetica>
<I><font color="#FBFBFB">T</font><font color="#F7F7F7">h</font><font color="#F3F3F3">e</font><font color="#EFEFEF"> </font><font color="#EBEBEB">G</font><font color="#E7E7E7">a</font><font color="#E3E3E3">m</font><font color="#DFDFDF">e</font><font color="#DBDBDB"> </font><font color="#D7D7D7">P</font><font color="#D3D3D3">r</font><font color="#CFCFCF">o</font><font color="#CBCBCB">g</font><font color="#C7C7C7">r</font><font color="#C3C3C3">a</font><font color="#BFBFBF">m</font><font color="#BBBBBB">m</font><font color="#B7B7B7">i</font><font color="#B3B3B3">n</font><font color="#AFAFAF">g</font><font color="#ABABAB"> </font><font color="#A7A7A7">M</font><font color="#A3A3A3">e</font><font color="#9F9F9F">g</font><font color="#9B9B9B">a</font><font color="#979797">S</font><font color="#939393">i</font><font color="#8F8F8F">t</font><font color="#8B8B8B">e</font> - ⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -