【译】寻找最快的途径——A*寻路算法

发表于2016-03-21
评论0 879浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏程序行业精英群

711501594
寻找最快的途径——A*寻路算法
  在计算机科学中最常见的问题之一就是找到从出发点到目标的最短途径。有许多算法致力于解决这个问题,其中最流行的就是我们所知道的A*算法。
  A*算法基本上由一个互相联系的网络构成。每个网络上的节点都知道它相邻的节点,并且知道它到它们的距离。没有要求规定路径一定是对称的,所以如果一个路径加入了,没有路径到其他节点,那么算法就会给这个节点建立一个模型,但是不包括反向路径。
  A*算法的关键叫做the Heuristic(启发式)。如果 heuristic 大于最小值,那么它就会发现一个更慢的路径,但是如果 heuristic 太低,A*算法就会花费更多的时间来运行。一个普通的算法应该包括两点之间的物理路径。举个例子如果你的节点是基于网格式的系统,你正打算从点(2,0)到点(5,0),你的 heuristic 可能就是3。
  A*算法工作原理是:从最开始的节点开始,识别其周围节点和到每个周围节点的距离。每个节点通过启发式来估算它到目标网格的距离。这些方格被放置在排序缓冲区,以距离排序。下一个测试的节点就是到网格终点最近的节点。起始处的方格被加到一系列已经被测试过的方格中,它们不会被更新。程序继续运行,每个节点逐步找到到起始节点的最短路径,然后按它自己的路线到达最终节点。最后,当最终节点被选中时,最短的路径就已经确定了。每个节点都知道路径来时的节点,后续可以在后面计算出来。维基百科上有一个形象的图来说明这一点。(gif见附件)

   

  我用C#实现了这个算法,我已经将其发布到GitHub,大家可以随意下载,或是在您的程序中使用它,如果你想的话甚至可以改进我的算法。实现它的关键就是实现TilePathfinder 接口。每一个节点,或是在我的例子中中,方格,要提供周围的一系列方格和heuristic函数。


  我提供给GitHub的实现相同目标的算法就是通过这个迷宫找到我的路径,找到最短的路径。它工作起来的确不错。注意棕色的正方形是地,我门不能前往地。(毕竟,游戏就是一艘船,由图片中心更低的矩形框表示)
   
关于作者
  本·皮尔森是业余无线电爱好者博客KD7UIY的作者以及谷歌游戏、应用开发者,他计划在那里发表一些由gamedev.tv带来灵感的游戏。他从小就是程序员,最近才开始从事游戏编程。他已经完成了完全统一开发课程,正在研究完全搅拌开发课程,统一游戏物理?和程序生成课程。他希望不久就能开始“不真实课程”。你可以在推特上关注他@KD7UIY。
  原文链接http://www.completeunitydeveloper.com/blog/finding-the-quickest-path-a
  原文作者未做权利声明,视为共享知识产权进入公共领域,自动获得授权

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台