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】

//FindPathdo{    //确定核心搜寻点，上一个中心点敞开，新的中心点开启     查找：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.性质
```
 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)