1、 人工智能与专家系统课程设计-迷宫游戏人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302目录序言-3算法详解-3程序代码内容与说明程序各个全局变量的声明-7主体程序的实现-8执行结果演示-15设计心得体会-17参考书目-17附录：程序源代码-18序序 言言“人工智能”也就是所谓的 AI（artifical intelligence） ，它是一门抽象的技术，人工智能程序的编写不需要遵循任何即定的思考模式或者规则，而游戏中的 AI 完全按照程序员人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302自己的思考逻辑而发展。这就是说，程序员越是聪明越是能够写出更为精
2、明的计算机人工智能程序，这和程序员自身的条件有着很大的关系。如果对于一个很陌生不熟悉的游戏领域，程序员从来没有接触过，这样即使有很高的编程水平，也没有办法实现我们想要达到的目标，根本不可能在游戏中将所有的情况包罗其中。人工智能具有特定的三种思考模式，分别为移动模式，行为模式和策略模式。顾名思义，给定一个物体移动路径的公式，物体按照这样的公式来移动的就是移动模式。这种情况很多见，例如：某个物体追着玩家跑，目标射击等等。它又可以分为固定模式移动，追逐移动，躲避移动。策略型人工智能是 AI 中比较复杂的一种，最常见的运用策略型 AI 游戏是棋盘类的游戏，通常计算机必须判断目前情况下所有可走的棋步和可
3、能获胜的情况，并计算目前计算机可走棋步的制胜分数或者是玩家可走棋步的制胜分数，最后决定出最佳的走法。行为型 AI 在游戏中是经常会运用到的，它的主要意义是物体会随着情况的改变来做出一些行为动作，而这些物体可以是游戏中的主角、怪物或者是四周环境中的物品。而此次迷宫游戏的设计也是属于人工智能中的行为模式。算法详解算法详解 路径搜寻的概念路径搜寻与行为型人工智能有直接的关系。在迷宫游戏中，涉及路径搜寻时必须设定物体的一些走出迷宫的法则。如前面有路时就往前走，前面的路走过就往没走过的地方走等。这些法则必须确实可以让物体搜索迷宫中的每一块区域来找到出口，若走迷宫的法则设定得不完整，那么物体就有可能在同一
4、个地方兜圈子，永远找不到出口了。此外，为了让物体在走出迷宫后能知道正确走出迷宫的路径，必须给物体一张地图来记录所走过的路径，这张图就是一个链表结构，当物体成功走出迷宫后，整个链表就是正确走出迷宫的路径。如图 1 所示图 1图 1 中，实线部分为小球走迷宫的最短路径，依照走迷宫的规则每移动到新一格时，该区域就被增加到链表中，而当走过的区域并非正确路径时（图中虚线部分） ，则从链表中删除。例如：上图中虚线部分为小球所走过的区域，但小球进入该区域后发现是死路，因此必须倒退，每倒退一格时，就表示该格不是正确路径，因此从链表中删除；最后，当小球走出迷宫后，正确路径便会记录在链表中。人工智能程序设计-迷宫
5、游戏 计算机 013 班 郭玥 01095302 搜寻最佳路径在这个迷宫路径搜寻的程序中，我以一颗小球来走迷宫，小球会自动搜寻到迷宫的入口，接着自动找寻出口，当找到出口后便记录着正确走出迷宫的路径，按F2键察看此最短路径。 定义迷宫的方式使用一个整数的二维数组 maze88来存储整个迷宫的状态。如图 2出口 图 2定义数组时，设定出口元素值为 3，入口的元素值为 2，墙元素值为 1，通道的元素值为 0。图 2 中，代表入口的数组元素为 maze01，同时，以变量 m,n 分别代表数组一维与二维的索引值，具体如下所示：mazemn=3 / 出口mazemn=2 / 入口mazemn=1 / 墙m
6、azemn=0 / 通道 双向链表的使用在程序中我使用双向链表记录小球所走过的路径，结构定义如下：struct list /定义链表结构入口人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302int m;int n;struct list*next; /指向下一结点struct list*back; /指向前一个结点;typedef struct list node; /定义结点typedef mode*pointer; /定义动态指针当小球走迷宫时，主要王没有走过的格子走，程序使用一个二维的布尔数组 pass88来记录格子是否走过，小球走向未走过的格子时，这一格会被加到链表
7、里，而当小球走到其上、下、左、右有墙或者都已经走过的格子时，此时必须倒退，而每倒退一格就表示那一格是错误的格，因此将其从链表中删除，直到最后走出迷宫时，链表中每一结点便是正确的行进路线。如图 3：图 3图中，虚线部分是小球所走过的错误路径，在走进错误区域后，都是死路。因此小球必须沿原先进入的路径后退。在后退后，原先加到链表中的错误结点也会同时从链表中删除，而后退到有其他未走过的格子可以走时，就往那一个格子前进，最后找到出口后，正确的行进路线的结点便记录在链表中。 走迷宫的规则 先试着往下走，若下一格有墙或者走过，则试着往右走 若右一格有墙或者走过，则试着往左走 若左一格有墙或者走过，则试着往上
8、走 若上一个有墙或者走过，此时表示上、下、左、右都有未走过的格，便必须往后退，回到上一结点位置并删除目前结点人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302以下列出依各条规则所设定出的算法：1) 试图往下走的程序代码：if(下一格是墙)/*试图往右走的程序代码*/elseif（下一格走过）/*试图往右走的程序代码*/else/往下走并新增结点2) 试图往右走的程序代码：if(右一格是墙)/*试图往左走的程序代码*/elseif（右一格走过）/*试图往左走的程序代码*/else/往右走并新增结点3) 试图往左走的程序代码：if(左一格是墙)/*试图往上走的程序代码*/els
9、eif（左一格走过）/*试图往上走的程序代码*/else/往左走并新增结点4) 试图往上走的程序代码：if(上一格是墙)/回上一个结点并删除目前结点elseif（上一格走过）/回上一个结点并删除目前结点else/往上走并新增结点将上面 4 组算法结合起来，就得到整个走迷宫的判断式结构了 程序内容说明：本迷宫游戏的主要功能如下： 程序执行式自动搜寻入口与出口人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302 按F1键可重新进行搜寻 按F2键辉县是正确走迷宫的路径 若迷宫无出口，则搜寻结果会显示无出口的信息程序代码内容与说明程序代码内容与说明一 程序各个全局变量的声明int m
10、aze88 = 1,1,1,1,1,1,1,1,2,0,0,1,0,0,0,1,1,1,0,0,0,1,1,1,1,0,0,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,0,1,1,0,1,0,1,0,0,1,1,3,1,1,1,1,1,1;BOOL pass88;int i,j,m,n,lastm,lastn;BOOL start= true,search= true,go;pointer ptr,preptr,first;char str10;说明：1) 第 1、2 行程序代码定义大小为 88 迷宫数组的内容，其中值为 2 与 3 的元素就是迷宫的入口与出口2
11、) 第 3 行程序代码定义一个 pass 数组，用来记录迷宫中各个格子是否走过，举例来说，若 maze45走过，则 pass45会被设定为 true3) 第 4 行程序代码定义的格个整数变量用途说明如下变量名称 说明i 计数变量j 计数变量m 小球所在位置的第一个索引值n 小球所在位置的第二个索引值lastm 上一次小球所在位置的第一个索引值lastn 上一次小球所在位置的第二个索引值4) 第 5 行程序代码所定义的 3 个布尔变量 start、search、go 分别用以表示程序开始，重新搜寻以及显示最短路径5) 第 6 行程序代码定义了 ptr、preptr 与 first 动态指针，分别
12、代表目前结点、上一个结点与第一个节点。二 主体程序的实现canvasFrame:canvasFrame()人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302/*建立窗口与加载图文件的程序代码 */for(i=0;im = m;ptr-n = n;ptr-next = NULL;ptr-back = NULL;first = ptr;说明：1) 第 3-10 行程序代码为一个双层循环，用来搜寻二位数组中，元素值为 2 的元素；第6-8 行程序代码判断若找到了此元素，则结束循环，此时 I 与 j 的值便是代表迷宫入口的索引值2) 第 11、12 行程序代码将 i，j 的值赋予给
13、 m、n，这是第一个链表结点中所要存储的值3) 第 13 行程序代码建立第一个节点的指针 ptr，接着 14、15 行程序代码设定其中的成员变量 m 与 n 的值，第 16、17 行程序代码则将结点的前后指针指向 NULL。如此，第一个结点结构如下：其中结点的 back 指针是用以指向链表中的上一个结点， next 指针则是指向下一个结点，如此便形成双向链表，而小球在走迷宫时才能够前进与后退4) 第 18 行程序代码则设定 first 等于 ptr，用来记录链表第一个结点的位置void canvasFrame:OnTimer(UINT nIDEvent) if(start)Start(); /
14、开始搜寻elseif(search)Search(); /进行搜寻if(go)Go(); /显示最短路径m n back next人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302CFrameWnd:OnTimer(nIDEvent);说明：在 OnTimer 函数中则是会依目前程序的状况来执行开始搜寻，显示最短路径等于自定义函数。程序于一开始进行搜寻时便会执行 Start 函数，将小球的图案显示于入口上。接下来每次进行搜寻而小球移动时，会执行 Search 函数，而当用户按下 F2键时，则会调用 Go 函数来显示走出迷宫最短路径void canvasFrame:Start
15、()CClientDC dc(this);mdc-SelectObject(tile);for(i=0;iSelectObject(ball);dc.BitBlt(ptr-n*40,ptr-m*40,40,40,mdc,0,0,SRCCOPY);start = false;lastn = ptr-n;lastm = ptr-m;说明：1) 在 start 函数中，第 4-8 行程序代码会先贴上迷宫中的墙。使用双层循环在条件式mazeij = 1 成立时，则以左上角的贴图坐标(j*40,i*40,) 来进行贴上墙的动作2) 第 10 行程序代码则以 ptr 所指结点中 m 与 n 成员变量的值来
16、计算贴图坐标，此时 ptr所指结点为第一个结点，因此贴图后，小球会出现在迷宫入口位置上3) 接下来第 11 行程序代码将 start 变量设定为 false，第 12、13 行程序代码则将结点 m与 n 的值记录在 lastm 与 lastn 中，以便下次执行 OnTimer 时可以覆盖掉前一次的贴图void canvasFrame:Search()CClientDC dc(this);mdc-SelectObject(tile);for(i=0;iSelectObject(ball);lastn = ptr-n;人工智能程序设计-迷宫游戏 计算机 013 班 郭玥 01095302lastm
17、 = ptr-m;if(mazem+1n=1) /下一格是墙/*判断行进方向与变更链表内容的程序代码 */elseif(passm+1n) /下一格走过if(mazemn+1 = 1) /右一格是墙if(mazemn-1 =1) /左一格是墙if(mazem-1n = 1) /上一格是墙if(ptr-back != NULL)ptr = ptr-back;free(ptr-next);ptr-next = NULL;m = ptr-m;n = ptr-n;elseif(passm-1n) /上一格走过if(ptr-back != NULL)ptr = ptr-back;free(ptr-next);ptr-next = NULL;m = ptr-m;n = ptr-n;elsem-=1; /往上一格ptr-next = (pointer)malloc(sizeof(node);ptr-next-m = m;ptr-next-n = n;preptr = ptr;ptr-next-next = NULL;passmn = true;ptr = ptr-next;ptr-back = preptr;else/*判断行进方向与变更链表内容的程序代码*/
