推箱子游戏实习报告书
- 格式：doc
- 大小：403.21 KB
- 文档页数：10
数据结构与C语言综合训练实习报告
信息工程学院
数据结构与C语言综合训练报告
（2012～2013学年第 二学期）
报告题目：____推箱子的最短路径_ __
姓 名：_ __ 程 榜____
专 业： 软件工程
年级班级：___2012级2班___
指导教师： 刘全中
完成日期： 2013年7月21号
数据结构与C语言综合训练实习报告
1 一、综合训练目的和要求
本综合训练是计算机科学与技术、信息管理与信息系统、软件工程、电子商务专业重要的实践性环节之一，是在学生学习完《程序设计语言(C)》、《数据结构》课程后进行的一次全面的综合练习。本课综合训练的目的和任务：
1. 巩固和加深学生对C语言、数据结构课程的基本知识的理解和掌握
2. 掌握C语言编程和程序调试的基本技能
3. 利用C语言进行基本的软件设计
4. 掌握书写程序设计说明文档的能力
5. 提高运用C语言、数据结构解决实际问题的能力
二、综合训练任务内容
1.题目要求：
推箱子是一个很经典的游戏.今天我们来玩一个简单版本.在一个5×5的房间里有一个箱子和一个搬运工,搬运工的工作就是把箱子推到指定的位置,注意,搬运工只能推箱子而不能拉箱子,因此如果箱子被推到一个角上那么箱子就不能再被移动了,如果箱子被推到一面墙上,那么箱子只能沿着墙移动.同时，房间里头还有若干障碍物（用阴影部分表示）。
现在给定房间的结构,箱子的位置,搬运工的位置和箱子要被推去的位置,请你计算出搬运工至少要推动箱子多少格.
2.扩展实现的内容：
绘制图形界面，通过按钮实现推箱子的整个过程，整个过程中可以动态的看到箱子的移动。
游戏界面如下图： 数据结构与C语言综合训练实习报告
2
游戏动态移动的过程图如下：
数据结构与C语言综合训练实习报告
3 三、总体设计
所用算法主要是根据广度优先搜索，纪录路径，然后利用回溯法实现最短路径的查找并纪录保存下来。所用的数据结构主要为顺序结构。
返回开始界面 进行游戏开
始 开始进入游戏界面
进行选择
选择游戏开始，进行游戏
选择游戏说明，了解游戏规则
选择关卡，或者返回游戏开始 关卡（1）
关卡（2）
关卡（3） 按空格键进行游戏
返回游戏开始后，可以单机鼠标右键退出游戏 数据结构与C语言综合训练实习报告
4
四、详细设计说明
1、推箱子游戏具有的功能
（1）能够显示主菜单和界面
游戏需要提供主菜单进行选择，同时能够把地图文件中的信息转换成为图像 显示到游戏界面上。
（2）能够实现键盘操作功能
能够接收到空格键信息，按照软件内部实现的箱子移动到相应的位置。
（3）能够进行关卡选择功能
进入开始游戏的界面时，可以进行游戏的关卡的选择，然后利用空格键进行箱子的移动。
（4）提供游戏说明功能
进入游戏说明界面时，可以了解游戏的一些规则，及如何进行游戏。
2、程序结构设计
运用C++语言，以及VS2010开发环境
（1）、typedef struct Pnode{
int row;
int col;
int weight;
struct Pnode* back_man;
}Pnode, * Position;
某一点的坐标表示，当用来实现箱子的最短路径的搜索时，back_man 用来存储箱子移动一个位置后，人所在的位置。
（2）、typedef struct Mnode{
int mrow;
int mcol;
char maze[MAX_ROW][MAX_COL];
}MNode, *MazeType;
用来存储地图的信息 数据结构与C语言综合训练实习报告
5
（3）、算法的实现
主要有两个类，第一个类是class ShortestPath ；
第二个类是class ManBoxStep: public ShortestPath ；
A、第一个类class ShortestPath 是用来实现地图中任意两点之间的最短路径，成员函数及其功能如下：
Position NextPosition(Position &curpos, int di);
用来计算当前点在四个方向下的移动一格得到的下一点的坐标位置，并返回；
bool CanArrive( vector< list > &vec);
数据成员有start，end，此函数是判断在地图中能否从 start 到 end ，并利用广度优先搜索搜索从start 到end 的路径，并把所有搜索过的位置全部记录在顺序容器 vec 中，vec[i] 表示存储一系列与start 位置相距i 个格子的被搜索的点的位置；
void RecordWay( vector< list > &vec, vector &way);
此函数根据 vec 中所存储的数据，利用回溯法进行往回搜索，找到从 start 到
end 的最短路径， 并把路径存到容器 way 中；
B、第二个类class ManBoxStep 是利用第一个类中的函数实现人和箱子一起从起点到箱子应到的位置的最短路径，其中的成员函数及其功能如下：
Position NextState(Position box, int di);
此函数的功能是纪录当人能够移动箱子的情况下，纪录移动后箱子和人的位置；
MazeType UpdateMaze(MazeType mymaze, Position curpos, Position newpos);
此函数的功能是每当在搜索下一步时，及时的更新所在的地图（即改变人和箱子的位置），并每次都将地图纪录下来；
bool BFSCanArrive( vector< list > &AllWay,
vector< vector > &man_way,
vector &maze_state);
此函数的功能是，可以说是有条件的进行广度优先搜索，即每次搜索四个方向中的一个方向时，都要利用第一个类中的 CanArrive 函数判断是否能从人的当前位置移动到推箱子的位置，并记录最短的路径，并保证箱子前面不是墙，AllWay 是用于存储有条件的广度优先搜索中所搜索到的位置，AllWay [i] 是用来存储从开始走i
个格子的所有被搜索到的位置，man_way 是用来存储人走过的所有的路径，man_way[i]
存储走过的某条路径所经过的点的位置；maze_state 用来存储搜索过程中所更新的数据结构与C语言综合训练实习报告
6 所有的地图的状态；
void RecordBestWay( vector< list > &AllWay,
vector &bestWay,
vector< vector >&man_way,
vector &man_bestway);
此函数是根据 AllWay 的数据往回进行回溯法找到箱子可以移动的最短的路径，同理，man_bestway 是根据 man_way 来找到人整个过程中所走过的最短的路径；
（4）、界面及图形的绘制
此软件的界面设计主要是利用 Easyx 中的函数进行绘画的，游戏的主界面以及一些按钮时利用绘图函数实现的，并且根据所画按钮的坐标范围，来控制鼠标，从而来实现界面中按钮的控制，游戏过程中的箱子、墙、人均是利用函数所插入的图片，移动的时候，在不同的位置插入不同的图片来显示动态的过程；
插入图片的函数
loadimage(&img[0], _T("F:\\VS\\test\\pushbox\\s.jpg"));
loadimage(&img[1], _T("F:\\VS\\test\\pushbox\\w.jpg"));
loadimage(&img[2], _T("F:\\VS\\test\\pushbox\\m.jpg"));
loadimage(&img[3], _T("F:\\VS\\test\\pushbox\\b.jpg"));
loadimage(&img[4], _T("F:\\VS\\test\\pushbox\\d.jpg"));
loadimage(&img[5], _T("F:\\VS\\test\\pushbox\\bd.jpg"));
绘制按钮：
ellipse(580,440,740,490);//画椭圆
RECT r2 = {580,440,740,490};
drawtext(_T("游戏说明"), &r2, DT_CENTER | DT_VCENTER |
DT_SINGLELINE);
鼠标的响应：
MOUSEMSG m;
while(true)
{
m = GetMouseMsg();
switch(m.uMsg)
{
case(WM_LBUTTONDOWN):
......
}
}
(5) 地图的获得
const char Wall = 'w';//表示墙
