chapter11 游戏中的人工智能

第十一章 游戏中的人工智能技术浙江大学软件学院 梁秀波 Email：liangxbcst.zju.edu.cn 游戏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*算法二维游戏寻路技术广度优先搜索二维游戏寻路技术 根结点->儿子结点->孙子结点 缺点：内存消耗大RootRootChild1Child2RootChild1Child2GChild1GChild2GChild3GChild4(1)(2)(3)深度优先搜索二维游戏寻路技术 先搜索儿子结点，后搜索兄弟RootChild1GChild1GChild2RootChild1RootChild1GChild1(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实例迷宫寻宝小结