page2.asp.html

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

                  <td valign="middle" class="featmenu">
                  <table cellspacing="0" cellpadding="0" border="0"
 width="100%">
                    <tbody>
                      <tr valign="top">
                        <td width="7"><img
 src="page2.asp_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="page2.asp_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="page2.asp_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="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>路径排序Path Scoring</h1>
      <p>The key to determining which squares to use when figuring out
the path is the following equation:<br>
找到形成路径的方块的关键是下面的等式：<br>
      </p>
      <p>F = G + H</p>
      <p>where<br>
这里<br>
      </p>
      <ul>
        <li>G = the movement cost to move from the <u>starting</u>
point A to a <u>given</u> square on the grid, following the path
generated to get there.</li>
        <li>G = 从<span style="text-decoration: underline;">开始</span>点A到格
子中<span style="text-decoration: underline;">给定</span>方块的移动代价，沿着到达该方块而生成的
那个路径。</li>
        <li>H = the estimated movement cost to move from that <u>given</u>
square on the grid to the <u>final destination</u>,
point B. This is often referred to as the heuristic, which can be a bit
confusing. The reason why it is called that is because it is a guess.
We really don't know the actual distance until we find the path,
because all kinds of stuff can be in the way (walls, water, etc.). You
are given one way to calculate H in this tutorial, but there are many
others that you can find in other articles on the web.</li>
        <li>H = 从格子中<span style="text-decoration: underline;">给定</span>的
方块到<span style="text-decoration: underline;">最终目标</span>B点的评估移动代价。这种方式通
常称作试探法，有点让人混乱。因为这是一个猜测，所以得到这个称谓。在找到路径之前，我们真的不知道实际的距离，因为途中有各种东西（墙，水，等等）。
在本教程里给出了一种计算H的方法，但在网上你能找到很多其他的文章。</li>
      </ul>
      <p>Our path is generated by repeatedly going through our open
list and
choosing the square with the lowest F score. This process will be
described in more detail a bit further in the article. First let's look
more closely at how we calculate the equation.<br>
我们需要的路径是这样生成的：反复的遍历开放列表，选择具有最小F值的方块。这个过程在本文稍后会详细描述。先让我们看看如何计算前面提到的等式。<br>
      </p>
      <p>As described above, G is the movement cost to move from the
starting
point to the given square using the path generated to get there. In
this example, we will assign a cost of 10 to each horizontal or
vertical square moved, and a cost of 14 for a diagonal move. We use
these numbers because the actual distance to move diagonally is the
square root of 2 (don't be scared), or roughly 1.414 times the cost of
moving horizontally or vertically. We use 10 and 14 for simplicity's
sake. The ratio is about right, and we avoid having to calculate square
roots and we avoid decimals. This isn't just because we are dumb and
don't like math. Using whole numbers like these is a lot faster for the
computer, too. As you will soon find out, pathfinding can be very slow
if you don't use short cuts like these.<br>
如上所述，G是经由到达它的路径，从开始点到给定方块的移动代价。在本例中，我们为每个水平/垂直的移动指定代价为10，而斜角的移动代价为14。我们使
用这些值，因为斜角移动的实际距离是2的平方根（别害怕），或者大概1.414倍的水平/垂直的移动代价。出于简化的目的使用了10和14。比例大致是正
确的，而我们却避免了方根和小数的计算。倒不是我们没有能力做或者不喜欢数学。使用这些数字也能让计算更快一些。以后你就会发现，如果不使用这些技巧，寻
路的计算非常慢。<br>
      </p>
      <p>Since we are calculating the G cost along a specific path to a
given
square, the way to figure out the G cost of that square is to take the
G cost of its parent, and then add 10 or 14 depending on whether it is
diagonal or orthogonal (non-diagonal) from that parent square. The need
for this method will become apparent a little further on in this
example, as we get more than one square away from the starting square.<br>
既然我们沿着到达给定方块的路径来计算G的值，找出那个方块的G值的方法就是找到其父亲的G值，再加上10或者14而得，这依赖于他处于其父亲的斜角或者
直角（非斜角）而定。这在本例后面会更加清晰，随着我们从开始点离开而得到更多的方块。<br>
      </p>
      <p>H can be estimated in a variety of ways. The method we use
here is
called the Manhattan method, where you calculate the total number of
squares moved horizontally and vertically to reach the target square
from the current square, ignoring diagonal movement. We then multiply
the total by 10. This is called the Manhattan method because it's like
calculating the number of city blocks from one place to another, where
you can't cut across the block diagonally. Importantly, when
calculating H, we ignore any intervening obstacles. This is an <u>estimate</u>
of the remaining distance, not the actual distance, which is why it's
called the heuristic. Want to know more? You can find equations and
additional notes on heuristics <a
 href="http://www.policyalmanac.org/games/heuristics.htm">here</a>.<br>
H能通过多种方法估算。我们这里用到的方法叫做Manhattan方法，计算从当前方块经过水平/垂直移动而到达目标方块的方块总数。然后将总数乘以
10。这种方法之所以叫做Manhattan方法，因为他很象计算从一个地点到达另一个地点的城市街区数量计算，此时你不能斜向的穿越街区。重要的是，当
计算H的时候，要忽略任何路径中的障碍。这是一个对剩余距离的<span style="text-decoration: underline;">估
算值</span>，而不是实际值，这就是试探法的称谓由来。想知道更多？关于试探法的更多说明<a
 href="http://www.policyalmanac.org/games/heuristics.htm">在这里</a>。<br>
      </p>