AStar算法介绍

A *算法介绍 路径寻找 单个物体的移动看起来简单。 但路径寻找时复杂的。 为什么要为路径寻找烦恼呢？譬如下述情况： 移动单位被初始化在地图的底部，并准备移动到地图上方。这时它探测周围没有任何障碍物（以粉红色标出）阻碍单位向上移动，因此它就可以不断地向上。在地图上方附近，它遇到了障碍，随即改变了方向。随着移动它发现在路上有个U型的障碍。相对的，一个路径寻找者会探测较大的区域（以浅蓝色表示），但能够发现一条最短的路径（以蓝色表示），从不会让单位移动到凹形障碍物内。 但是你能够扩展你的移动算法来解决像上述的情况。比如回避凹形的障碍，或者把他们标记为危险的凸包（只有当目标在内部时才进入）： 路径寻找者让你向前看并做出计划，而不是等待直到最后发现了问题。路径寻找者的制定计划和移动反应算法之间有一个权衡。制定计划常常是缓慢的，但是能够得到更好的结果；而移动一般比较快，但可能会被阻塞。如果游戏世界是不断变化的时候，那么在一开始制定计划只有较少的价值。我建议同时使用他们：路径寻找应对大地图，缓慢变化的障碍和长路径；而移动应对当前区域，快速的变化和短路径。 算法 在计算机科学教科书中，路径寻找算法在数学上的意义是一个用边连接起来的顶点集合。砖块游戏地图能够被看做一个图，其中每个砖块为一个顶点，相邻的砖块之间由一条边连接： 现在，我假定我们使用二维的网格。后面，我们会讨论怎么建立其他类型的图来表示你的游戏世界。 来自 AI 或算法研究的大多数的路径寻找算法是为任意图设计的而不是基于网格的游戏。我们想要找到一些有利于网格地图的算法。有些我们认为是常识的事情，算法却不明白。例如，关于方向，我们知道一般情况下，两个物体越远，那么从一个移动到另一个所花费的时间就越长；并且没有任何秘密的虫洞能让你到地图上从一个点传送的另一个点。（嗯，我们假设没有；如果有，那么找到一条好的路径会变得很困难，应为你不知道从哪里看起。） Dijkstra 的算法和最佳优先搜索 Dijkstra 算法以对象的起始点作为访问图的开始节点。然后重复检查离当前点最近的还没被检查过的顶点，并将它加入到已检查过的顶点集合。它从起点向外扩张，直到找到目标顶点。只要边的权值不为负，Dijkstra 算法能够保证找到一条从起始点到目标点的最短路径。（我写了“一条”最短路径，因为常常有多条一样短的路径。）下面的图表，粉色的方块代表起始点，蓝色方块为目标点，蓝绿...