3D游戏开发技术-第三章游戏开发中的人工智能详解

北京工业大学第三章游戏开发中的人工智能技术授课人：张勇提纲•AI的基本概念•游戏中简单的AI模式•游戏中常用的AI技术有限状态机模糊逻辑等A*算法神经网络遗传算法提纲•AI的基本概念•游戏中简单的AI模式•游戏中常用的AI技术有限状态机模糊逻辑等A*算法神经网络遗传算法简介（1）•AI的定义计算机或其他机器有能力执行那些通常认为需要智慧才能做的事。创建拥有智慧的机器的过程或科学。•GameAI使得游戏表现出与人的智能行为/活动相类似，或者与玩家的思维/感知相符合的特性。融合娱乐性。简介（2）•游戏中涉及的AI技术有限状态机基于规则的系统，有限个状态连接成一有向图，每一条边称为一个转移。专家系统知识表示专家的经验，并在此基础上作自动推理。案例式推理将输入与数据库中已有的案例进行比较，选取最为相近的案例，其已有的解决方法即为输出。简介（3）•游戏中涉及的AI技术（续）产生式系统包含多个产生式，每一条产生式由条件和动作两部分组成，当产生式的条件满足时，系统就执行相应的动作。决策树给定输入，从树的根部开始，将输入与当前结点相比较，选择当前结点的某一个子结点作为下一次比较的对象。当到达树的叶子时，则给出相应的决策。搜索方法找到一列动作（或状态转移），使得最终的结果满足某一特定目标。简介（4）•游戏中涉及的AI技术（续）多Agent研究在多个相互竞争相互合作的智能体之间所产生的交互智能行为。人工生命多agent系统一种，试图将生命系统中一些普遍规律应用到虚拟世界的人工智能体上。群组行为(Flocking)人工生命的一类，研究协同移动技术，例如人工智能体如何在大量的羊群中移动。简介（5）•游戏中涉及的AI技术（续）Robotics•让机器在自然环境下交互的工作遗传算法•直接模拟生物进化过程，通过随机选择、杂交和突变等对程序、算法或者一系列参数进行操作神经网络•模拟动物神经系统功能的机器学习方法•通过反复调节系统内部中各个神经元之间的连接参数，使得训练得到的系统在大多数情况下作出优或者近似优的反应简介（6）•游戏中涉及的AI技术（续）模糊逻辑•与传统二值（对-错）逻辑不同，模糊逻辑用实数表示物体隶属于某一类的可能性置信网络•提供建立不同现象之间内在因果关系的工具，并利用概率理论处理未知的和不完全的知识•对当前状态作出判断，并决定下一步可能的动作以及其带来的后果简介（7）•GAMEAI技术的分类定性•定性行为或其表现是特定的，并且可预测，没有不确定性。非定性•非定性行为有某种不确定性，有点不可预测。具体实例是，让NPC学习到适应玩家的作战战术。提纲•AI的基本概念•游戏中简单的AI模式•游戏中常用的AI技术有限状态机模糊逻辑等A*算法神经网络遗传算法定性AI算法•确定性算法指预先编入代码当中的可预测的行为–从最简单的算法开始•例如，系统中有一颗小行星，以某一速度作匀速直线运动，它在任意时刻的位置由下列公式决定：•某种程度上，它们是智能的，但是这种智能是确定的，可预测的追逐/闪躲AI•当智能体找到目标后，一心一意向其移动，而不考虑任何其他的因素，例如障碍物、另外的目标等•非常机械化•在每一帧中，智能体计算其到目标的前进方向，并根据其速度，前进一段距离砖块环境•基本追逐算法if(predatorXpreyX)predatorX--;elseif(predatorXpreyX)predatorX++;if(predatorYpreyY)predatorY--;elseif(predatorYpreyY)predatorY++;追逐/闪躲AI•基本追逐算法if(preyXpredatorX)preyX++;elseif(preyXpredatorX)prey--;if(preyYpredatorY)preyY++;elseif(preyYpredatorY)prey--;•改进的Tracking算法：在每一帧中，智能体仍然首先计算其到目标的前进方向这时，智能体的速度允许发生变化，并根据更新后的速度，计算下一帧的位置速度有一个上限，超过这个上限，智能体的速度将减慢，直到重新加速为止追逐/闪躲AI连续环境•连续环境运动=几何变换（2D?）追逐/闪躲AI群聚算法•1987年，CraigReynolds在SIGGRAPH论文《Flocks,Herbs,andSchools:ADistributedBehavioralModel》中第一次提到了群聚算法，这个算法在日后广泛地被人们使用，用来仿真整群的鸟、鱼或其他生物群。•Reynolds的鸟群运动三条规则是：（1）凝聚：每只鸟都向它邻近同伴的平均位置移动。（2）对齐：每只鸟都把自己前进的方向和它邻近同伴的平均方向保持一致。（3）分隔：每只鸟在飞行时都要避免碰上身边其它同伴。就这么简单!然而简单的规则却保证了鸟群纷繁地、优雅地飞行而队形不散。群聚算法•为了分析我们这个群聚算法，我们需要理解一些基本的概念：（1）单位的视野，我们以r为单位的视野半径，以θ为视野角度，落在这个圆弧内的所有物体都是可见的。（2）避开规则（Avoidancerule），单位不会被彼此撞上。（3）凝聚规则，单位离得太远就应该靠近一点，这个规则和避开规则合在一起，从而形成了群聚。群聚算法群聚算法单位的视野宽视野VS窄视野以势函数实现移动•Lenard-Jones势函数–代表分子间的吸引和排斥的势能，取该势函数的导数，可得代表力的函数。追逐、闪躲、避碰、群聚•追逐、闪躲•避开障碍物引力强度A设置为0，只保留斥力分量。同时调整B，决定斥力强度，以及m来决定衰减。•群聚通过引力分量控制。以势函数实现移动以势函数实现移动提纲•AI的基本概念•游戏中简单的AI模式•游戏中常用的AI技术有限状态机模糊逻辑等A*算法神经网络遗传算法有限状态机（FSM）•状态（要采取的行为）追击随机走动巡逻吃•转移（发生转移的原因）时间片结束发生某个事件完成某个行为伐木将木头运往最近的仓库足够多木材放下木头:返回林场到仓库到林场有限状态机（FSM）•条件定义发生转移的先决条件•输入和事件允许状态机对环境变化作出反应•动作作为状态的一部分，或者伴随转移出现状态空间图•有向图•每个结点表示系统状态模型，每条弧表示状态转移所伴随的动作行为•结点可以是无穷多个•有些结点之间可能没有弧相连接FSM设计步骤•状态的设置。•设置一个开始状态。•创建一个映射，每个输入对应一个状态间转换函数。•编写状态转换函数。模糊逻辑•传统逻辑把思维过程绝对化，从而达到精确、严格的目的•举例：一个被讨论的对象X，要么属于某一个集合A，要么不属于该集合，两者比居其一，而且两者仅居其一，决不模棱两可•对于命题：张三的性格稳重，如何判断这一命题的真假？模糊逻辑•对于上述的例子，模糊逻辑允许我们用一个[0,1]的实数表示X属于A的隶属程度。传统逻辑即隶属程度只能从0和1之间选择的情况•对于“性格稳重”这个模糊概念，能够用“一点而也不稳重”、“不太稳重”、“不好说”、“有点稳重”、“挺稳重”、“很稳重”等没有明确界限的词语形容模糊逻辑的应用•将重心转移至物体属于某个集合的隶属程度上•在AI领域的主要应用为–决策–行为选择–输入、输出过滤符合逻辑操作•设A,B,C均为U中的模糊集–模糊并•若对8x2U，均有c=max(A(x),B(x))，则称C为A与B的模糊并–模糊交•若对8x2U，均有c=min(A(x),B(x))，则称C为A与B的模糊交例子15feet6feet7feet15feet6feet7feet大约6英尺长的高的人•归属度函数与15feet6feet7feet或15feet6feet7feet非15feet6feet7feet模糊控制实例•举例：车辆驾驶•前提：两辆车之间不能相撞•在模糊逻辑中的实现：–用两个变量描述每一辆车•当前时刻，车与前面一辆车之间的距离d•当前时刻与前一时刻距离的差d模糊控制实例•Ifd=0且d=两个车位长，保持现有速度•Ifd0且d两个车位长，减慢速度•Ifd0且d两个车位长，加快速度模糊的有限状态机•将模糊逻辑和有限状态机结合–状态之间的迁移不再是确定的–同时有多个状态FSMFuSM路径规划•状态智能体在空间的位置其他离散空间•体素•室内位置•局部区块（tile）•操作从一个位置移动到其他位置路径规划算法•必须对状态空间进行搜索，才能转移至目标状态•完全性如果目标状态存在，算法是否能够将其找到？•时间复杂度•空间复杂度•能够找到最优解搜索策略•如何评价搜索算法时间：多长时间能够找到解找到的解是最优、次优还是其他•盲目搜索没有先验知识仅仅知道目标状态是什么•经验搜索用经验公式表示拥有的先验知识“经验”只能作相对简单、低级的决策启发式图搜索过程•利用所处理问题的启发信息引导搜索，称为启发式搜索，可以达到减少搜索范围，降低问题复杂度的目的。•启发式图搜索算法A–基本思想：如果既考虑从起始节点到节点n的路径费用，又考虑从节点n到达目标节点的费用，即定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。–其形式为：f(n)=g(n)+h(n)n为被评价的节点。用此函数来排列Open表中节点顺序的图搜索算法称为A算法。最佳图搜索算法A*在算法A中，当h(n)≤h*(n)时，我们把这个算法称为A*算法，A*算法具有如下的性质：•完备性：如果问题有解，则算法一定能找到解。•可采纳性：如果问题有解，则算法一定能找到最佳解。即算法总能找到一条从S到目标节点的最佳路径。•最优性：对两个算法A*算法A1和A2，若对所有非目标节点均有h1(n)〈h2(n)≤h*(n)则算法A1展开的节点数目至少和A2一样多。（启发函数和A*算法的关系）不同启发函数对比下表为不同启发函数，应用A*算法求最佳解时所扩展和生成的节点数。启发函数扩展节点数生成节点数h（n）=0h（n）=W（n）h（n）=P（n）2665461311启发式函数的选取影响搜索效率。A*路径规划假设从A点移动到一墙之隔的B点，绿色的是起点A，红色是终点B，蓝色方块是中间的墙。A*路径规划f(n)=g(n)+h(n)g(n)为从起点A沿着产生的路径，移动到网格上指定方格的移动耗费（水平或者垂直移动的耗费为10，对角线方向耗费为14）h(n)为从网格上那个方格移动到终点B的预估移动耗费（曼哈顿距离）A*路径规划A*路径规划AI设计技巧•对于行为简单的物体，使用简单的确定性AI技术•对于不是主要角色，但是需要一点智能行为的物体，可以对其设定几种模式，并加上一点随机的因素扰动即可•对于比较重要的角色，可以使用有限状态机技术，加上另外一些辅助技巧•对于最最重要的角色，你需要利用一切可能利用的技术状态驱动，使用条件逻辑、概率、以及经历过的状态等控制状态转移如果状态转移条件满足，物体要能够发生强制性状态转移动作A*路径规划建议•使用更小的地图或者更少的寻路者。•不要同时给多个对象寻路。•路径规划的层次细节模型。•预处理地图。•平滑路径。•不规则区域。神经网络•监督学习输入学习样本，随机给定初始值，根据目标输出，使用反向传播算法对网络的权值和偏置进行反复的调整训练，使输出的向量与期望向量尽可能地接近，当网络输出层的误差平方和小于指定的误差时训练完成。•自动控制感应到前方、两侧的障碍物作为输入，输出履带的移动。•威胁评估以对方地面单位数量、空中单位数量、地面单位是否有移动机箱、空中单位是否有移动机箱等为输入，输出空中威胁、地面威胁、陆空威胁或者无威胁作为•攻击或者逃离友军个数、敌人状况等神经网络遗传算法•遗传算法模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。遗传算法•敌人的优化组合•场景的自动生成•游戏中防守/攻击位置的选择•路径规划ThankYou!