单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2019/12/18,#,游戏,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,作用,于多个对象的调度与资源分配,常用于即时战略游戏,战士位于前排，吸收伤害,法师输出魔法伤害,射手输出物理伤害,牧师治疗受伤友军,游戏,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,Root,Child1,Child2,GChild1,GChild2,GChild3,GChild4,(1),(2),(3),深度优先搜索,二维游戏寻路技术,先搜索儿子结点，后搜索兄弟,Root,Child1,GChild1,GChild2,Root,Child1,Root,Child1,GChild1,(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,实例,迷宫寻宝,小结,