page3.asp.html

一篇关于a*很好的入门文章

际上是穿越彼此而通过。依赖于游戏，这可能是正确的，或者是不正确的。如果你要考虑地图上的其他单元，并让他们能围绕彼此移动，我建议你在寻路代码里忽略
其他的单元，而另外写一些代码来检测两个单元是否发生了碰撞。当碰撞发生时，你可以生成一个新路径或者使用一些标准的移动规则，直到障碍不在路上，然后生
成新路径。当计算初始路径时，为什么不包含其他单元？嗯，因为其他单元会动，他们可能不在自己的位置，当你到达那里的时候。这会造成一些怪异的结果，路径
计算后，在某处单元突然转向避开一个不再停留在那里的单元，却撞上了另一个经过它路径的单元。</p>
      <p>寻路代码中忽略其他的单元，然而，这意味着你要写单独的代码来处理碰撞。这是和游戏很相关的，所以我把决定权留给你。本文后面的参考资
料一节里，
Bryan Stout的文章值得一读，里面有一些可能的解决方案（如强力跟踪[robust tracing]，等等）。<br>
      </p>
      <p><b><i></i></b><b><i>3. 关于速度的更多技巧</i></b>：当你开发自己的A*程序，或者改编我所写的那
个，最终你会发现寻路使用了大块的
CPU时间，特别是当你有大量的寻路怪物，运行在一个相当大的地图上的时候。如果你读网上的资料，你会发现甚至象星际争霸[Starcraft]或者帝国
时代[Age of
Empires]这样的专业游戏也会遇到这些问题。如果你发现由于寻路导致运行变慢，这里有一些可能提高速度的主意：<br>
      </p>
      <ul>
        <li>考虑小一些的地图或者少一些的怪物。<br>
        </li>
        <li>不要一次对太多的怪物做寻路。而是把他们放入队列，从而把他们分散到更多的游戏循环。如果你的游戏运行在，比如，40帧/秒，
没有人会注意到。但是他们会注意到每一小段时间的游戏变慢，当大量的怪物都在同一时间寻路的时候。<br>
        </li>
        <li>考虑对地图使用大一些的方块。这样就减少了寻路要搜索的方块总数。如果你有雄心的话，可以设计两种或更多寻路系统，依赖于路径的
长度而用于不同的场合。这就是专业人士的做法，对长路径使用大的区域，然后当接近目标时切换到使用小一些的方块/区域的精确搜索。如果你对这个概念有兴
趣，参考我的文章<a href="http://www.policyalmanac.org/games/twoTiered.htm">Two-Tiered
A*
Pathfinding</a>。</li>
        <li>考虑对较长的路径应用路点系统，或者设计预计算[precalculated]的多个路径，它们对游戏是固定不变
[hardwired]的。<br>
        </li>
        <li>考虑预处理地图，计算出哪些区域是从其他区域不可到达的。我把这些区域叫做“岛屿”。实际上，他们也可以是岛屿或者其他围了墙而
无法到达的区域。A*的缺点之一就是，如果你告诉它搜索到达这些区域的路径，它会搜索整个地图，仅当每一个开放列表和封闭列表中的可到达方块/节点都处理
后，才会停止。那会浪费大量的CPU时间。这种现象是可以避免的，通过预先决定那些区域是无法到达的，用数组或者类似的数据结构记录这些信息，然后在开始
路径搜索前检查它。在我的代码的Blitz版本中，我创建了一个地图预处理器[map
pre-processor]来做这件事。它也预先检查寻路算法可以忽略的死点[dead-ends]，这样速度就提高了很多。<br>
        </li>
      </ul>
      <p><b><i></i></b><b><i>4. 多样的地形代价：</i></b>在本教程以及我的附带程序里，地形只有两种情况：可
行走和不可行走。如果你有可以行走但
移动代价更高的地形怎么办？沼泽，山坡，地下城的楼梯，等等？这些都是可行走而移动代价高于平坦地面的地形实例。同样的，道路可能具有比它周围地形小一些
的移动代价。<br>
      </p>
      <p>这个问题很容易解决，当计算任意给定的方块的G值时，加上地形的代价。简单的加上一个奖励代价给这些方块。A*寻路算法已经写成查找最
小代价的路径，应该
容易处理它。在我描述得简单示例中，当地形只有可行走和不可行走时，A*能找到最短，最直接得路径。但是在多代价[variable-cost]地形环境
中，最小代的得路径可能行走了较长的距离。如同选择围绕沼泽的道路，而不是直接穿越沼泽。<br>
      </p>
      <p>还有一个有趣的附加考虑是被专业人士称作“影响映射[influence
mapping]”的东西。如同上面描述的多代价地形一样，你可以创建一个附加的点系统，并引用到AI的路径中。想象你有一个地图，有大量的怪物守护着穿
越山区的通道。每次当电脑送某人到经过这个通道的路径时，都会被困住。如果你愿意，你可以创建一个影响地图，处罚发生大量流血残杀处的那些方块。这会教电
脑偏好安全的路径，并帮助它避免不利的位置：仅仅由于路径更短（但更危险），而不停的输送部队和怪物通过这个路径。<br>
      </p>
      <p><b><i></i></b><b><i>5. 处理未探索区域：</i></b>你是否玩过一款PC游戏，在那里电脑总是准确的知道
路该如何走，即使地图没有探索？依赖
与游戏，那样的寻路太好了反而不够真实。幸运的是，这个问题很容易解决。</p>
      <p>答案就是创建一个独立的“发现可行走[knowWalkability]”数组用于每一个玩家以及电脑对手（每一个玩家，不是每一个单
元 --
那将需要更多的计算机内存）。每个数组包含了玩家已探索区域的信息，另一方面，地图上其它区域直到被证实后才被假设是可行走的。使用这个方法，单元会漫步
于死点位置，重复做相同的错误选择，直到他们发现周围的路。一旦地图都探索了，寻路就正常工作。<br>
      </p>
      <p><b><i></i></b><b><i>6. 更平滑的路径：</i></b>虽然A*会自动给出最短的，最低代价的路径，它不会自
动给出看起来最平滑的路径。看一看本
例最后计算出来的路径（图 7）。那条路径的第一步位于开始方块的右下方。如果第一步的方块就是开始方块相邻下方的方块，路径会不会更平滑些？<br>
      </p>
      <p>有很多方法可以解决这个问题。当你计算路径的时候，要处罚那些改变方向的方块，给它们一个附加的G值扣分。这样计算后，你可以走一遍那
条路径，看一看那些
选择了邻近方块而让路径看起来更好的地方。关于这个问题的完整信息，参考Gamasutra.com上Macro Pinter的文章 <a
 href="http://www.gamasutra.com/features/20010314/pinter_01.htm">Toward
More Realistic Pathfinding</a>，它是免费的，但需要注册。 </p>
      <p><b><i></i></b><b><i>7. 非方块搜索区域：</i></b>在我们的示例中，我们使用了一个简单的2D方块布
局。你不必使用这个方法。你可以使用不
规则的形状区域。考虑一下棋盘游戏Risk，和游戏中的国家。你可以设计一个象那样的寻路关卡。为此，你将需要创建一个表来存储哪些国家和哪些国家相邻，
以及相关的从一个国家移动到另一个国家的G值。你也需要选择一种估算H值的方法。其它的处理就和上面示例一样。当添加新项目到开放列表中时，你将简单的查
找表中的国家，而不是邻近的方块。<br>
      </p>
      <p>同样的，你可以创建一个路点系统，对于固定地形场景中的路径。路点通常是一条路径上往来移动的点，这路径可能是一条道路，也可能是一个
地下城的关键通道。
作为游戏设计者，你能预先指定这些路点。如果没有障碍存在于两个路点间的直线路径上，就可以认为它们是“相邻”的，如同在Risk中那样，你应该保存这些
邻接信息到一个某种类型的查找表中，当生成新的开放列表项目的时候使用它。然后记录相关的G值（可能是节点间的直线距离）和H值（可能是节点到目标的直线
距离）。其他的和往常一样处理。<br>
      </p>
      <p>另有一个使用非方块搜索区域进行斜视角RPG地图搜索的例子，参考我的文章<a
 href="http://www.policyalmanac.org/games/twoTiered.htm">Two-Tiered A*
Pathfinding</a>。</p>
      <h1>进阶阅读</h1>
      <p><a name="code"></a>好了，现在你具备了基础知识和对一些高级概念的感觉。在这里，我建议你到我的代码中跋涉。程序
包有两个版本，一个是C++的，另一个是用Blitz
Basic语言写的。两个版本都有大量注释，应该容易理解。链接在这里。<br>
      </p>
      <ul>
        <li><a
 href="http://www.blitzcoder.com/cgi-bin/showcase/showcase_showentry.pl?id=turtle177604062002002208&amp;comments=no">Sample
Code: A* Pathfinder (2D) Version 1.71</a></li>
      </ul>
      <p>如果你无法使用C++或者Blitz Basic，可以找到C++版本的两个exe执行文件。通过在<a
 href="http://www.blitzbasic.com/">Blitz Basic</a>的网站下载免费的demo版Blitz
Basic 3D，就能运行Blitz Basic版本。还能找到Ben O‘Neill写的在线使用示范。<br>
      </p>
      <p>你也应该考虑通读下面的网页。阅读了本文后，它们应该非常容易理解了。<br>
      </p>
      <ul>
        <li><a
 href="http://www-cs-students.stanford.edu/%7Eamitp/gameprog.html#Paths">Amit's
A* Pages</a>:
这是Amit Patel维护的一个很广泛的参考页面，如果你开始没有读过本文，它是有点混乱的。很值得一读。特别看一下关于Amit本人的<a
 href="http://theory.stanford.edu/%7Eamitp/GameProgramming/">思想</a>那个主题。
        </li>
        <li><a
 href="http://www.gamasutra.com/features/19970801/pathfinding.htm">Smart
Moves: Intelligent Path Finding</a>:
这篇文章位于Gamasutra.com，Bryan
Stout所写，需要注册才能阅读。注册是免费的，为了这篇文章是值得的，因为此类的文章可不多见了。程序是Bryan用delphi语言写的，它帮助我
学会了A*，我的A*程序背后也有它的灵感。它也讨论了一些替代A*的解决方案。<br>
        </li>
        <li><a
 href="http://www.ensemblestudios.com/news/devnews/terrain1.shtml">Terrain
Analysis</a>: 这是一篇高阶的文章（但很有趣），Dave Pottinger所写。Ensemble
Studios的专家。这些家伙开发了帝国时代[Age of Empires]和<font size="-1">帝国时代II：帝王时代[Age
of
Kings]。不要指望能理解这里的所有东西，但它是一篇有趣的文章，也许能带给你一些属于你自己的想法。它包含了一些mip映射[mip-
mapping]，影响映射[influence mapping]，和一些其他的高级AI/寻路的概念的讨论。对”洪水泛滥[flood
filling]“的讨论给予了我设计自己的"死点[dead
ends]"和"岛屿"地图预处理代码的灵感，这些都包含在我的程序的Blitz版本里面。</font></li>
      </ul>
      <p>其它值得拜访的站点：<br>
      </p>
      <ul>
        <li><a href="http://www.aiguru.com/pathfinding.htm">aiGuru:
Pathfinding</a></li>
        <li><a href="http://www.gameai.com/pathfinding.html">Game AI
Resource: Pathfinding</a></li>
        <li><a
 href="http://www.gamedev.net/reference/list.asp?categoryid=18#94">GameDev.net:
Pathfinding</a></li>
      </ul>
      <p>好了，没有了。如果你要应用这些概念来写一个程序的话，我很高兴看到它。我的联系地址是<br>
      </p>
      <p><img border="0" src="page3.asp_files/mail2.jpg"></p>
      <p>那么，祝好运！<br>
      </p>
翻译：白龙[[e-mail]]<br>
      <br>
      <br>
      </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>