📄 crashnturn.htm
字号:
<!--Header-->
<HTML>
<HEAD>
<TITLE>GPMega - Advanced Section - Crash 'n Turn Pathfinding</TITLE>
<META NAME="DESCRIPTION" CONTENT="John's continuing pathfinding series, this one covering a simple 'if you hit something.... turn and continue' pathfinding algorithm. Easy to implement and test.">
</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/crashnturn.htm/" + random_num + "/@Top'>");
document.write("<IMG SRC='http://www.ugo.net/RealMedia/ads/adstream_nx.cgi/www.perplexed.com/GPMega/advanced/crashnturn.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="#FFF500">C</font><font color="#FFEB00">r</font><font color="#FFE100">a</font><font color="#FFD700">s</font><font color="#FFCD00">h</font><font color="#FFC300"> </font><font color="#FFB900">'</font><font color="#FFAF00">n</font><font color="#FFA500"> </font><font color="#FF9B00">T</font><font color="#FF9100">u</font><font color="#FF8700">r</font><font color="#FF7D00">n</font><font color="#FF7300"> </font><font color="#FF6900">P</font><font color="#FF5F00">a</font><font color="#FF5500">t</font><font color="#FF4B00">h</font><font color="#FF4100">f</font><font color="#FF3700">i</font><font color="#FF2D00">n</font><font color="#FF2300">d</font><font color="#FF1900">i</font><font color="#FF0F00">n</font><font color="#FF0500">g</font><BR><FONT SIZE=-2>By: <A HREF="mailto: john@lis.pitt.edu">john@lis.pitt.edu</A></FONT></H3>
<!--End Title-->
<P>This is probably the easiest one to implement and was the first one I
implemented in my Prisoner of War project. This is an algorithm that
evaluates the way one step at a time. Trying to move in a straight line
to the endpoint direction and adjusting the rules as it goes. As most of
you already know, this is not a good way of solving it. The unit will
behave odd, choosing silly path's. Sometimes it will get locked up in a
loop. Anyway, here is how I implemented it:
<ol>
<li>Try to move in a straight line to the endpoint. Always remember the
previous tile coordinates. (One brain-cell).
<li>If it collides with an obstacle (landscape or other unit) try the
RIGHT_HAND rule. Rotating right until a free passage is found and then
move to that tile.
<li> Repeat 1-2 until the goal is reached or a collision with the previous
tile occurs.
<li> If we collided with our previous position (trying to go back to the
last tile we came from) try changing to a LEFT_HAND rule instead. Then
follow the same procedure above (using a LEFT_HAND rule instead of
RIGHT_HAND).
</ol>
<P>The last point can be changed to say it should not be able to go back
into it's previous tracks. This way it will continue using the RIGHT_HAND
rule all the way.
<P>The algorithm is not very good and gets easily locked up. Especially in
the U-formed obstacle example.
<P>The crash'n turn algorithm can be further enhanced to make the unit behave a bit
more intelligent. I.e. look at the below example:
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
########
########### A
###########
###########
###########
#######
B
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER>
<P>Our unit wants to go from A to B. We can easily see the best way will be
to use a LEFT_HAND rule to reach the goal. Our initial algorithm will
always use a RIGHT_HAND rule first. This will look silly, as it will take
the other way around the obstacle.
<P>By modifying the algorithm a bit we can decide which rule we should start
using. Imagine yourself wanting to go past the obstacle. You would
probably think something like: Lets follow the edge until we reach the
corner and then move towards the endpoint B. Okay, you naturally chose a
LEFT_HAND rule.
<P>This is what we do: Alternate between RIGHT_HAND and LEFT_HAND scanning on
the first obstacle you meet. The first one that gives a free path tells
you which rule to use. This way the routine will probably choose a
smarter rule to start with based on it's angle to the destination point.
It will of course fail on difficult terrain and the same loop problems
are quite evident in this implementation also.
<P>Here is another example, it will choose the LEFT_HAND rule because it
saw that the left edge was free. It will choose the same path from B to A
also:
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
***********
A**###########**B
###########
###########
###########
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER>
<P>On the example below it will fail to behave intelligently because the scanning found
the right to be the first free path:
<CENTER><P><TABLE WIDTH=65% CELLPADDING=0 CELLSPACING=0>
<TR><TD>
<TABLE><TR><TD>
<PRE><FONT COLOR=#FF0000 FACE=Courier SIZE=2>
######
A***###### B
*###### *
**###### *
*###########*
*###########*
**#######**
*******
</FONT></PRE>
</TD></TR></TABLE>
</TD></TR>
</TABLE></CENTER>
<!--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 + -