📄 page3.asp.html
字号:
src="page3.asp_files/astar.png" border="0" alt=""></a>
<table width="170" align="right" cellpadding="2" cellspacing="0"
border="0">
<tbody>
<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="page3.asp_files/dotsm.gif" width="7" height="6" border="0" alt=""> </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="page3.asp_files/dotsm.gif"
width="7" height="6" border="0" alt=""> </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="page3.asp_files/dotsm.gif"
width="7" height="6" border="0" alt=""> </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="page3.asp_files/print.gif" width="16" height="16" border="0"
alt=""> </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="page3.asp_files/discuss.gif" width="16" height="16" border="0"
alt=""> </td>
<td><a
href="http://www.gamedev.net/community/forums/topic.asp?key=featart&uid=2003&forum_id=35&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="page3.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=17157"
target="_new"> <img
src="http://www.gamedev.net/banman/banman.asp?ZoneID=9&Task=Get&Mode=HTML&PageID=17157"
width="160" height="600" border="0"></a> </noscript>
<!-- End Ban Man Pro Banner Code - Zone: GameDev.net Skyscraper --> </td>
</tr>
</tbody>
</table>
</p>
<h1>A*方法汇总</h1>
<p>好了，现在你已经读完了解释，让我们在这里一步一步的列出所有操作：<br>
</p>
<ol>
<li>添加开始方块到开放列表。<br>
</li>
<li>重复下面的过程：<br>
a) 查找开放列表中具有最小F值的方块。我们把它作为当前方块。<br>
b) 把它放入封闭列表。<br>
c) 对当前方块的8个相邻方块的每一个？<br>
<ul>
<li>如果它不可行走，或者存在于封闭列表，忽略它。否则执行下面操作。<br>
</li>
<li>如果它不在开放列表，将它添加进去。以当前方块作为其父亲。记录这个方块的F，G和H值。<br>
</li>
<li>如果它已经在开放列表了，检查到达那个方块的路径是否更优，以G值为测量值。更低的G值意味着更好的路径。如果找到，这
个方块的父亲改为当前方块，并重新计算这个方块的G和F值。如果你保持开放列表按F值排序的话，可能需要重新排序来解决这个变化。<br>
</li>
</ul>
<br>
d) 结束循环，当你<br>
<ul>
<li>将目标方块加入到开放列表，此时路径已经找到，或者<br>
</li>
<li>没有找到目标方块，并且开放列表是空的。此时，没有路径。<br>
</li>
</ul>
</li>
<li>保存路径。从目标方块往回走，从每个方块走到它的父亲方块，直到抵达开始方块。那就是路径。<br>
</li>
</ol>
<h1>一点感慨</h1>
<p>原谅我离题了，但是值得指出的是，当你在网上和分类论坛阅读很多讨论A*寻路的时候，你有时候会发现某些人所指的A*代码实际上并不是
真正的A*算法。对
于应用中的A*方法，你需要包含上面讨论到的元素 --
特别是开放列表和封闭列表，以及使用F，G，和H的路径排序。有很多其他的寻路算法，但是其它的方法不是A* --
通常认为它是最好的算法。Bryan
Stout在本文后面的一个参考文档里讨论了这些算法，有正面的，也有反面的。有时候在特定的环境下，选择其他的算法会更好，但是你应该理解
你做了什么。好了，说够了。回到文章中来。<br>
</p>
<h1>关于实现的提示</h1>
<p>现在你已经理解了基本的方法，这里是当你写自己的程序时要考虑的更多东西。下面的某些材料引用了我用C++和Blitz
Basic写的程序，但是这些要点对其他语言也是同样有效的。<br>
</p>
<p><b><i></i></b><b><i>1.维护开放列表</i></b>:
实际上这是A*寻路函数最耗费时间的元素之一。每次访问开放列表时，你都需要找到具有最小F值的方块。有很多种方法可以做到这点。你可以保存所需的路径项
目，每次当你需要找到最小F值的方块时，简单的遍历整个列表。这很简单，不过路径长的时候非常慢。这个方法可以改进，通过维护一个排序的列表，每次需要最
小F值的方块时，简单的抓出第一个项目就可以了。当我写自己的程序时，这是我用到的第一个方法。<br>
</p>
<p>这个方法对小的地图相当的好，但不是最快的方案。真正需要速度的认真的A*程序员使用叫做二元堆[binary
heap]的东西，这也是我的代码中所使用的。以我的经验，在大多数解决方案中，这个方法会快至少2-3倍，在长路径上更快（10倍以上）。如果你有兴趣
发现更多二元堆的奥秘，参考我的文章，<a
href="http://www.policyalmanac.org/games/binaryHeaps.htm">Using Binary
Heaps in A* Pathfinding</a>。</p>
<p><b><i></i></b><b><i>2. 其他单元：</i></b>如果你碰巧深入的阅读我的范例代码，将会注意到它完全忽略
了地图上的其他单元。我的寻路怪物实
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -