游戏中的人工智能.pptx
第十一章 游戏中的人工智能技术,浙江大学软件学院梁秀波Email：,游戏AI概述游戏AI基本类型常用的游戏AI技术二维游戏寻路A*算法游戏AI实例迷宫寻宝,本章目录,人工智能（Artificial Intelligence）研究、开发用于模拟、延伸和扩展人脑智能的理论、方法、技术及应用系统的一门新兴学科。使用计算机来模拟人类的思维过程和智能行为，如学习、推理、思考、规划等游戏AI在游戏中使用计算机来使游戏角色模拟人的思维过程和智能行为,游戏中人工智能的概念,AI系统的4个部分,游戏AI概述,感知部分相当于人类的眼睛、耳朵等感官，用于获取游戏环境中的信息策略游戏中，通过感知部分来获取敌军数量、兵种、阵型等情报,游戏AI概述,记忆部分与人脑的记忆功能相同，将感知得到的信息以计算机所接受的格式进行存储在射击游戏中，需要存储友军和敌军的位置、武器弹药数量等信息,游戏AI概述,分析部分游戏AI系统的核心，相当于人类智能中最重要的判断推理能力游戏中的怪物选择攻击目标时，可以选择距离最近的目标，或生命值最低的目标，也可以选择战斗力最强的目标选择的过程需要通过恰当的分析方法来实现,游戏AI概述,决策部分相当于人类控制手脚运动的中枢神经信号，在游戏世界中即是将AI系统的决策和行为作用到游戏角色上在足球游戏中，游戏AI系统经过感知、记忆和分析，球员应该采取射门动作决策部分调用角色射门的动画，将射门行为表现出来。,游戏AI概述,游戏AI基本类型,漫游AI确定一个游戏对象如何在游戏世界中移动，对其运动进行控制角色扮演游戏：怪物巡逻竞速游戏：赛车选择合适路线射击游戏：士兵向目的地进发,游戏AI基本类型,行为AI规定一个游戏对象在游戏世界中的行为方式，以及面对游戏环境的动态变化做出恰当反应角色扮演游戏：怪物未发现玩家时，睡觉；玩家靠近时，惊醒体育游戏：球员无球状态下，跑位；有球状态下，传球动作游戏：怪物未被激怒，单体攻击；被激怒后，范围攻击,游戏AI基本类型,策略AI作用于多个对象的调度与资源分配常用于即时战略游戏战士位于前排，吸收伤害法师输出魔法伤害射手输出物理伤害牧师治疗受伤友军,游戏AI基本类型,常用的游戏AI技术,有限状态机表示有限个状态以及在这些状态之间的转移和动作等行为的数学模型由有限个状态组成，连成有向图图中每一条边称为一个转换接受输入，导致状态转换的发生,常用的游戏AI技术,有限状态机示意图初始状态S0沿a，b，c边转换为3种不同状态,常用的游戏AI技术,模糊逻辑采用多值逻辑，不同于计算机的二值逻辑元素属于集合的观念模糊化，存在既非完全属于某集合，又非完全不属于某集合的元素“属于”的概念量化，不同元素对同一集合有不同隶属度角色扮演游戏中，怪物对玩家的害怕程度、威胁程度,常用的游戏AI技术,人工神经网络由节点相互连接而成，相当于人脑的神经元细胞输入/输出节点：和外部环境连接，负责输入输出信息隐藏节点：位于网络内部输入节点的输出是隐藏节点的输入隐藏节点的输出是输出节点的输入,常用的游戏AI技术,人工神经网络每个神经元是一个处理单元接收的信息(x0,x1,xn)通过(W0,W1,Wm)表示互联强度以点积的形式合成输入，并与设定阈值比较,常用的游戏AI技术,遗传算法类似于大自然优胜劣汰的机制使用适者生存原理、基因遗传原理模拟生物进化过程通过随机选择、杂交、突变对程序、算法和其他参数进行操作,常用的游戏AI技术,脚本语言具有行为解释功能的AI技术规定游戏角色的智能行为什么时候、什么条件执行什么动作规定整个游戏的进程地图上出现什么，消失什么，角色状态的改变,常用的游戏AI技术,1.将游戏路径信息转化为图结构预处理：对地图信息进行预处理，构造简化的新地图，方便路径查找矩阵分析法：将游戏地图均匀转换为二阶矩阵单元，每一矩阵单元代表可能的地图元素类型,二维游戏寻路技术,2.确定地图中障碍物的处理方法将障碍对象通过简化处理，看成凸多边形只能绕行的障碍：根据特定地图信息选择一个方向绕行可穿越的障碍：直接路径连接障碍区域入口或出口，形成穿越,二维游戏寻路技术,3.确定采用何种技术寻路盲目搜索方法：除了能够区分目标位置和非目标位置之外，没有其他参考信息广度优先搜索深度优先搜索启发式搜索方法：在搜索过程中，计算目前位置与初始位置的距离，由启发函数评估，提高效率局部择优搜索最好优先搜索A*算法,二维游戏寻路技术,广度优先搜索,二维游戏寻路技术,根结点-儿子结点-孙子结点缺点：内存消耗大,Root,Root,Child1,Child2,(1),(2),(3),深度优先搜索,二维游戏寻路技术,先搜索儿子结点，后搜索兄弟,(1),(2),(3),局部择优搜索法,二维游戏寻路技术,永远沿着具有最小目标函数值的路径进行搜索不一定能够找到目标可能得到局部最优解，而不是全局最优,A*算法的估价函数f(n)=g(n)+h(n)f(n)：节点n的估价函数g(n)：起点到节点n的最短路径代价h(n)：节点n到目标节点的启发式估计代价采用估价函数能找到最短路径，称有可采纳性,A*算法及其原理,第1步执行将起点插入OPEN表OPEN表是A*算法需要维护的一张链表OPEN表用于存放可以到达而未被访问的节点OPEN表中节点均有待检验,A*算法及其原理,第2步执行将在OPEN表中查找具有最小f值的节点。对于起点而言，g=0，f=h。（1）若OPEN表为空，则表示没有相邻节点可以访问，寻路失败。（2）若OPEN表不空，则把查找到的节点作为当前节点，将其移入CLOSED表中CLOSED表也是一张链表，由于存放OPEN表中已经检验过的节点（3）若当前节点为终点，则寻路成功，转到第4步,A*算法及其原理,第3步执行循环检验当前节点相邻8个方向的每个节点（1）若该相邻节点不可到达或者已经在CLOSED表中，将其忽略。（2）若该相邻节点已存在OPEN表中，则判断从起点经过当前节点到达该相邻节点的g值是否比原来更小。若是则修改该节点的f、g、h值，并将该相邻节点的父节点设为当前节点；若不是则不进行操作,A*算法及其原理,第3步执行循环检验当前节点相邻8个方向的每个节点（3）若该相邻节点可到达而不在OPEN表中，则计算它的f、g、h值并加入OPEN表，将该相邻节点的父节点设为当前节点。（4）若所有方向检查完毕，则返回第2步；未检查完毕，则继续循环。,A*算法及其原理,第4步执行从终点开始遍历CLOSED表中的父节点，进行逆向提取遍历得到的节点即组成了从起点到终点的路径,A*算法及其原理,节点结构地图数组OPEN表结构CLOSED表结构OPEN表插入节点到CLOSED表检验当前节点相邻8个方向的节点计算相邻节点的估价函数将节点插入OPEN表,A*算法的基础实现,游戏AI实例迷宫寻宝,使用TiledMap编辑瓦片地图,游戏AI实例迷宫寻宝,修改命令行版本的A*算法修改计算估价函数的calculateValues函数修改父节点发生改变的ifChangeParent函数修改检查节点的函数checkNeighboringNodes修改A*算法的主函数aStar函数,游戏AI实例迷宫寻宝,建立实例场景类MazeScene初始化游戏场景在init函数中对场景类初始化如下，完成载入场景地图、初始化地图数组、预置提示标签、添加精灵等操作：初始化地图数组函数initMap监听屏幕触摸事件的函数addTouchListener,游戏AI实例迷宫寻宝,设置触摸监听函数添加寻路处理在A*算法的主函数中，代码框架基本相同，主要区别在于对寻路失败和寻路成功的处理在控制精灵沿路径移动的moveOnPath函数中，需要存储由父节点指针得到的路径信息，保存在结构体数组中，然后从结构体数组末尾反向提取。,游戏AI实例迷宫寻宝,添加定时器更新通过定时器更新update函数判断精灵是否到达目的地更多内容参见实验手册,游戏AI实例迷宫寻宝,游戏AI的整体设计上，分为感知、记忆、分析、决策四个部分游戏AI基本类型：漫游AI、行为AI和策略AI常用的游戏AI技术二维游戏寻路技术：地图转化、障碍处理和搜索算法A*算法基本原理游戏AI实例迷宫寻宝,小结,
