a算法在游戏中的应用

Ⅰ A*算法介绍

姓名：车文扬 学号：16020199006

【嵌牛导读】：A*算法的逐步详解

【嵌牛鼻子】：启发式算法

【嵌牛提问】：A*算法的原理是什么？

【嵌牛正文】：

A*算法

路径规划是指的是机器人的最优路径规划问题，即依据某个或某些优化准则（如工作代价最小、行走路径最短、行走时间最短等），在工作空间中找到一个从起始状态到目标状态能避开障碍物的最优路径。机器人的路径规划应用场景极丰富，最常见如游戏中NPC及控制角色的位置移动，网络地图等导航问题，小到家庭扫地机器人、无人机大到各公司正争相开拓的无人驾驶汽车等。

目前路径规划算法分为：

A*算法原理：

在计算机科学中，A*算法作为Dijkstra算法的扩展，因其高效性而被广泛应用于寻路及图的遍历，如星际争霸等游戏中就大量使用。在理解算法前，我们需要知道几个概念：

搜索区域（The Search Area）：图中的搜索区域被划分为了简单的二维数组，数组每个元素对应一个小方格，当然我们也可以将区域等分成是五角星，矩形等，通常将一个单位的中心点称之为搜索区域节点（Node）。

开放列表(Open List)：我们将路径规划过程中待检测的节点存放于Open List中，而已检测过的格子则存放于Close List中。

父节点（parent）：在路径规划中用于回溯的节点，开发时可考虑为双向链表结构中的父结点指针。

路径排序（Path Sorting）：具体往哪个节点移动由以下公式确定：F(n) = G + H 。G代表的是从初始位置A沿着已生成的路径到指定待检测格子的移动开销。H指定待测格子到目标节点B的估计移动开销。

启发函数（Heuristics Function）：H为启发函数，也被认为是一种试探，由于在找到唯一路径前，我们不确定在前面会出现什么障碍物，因此用了一种计算H的算法，具体根据实际场景决定。在我们简化的模型中，H采用的是传统的曼哈顿距离（Manhattan Distance），也就是横纵向走的距离之和。

如下图所示，绿色方块为机器人起始位置A，红色方块为目标位置B，蓝色为障碍物。

我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步，简化搜索区域。这个特殊的方法把我们的搜索区域简化为了2 维数组。数组的每一项代表一个格子，它的状态就是可走(walkalbe)或不可走(unwalkable) 。现用A*算法寻找出一条自A到B的最短路径，每个方格的边长为10，即垂直水平方向移动开销为10。因此沿对角移动开销约等于14。具体步骤如下：

从起点 A 开始，把它加入到一个由方格组成的open list(开放列表) 中，这个open list像是一个购物清单。Open list里的格子是可能会是沿途经过的，也有可能不经过。因此可以将其看成一个待检查的列表。查看与A相邻的8个方格 ，把其中可走的 (walkable) 或可到达的(reachable) 方格加入到open list中。并把起点 A 设置为这些方格的父节点 (parent node) 。然后把 A 从open list中移除，加入到close list(封闭列表) 中，close list中的每个方格都是不需要再关注的。

如下图所示，深绿色的方格为起点A，它的外框是亮蓝色，表示该方格被加入到了close list 。与它相邻的黑色方格是需要被检查的，他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点A。

下一步，我们需要从open list中选一个与起点A相邻的方格。但是到底选择哪个方格好呢？选F值最小的那个。我们看看下图中的一些方格。在标有字母的方格中G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方，下方，左方的方格的G 值都是10 ，对角线的方格G 值都是14 。H值通过估算起点到终点( 红色方格) 的Manhattan 距离得到，仅作横向和纵向移动，并且忽略沿途的障碍。使用这种方式，起点右边的方格到终点有3 个方格的距离，因此H = 30 。这个方格上方的方格到终点有4 个方格的距离( 注意只计算横向和纵向距离) ，因此H = 40 。

比较open list中节点的F值后，发现起点A右侧节点的F=40，值最小。选作当前处理节点，并将这个点从Open List删除，移到Close List中。

对这个节点周围的8个格子进行判断，若是不可通过（比如墙，水，或是其他非法地形）或已经在Close List中，则忽略。否则执行以下步骤：

若当前处理节点的相邻格子已经在Open List中，则检查这条路径是否更优，即计算经由当前处理节点到达那个方格是否具有更小的 G值。如果没有，不做任何操作。相反，如果G值更小，则把那个方格的父节点设为当前处理节点 ( 我们选中的方格 ) ，然后重新计算那个方格的 F 值和 G 值。

若当前处理节点的相邻格子不在Open List中，那么把它加入，并将它的父节点设置为该节点。

按照上述规则我们继续搜索，选择起点右边的方格作为当前处理节点。它的外框用蓝线打亮，被放入了close list 中。然后我们检查与它相邻的方格。它右侧的3个方格是墙壁，我们忽略。它左边的方格是起点，在close list 中，我们也忽略。其他4个相邻的方格均在open list 中，我们需要检查经由当前节点到达那里的路径是否更好。我们看看上面的方格，它现在的G值为14 ，如果经由当前方格到达那里，G值将会为20( 其中10为从起点到达当前方格的G值，此外还要加上从当前方格纵向移动到上面方格的G值10) ，因此这不是最优的路径。看图就会明白直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。

当把4个已经在open list 中的相邻方格都检查后，没有发现经由当前节点的更好路径，因此不做任何改变。接下来要选择下一个待处理的节点。因此再次遍历open list ，现在open list中只有7 个方格了，我们需要选择F值最小的那个。这次有两个方格的F值都是54，选哪个呢？没什么关系。从速度上考虑，选择最后加入open list 的方格更快。因此选择起点右下方的方格，如下图所示。

接下来把起点右下角F值为54的方格作为当前处理节点，检查其相邻的方格。我们发现它右边是墙（墙下面的一格也忽略掉，假定墙角不能直接穿越)，忽略之。这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ，所以把它们加入，同时把当前方格设为他们的父亲。在剩下的 3 个方格中，有 2 个已经在 close list 中 ( 一个是起点，一个是当前方格上面的方格，外框被加亮的 ) ，我们忽略它们。最后一个方格，也就是当前方格左边的方格，检查经由当前方格到达那里是否具有更小的 G 值。没有，因此我们准备从 open list 中选择下一个待处理的方格。

不断重复这个过程，直到把终点也加入到了open list 中，此时如下图所示。注意在起点下方2 格处的方格的父亲已经与前面不同了。之前它的G值是28并且指向它右上方的方格。现在它的G 值为20 ，并且指向它正上方的方格。这是由于在寻路过程中的某处使用新路径时G值更小，因此父节点被重新设置，G和F值被重新计算。

那么我们怎样得到实际路径呢？很简单，如下图所示，从终点开始，沿着箭头向父节点移动，直至回到起点，这就是你的路径。

A*算法总结：

1. 把起点加入 open list 。

2. 重复如下过程：

a. 遍历open list ，查找F值最小的节点，把它作为当前要处理的节点，然后移到close list中

b. 对当前方格的 8 个相邻方格一一进行检查，如果它是不可抵达的或者它在close list中，忽略它。否则，做如下操作：

□  如果它不在open list中，把它加入open list，并且把当前方格设置为它的父亲

□  如果它已经在open list中，检查这条路径 ( 即经由当前方格到达它那里 ) 是否更近。如果更近，把它的父亲设置为当前方格，并重新计算它的G和F值。如果你的open list是按F值排序的话，改变后你可能需要重新排序。

c. 遇到下面情况停止搜索：

□  把终点加入到了 open list 中，此时路径已经找到了，或者

□  查找终点失败，并且open list 是空的，此时没有路径。

3. 从终点开始，每个方格沿着父节点移动直至起点，形成路径。

Ⅱ 什么是A搜索算法

A*搜索算法，俗称A星算法，作为启发式搜索算法中的一种，这是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样，可以找到一条最短路径；也像BFS一样，进行启发式的搜索。

Ⅲ 人工智能在游戏中的应用有什么

1. 现代电脑游戏简介
电子游戏从1971年诞生以来，越来越受到人们的喜爱。随着现代计算机、网络、虚拟现实、人工智能等技术的发展，游戏的拟人化越来越逼真。高度的拟人化使得现代电脑游戏能够模仿人类社会中的各种情形，并把这些情形通过视觉、听觉、甚至触觉等多种感官反映到人的大脑，从而对人们的现实生活产生巨大冲击。基于游戏中的这些反映人类社会的情形不同和游戏表示的方式不同，可以把电子游戏分为几大类别：纵向卷轴和横向卷轴类、棋牌逻辑类、文字冒险类、图形冒险类、模拟类、战略类、第一或第三人称射击类和角色扮演类。
无论游戏属于何种类别，游戏玩家都希望在游戏中能够体验到现实中无法体验到的刺激，得到现实中无法得到的满足。这些刺激和满足主要表现在特定的挑战、社会化、吹嘘与幻想、情感等方面。实际上，大部分的玩家并不能预先知道他们想要什么样的游戏，但是他们往往在看到了一个精美的游戏后说，“嗯，我要的就是这个！”
要使得玩家喜欢游戏，游戏的开发过程必须得到重视。一般来说，游戏的开发过程主要分为四个阶段：构想阶段、总体设计阶段、细节设计阶段和建设阶段。[1]
万事开头难，构想阶段是游戏开发中最为重要的阶段。一个好的游戏背景故事是整个游戏成功的一半。在准备好游戏故事之后，就需要考虑游戏采用何种游戏类型，并把游戏故事分割成幕(Act)，改编为游戏剧本(Gameplay)。
在总体设计阶段，要考虑每个幕中的角色和规则，同时也要考虑相关的技术问题。比如，游戏将采用何种技术、准备运行在什么平台上等。
在细节设计阶段，要对每一幕中的焦点(Focus)进行设计，对每一幕的效果产生效果图，选择合适的音乐匹配到各个场景，设计各个角色和场景的细节。
最后是建设阶段。开发者要采用选定的技术对游戏进行开发。游戏制作包括编程和触发器的制作。最后要进行游戏测试。2. 基于电脑游戏的图灵实验
人们在娱乐电脑游戏的时候，往往希望游戏中的其他角色能够拥有某些程度上的智能。这些智能可以使得人们能够在游戏的同时得到满足。然而，这种智能必须得到控制。如果游戏中的机器角色的智能明显高于玩家的能力，使得玩家对胜利丧失信心，那么玩家会放弃这样的游戏。所以，人工愚蠢(Artificial Stupidity)技术也是必不可少的。在游戏中，太强或太弱的人工智能都是不合适的。
那何种程度的人工智能才是合适的呢？回答这个问题首先要考虑怎样的机器可以算作智能机器。图灵曾经提出了“图灵实验”的概念。他认为能够通过图灵实验的机器是具有智能的。其实，在游戏中也是一样的。“图灵实验”在游戏中可以这样描述：当玩家和其他玩家同诸多机器在同时游戏时，如果这个玩家通过游戏规则中的任何方式都无法分辨游戏中的其他角色哪个是其他玩家，哪个是机器的线程，那么我们可以说这个游戏通过了“游戏中的图灵测试”。[2]一般来说，通过了“游戏中的图灵测试”的游戏是最适合玩家娱乐的。3. 游戏中的人工智能技术
人工智能在游戏中的目标主要有五个：一是为玩家提供适合的挑战；二是使玩家处于亢奋状态；三是提供不可预知性结果；四是帮助完成游戏的故事情节；五是创造一个生动的世界。这个生动的世界可以是类似现实生活中的世界，也可以是与现实世界完全不同的世界。但不管何种世界都要求有一整套能够自圆其说的游戏规则。
在游戏制作过程中，实现人工智能的关键主要有：虚拟现实与拟人化、动画效果与机器角色场景感知[3]、机器角色的机器学习和进化、玩家与机器角色之间的平衡性、人工愚蠢技术、确定性人工智能技术与非确定性人工智能技术的互补。
游戏中的人工智能的主要技术主要有：有限状态自动机(Finite State Machines)、模糊逻辑(Fuzzy Logic)、A*算法与有效寻径(A* Algorithm for Efficient Pathfinding)、脚本设计(Scripting)、基于规则的人工智能和系统(Rules-based AI and Systems)、人工生命(Artificial life)、贝叶斯推论(Bayesian Inference)和非确定性贝叶斯网络(Bayesian Networks for Uncertainty Decisions)、神经网络(Neural Networks)和遗传算法(Genetic Algorithms)等。4. 目前的局限与前景展望
就目前来说，技术上的困难主要来源于两个方面：一是游戏中的非确定状态实在太多；二是现有的硬件和计算机网络对于高级人工智能还说，速度还达不到要求。[4]
目前要解决这些困难，在技术上来说还是不成熟的。对于数量极多的非确定状态来说，尽可能地提高硬件和计算机网络的速度，可能是一个解决方法。但是要提高硬件和计算机网络的速度也并非易事。这可能要等到全息光学计算机和光互联网诞生之后才能彻底解决。但目前有效的办法是提高软件的执行速度。比如使用更有效的算法或神经网络等新技术。

Ⅳ 游戏中为什么用启发式a星算法

首先，A* 是启发式算法，在寻路过程中搜索的范围相比 Dijsktra 一般要小得多（当然，有时也可能一样）
其次，A* 算法的搜索速度和效率可控，可以通过控制代价函数来权衡搜索的速度和精度之间的关系

Ⅳ A*算法的好处

其实A*算法也是一种最好优先的算法
只不过要加上一些约束条件罢了。由于在一些问题求解时，我们希望能够求解出状态空间搜索的最短路径，也就是用最快的方法求解问题，A*就是干这种事情的！
我们先下个定义，如果一个估价函数可以找出最短的路径，我们称之为可采纳性。A*算法是一个可采纳的最好优先算法。A*算法的估价函数可表示为：
f'(n) = g'(n) + h'(n)
这里，f'(n)是估价函数，g'(n)是起点到节点n的最短路径值，h'(n)是n到目标的最短路经的启发值。由于这个f'(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。g(n)代替g'(n)，但 g(n)>=g'(n)才可（大多数情况下都是满足的，可以不用考虑），h(n)代替h'(n)，但h(n)<=h'(n)才可（这一点特别的重要）。可以证明应用这样的估价函数是可以找到最短路径的，也就是可采纳的。我们说应用这种估价函数的最好优先算法就是A*算法。
举一个例子，其实广度优先算法就是A*算法的特例。其中g(n)是节点所在的层数，h(n)=0，这种h(n)肯定小于h'(n)，所以由前述可知广度优先算法是一种可采纳的。实际也是。当然它是一种最臭的A*算法。
再说一个问题，就是有关h(n)启发函数的信息性。h(n)的信息性通俗点说其实就是在估计一个节点的值时的约束条件，如果信息越多或约束条件越多则排除的节点就越多，估价函数越好或说这个算法越好。这就是为什么广度优先算法的那么臭的原因了，谁叫它的h(n)=0，一点启发信息都没有。但在游戏开发中由于实时性的问题，h(n)的信息越多，它的计算量就越大，耗费的时间就越多。就应该适当的减小h(n)的信息，即减小约束条件。但算法的准确性就差了，这里就有一个平衡的问题。