迷宫游戏设计报告

人工智能与专家系统

课程设计

---------迷宫游戏

目录

序言-------------------------------------------------------------3

算法详解-------------------------------------------------------3

程序代码内容与说明

程序各个全局变量的声明---------------------------------7

主体程序的实现----------------------------------------------8

执行结果演示------------------------------------------------15

设计心得体会------------------------------------------------17

参考书目------------------------------------------------------17

附录：程序源代码------------------------------------------18

序 言

“人工智能”也就是所谓的AI（artifical intelligence），它是一门抽象的技术，人工智能程序的编写不需要遵循任何即定的思考模式或者规则，而游戏中的AI完全按照程序员自己

的思考逻辑而发展。这就是说，程序员越是聪明越是能够写出更为精明的计算机人工智能程序，这和程序员自身的条件有着很大的关系。如果对于一个很陌生不熟悉的游戏领域，程序员从来没有接触过，这样即使有很高的编程水平，也没有办法实现我们想要达到的目标，根本不可能在游戏中将所有的情况包罗其中。

人工智能具有特定的三种思考模式，分别为移动模式，行为模式和策略模式。顾名思义，给定一个物体移动路径的公式，物体按照这样的公式来移动的就是移动模式。这种情况很多见，例如：某个物体追着玩家跑，目标射击等等。它又可以分为固定模式移动，追逐移动，躲避移动。策略型人工智能是AI中比较复杂的一种，最常见的运用策略型AI游戏是棋盘类的游戏，通常计算机必须判断目前情况下所有可走的棋步和可能获胜的情况，并计算目前计算机可走棋步的制胜分数或者是玩家可走棋步的制胜分数，最后决定出最佳的走法。行为型AI在游戏中是经常会运用到的，它的主要意义是物体会随着情况的改变来做出一些行为动作，而这些物体可以是游戏中的主角、怪物或者是四周环境中的物品。

而此次迷宫游戏的设计也是属于人工智能中的行为模式。

算法详解

路径搜寻的概念

路径搜寻与行为型人工智能有直接的关系。在迷宫游戏中，涉及路径搜寻时必须设定物体的一些走出迷宫的法则。如前面有路时就往前走，前面的路走过就往没走过的地方走等。这些法则必须确实可以让物体搜索迷宫中的每一块区域来找到出口，若走迷宫的法则设定得不完整，那么物体就有可能在同一个地方兜圈子，永远找不到出口了。

此外，为了让物体在走出迷宫后能知道正确走出迷宫的路径，必须给物体一张地图来记录所走过的路径，这张图就是一个链表结构，当物体成功走出迷宫后，整个链表就是正确走出迷宫的路径。如图1所示

图 1

图1中，实线部分为小球走迷宫的最短路径，依照走迷宫的规则每移动到新一格时，该区域就被增加到链表中，而当走过的区域并非正确路径时（图中虚线部分），则从链表中删除。例如：上图中虚线部分为小球所走过的区域，但小球进入该区域后发现是死路，因此必须倒退，每倒退一格时，就表示该格不是正确路径，因此从链表中删除；最后，当小球走出迷宫后，正确路径便会记录在链表中。

搜寻最佳路径

在这个迷宫路径搜寻的程序中，我以一颗小球来走迷宫，小球会自动搜寻到迷宫的入口，接着自动找寻出口，当找到出口后便记录着正确走出迷宫的路径，按[F2]键察看此最短路径。

定义迷宫的方式

使用一个整数的二维数组maze[8][8]来存储整个迷宫的状态。如图2

出口

图 2

定义数组时，设定出口元素值为3，入口的元素值为2，墙元素值为1，通道的元素值为0。图2中，代表入口的数组元素为maze[0][1]，同时，以变量m,n分别代表数组一维与二维的索引值，具体如下所示：

maze[m][n]=3 // 出口 maze[m][n]=2 // 入口 maze[m][n]=1 // 墙 maze[m][n]=0 // 通道

双向链表的使用

在程序中我使用双向链表记录小球所走过的路径，结构定义如下： struct list //定义链表结构 {

int m; int n;

struct list*next; //指向下一结点 struct list*back; //指向前一个结点 };

typedef struct list node; //定义结点

typedef mode*pointer; //定义动态指针

当小球走迷宫时，主要王没有走过的格子走，程序使用一个二维的布尔数组pass[8][8]来记录格子是否走过，小球走向未走过的格子时，这一格会被加到链表里，而当小球走到其上、下、左、右有墙或者都已经走过的格子时，此时必须倒退，而每倒退一格就表示那一格是错误的格，因此将其从链表中删除，直到最后走出迷宫时，链表中每一结点便是正确的行进路线。如图3：

图3

图中，虚线部分是小球所走过的错误路径，在走进错误区域后，都是死路。因此小球必须沿原先进入的路径后退。在后退后，原先加到链表中的错误结点也会同时从链表中删除，而后退到有其他未走过的格子可以走时，就往那一个格子前进，最后找到出口后，正确的行进路线的结点便记录在链表中。

走迷宫的规则

先试着往下走，若下一格有墙或者走过，则试着往右走 若右一格有墙或者走过，则试着往左走 若左一格有墙或者走过，则试着往上走

若上一个有墙或者走过，此时表示上、下、左、右都有未走过的格，便必须往后退，回到上一结点位置并删除目前结点

以下列出依各条规则所设定出的算法：

1) 试图往下走的程序代码：

if(下一格是墙)

/*试图往右走的程序代码*/ else

if（下一格走过）

/*试图往右走的程序代码*/ else

//往下走并新增结点

2) 试图往右走的程序代码：

if(右一格是墙)

/*试图往左走的程序代码*/ else

if（右一格走过）

/*试图往左走的程序代码*/ else

//往右走并新增结点

3) 试图往左走的程序代码：

if(左一格是墙)

/*试图往上走的程序代码*/ else

if（左一格走过）

/*试图往上走的程序代码*/ else

//往左走并新增结点

4) 试图往上走的程序代码：

if(上一格是墙)

//回上一个结点并删除目前结点 else

if（上一格走过）

//回上一个结点并删除目前结点 else

//往上走并新增结点

将上面4组算法结合起来，就得到整个走迷宫的判断式结构了

程序内容说明：

本迷宫游戏的主要功能如下：

程序执行式自动搜寻入口与出口 按[F1]键可重新进行搜寻

按[F2]键辉县是正确走迷宫的路径

若迷宫无出口，则搜寻结果会显示无出口的信息

程序代码内容与说明

一 程序各个全局变量的声明

int maze[8][8] =

{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 pass[8][8]; int i,j,m,n,lastm,lastn;

BOOL start= true,search= true,go; pointer ptr,preptr,first; char str[10];

说明： 1) 第1、2行程序代码定义大小为8×8迷宫数组的内容，其中值为2与3的元素就是迷宫

的入口与出口

2) 第3行程序代码定义一个pass数组，用来记录迷宫中各个格子是否走过，举例来说，

若maze[4][5]走过，则pass[4][5]会被设定为true 3) 第4行程序代码定义的格个整数变量用途说明如下

变量名称 说明

i 计数变量 j 计数变量

m 小球所在位置的第一个索引值 n 小球所在位置的第二个索引值 lastm 上一次小球所在位置的第一个索引值 lastn 上一次小球所在位置的第二个索引值

4) 第5行程序代码所定义的3个布尔变量start、search、go分别用以表示程序开始，重新

搜寻以及显示最短路径

5) 第6行程序代码定义了ptr、preptr与first动态指针，分别代表目前结点、上一个结点

与第一个节点。

二 主体程序的实现

canvasFrame::canvasFrame() { /*建立窗口与加载图文件的程序代码*/

for(i=0;i<7;i++) { for(j=0;j<7;j++) if(maze[i][j]==2) break; if(maze[i][j]==2) break; } m = i; n = j; ptr = (pointer)malloc(sizeof(node)); ptr->m = 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的值赋予给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(); //开始搜寻 else { if(search) Search(); //进行搜寻 if(go) Go(); //显示最短路径 }

CFrameWnd::OnTimer(nIDEvent); }

说明：

在OnTimer函数中则是会依目前程序的状况来执行开始搜寻，显示最短路径等于自定义函数。

程序于一开始进行搜寻时便会执行Start函数，将小球的图案显示于入口上。

接下来每次进行搜寻而小球移动时，会执行Search函数，而当用户按下[F2]键时，则会调用Go函数来显示走出迷宫最短路径

void canvasFrame::Start() { CClientDC dc(this); mdc->SelectObject(tile); for(i=0;i<=7;i++) for(j=0;j<=7;j++) if(maze[i][j] == 1) dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY); mdc->SelectObject(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行程序代码会先贴上迷宫中的墙。使用双层循环在条件式

maze[i][j] == 1成立时，则以左上角的贴图坐标(j*40,i*40,)来进行贴上墙的动作

2) 第10行程序代码则以ptr所指结点中m与n成员变量的值来计算贴图坐标，此时ptr

所指结点为第一个结点，因此贴图后，小球会出现在迷宫入口位置上

3) 接下来第11行程序代码将start变量设定为false，第12、13行程序代码则将结点m与

n的值记录在lastm与lastn中，以便下次执行OnTimer时可以覆盖掉前一次的贴图

void canvasFrame::Search() { CClientDC dc(this); mdc->SelectObject(tile); for(i=0;i<=7;i++) for(j=0;j<=7;j++) if(maze[i][j] == 1) dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY); mdc->SelectObject(ball); lastn = ptr->n; lastm = ptr->m;

if(maze[m+1][n]==1) //下一格是墙 /*判断行进方向与变更链表内容的程序代码*/ else if(pass[m+1][n]) //下一格走过 if(maze[m][n+1] == 1) //右一格是墙 if(maze[m][n-1] ==1) //左一格是墙 if(maze[m-1][n] == 1) //上一格是墙 { if(ptr->back != NULL) { ptr = ptr->back; free(ptr->next); ptr->next = NULL; } m = ptr->m; n = ptr->n; } else if(pass[m-1][n]) //上一格走过 { if(ptr->back != NULL) { ptr = ptr->back; free(ptr->next); ptr->next = NULL; } m = ptr->m; n = ptr->n; } else { m-=1; //往上一格 ptr->next = (pointer)malloc(sizeof(node)); ptr->next->m = m; ptr->next->n = n; preptr = ptr; ptr->next->next = NULL; pass[m][n] = true; ptr = ptr->next; ptr->back = preptr; } else /*判断行进方向与变更链表内容的程序代码*/ else

{ m+=1; //往下一格 ptr->next = (pointer)malloc(sizeof(node)); ptr->next->m = m; ptr->next->n = n; preptr = ptr; ptr->next->next = NULL; pass[m][n] = true; ptr = ptr->next; ptr->back = preptr; } dc.BitBlt(lastn*40,lastm*40,40,40,mdc,0,0,WHITENESS); dc.BitBlt(ptr->n*40,ptr->m*40,40,40,mdc,0,0,SRCCOPY); if(ptr->back == NULL) { dc.TextOut(120,320,"找不到出口"); search = false; } if(maze[m][n] == 3) { dc.TextOut(120,320,"找到出口"); search = false; } }

说明：

在search（）函数中主要是进行迷宫出口的搜寻与小球的移动，而当搜寻完毕后，便显示是否找到出口的信息

1) 第4---8行程序代码会先贴上迷宫中墙的部分

2) 第12—14行程序代码则是路径搜寻的判断式，由于整个判断式内容相当冗长，在此仅

列出部分来作说明

3) 第12行程序代码判断目前为止的下一个是否有墙，即maze[m+1][n]是否等于1，如果

有墙接下来的程序代码便试图往其他的方向走

4) 若目前位置的下方没有墙，此时第14行程序代码会以pass[m+1][n]是否为true来判断

下一格走过或者没有走过。如果条件式成立，表示下一格走过，接下来的程序代码同样会试图往其他的方向走。倘若条件式不成立，表示下一格未走过，便执行第54---63行的程序代码，在链表中新增一个结点

5) 如果目前位置的下一格走过且第15---17行程序代码都成立，就表示已走到了死路，小

球必须往后退，也就是必须从链表中删除错误路径的结点。

6) 第19---26行程序代码进行删除结点的动作，第19行程序代码判断ptr back是否为

NULL，若为NULL，则表示目前结点为链表的第一个结点，并不删除该结点；若目前结点不是第一个结点，便依底下图标过程来删除结点。 执行第21行程序代码：

NULL

ptr

ptr 执行第22行程序代码：

释放其后面所指

结点的存储单元

执行第23行程序代码：

第24、25行程序代码则依目前ptr所指的结点来重设m与n的值

7) 当有未走过的格子可走时，此时就必须在链表的最后加上代表新格子的结点，如第

40---51行与第53---64行的程序代码

8) 以第40---51行往上一动一格的程序代码为例，我们来说明加入新结点的方式，第42

行程序代码将m值减1代表上一个格子，而新增结点的过程则如底下的图标所示。 执行第43

行程序代码：

执行第44、45行程序代码：

执行第46行程序代码：

ptr preptr 执行第47行程序代码：

NULL

ptr preptr 执行第49行程序代码：

NULL

执行第50行程序代码：

NULL

完成以上步骤之后，在链表中便新增一个结点，m与n的值则是代表新的一格在数组中的索引值，而第48行程序代码是设定mass[m][n]为true，表示此格已走过

9) 第65行程序代码以上一次的m与n的值lastm和lastn来覆盖上一次的小球贴图，第

66行程序代码则以目前结点的m与n值来贴上小球到所移动的格子上。

10) 第67行程序代码判断小球是否会到第一个结点，便表示这个迷宫没有出口，而第一个

结点的back指针指向NULL，因此69行程序代码显示找不到出口的信息，并将Search设为false。

11) 在每次计算m与n值之后，若maze[m][n]元素值为3，则表示小球移动到了定义为出口

的地方，第72行判断式成立，接下来便显示找到出口的信息，同时将Search设定为false。

void canvasFrame::Go() { CClientDC dc(this); m = ptr->m; n = ptr->n; mdc->SelectObject(tile); for(i=0;i<=7;i++) for(j=0;j<=7;j++) if(maze[i][j] == 1) dc.BitBlt(j*40,i*40,40,40,mdc,0,0,SRCCOPY); mdc->SelectObject(ball); dc.BitBlt(n*40,m*40,40,40,mdc,0,0,SRCCOPY); if(maze[m][n] == 3) { dc.TextOut(120,320,"最短路径"); go = false; } else ptr = ptr->next;

}

说明：

当用户按下[F2]键后便会将go变量设定为true，并将链表的指针移回第一个结点。OnTimer函数中就会不断地调用Go函数来进行小球贴图显示正确走出迷宫的路径： 1) 第4、5行程序代码取出目前结点m与n的值 2) 第7---10行程序代码贴上迷宫中的墙

3) 第12行程序代码依m与n的值贴上小球图

4) 第13行判断式判断maze[m][n]是否等于3，若等于3则表示已走到了出口，显示最短

路径的信息，并将go设定为false；否则第19行程序代码将指针移到链表的下一个结点，已进行下一次小球的移动

void canvasFrame::OnKeyDown(UINT nChar, UINT nRepCnt, UINT nFlags) { CClientDC dc(this); if(nChar == VK_ESCAPE) PostMessage(WM_CLOSE); if(nChar == VK_F1) { start = true; search = true; go = false; for(i=0;i<=8;i++) //清空数组 for(j=0;j<=8;j++) pass[i][j] = false; dc.BitBlt(ptr->n*40,ptr->m*40,40,40,mdc,0,0,WHITENESS); while(ptr->back) //删除结点 { ptr = ptr->back; free(ptr->next); ptr->next = NULL; } m = ptr->m; n = ptr->n; } if(nChar == VK_F2) { if(ptr->back == NULL) dc.TextOut(120,320,"此迷宫无出口"); else { ptr = first; //移动指针到第一个结点 go = true; search = false;

} } CFrameWnd::OnKeyDown(nChar, nRepCnt, nFlags); }

OnKeyDown函数用于处理按下按键信息，用户可按下[ESC]键来结束程序，按[F1]键重新进行搜寻，按[F2]键显示走出迷宫的路径。 说明：

1) 第7行程序代码判断若用户按下[F1]键，则将start、search变量设定为true，go变量设

定为false，如此OnTimer函数会调用Start与Search函数重新进行路径搜寻 2) 第12---14行程序代码将记录走过格子的二维数组中的各元素重新设定为false 3) 第15行程序代码覆盖最后一次的小球贴图

4) 第16---21行得while循环进行链表结点的删除，仅留下第一个开始的结点

5) 第22、23行程序代码设定变量m与n的值为第一个结点的成员变量m与n的值，即

为小球已开始所在的格子

6) 若用户按下了[F2]键，此时程序必须将链表指针的位置移到第一个结点，然后再一一取

出各个结点中的m与n的值，来贴上小球图以显示路径

7) 第27行判断式中的条件式ptr back==NULL若成立则所在结点为第一个结点（入口结

点），即表示迷宫没有出口 8) 若ptr back==NULL不成立，则31行程序代码将链表的指针移动到第一个结点的位置

上，然后将go设定为ture，search设定为false，以执行显示最佳路经得Go函数

执行结果演示

进行迷宫搜寻 找到出口

最短路径

当迷宫设定为无出口时，则搜寻后结果如下图所示：

找不到出口

可以通过改变数组中的数据来改变迷宫路径，程序也可自动找到入口并搜寻走出迷宫的路径

设计心得体会

5年前，当得知象棋大师卡斯帕罗夫同IBM“深蓝二代”计算机的对弈以失败告终后，人工智能，在我的脑海里便成为了一个神秘并且深不可及的名词。在我看来，它可以让很多本来没有思想的东西变得富有生命力，赋予他们思考的能力。比如会踢足球的机器人，会与人对弈的计算机，可以自动控制的家电等等。

这个学期，通过人工智能与专家系统这门课程的学习，使我对人工智能这个前沿领域有了初步的了解。当得知要进行课程设计的时候，我的心里是欣喜并且有些担忧的。虽然迷宫游戏只是属于人工智能的一个小小的分支，但是，要完成这样的课程设计对我来说还是有相当大的难度的。为此，我查阅了很多计算机游戏编程的书籍，并且到网上搜集了很多的资料，为这次编程进行了很充足的准备。然而，理论转变为实际的过程中，还是存在着许多大大小小的问题的。

首先，在分析问题的时候，应该要尽可能的全面。迷宫游戏中，涉及路径搜寻时必须设定物体的一些走出迷宫的法则。如前面有路时就往前走，前面的路走过就往没走过的地方走等。这些法则必须确实可以让物体搜索迷宫中的每一块区域来找到出口，若走迷宫的法则设定得不完整，那么物体就有可能在同一个地方兜圈子，永远找不到出口了。

写程序对我来说确实是件有点头疼的事情。起初设想的算法写着写着发现原来是行不通的。这时，就需要及时的更正，一条路走不同，就要从另外的角度去思考问题了。在程序调试的过程中一份平和的心态以及冷静的头脑尤为重要，不能急躁，往往漏洞就出现在最不起眼的地方。只有冷静下来，心思缜密的从头把程序梳理下来，细心思考每一个步骤，每一个过程，通过逐步调试，才能一点点地将错误纠正过来。

在通过自己的一番辛苦努力以及同学的指导之下，当最终调试出了另人满意的结果的时候，心里那种成功的喜悦感是无法言表的。

人工智能是一个很深奥的领域。通过这次的课程设计，初步激发了我对这个领域的兴趣。相信在以后的学习以及工作过程当中，我一定会尝试着去接触更多更深层次的方面，希望有朝一日，我也可以为人工智能这个领域做出一些贡献。

参考书目

c++动画编程 水力水电出版社

c++游戏动感编程 电子工业出版社

人工智能基础编程 西北电子科技大学出版社

附录：程序源代码

// canvasFrame.cpp : implementation file

#include "stdafx.h" #include "canvasr.h"

#include "canvasFrame.h"

#ifdef _DEBUG

#define new DEBUG_NEW #undef THIS_FILE

static char THIS_FILE[] = __FILE__; #endif

struct list //定义链表结构 { int m; int n; struct list *next; //指向下一个结点 struct list *back; //指向前一个结点 };

typedef struct list node; //定义结点

typedef node *pointer; //定义动态指针

///////////////////////////////////////////////////////////////////////////// // canvasFrame

IMPLEMENT_DYNCREATE(canvasFrame, CFrameWnd) int maze[8][8] = {1,1,/*2*/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,/*3*/1,1,/*1*/3,1,1,1,1,1,1}; BOOL pass[8][8]; int i,j,m,n,lastm,lastn;

BOOL start= true,search= true,go; pointer ptr,preptr,first; char str[10];

canvasFrame::canvasFrame() { RECT rect;

Create(NULL,"绘图窗口",WS_OVERLAPPEDWINDOW,CRect(0,0,330,380)); CClientDC dc(this); int width = dc.GetDeviceCaps(HORZRES); int height = dc.GetDeviceCaps(VERTRES); GetWindowRect( &rect ); width = ( width - ( rect.right - rect.left ))/2 ; height = (height - (rect.bottom - rect.top ))/2 ; MoveWindow( width , height , (rect.right - rect.left ) , (rect.bottom - rect.top ) ,true); mdc = new CDC; mdc->CreateCompatibleDC(&dc); tile = new CBitmap; ball = new CBitmap; tile->m_hObject = (HBITMAP)::LoadImage(NULL,"tile.bmp",IMAGE_BITMAP,40,40,LR_LOADFROMFILE); ball->m_hObject = (HBITMAP)::LoadImage(NULL,"ball.bmp",IMAGE_BITMAP,40,40,LR_LOADFROMFILE); for(i=0;i<7;i++) { for(j=0;j<7;j++) if(maze[i][j]==2) break; if(maze[i][j]==2) break; } m = i; n = j; ptr = (pointer)malloc(sizeof(node)); ptr->m = m; ptr->n = n; ptr->next = NULL; ptr->back = NULL; first = ptr; }

canvasFrame::~canvasFrame() { delete tile; delete ball; delete mdc; ptr = first; while(ptr->next) { ptr = ptr->next; free(ptr->back);

本文来源：https://www.bwwdw.com/article/6q5i.html