AI:A*寻路算法

Reading time ~1 minute

这篇介绍一下A*寻路算法。

基本概念

A*(A-Star)算法是一种静态路网中求解最短路最有效的直接搜索方法。 我们会把地图分割成一个个方格(也可以是别的形状),在此基础上进行寻路算法。

启发式搜索

启发式搜索就是对每一个位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径,提高了效率。 在启发式搜索中,对位置的估价是十分重要的。

估价函数

从当前节点移动到目标节点的预估费用。在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数预估费用。

特点

A*算法在理论上是时间最优的,但是也有缺点:它的空间增长是指数级别的。(优化:二叉堆)

通过从点A开始,检查相邻方格的方式,向外扩展直到找到目标。

算法步骤

术语

开启列表:待检查方格的集合列表,寻找周围可以达到的点,加入到此表中,并保存中心点为父节点。
关闭列表:列表中保存不需要再次检查的方格。

G:与起始点的距离。
H:与目标点的距离。
F:表示G与H的和。F最小的格子表示该选择的位置。

F,G和H的评分被写在每个方格里。F在中间,G在左上角,H则在右上角。

我们另水平或垂直移动的耗费为10,对角线方向的耗费为14。因为,对角线距离是根号2即1.4,为了取整都乘以10。
求G的值,就是一个格子到它父节点的距离,加上父节点的G的值。
求H的值,就是直接求这个格子到终点的最短路径的距离,并且这个过程会忽略障碍。

开始查找

1、从A点开始,把它作为待处理点加入“开启列表”。开启列表的格子会逐渐增多,这是一个待检测方格的列表。

2、寻找起点周围所有可到达或通过的方格,把他们加入“开启列表”。把A点作为它们的父节点。

3、从开启列表中删除点A,把它加入到一个“关闭列表”,列表中保存所有不需要再次检查的方格。

为了继续搜索,我们简单的从开启列表中选择F值最低的方格,如果最低的F值相同,就取其中H值最低的。然后,对选中的方格做如下处理:

4、把当前格子从开启列表中删除,然后添加到关闭列表中。

5、检查所有相邻格子。跳过已经在关闭列表中的或者有障碍的,剩下的如果还不在开启列表的话就添加进去,把当前格子作为这些新的方格的父节点。

6、如果某个相邻格已经在开启列表里了,检查新的路径到达它的话,G值是否会更低一些。如果不是,那就什么都不做。反之,如果新的G值更低,那就把相邻方格的父节点改为目前选中的方格,重新计算F和G的值。

步骤总结

  1. 把起始格添加到开启列表。

  2. 重复如下的工作:

    1. 寻找开启列表中F值最低的格子。我们称它为当前格。

    2. 把它切换到关闭列表。

    3. 对相邻的格中的每一个
      • 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
      • 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
      • 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。
    4. 停止,当你
      • 把目标格添加进了关闭列表,这时候路径被找到。
      • 没有找到目标格,开启列表已经空了。这时候,路径不存在。
  3. 保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。

例子

这里是我写的一个简单的 U3D A* Demo

Scriptable Objects 及 游戏架构

Scriptable Objects 相关介绍,及基于其的游戏架构技术 Continue reading

AssetBundle 最佳实践

Published on January 29, 2019

AssetBundle 基础总结

Published on January 27, 2019