<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>