page2.asp.html

一篇关于a*很好的入门文章

                <tr>
                  <td>
                  <table width="100%" border="0" cellspacing="0"
 cellpadding="0">
                    <tbody>
                      <tr valign="top">
                        <td width="24"><img
 src="page2.asp_files/print.gif" width="16" height="16" border="0"
 alt="">&nbsp;</td>
                        <td><a
 href="http://www.gamedev.net/reference/articles/article2003.asp"><font
 color="#ffffff">Printable version</font></a></td>
                      </tr>
                      <tr valign="top">
                        <td width="24"><img
 src="page2.asp_files/discuss.gif" width="16" height="16" border="0"
 alt="">&nbsp;</td>
                        <td><a
 href="http://www.gamedev.net/community/forums/topic.asp?key=featart&amp;uid=2003&amp;forum_id=35&amp;Topic_Title=A%2A+Pathfinding+for+Beginners"><font
 color="#ffffff">Discuss this article</font></a></td>
                      </tr>
                    </tbody>
                  </table>
                  </td>
                </tr>
              </tbody>
            </table>
            <br>
<!-- Begin Ban Man Pro Banner Code -  Zone: GameDev.net Skyscraper -->
            <script language="JAVASCRIPT">
<!--
var browName = navigator.appName;
var browDateTime = (new Date()).getTime();
var browVersion = parseInt(navigator.appVersion);
var ua=navigator.userAgent.toLowerCase();
var adcode='';
if (browName=='Netscape'){
     if (browVersion>=5) 
          { document.write('<ifr'+'ame src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Browser=NETSCAPE6&X=' + browDateTime + '" width=160 height=600 Marginwidth=0 Marginheight=0 Hspace=0 Vspace=0 Frameborder=0 Scrolling=No></ifr'+'ame>'); }
     else if ((browVersion>=4)&&(ua.indexOf("mac")==-1))
          { document.write('<S'+'CRIPT src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Browser=NETSCAPE4">');
          document.write('</'+'scr'+'ipt>');
          document.write(adcode); }
     else if (browVersion>=3) 
          { document.write('<A HREF="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Click&Mode=HTML&PageID=' + browDateTime + '&RandomNumber=' + browDateTime + '" target="_new"><IMG SRC="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Mode=HTML&PageID=' + browDateTime + '&RandomNumber=' + browDateTime + '" width="160" height="600" border="0"></A>'); } }
if (browName=='Microsoft Internet Explorer')
     { document.write('<ifr'+'ame src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&X=' + browDateTime + '" width=160 height=600 Marginwidth=0 Marginheight=0 Hspace=0 Vspace=0 Frameborder=0 Scrolling=No></ifr'+'ame>'); }
// --> 
            </script><iframe
 src="page2.asp_files/banman_002.htm" width="160" height="600"
 marginwidth="0" marginheight="0" hspace="0" vspace="0" frameborder="0"
 scrolling="no"></iframe>
            <noscript> <a
href="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Click&Mode=HTML&PageID=63428"
target="_new"> <img
src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Mode=HTML&PageID=63428"
width="160" height="600" border="0"></a> </noscript>
<!-- End Ban Man Pro Banner Code -  Zone: GameDev.net Skyscraper --> </td>
          </tr>
        </tbody>
      </table>
      </p>
      <h1>路径排序</h1>
      <p>找到形成路径的方块的关键是下面的等式：<br>
      </p>
      <p>F = G + H</p>
      <p>这里<br>
      </p>
      <ul>
        <li>G = 从<span style="text-decoration: underline;">开始</span>点A到格
子中<span style="text-decoration: underline;">给定</span>方块的移动代价，沿着到达该方块而生成的
那个路径。</li>
        <li>H = 从格子中<span style="text-decoration: underline;">给定</span>的
方块到<span style="text-decoration: underline;">最终目标</span>B点的评估移动代价。这种方式通
常称作试探法，有点让人混乱。因为这是一个猜测，所以得到这个称谓。在找到路径之前，我们真的不知道实际的距离，因为途中有各种东西（墙，水，等等）。
在本教程里给出了一种计算H的方法，但在网上你能找到很多其他的文章。</li>
      </ul>
      <p>我们需要的路径是这样生成的：反复的遍历开放列表，选择具有最小F值的方块。这个过程在本文稍后会详细描述。先让我们看看如何计算前面
提到的等式。<br>
      </p>
      <p>如上所述，G是经由到达它的路径，从开始点到给定方块的移动代价。在本例中，我们为每个水平/垂直的移动指定代价为10，而斜角的移动
代价为14。我们使
用这些值，因为斜角移动的实际距离是2的平方根（别害怕），或者大概1.414倍的水平/垂直的移动代价。出于简化的目的使用了10和14。比例大致是正
确的，而我们却避免了方根和小数的计算。倒不是我们没有能力做或者不喜欢数学。使用这些数字也能让计算更快一些。以后你就会发现，如果不使用这些技巧，寻
路的计算非常慢。<br>
      </p>
      <p>既然我们沿着到达给定方块的路径来计算G的值，找出那个方块的G值的方法就是找到其父亲的G值，再加上10或者14而得，这依赖于他处
于其父亲的斜角或者
直角（非斜角）而定。这在本例后面会更加清晰，随着我们从开始点离开而得到更多的方块。<br>
      </p>
      <p>H能通过多种方法估算。我们这里用到的方法叫做Manhattan方法，计算从当前方块经过水平/垂直移动而到达目标方块的方块总数。
然后将总数乘以
10。这种方法之所以叫做Manhattan方法，因为他很象计算从一个地点到达另一个地点的城市街区数量计算，此时你不能斜向的穿越街区。重要的是，当
计算H的时候，要忽略任何路径中的障碍。这是一个对剩余距离的<span style="text-decoration: underline;">估
算值</span>，而不是实际值，这就是试探法的称谓由来。想知道更多？关于试探法的更多说明<a
 href="http://www.policyalmanac.org/games/heuristics.htm">在这里</a>。<br>
      </p>
      <p>G和H相加就算出了F。第一步搜索的结果见下图的描述。F，G，和H值都写入了每个方块。如开始方块相邻右边的方块，F显示在左上方，
G显示在左下方，而
H显示在右下方。<br>
      </p>
      <p class="caption"><img border="0" width="362" height="256"
 src="page2.asp_files/image003.jpg"> <br>
[图 3]</p>
      <p>好，让我们来观察某些方块。在有字母的方块中，G =
10。这是由于在水平方向上从开始点（到那里）只有一个方块（的距离）。开始点相邻上方，下方和左边的方块都具有同样的G值：10。斜角的方块G值为
14。<br>
      </p>
      <p>H的计算通过估算Manhattan距离而得，即：水平/垂直移动，忽略途中的障碍，到达红色的目标方块的距离。用这种方法，开始点相
邻右边的方块和红色
方块相距3个方块，那么H值就是30。其上的方块距离为4（记住，只能水平或者垂直移动），H就是40。你也许可以看看其他方块的H值是如何算出的。<br>
      </p>
      <p>每个方块的F值，再说一下，不过就是G和H相加。<br>
      </p>
      <h1>持续的搜索</h1>
      <p>为了继续搜索，我们简单的选择开放列表里具有最小F值的方块。然后对选定的方块做如下操作：<br>
      </p>
      <ol start="4">
        <li>将他从开放列表取出，并加入封闭列表。</li>
        <li>测试所有的相邻方块。忽略封闭列表内的和不可行走的（墙，水及其它非法地形）方块，如果方块不在开放列表中，则添加进去。将选定
方块作为这些新加入方块的父亲。</li>
        <li>如果一个相邻方块已经存在于开放列表，检查到达那个方块的路径是否更优。换句话说，检查经由当前方块到达那里是否具有更小的G
值。如果没有，不做任何事。<br>
相反，如果新路径的G值更小，把这个相邻方块的父亲改为当前选定的方块（在上图中，修改其指针方向指向选定方块）。最后，重新计算那个方块的F和G值。如
果这样还是很迷惑的话，后面还会有图解说明。</li>
      </ol>
      <p>好了，让我们看看它是怎样工作的。在初始的9个方块中，当开始方块被纳入封闭列表后，我们的开放列表就只有8个方块了。在这些块中，具
有最小F值的是开始
方块相邻右边的那个，其F值为40。所以我们选定这个块作为下一个方块。在随后的图例中，它以高亮的蓝色表示。<br>
      </p>
      <p class="caption"><img border="0" width="357" height="256"
 src="page2.asp_files/image004.jpg"> <br>
[图 4]</p>
      <p>首先，我们把它从开放列表取出，并加入到封闭列表（这就是它现在是高亮的蓝色的原因）。然后我们检查相邻的方块。然而，这个方块相邻右
边的是代表墙的方
块，所以忽略它们。其相邻左边是开始方块。它处于封闭列表内，所以也忽略它<br>
      </p>
      <p>其它4个已经在开放列表中了，所以我们需要检查经由当前方块到达他们是否是更优的路径，使用G值为参考点。我们来看看这个选定方块上面
右边的那个方块。它
的当前G值是14。如果我们经由当前方块到达那里，G值将是20（10，到达当前方块的G值，再加上10垂直移动到它上面的方块）。20 &gt;
14，所以这不是一个好的路径。看看图解能更好的理解这些。从开始方块斜向移动到那个方块更直接，而不是水平移动一个方块，再垂直移动一个方块。<br>
      </p>
      <p>当我们对已经存在于开放列表的所有4个相邻方块都重复这个过程，我们发现经由当前方块没有更佳的路径，所以什么也不用改变。现在看看所
有的相邻方块，我们
已经处理完毕，并准备移动到下一个方块。<br>
      </p>
      <p>现在，我们再遍历开放列表，它只有7个方块了，选择具有最小F值的那个。有趣的是，此时有两个方块都有值54。那么我们选择哪个？实际
上这不算什么。为了
速度的目的，选择你最后加入到开放列表的那个方块更快。当你更接近目标的时候，它倾向于后发现的方块。但这真的没什么关系。（不同的处理造成了两
个版本的A*可能找到不同的等长路径。）<br>
      </p>
      <p>我们选择下面的那个，位于开始方块的右边，如下图所示。<br>
      </p>
      <p class="caption"><img border="0" width="357" height="254"
 src="page2.asp_files/image005.jpg"> <br>
[图 5]</p>
      <p>这一次，当检查相邻的方块时，我们相邻右边的是一个墙方块，所以忽略它。对那个方块上面的块同样忽略。我们也忽略墙下面的方块。为什
么？因为你不把临近墙
的角切开就无法直接到达那个方块。实际上你需要先向下走，然后越过那个方块，在这个过程中都是围绕角在移动。（说明：切开角的规则是可选的。它的使用依赖
于你的节点如何放置。）<br>
      </p>
      <p>这样就剩下5个方块了。当前方块下的两个方块不在开放列表中，所以要添加他们，并把当前方块作为它们的父亲。在另外三个方块中，有两个
已经在封闭列表中了
（开始方块，和当前方块上面的那个，它们都用高亮的蓝色在图中标出来了），所以忽略它们。最后一个方块，当前方块相邻左边的那个，检查经由当前方块到达那
里是否得到更小的G值。没有。所以处理完毕，并准备检查开放列表中的下一个方块。<br>
      </p>
      <p>我们重复这个过程，直到把目标点添加到开放列表，此时的情形如下图所示。<br>
      </p>
      <p class="caption"><img border="0" width="404" height="307"
 src="page2.asp_files/image006.jpg"> <br>
[图 6]</p>
      <p>注意开始方块向下的第二个方块，在前面的描述中其父亲已经发生改变。开始它的G值为28，指向其右上角的方块。现在它的值是20，指向
其上方的方块。这是
在搜索方法中某处发生的吗？在那里G值被检查，而且使用新的路径后，它得到了更小的值。所以它的父亲切换了，G和F也重新计算。而这个改变在本例中不见得
非常重要，还有足够多的可能位置，在决定最佳路径的时候，持续的检查会产生各种差别。<br>
      </p>
      <p>那么我们怎样决定实际的路径呢？简单，从红色目标方块开始，向后移动到它的父亲，跟从箭头的指示。最终你会回到开始方块，这就是路径！
它应该如下图所示。
从方块A移动到目标方块B就是从每一个方块（节点）的中心移动到路径上的下一个方块的中心的简单过程，直到到达目标。简单！<br>
      </p>
      <p class="caption"><img border="0" width="411" height="308"
 src="page2.asp_files/image007.jpg"> <br>
[图 7]</p>
      <br>
      <br>
      <br>
      <p align="right"><b><a href="page3.asp.html"><img
 src="page2.asp_files/pointernext.gif" width="62" height="35" border="0"
 alt="" align="right"> <br>
A*方法汇总</a></b></p>
      </td>
    </tr>
  </tbody>
</table>
<p align="center">
<a href="http://www.gamedev.net/info/about">About Us</a> | <a
 href="http://www.gamedev.net/info/media/">Advertise on GameDev.net</a>
| <a href="http://www.gamedev.net/info/writers.asp">Write for us</a><br>
&#169; 1999-2004 Gamedev.net. All rights reserved. <a
 href="http://www.gamedev.net/info/legal.htm#copyright"><u>Terms of Use</u></a>
<a href="http://www.gamedev.net/info/legal.htm#privacy"><u>Privacy
Policy</u></a>
<br>
<span class="maintext-1">Comments? Questions? Feedback? <a
 href="http://www.gamedev.net/info/faq.asp">Click here!</a>&nbsp;&nbsp;&nbsp;&nbsp;GameDev.net
is Powered By <a
 href="http://www.nieropwebconsult.nl/asp_session_manager.htm">ISP
Session</a></span>
<br>
<span class="maintext-2">GameDev.net<sup>TM</sup>, the GameDev.net
logo, and GDNet<sup>TM</sup> are trademarks of GameDev.net, LLC</span><br>
</p>
</body>
</html>