gamedev.net -- a pathfinding for beginners.html

实现人工智能中的AI自动寻找路径

          <tr>
            <td align="center">
            <table width="100%" border="0" cellspacing="2"
 cellpadding="4">
              <tbody>
                <tr>
                  <td valign="top" class="boxheadr">Contents</td>
                </tr>
                <tr>
                  <td valign="middle" class="featmenu">
                  <table cellspacing="0" cellpadding="0" border="0"
 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 class="maintext-1"><i>This article has been translated into <a
 href="http://elthanar.iespana.es/elthanar/tutoriales/articulo1.htm">Spanish</a>
and <a href="http://www.lalex.com/blog/detail.php?id=49">French</a>.
Other translations are welcome.</i></p>
      <p>While it is easy once you get the hang of it, the A*
(pronounced
A-star) algorithm can be complicated for beginners. There are plenty of
articles on the web that explain A*, but most are written for people
who understand the basics already. This one is for the true beginner.<br>
虽然掌握了A*（读作A-star）算法就认为它很容易，对于初学者来说，它却是复杂的。网上有很多解释A*的文章，不过大多数是写给理解了基础知识的
人。本文是给初学者的。<br>
      </p>
      <p>This article does not try to be the definitive work on the
subject.
Instead it describes the fundamentals and prepares you to go out and
read all of those other materials and understand what they are talking
about. Links to some of the best are provided at the end of this
article, under Further Reading.<br>
本文并不想成为关于这个主题的权威论文。实际上它讨论了基础知识并为你做一些准备，以便进一步阅读其他资料和理解它们讨论的内容。本文的后面列出了几个最
好的文章，在进阶阅读中。<br>
      </p>
      <p>Finally, this article is not program-specific. You should be
able to
adapt what's here to any computer language. As you might expect,
however, I have included a link to a sample program at the end of this
article. The package contains two versions: one in C++ and one in Blitz
Basic. It also contains executables if you just want to see A* in
action.<br>
最后，本文不是编程规范的。你应该能够改写这里的东西到任何计算机语言上。如你所期望的，同时，我包含了一个示例程序的链接，在本文后面结束的地方。这个
程序包有两个版本：一个是C++，另一个用Blitz Basic语言编写。如果你只是想看看A*的行为，里面也含有可执行exe文件。<br>
      </p>
      <p>But we are getting ahead of ourselves. Let's start at the
beginning ...<br>
但我们要超越自己。让我们从头开始 ...<br>
      </p>
      <h1>介绍：搜索区域Introduction: The Search Area</h1>
      <p>Let's assume we have someone who wants to get from point A to
point
B and that a wall separates the two points. This is illustrated in the
graphic found below, with green being the starting point A, red being
the ending point B, and the blue filled squares being the wall in
between.<br>
我们假设某人想从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][Figure 1]</p>
      <p>The first thing you should notice is that we have divided our
search
area into a square grid. Simplifying the search area, as we have done
here, is the first step in pathfinding. This particular method reduces
our search area to a simple two dimensional array. Each item in the
array represents one of the squares on the grid, and its status is
recorded as walkable or unwalkable. The path is found by figuring out
which squares we should take to get from A to B. Once the path is
found, our person moves from the center of one square to the center of
the next until the target is reached.<br>
你应该注意的第一件事是，我们把搜索区域分割成了方块的格子。简化搜索区域，如你目前完成的那样，这是寻路的第一步。这个特殊方法把搜索区域简化成了一个
二维数组。数组的每一个项目代表了格子里的一个方块，它的状态记录成可行走和不可行走。通过计算出从A到达B应该走哪些方块，就找到了路径。一旦路径找
到，我们的人从一个方块的中心移动到下一个方块的中心，直到抵达目标。<br>
      </p>
      <p>These center points are called "nodes". When you read about
pathfinding elsewhere, you will often see people discussing nodes. Why
not just refer to them as squares? Because it is possible to divide up
your pathfinding area into something other than squares. They could be
rectangular, hexagons, or any shape, really. And the nodes could be
placed anywhere within the shapes