📄 gamedev.net -- a pathfinding for beginners.html

📁 一篇关于a*很好的入门文章
💻 HTML
📖 第 1 页 / 共 2 页
字号:
上一页 12
 width="100%">
                    <tbody>
                      <tr valign="top">
                        <td width="7"><img
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/dotsm.gif"
 width="7" height="6" border="0" alt="">&nbsp;</td>
                        <td><a
 href="http://www.gamedev.net/reference/programming/features/astar/default.asp"><font
 color="#ffffff">Introduction</font></a></td>
                      </tr>
                      <tr valign="top">
                        <td><img
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/dotsm.gif"
 width="7" height="6" border="0" alt="">&nbsp;</td>
                        <td><a
 href="http://www.gamedev.net/reference/programming/features/astar/page2.asp"><font
 color="#ffffff">Path Scoring</font></a></td>
                      </tr>
                      <tr valign="top">
                        <td><img
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/dotsm.gif"
 width="7" height="6" border="0" alt="">&nbsp;</td>
                        <td><a
 href="http://www.gamedev.net/reference/programming/features/astar/page3.asp"><font
 color="#ffffff">Summary of the A* Method</font></a></td>
                      </tr>
                    </tbody>
                  </table>
                  </td>
                </tr>
              </tbody>
            </table>
            <br>
            <table width="100%" border="0" cellspacing="2"
 cellpadding="4" class="featmenu">
              <tbody>
                <tr>
                  <td>
                  <table width="100%" border="0" cellspacing="0"
 cellpadding="0">
                    <tbody>
                      <tr valign="top">
                        <td width="24"><img
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_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="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_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="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_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=29334"
target="_new"> <img
src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Mode=HTML&PageID=29334"
width="160" height="600" border="0"></a> </noscript>
<!-- End Ban Man Pro Banner Code -  Zone: GameDev.net Skyscraper --> </td>
          </tr>
        </tbody>
      </table>
      </p>
      <p>虽然掌握了A*（读作A-star）算法就认为它很容易，对于初学者来说，它却是复杂的。网上有很多解释A*的文章，不过大多数是写给
理解了基础知识的
人。本文是给初学者的。<br>
      </p>
      <p>本文并不想成为关于这个主题的权威论文。实际上它讨论了基础知识并为你做一些准备，以便进一步阅读其他资料和理解它们讨论的内容。本文
的后面列出了几个最
好的文章，在进阶阅读中。<br>
      </p>
      <p>最后，本文不是编程规范的。你应该能够改写这里的东西到任何计算机语言上。如你所期望的，同时，我包含了一个示例程序的链接，在本文后
面结束的地方。这个
程序包有两个版本：一个是C++，另一个用Blitz Basic语言编写。如果你只是想看看A*的行为，里面也含有可执行exe文件。<br>
      </p>
      <p>但我们要超越自己。让我们从头开始 ...<br>
      </p>
      <h1>介绍：搜索区域</h1>
      <p>我们假设某人想从A点到达B点，一堵墙把它们分开了。如下图所示，绿色是开始点A，红色是结束点B，而蓝色填充的方块是中间的墙。<br>
      </p>
      <p class="caption"><img border="0" width="362" height="256"
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/image001.jpg">
      <br>
[图 1]</p>
      <p>你应该注意的第一件事是，我们把搜索区域分割成了方块的格子。简化搜索区域，如你目前完成的那样，这是寻路的第一步。这个特殊方法把搜
索区域简化成了一个
二维数组。数组的每一个项目代表了格子里的一个方块，它的状态记录成可行走和不可行走。通过计算出从A到达B应该走哪些方块，就找到了路径。一旦路径找
到，我们的人从一个方块的中心移动到下一个方块的中心，直到抵达目标。<br>
      </p>
      <p>这些中心点称作“节点”。当你在其它地方阅读关于寻路时，你将经常发现人们讨论节点。为什么不直接把它们认为是方块呢？因为有可能你要
把你的寻路区域以非
方块的东西来分割。它们可能是矩形，六角形，或任何形状，真的。而节点可以放到形状内的任何位置。在中心，或者沿着边缘，或其它地方。然而我们使用这个
系统，因为它最简单。<br>
      </p>
      <h1>开始搜索</h1>
      <p>一旦我们把搜索区域简化成了可以管理的大量节点，就象我们上面所做的那样采用格子的布局，下一步就是引导一个搜索来找出最短路径。在
A*寻路的做法，我们
从开始点A做起，检查它周围的方块，并且向外普通的搜索，直到找到目标。<br>
      </p>
      <p>我们这样开始搜索：<br>
      </p>
      <ol>
        <li>从开始点A起，添加它到待考虑的方块的“开放列表”。开放列表有点象购物列表。此时只有一个项目在里面，但很快我们会得到更多。
它包含了你可能取用的沿途的方块，也可能不用它。基本上，这是需要检查的方块的列表。<br>
        </li>
        <li>观察开始点邻近的所有可到达或可行走的方块，忽略有墙，水或其他非法地形的方块。也把它们添加到开放列表。对每一个方块，保存A
点作为它们的“父亲”。这个父亲方块在跟踪路径时非常重要。后面会更多的解释。<br>
        </li>
        <li>把开始方块A从开放列表中取出，并放到“封闭列表”内，它是所有现在不需要再关注的方块的列表。<br>
        </li>
      </ol>
      <p>在此，你应该有了类似下图的东西。在这个图中，中间的深绿色的方块就是开始方块。它有浅蓝色的外框，表示它被添加到封闭列表了。所有的
相邻方块现在都进入
要检查的方块的开放列表中了，它们有浅绿的外框。每一个都有灰色的指针指回它的父亲，它就是开始方块。<br>
      <br>
      </p>
      <p class="caption"><img border="0" width="151" height="150"
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/image002.jpg"><br>
[图 2]</p>
      <p>下一步，我们从开放列表中，选出一个相邻的方块，然后多多少少重复早先的过程，下面会说到。但是我们选择哪一个呢？具有最小F值的那
个。<br>
      </p>
      <br>
      <br>
      <br>
      <p align="right"><b><a href="page2.asp.html"><img
 src="GameDev.net%20--%20A%20%20Pathfinding%20for%20Beginners_files/pointernext.gif"
 width="62" height="35" border="0" alt="" align="right"> <br>
路径排序</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>
上一页 12
💿 文件大小 497 K
👤 上传用户 KuFly
📂 所属分类文章/文档
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -