2022-02-23

1. 引言

随着上世纪六十年代呈现的电子游戏至今，许多经典的、乏味的、品质极高的游戏出现呈现在了咱们背后（如，坦克大战、马里奥、lol、艾尔登法环）毋庸置疑的，当一个游戏随之成长，那么玩家的体验也会进步，当初的游戏有着更实在的物理模仿引擎、绝美的画面、良好的互动以及真切的人工智能 （强调人工智能） 所带给玩家的极佳沉迷感 强调沉迷
正式开始

2. 背景

明天我为大家来分享的是一篇由杭州电子科技大学研究生 贾森浩 所写的论文《游戏人工智能中 A * 算法的利用钻研》，为该算法的优化提出一些倡议
不论是在英雄联盟和人机的对战里，还是斗地主的 AI 托管里，在游戏中，人工智能的使用范畴极广，但大家有没有想过，其实游戏中 NPC 的主动寻路零碎、亦是人工智能算法的一种体现
（寻路视频）
而寻路零碎中，咱们最罕用的算法，其实就是 本文中提到的 A* 门路搜索算法

3.A* 算法

解决什么问题？

ROS 机器人：全局门路布局，依据给定的指标地位和全局地图进行总体门路布局。导航中应用 A* 算法 计算出机器人到指标地位的最优路线，作为机器人的全局路线。
罕用于游戏中的 NPC 的挪动计算，或线上游戏的 BOT 的挪动计算上。
(三国战纪 天剑狂刀)【3】

来历

其实游戏人工智能的门路搜索算法最早来源于简略 A*算法，由 Peter Hart （须要其人照片及简略介绍）Peter E. Hart – Wikidata 于 1968 年，形容了该算法，其启发函数参考 Dijkstra 算法，亦是对其的一种扩大，是一种高效的搜索算法。

BFS

尽管咱们最相熟的其实 BFS。如果咱们将一张图分成一个个小块，用二维数组来示意地图，那么广度优先算法实际上就是通过对 图的遍历 来找到最短门路
视频演示
然而，很显著 BFS 也存在肯定缺点，就是在最坏的状况下，它要遍历所有的点或是大部分的点能力找到最短门路，这节约了大量的工夫和空间。所以咱们利用贪婪算法的思维给它加一个评估函数，来判断当先代价最小的门路，而这也是咱们重点要介绍的 A* 算法 的外围思维。

原理

视频演示
这是它的为伪代码：【3】

//FindPath
do{
    // 确定核心搜寻点，上一个中心点敞开，新的中心点开启 
    查找：Find the minimumm "point" of "F" from the "open_list" center;
    "now_point" = "min_point";//minimumm point 
    "now_point" 增加到 "close_list";
    
    // 新中心点的四周点开启，新中心点敞开 
    循环遍历："now_point" 相邻的四周 8 格 "s_now_point" 中的每一个;
    // 这一块它指的就是 now_point 四周 8 点以后搜寻点 s_now_point，为了简略间接用它示意 
    if (它不可通过 || 它曾经在 "close_list" 中){什么也不做;} else if (它不在开启列表中){
        把它增加进 "open_list";
        把 "now_point" 作为这它的 "father", 计算它的 "F","G","H";
    }else if (它曾经在开启列表中){// 通过 G 来判断是否须要更新 
        if (new_G < old_G){
            更新它的 "father" 为以后核心搜寻点 "now_point";
            更新它的 "G" 与 "F" ;
        } else{不更新，放弃原来的 "father", "G" 与 "F" ;} 
    }
} while(指标格 "end_point" 曾经在 "open_list"||"open_list"==NULL)
// 存在门路：指标格 "end_point" 曾经在 "open_list"
// 不存在门路："open_list"==NULL，搜寻了所有可能的点 

那么我从论文中找到了这张图不便大家了解【图 2 -8】
// 图注：开启列表：寄存着行将被拜访当为被拜访的点；敞开列表：列表寄存着曾经实现的节点门路信息（包含节点的要害信息）//

毛病

开启链表的保护

在 A* 算法进行寻路搜寻的过程中，每次都要从开启列 表中查找一个顶点，同时还会对该表有插入、删除、替换等操作，这些对表的操作都须要肯定的工夫。
但当游戏地图很小时，开启列表的保护是简略的，当当游戏地图很大有几百万、千万的时候 A* 算法的保护就会变的艰难。

启发函数的抉择

如果启发函数算出大量的雷同的门路长度时，如果每个都要再算一遍会节约很多工夫，其实只有选其中一条门路即可
对边缘不规则的障碍物进行寻路时，门路会产生锯齿形
甚至会呈现下一步要搜寻的店“穿过”阻碍的状况
“多对一”的艰难
当一个集群要寻找雷同的指标点时，只能一个一个找他们的最短门路

改良

应用 最小二叉堆 来保护开启列表和敞开列表

开启列表的操作

1. 一直循环的读入以后估价最好的节点，并将之删除
2. 拜访相邻节点时，查看此点是否在表中，
3. 如果在表中，且此次估价要比表内估价好，则替换表内估价和要害信息

4. 拜访新的临接节点，并插入表中

   二叉堆

   1. 性质

    1、齐全二叉树
    2、父节点的值总是比子节点要大（或小）

   2. 操作（以【图 -3】为例）

    1、插入
    2、删除

   启发函数优化

【1】A* 算法入门 . 极限定律 . 2009-04-191.
【2】A* 寻路算法详解 #A 星 #启发式搜寻 . 奇乐编程学院 . 2020-09-30
【3】A* 算法 . Clark-dj . 2020-11-17
【4】Introduction to the A* Algorithm (redblobgames.com)