《人工智能导论》课程教学资源（PPT课件讲稿）第13章 游戏中的人工智能

第13章游戏中的人工 智能

第13章 游戏中的人工 智能

游戏中的AI 人工智能( Artificial Inte! gence,A),是让 计算机有一定的智能,能够与人进行交互的技 术 游戏中应用人工智能可增加游戏的可玩性,如 果游戏中没有人工智能,就不会有象棋的人机 对战,也不会有逃脱密室的怪物追捕英雄,更 不会有网络游戏中玩家与怪兽的激烈战斗

游戏中的AI ◼ 人工智能（Artificial Intelligence，AI），是让 计算机有一定的智能，能够与人进行交互的技 术。 ◼ 游戏中应用人工智能可增加游戏的可玩性，如 果游戏中没有人工智能，就不会有象棋的人机 对战，也不会有逃脱密室的怪物追捕英雄，更 不会有网络游戏中玩家与怪兽的激烈战斗

Fg游戏中的路径搜索 Lv46:53 更运之恒 L40=70 L026 月光酒 万圈谁所 赫顿玛尔废1 心 行会 黑 银色制庄 K四 漂 家一一N网带 2750 天雕巨昌 匣蓝布 L270 bbs. duowan com

Eg:游戏中的路径搜索

1. Android中的路径搜索 深度优先路径搜索DFS 广度优先路径搜索BFS 路径搜索算法_ Dijkstra A算法优化搜索

1. Android中的路径搜索 ◼ 深度优先路径搜索DFS ◼ 广度优先路径搜索BFS ◼ 路径搜索算法—Dijkstra ◼ A*算法优化搜索

(1)深度优先路径搜索DFS 口深度优先搜索DFS在搜索过程中不考虑各个边的开销 只考虑路径的选择。其思路是站在一个连通图的节点上 然后尽可能地沿着一条边深入,当遇到死胡同时进行 )溯,然后继续搜索,直到找到目标为止。 节点2 节点6③点 节7节点6节 节点5节点3 510 节点4 点x技术成就 图8-5深度优先示例图

(1)深度优先路径搜索DFS ❑ 深度优先搜索DFS在搜索过程中不考虑各个边的开销， 只考虑路径的选择。其思路是站在一个连通图的节点上 ，然后尽可能地沿着一条边深入，当遇到死胡同时进行 回溯，然后继续搜索，直到找到目标为止

深度优先搜索的基本算法结构:递归实现 Procedure dfs try ■Fori:=1 to maxr do begin f子结点m符合条件then begin 产生的子结点m入栈; i子结点mr是目标结点then输出 else dfs try(i+1) 栈顶元素出栈; End ■End;

深度优先搜索的基本算法结构：递归实现 ◼ Procedure dfs_try(i); ◼ For i:=1 to maxr do ◼ begin ◼ if 子结点mr符合条件 then ◼ begin ◼ 产生的子结点mr入栈； ◼ if子结点mr是目标结点 then 输出； ◼ else dfs_try(i+1); ◼ 栈顶元素出栈； ◼ End; ◼ End;

深度优先搜索S到T的搜索路径 留们6:17PM @62PM 国 用步几229 图36搜索目标的深度优先图-7搜索目标的采度优先

◼ 深度优先搜索S到T的搜索路径 S T S T

(2广度优先路径搜索BFS 口广度优先搜索是在游戏中使用较多的一种搜索算法,其 基本思路是站在一个节点上,先将所有连接到该节点的 节点访问到,然后再继续访问下一层,直到找到目标为 节点2 Eg扫雷游戏 节点6节点5 节点4节点 叫 节点点力点6等节越 图8-8广度优先算法搜索过程

(2)广度优先路径搜索BFS ❑ 广度优先搜索是在游戏中使用较多的一种搜索算法，其 基本思路是站在一个节点上，先将所有连接到该节点的 节点访问到，然后再继续访问下一层，直到找到目标为 止。 Eg:扫雷游戏

BFS一广度优先搜索 A 氵/B BFS在访问了起始页点A之 后,由A出发,依次访问A的 各个未被访问过的邻接顶点 B,D,,c,然后再顺序访问 4(D C)3 : B,D,…,c的所有还未被访 问过的等接顶点。再从这些访 问过的项点出发,再访问它们 的所有还未被访问过的邻接顶 点,…如此做下去,直到图 中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜 索过程每向前走一步可能访 9问一批顶点

BFS – 广度优先搜索 BFS在访问了起始顶点A 之 后, 由 A 出发, 依次访问 A 的 各个未被访问过的邻接顶点 B, D,…, C, 然后再顺序访问 B, D, …, C 的所有还未被访 问过的邻接顶点。再从这些访 问过的顶点出发，再访问它们 的所有还未被访问过的邻接顶 点，… 如此做下去，直到图 中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜 索过程,每向前走一步可能访 问一批顶点。 A D C E G B F H I 1 2 4 3 5 6 7 8 9

BFS的代码分析 void BFSO queueq;/队列 g push(st);初始点入队列 Whle(! g empty)爪队列中还有要处理的点 从队列中取出下一个处理的点p; for(p的所有邻接点) if该邻接点满足搜索条件) g- push邻接忘; 标记该邻接点为已访问

BFS的代码分析 void BFS() { queue q;//队列 q.push(st);//初始点入队列 while(!q.empty())//队列中还有要处理的点 { 从队列中取出下一个处理的点p； for(p的所有邻接点) if(该邻接点满足搜索条件) { q.push(邻接点); 标记该邻接点为已访问； } } }