3D游戏开发步步高系列课程(5)：人工智能

3D游戏开发步步高系列课程（5）人工智能付仲恺微软特邀开发专家议题•介绍算法复杂度概念–O(n)概念•路径查找算法–常用路径查找算法介绍•DFS，BFS，Dijkstra，A*•如何在游戏中利用Dijkstra算法？–添加敌人–演示课程准备•基本软件开发知识•Microsoft®VisualC#®基础Level200Level2003D游戏引擎使用需求•Microsoft®.NETFramework2.0•Microsoft®VisualC#®ExpressEdition•Microsoft®DirectX®SoftwareDevelopmentKit(SDK)基本人工智能•我们希望敌人能够在游戏中阻碍玩家–由于我们的游戏棋盘非常类似于迷宫，因此从敌人到玩家之间的路径通常不是一条直线–敌人会与墙发生碰撞，并且改变运动方向–我们需要为敌人决定一条最佳路线来跟踪玩家•我们需要路径查找算法–DFS，BFS，Dijkstra算法，A*算法议题•介绍算法复杂度概念–O(n)概念•路径查找算法–常用路径查找算法介绍•DFS，BFS，Dijkstra，A*•如何在游戏中利用Dijkstra算法？–添加敌人–演示算法复杂度•大写O通常用于表示算法在执行过程中的时间需求•用于搜索，排序，碰撞检测等等.•表示方式•O(k)-算法使用常量时间•O(log(n))-算法使用log(n)时间•O(n)-算法使用线形时间•O(nlog(n))-算法使用nlog(n)时间•O(n*n)-算法使用n*n时间•O(n^n)-算法使用n^n时间算法复杂度议题•介绍算法复杂度概念–O(n)概念•路径查找算法–常用路径查找算法介绍•DFS，BFS，Dijkstra，A*•如何在游戏中利用Dijkstra算法？–添加敌人–演示深度优先搜索（DFS）•沿着某一方向前进，无法前进则改变方向或者退回，直到达到目的地–类似于走迷宫–找到一条路径，但不一定是最短路径•采用栈（Stack）数据结构•实现简单广度优先搜索（BFS）•类似于扩散运动，沿着各个方向同时前进–获得所有可达到目的地的路径•采用队列（Queue）数据结构•实现简单Dijkstra算法•基于图论的单源最短路径算法–带权图，权值非负•采用贪心算法–每一次都选择距离最短的邻接结点–理论依据：•对于一条最短路径来讲，在这条路径上的每一段子路径都是最短的•在我们的游戏中使用Dijkstra算法Dijkstra最短路径算法演示•寻找从s到t的最短路径s3t267452418291415530204416116196Dijkstra最短路径算法演示s3t267452418291415530204416116196∞∞∞∞∞∞∞0距离值S={}PQ={s,2,3,4,5,6,7,t}Dijkstra最短路径算法演示s3t267452418291415530204416116196∞∞∞∞∞∞∞0距离值S={}PQ={s,2,3,4,5,6,7,t}delminDijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0距离值S={s}PQ={2,3,4,5,6,7,t}减少key值∞X∞∞XXDijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0距离值S={s}PQ={2,3,4,5,6,7,t}∞X∞∞XXdelminDijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0S={s,2}PQ={3,4,5,6,7,t}∞X∞∞XXDijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0S={s,2}PQ={3,4,5,6,7,t}∞X∞∞XX减少key值X33Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0S={s,2}PQ={3,4,5,6,7,t}∞X∞∞XXX33delminDijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞∞14∞0S={s,2,6}PQ={3,4,5,7,t}∞X∞∞XXX3344XX32Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞14∞0S={s,2,6}PQ={3,4,5,7,t}∞X∞∞XX44Xdelmin∞X33X32Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,6,7}PQ={3,4,5,t}∞X∞∞XX44X35X59X24∞X33X32Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞14∞0S={s,2,6,7}PQ={3,4,5,t}∞X∞∞XX44X35X59Xdelmin∞X33X32Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞14∞0S={s,2,3,6,7}PQ={4,5,t}∞X∞∞XX44X35X59XX51X34∞X33X32Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,3,6,7}PQ={4,5,t}∞X∞∞XX44X35X59XX51X34delmin∞X33X3224Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,3,5,6,7}PQ={4,t}∞X∞∞XX44X35X59XX51X3424X50X45∞X33X32Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,3,5,6,7}PQ={4,t}∞X∞∞XX44X35X59XX51X3424X50X45delmin∞X33X32Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,3,4,5,6,7}PQ={t}∞X∞∞XX44X35X59XX51X3424X50X45∞X33X32Dijkstra最短路径算法演示s3t2674518291415530204416116196159∞∞14∞0S={s,2,3,4,5,6,7}PQ={t}∞X∞∞XX44X35X59XX51X34X50X45delmin∞X33X3224Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞14∞0S={s,2,3,4,5,6,7,t}PQ={}∞X∞∞XX44X35X59XX51X34X50X45∞X33X32Dijkstra最短路径算法演示s3t267452418291415530204416116196159∞∞14∞0S={s,2,3,4,5,6,7,t}PQ={}∞X∞∞XX44X35X59XX51X34X50X45∞X33X32A*算法•启发式搜索–在搜索中涉及到三个函数•g(n)=从初始结点到结点n的耗费•h(n)=从结点n到目的结点的耗费评估值，启发函数•f(n)=g(n)+h(n)从起始点到目的点的最佳评估值–每次都选择f(n)值最小的结点作为下一个结点，直到最终达到目的结点–A*算法的成功很大程度依赖于h(n)函数的构建•在各种游戏中广泛应用A*算法数据结构•Open列表和Closed列表–Open列表•包含我们还没有处理到的结点•我们最开始将起始结点放入到Open列表中–Closed列表•包含我们已经处理过的结点•在算法启动时，Closed列表为空初始化OPEN列表初始化CLOSED列表创建目的结点；称为node_goal创建起始结点；称为node_start将node_start添加到OPEN列表whileOPEN列表非空{从OPEN列表中取出f(n)值最低的结点n将结点n添加到CLOSED列表中if结点n与node_goal相等then我们找到了路径，程序返回nelse生成结点n的每一个后继结点n'foreach结点n的后继结点n'{将n’的父结点设置为n计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用计算g(n‘)=g(n)+从n’到n的开销计算f(n')=g(n')+h(n')ifn‘位于OPEN或者CLOSED列表and现有f(n)较优then丢弃n’，处理后继n’将结点n‘从OPEN和CLOSED中删除添加结点n‘到OPEN列表}}returnfailure（我们已经搜索了所有的结点，但是仍然没有找到一条路径）A*算法伪代码启发式评估函数h(n)不同的启发式评估函数可以带来A*算法不同的行为：1.在极端情况下，如果h(n)为0，只有g(n)在起作用，那么A*算法将退化为Dijkstra算法，并且总能保证找到最短路径2.如果h(n)总是低于（或者等于）从结点n到目的结点的实际开销，那么A*算法保证总能找到最短路径。越低的h(n)，意味着A*算法需要展开越多的结点，效率也就越低3.如果h(n)能够始终准确的评价从结点n到目的地的开销，A*算法将只会生成最佳路径，而不会扩展任何额外的结点，这将使得算法速度非常快4.如果h(n)有时大于从结点n到目的地的实际开销，那么A*算法不能保证找到最短路径，但是它的运行速度较快5.在另一种极端情况下，如果h(n)远大于g(n)，只有h(n)在起作用，那么A*算法将会退化为Best-First-Search.常用启发式函数h(n)曼哈顿距离（Manhattandistance）h(n)=D*(abs(n.x-goal.x)+abs(n.y-goal.y))常用启发式函数h(n)对角线距离（Diagonaldistance）h(n)=D*max(abs(n.x-goal.x),abs(n.y-goal.y))h_diagonal(n)=min(abs(n.x-goal.x),abs(n.y-goal.y))h_straight(n)=(abs(n.x-goal.x)+abs(n.y-goal.y))h(n)=D2*h_diagonal(n)+D*(h_straight(n)-2*h_diagonal(n)))常用启发式函数h(n)欧几里德距离（Euclideandistance）h(n)=D*sqrt((n.x-goal.x)^2+(n.y-goal.y)^2)议题•介绍算法复杂度概念–O(n)概念•路径查找算法–常用路径查找算法介绍•DFS，BFS，Dijkstra，A*•如何在游戏中利用Dijkstra算法？–添加敌人–演示游戏中的路径查找•Dijkstra’s算法–如何工作？•在游戏加载时构建结点路径表•由于我们有n^2个结点，因此我们需要花费O(n^2)的时间来构造结点路径表•幸运的是，我们的n并不是非常大•在运行时，我们只需要索引结点数据，这个操作只需要O(k)复杂度–程序在启动时花费较多时间构建结点路径表，在运行时只需要非常少的时间就能够索引出来游戏中的路径查找•如何处理？•对于每一个结点，考虑源地址和目的地址•其余所有的结点仍然保存在池中•取出离源结点最近的结点，称之为closeNode•每个closeNode检查到达目的地的距离•距离最短的closeNode将会胜出，这个结点将作为下一个closeNode•代码位于AdvancedPathfinding.cs游戏中的路径查找•所需变量–Source•敌人的当前位置–NodeToBeReached•长期的目的地（我们尝试要到达的目的地）–Destination•短期目的地（要移动到的