大二C++数据结构课设报告

课程设计题目： 迷宫游戏

1、问题描述

程序开始运行时显示一个迷宫地图，迷宫中央有一只老鼠，迷宫的右下方有一个粮仓。游戏的任务是使用键盘上的方向健操纵老鼠在规定的时间内走到粮仓处。

基本要求：

（1） 老鼠形象可以辨认，可用键盘操纵老鼠上下左右移动；
（2） 迷宫的墙足够结实，老鼠不能穿墙而过；
（3） 正确检测结果，若老鼠在规定时间内走到粮仓处，提示成功，并给出一条路径，否则提示失败。

提高要求：

（1） 添加编辑迷宫功能，可修改当前迷宫，修改内容：墙变路、路变墙；
（2） 增加闯关和计分功能；
（3） 找出走出迷宫的所有路径，以及最短路径。

测试数据：要求用10*10及以上的方阵或长方阵。

2．需求分析

软件基本功能：

（1） 开始游戏时自动生成一个随机地图并确保有一条通路。
（2） 按键开始游戏功能，可以使用上下左右按键控制老鼠移动。
（3） 当游戏通过时提示按键确认进入下一关。
（4） 关卡具有不同的难度。
（5） 当倒计时结束时没有通过，提示游戏失败按键从新选择功能。
（6） 按键寻找路径。
（7） 按键更换地图。
（8） 按键进行地图编辑，实现路变墙，墙变路。

测试数据要求：用户只需使用方向键控制老鼠即可。

3. 概要设计

（1）抽象数据类型：

struct POSITION                //位置,栈
{
        int x, y;
};

struct QUEUE                //行列,队列
{
    int x, y;
    int PreSub;                //存储队头下标
};
POSITION Stack[1500] = { { 0,0 } };            //栈
QUEUE Queue[1500] = { { 0,0,0 } };            //队列
int head = -1, tail = -1, top = -1;            //初始化

（2）主程序流程：

图1.主程序流程图

（3）模块调用关系:

本程序中函数包括:main函数,栈队列相关结构体,生成地图make_map函数,输出地图PrintfMap函数,输出右侧栏PrintMenu函数,清空路径ClearMap函数,游戏game函数,改变光标位置 Setposition函数, 深度搜索演示DepthFirstSearch函数, 广度搜索演示BreadthFirstSearch函数,编辑地图ChangeMap函数, 光标是否可见ChangeCursor函数.

图2.函数调用关系

4．详细设计

(1) 主程序具体代码

int main()
{
    system("mode con cols=110 lines=41  ");    //cols改变宽度,lines改变高度
    ChangeCursor(0);
    make_map();
    PrintMap();
    PrintMenu();
    while (1)
    {
        switch (getch())
        {
        case '0':
            flage1 = true;
            ClearMap();
            PrintMap();
            game();
            if (pass > 10)
            {
                system("cls");
                SetConsoleTextAttribute(h, 14);
                SetPosition(Max_x / 2, Max_y / 2);
                cout << "恭喜通关,游戏结束";
                system("pause");
                return 0;
            }
            fflush(stdin);                //清空数据缓存区
            break;
        case '1':
            ClearMap();
            PrintMap();
            DepthFirstSearch();
            fflush(stdin);
            break;
        case '2':
            ClearMap();
            PrintMap();
            BreadthFirstSearch();
            fflush(stdin);
            break;
        case '3':
            ClearMap();
            PrintMap();
            break;
        case '4':
            make_map();
            PrintMap();
            break;
        case '5':
            ChangeMap();
            break;
        }
    }
    return 0;
}

主函数主要调用各个功能函数。其步骤为：打开程序，调用make_map函数、PrintMap函数、PrintMenu函数来生成地图和显示右侧栏。地图生成后，选择0，调用ClearMap函数、PrintMap函数、game函数来清空地图上多余的路径开始游戏，选择1，调用ClearMap函数、PrintMap函数、DepthFirstSearch函数进行深度优先搜索，最终显示出一条路径，选择2，调用ClearMap函数、PrintMap函数、BreadthFirstSearch函数进行广度优先搜索，最终显示出一条最短路径，选择3，调用ClearMap函数、PrintMap函数进行清空地图中的路径，选择4，调用make_map函数、PrintMap函数重新生成出一张地图，选择5，调用ChangeMap函数进行地图编辑。

（2）其他模块的算法描述

void ChangeCursor(int a)  // 设置光标是否可见  a=0不可见，a=1可见

功能：使用更改控制台函数，利用句柄改变光标显示。

void make_map()                //制作地图

功能：通过循环和使用随机数生成随机的地图并保证其生成的随机地图存在通路。主要算法为，地图内部大小必须为偶数，第一次为用墙圈起左上角的一块路后，路存在两个厚度为1的墙，存在一个算法计算周围存在几块厚度为1的墙并保存在sss二维数组中，两块则用随机数模除2，随机数只有0或1，随机的进行选择一块墙变为路，后面生成一样。因为地图内部长宽为偶数，所以它在墙壁四周生成路时路是紧贴在内壁上的，这就可以有效的保证生成的随机地图存在一条通路。最后开始随机生成更多的路，并进行难度设定，根据关卡的提升，此处随机生成的路的数量比例进行减小。最终地图保存map的二维数组中。

void PrintMap ()//输出迷宫

功能：利用for循环输出存储在map二维数组中的地图。

void ClearMap()//清除所有搜索时留下的标记，只留下墙和路

功能：清空地图中显示的标记。

void PrintMenu()//右侧菜单栏

功能：通过使用光标定位函数和改变控制台函数输出右侧菜单栏。

void DepthFirstSearch(int x = 2, int y = 2, int dir = 0)    //深度优先搜索

功能：使用栈存储路径，进行深度优先搜索，先检测右侧是否有路，有路入栈，无路判断下方是否有路，有路入栈，无路判断左侧是否有路，有路入栈，无路判断上方是否有路，有路入栈，无路进行标记为死路并退栈，返回到上一格进行判断。直到到达终点。

void BreadthFirstSearch()                    //广度优先搜索,时间最短

功能：使用队列存储路径，进行广度优先搜索。先检测右侧是否有路，有路队尾入队且记录一次队头下标并对此处地图进行标记，无路则不进行记录，再判断下方是否有路，有路队尾入队且记录一次队头下标并对此处地图进行标记，无路则不进行记录，再判断左侧是否有路，有路队尾入队且记录一次队头下标并对此处地图进行标记，无路则不进行记录，再判断上方是否有路，有路队尾入队且记录一次队头下标并对此处地图进行标记，无路则不进行记录，第一次结束后，队头后移一次读取当前队头下标存储的位置并从当前位置开始下一次入队操作。当到达终点时，读取当前位置和记录的队头下标，改变控制台当前位置并读取上一轮对应的队头下标及记录的上一次队头下标，输出，反复循环输出。

void game()        //游戏

功能：进行游戏，通过while循环内部使用clock/1000计算时间并利用GetAsyncKeyState（）读取按键是否按下函数来进行老鼠的控制，避免了对计数器显示的干扰，并进行判断所走方向是否是墙，避免了老鼠穿墙问题。通过判断关卡计数器执行相应的操作，chenggong 通过且还未通关执行make_map函数和PrintMap函数。

void ChangeMap()    //编辑地图

功能：通过while循环内部使用switch和getch函数结合执行相应的按键功能，通过查找可知，方向上为0x48、方向下为0x50、方向左为0x4d、方向右为0x4b。

5、编码与调试分析

（1）编码与调试过程中遇到的问题及解决办法：

【问题一】移动时光标闪烁问题

解决方法：上网搜资料，得知隐藏光标函数以及移动光标函数可以避免这一问题。

解决此问题的核心代码：

void ChangeCursor(int a)  // 设置光标是否可见  a=0不可见，a=1可见
{
    CONSOLE_CURSOR_INFO cursor_info = { 1, a };    //前面是光标粗度,后面是光标是否可见
    SetConsoleCursorInfo(h, &cursor_info);        //更改光标
}

【问题二】游戏时，老鼠移动无法正常显示倒计时问题

解决方法：上网搜资料，得知可以通过使用GetAsyncKeyState函数可以对指定按键进行判断是否按下，不会因为无按键按下程序等待按键按下影响倒计时显示问题。

解决此问题的核心代码：

GetAsyncKeyState(VK_DOWN)
GetAsyncKeyState(VK_UP)
GetAsyncKeyState(VK_LEFT)
GetAsyncKeyState(VK_RIGHT)

（2）待解决问题：

找出走出迷宫的所有路径。

6、使用说明

进入游戏界面后：

a) 开始游戏按1

b) 放弃按ESC

c) 通过按Y进入下一关

d) 深度搜索延时按1

e) 广度搜索延时按2

f) 清空路径按3

g) 重新生成地图按4

h) 编辑地图按5

7、测试结果

1) 进入程序

2) 开始游戏

3) 超过规定时间或按ESC放弃

4) 成功过关

5) 编辑地图

6) 通关游戏

7) 深度优先搜索

8) 广度优先搜索

8、自学知识

（1） 清屏函数：system("cls");

暂停函数：system("pause");

（2） 更改光标位置：

void SetPosition(int line, int col)            //更改光标的位置
{
    static COORD coord;
    coord.X = col * 2;
    coord.Y = line;
    SetConsoleCursorPosition(h, coord);
}

（3）控制台改变颜色函数：

SetConsoleTextAttribute（句柄，颜色值）

（4）对所检测按键是否按下函数

GetAsyncKeyState（）

（5）时钟函数的使用

clock（）

（6）隐藏光标函数

void ChangeCursor(int a)  // 设置光标是否可见  a=0不可见，a=1可见
{
    CONSOLE_CURSOR_INFO cursor_info = { 1, a };    //前面是光标粗度,后面是光标是否可见
    SetConsoleCursorInfo(h, &cursor_info);        //更改光标
}

（7）改变控制台窗口大小

system("mode con cols=110 lines=41 ");    //cols改变宽度,lines改变高度

9、课程设计心得体会

通过这次课程设计，增加了我对于软件游戏开发方面的认识。在一款游戏的代码编写时，应该全方面的思考问题，同时还要考虑到用户对于游戏使用的体验。同时在此次学习中，我还通过自学和同学老师帮助，学习了许多新的知识。当然，虽然最后的作品还有许多能够改进的地方，在以后的学习中，希望能改进，越做越好。

移动光标函数和隐藏光标函数以及清屏函数、控制台颜色改变函数、改变控制台大小函数是在百度百科上获取的知识，也属于自学的新知识。

参考书：
[1]《c++面向对象程序设计》 清华大学出版社 谭浩强著

[2]《数据结构（C++版）》清华大学出版社 王红梅、胡明、王涛著