《游戏设计2017070游戏中的常用算法》由会员分享，可在线阅读，更多相关《游戏设计2017070游戏中的常用算法（43页珍藏版）》请在金锄头文库上搜索。
1、剖析人工智能,电子游戏中的“人工智能”和广义上的人工智能有很大不同。这种智能主要是按程序员的自己的一套思考逻辑形成的，它很大程度上取决于程序员的思维方式、对游戏的构思的理解和游戏程序设计经验。,移动型“人工智能”,固定模式移动 追逐移动 躲避移动,固定模式移动,这种移动方式就是事先给定程序中物体移动模式的公式，在程序执行时物体按照相应的公式确定自己的位置和移动方式。,struct monster /建立怪物移动路径结构 CPoint p1; CPoint p2; CPoint p3; CPoint p4; CPoint p5; CPoint now; /目前所在的坐标 int d; /目前的移
2、动方向 ; int i,c,xp; monster mon2; /声明移动怪物数组,思考题：如何实现怪物沿一条曲线移动,贪吃蛇算法,追逐移动,追逐是游戏中经常使用的一种算法： If(MonsterXPlayerX) MonsterX-; Else MonsterX+; If(MonsterYPlayerY) MonsterY-; Else MonsterY+;,为了增强可玩性，在实际制作过程中经常要加一些衰减因素。 If(Monster.HP200) p=rand()%3; If (p!=1) If(MonsterXPlayerX) MonsterX-; Else MonsterX+; if(
3、MonsterYPlayerY) MonsterY-; Else MonsterY+; else Monster.HP+=5; ,躲避移动,躲避移动与追逐移动的算法刚好相反： If(MonsterXPlayerX) MonsterX+; Else MonsterX-; If(MonsterYPlayerY) MonsterY+; Else MonsterY-;,行为型人工智能,行为型AI在游戏中是经常用到的，它的主要意义是物体会随差情的改变来做一些行为动作，这里物体的概念指的是游戏中的主角、怪物或者是四周环境中的物品。,思考题：如何实现防止怪物只沿45斜向移动,物体的动作行为,在游戏中实现行为
4、型AI，只要预先设定在游戏中可能出现的情况和对应这些情况所要执行的动作。然后在程序执行过程中判断并根据判断结果执行这些行为。,例：依据生命值，怪物在遭遇战中行为表现,路径查找的概念,在游戏中从一点到达另一点往往存在着多条路径。经常要在这些路径中选择一条最佳路径。,查找最佳路径,定义迷宫的方式： 可以使用一个二维数组存储整个迷宫的状态,Maze88,使用双向链表记录小球走过的路径,struct list int m; int n; struct list *next; struct list *back; ; thpedef struct list node; typedef node *poi
5、nter;,使用BOOL类二维数组记录格子是否走过,Pass88,走迷宫的规则,先试着往下走，如果下一格有墙或走过，则试着往右走。 如果右一格有墙或者走过，则试着往左走。 如果左一格有墙或者走过，则试着往上走。 如果上一格有墙或走过，此时表示上、下、左、右都没有未走过的路，便必须后退，并删除目前的节点。,种子填充算法,种子填充算法是从多边形区域内部的一点开始，由此出发到区域内的所有像素。这一种交互式绘图中很常用的方法。,四向连通,四向连通方法指的是从区域上一点出发，可通过4个方向，即上、下、左、右移动的组合，在不越出区域的前提下，检测区域的任意像素。,四向连通区域,八向连通,八向连通方法指的是
6、区域内每一个像素，可能通过左、右、上、下、左上、右上、左下、右下这 8个方向的移动组合来检测。,八向连通域,四向连通算法,允许从4个方向寻找下一像素者称为四向算法。,八向连通算法,允许从8个方向搜索下一像素者，称为八向算法。,种子填充算法的实现,递归算法 链队列算法,四向连通填充的递归算法,将种子压入栈中 如果栈为空则程序结束 弹出栈顶元素，将其填充，并按上、下、左、右顺序判断其四连通邻接点是否已经是边界或已被填充，如不是则将其压栈。 回到第2步。,递归种子填充算法示意,S0,2,1,6,7,10,9,8,11,3,4,5,12,四连通链队列算法,将种子像素点填充，然后加入队列 如果队列空则结
7、束填充。 从队列中取出一个像素点，然后判断其上、下、左、右邻接点是否已经被填充或为边界，如果不是则将其填充并加入队列。 回到第2步。,S0,5,1,2,8,7,4,10,12,6,3,9,11,策略型人工智能,游戏中的策略型人工智能目前主要用在博弈类游戏中。算法一般都比较复杂。其原理是枚举法。先将所有可能获胜的走法统计出来。在程序运行时计算可走棋步的致胜分权值及玩家可走棋步致胜的权值。将其相比较，得出一个最佳的走法。,计算机的决策方法,以五子棋为例，计算机方式如下： 1，求得所有获胜组合 2，建立与使用获胜表 3，设定权值 4，攻击与阻挡相结合,1，求得所有获胜组合,水平方向计算60种,竖直方
8、向计算60种,计算两个对角线方向共72种,共有192种获胜方式,建立与使用获胜表,BOOL ptable1010192; 玩家 BOOL ctable1010192; 计算机 Int win2192;,获胜表初始化,设右图是统计中的第八种获胜方式则在初始化的时候会执行下列操作： ptable218=true; ptable328=true; ptable438=true; ptable548=true; ptable658=true; 其余为fslse;,获胜表的使用,在对方占领了获胜表的某位置，则将已方的此位置设这false，即不可再占。 已方下了某一子后，则遍历获胜表数组。并将每个获胜表的中已经存在的子数记入数组win192相应项内。 遍历查找有无达到5的项，如果有，则为胜。,权值设定,用一个数组记录棋盘上所有空位置的权值。权值越高，表示下一步走这里获胜的机会越大。,int grades1010;,攻击与防守,为了在游戏中获胜，不仅要抢占最佳位置，还要阻挡对方。在博弈类游戏中一般都有这样的算法。简单的说就是比较双方在各点上的权值，若对方在某点上的权值大于已方，则必须抢占。,五子棋游戏设计,
