1. 引言
九宫格是一款数字游戏，起源于河图洛书，与洛书是中国古代流传下来的两幅神秘图案，历来被认为是河洛文化的滥觞，中华文明的源头，被誉为“宇宙魔方”。九宫格游戏对人们的思维锻炼有着极大的作用，从古时起人们便意识到九宫的教育意义。千百年来影响巨大，在文学、影视中都曾出现过。九宫格最早叫“洛书”，现在也叫“幻方”。
2. 任务与需求分析
（1）背景需求：
本实验的核心任务是实现一个基于c语言的简单游戏系统。具体要求如下：
1. 编写符合需求的游戏程序。
2. 识别并读取图片。
3. 随机打乱图片。
4. 判断图片是否复原。
（2）问题分析：
生成图片：根据事先准备的图片输出打乱的图片。
游戏运行及判断：识别用户指令，移动小图片。
寻找最佳路径：找到复原图片的最快方案。
3.游戏规则设计
通过系统将原本图片分割打乱，用户通过鼠标点击与白块相邻的图块交换，将图片复原即为胜利。（鼠标右键快速复原）
4.数据结构设计
- 图像存储
用二维数组map[][]存储数字0-8，对分割后的图块进行标记。
- 寻找最短路径
(1).open表中存放的是按估价函数值排序且未被处理过的节点，close表存放的是每次从循环从open表中取出的第一个节点，即已拓展过的节点。
(2).一个图像状态称为一个节点，节点是按递进变化的，因此采用单链表存储节点当前状态以及它的父节点。
(3).open表是按F值升序存储节点，因此open表是个有序序列，采用二分查找寻找新的节点插入位置。
(4).用A*算法找最佳路径
- 求最佳路径解决思路(八数码问题)
- 启发式搜索
重排open表，选择最有希望的节点加以扩展。
- 估价函数
用来估算节点处于最佳求解路径上的希望程度的函数
F(n) = G(n) + H(n)
G为初始节点到该节点白块移动的次数
H采用的是计算节点中所有成员与目标节点中该成员的曼哈顿距离总和。
(3)A*算法
选择OPEN表上具有最小F值的节点作为下一个要扩展的节点，即总是选择最有希望的节点作为下一个要扩展的节点。白块8可以向与其相邻的图块交换做移动，相当于玩家对当前节点的几种选择，走的不同的路径，将当前节点移动一步后能达到的所有可能在图上画出，新节点与当前节点的相对位置和白块移动方向一致，把这个过程称作对当前节点做拓展。
5.游戏算法设计
1.图像分割并绘制:
(1).调用initgraph()函数创建一个600*600的窗口，调用loadimage()函数加载缩放图片，调用rand()函数初始化地图并调用putimage()函数绘制。
(2).用line()函数绘制切割线，为解决切割线闪烁问题，调用双缓冲绘图函数BeginBatchDraw()，FlushBatchDraw()，图像绘制完成;
2.左击与白块相邻的图块和白块交换位置:
(1).遍历map[i][j]数组获取白块位置坐标(j,i);
(2).定义鼠标信息结构体ExMessage m,调用peekmessage()函数获取鼠标点击信息，当获得鼠标左击信息且其坐标与白块坐标相邻时则交换位置;
3.右击快速恢复原图:
当获取到鼠标右击信息时，用冒泡排序对二维数组map[][]升序排序再次绘制地图，此时恢复原图;
4.寻找最佳路径*
初始化：将起始节点添加到开放列表中。
循环执行以下步骤：
(1).从开放列表中找出F评分最低的节点，将其设为当前节点。
(2).检查当前节点是否是目标节点。如果是，则算法结束，路径被找到。
(3).将当前节点移至关闭列表，并处理所有邻近节点：
(4).如果邻近节点不在开放列表中，计算其G、H和F值，然后将其添加到开放列表。
(5).如果邻近节点已在开放列表中，检查通过当前节点到达它的路径是否更好。如果更好，更新其F、G和H值。
5. 检查游戏结束
对二维数组map[][]进行遍历，若map[][]升序则游戏结束，弹出结束窗口。
7. 测试环境搭建
源代码要用到#include<graphics.h>头文件，需要用VisualStudio安装easyx图形库。
当在easyx图形库中遇到没有与参数列表匹配的重载函数错误时，问题可能出在VisualStudio的配置上。解决方案是将项目属性中的高级字符集从Unicode字符集改为多字节字符集，即可消除报错。
6.运行示例
1.系统实现
点击程序运行，生成图像。
2.用户通过鼠标点击白块与其相邻的图块交换图片。
图2
3.图片成功复原弹出弹窗判断胜利
图3
9 性能分析
- open表按F值升序存储未被拓展的节点，当插入一个新的节点时，可以采用二分查找将新的节点插入到合适位置，时间复杂度为O(log2 n)。
- 采用A*算法，设计评估函数F(n)=G(n)+H(n)来估计从当前状态到目标状态的代价,用来引导搜索方向，相较于深度优先算法和宽度优先算法，效率更高且搜索不具有盲目性。
- A*算法存在局限性，若启发函数设计不够准确，可能导致搜索效率降低甚至无法找到最优解。
#include<stdio.h> #include<graphics.h> #include<time.h> #include<stdlib.h> #define L 3 #define W 3 #define MAXLISTSIZE 1000 #define MAXSTEPSIZE 1000 IMAGE image, white; int map[3][3] = {0,1,2,4,3,5,6,7,8}; struct ENode { int status[9];//结点状态 int G; int H;//启发函数中的H int F;//评价函数中的F int White;//白块位置,即‘8’的位置 int step;//step存储该节点是上一节点通过怎样的移动得到的（1左2右3上4下） ENode* Parent;//父节点 };//节点定义 //最终目标状态 int FinalStatus[9] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; //定义OPEN表和CLOSE表 ENode OPEN[MAXLISTSIZE]; ENode CLOSE[MAXLISTSIZE]; int open = 0; int close = 0; void initmap() { int i, j; int array[8] = { 0 }; for (i = 0; i <= 7; i++) array[i] = i; int length = 8; for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { if (i == 2 && j == 2) { map[i][j] = 8; return; } int pos = rand() % length; map[i][j] = array[pos]; //调整一维数组 for (int k = pos; k < length-1; k++) { array[k] = array[k + 1]; } length--; } } } //计算逆序数对数 int countInversions(int arr[], int n) { int inversions = 0; for (int i = 0; i < n - 1; i++) { for (int j = i + 1; j < n; j++) { if (arr[i] > arr[j]) { inversions++; } } } return inversions; } // 判断解的存在性, int isSolvable(int map[3][3]) { int* arr = new int[9]; int index = 0; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) { *(arr + index) = map[i][j]; index++; } int inversions = countInversions(arr, 9); delete[] arr; // 释放数组空间 arr = NULL; // 将指针置为NULL return (inversions % 2 == 0); // 如果逆序数的个数是偶数，则存在解 } //求绝对值 int _abs(int a) { if (a < 0) return (-a); return a; } //计算H(n).时间复杂度为O(n) int CountH(int* s) { int H = 0; int i, distance = 0; for (i = 0; i <= 8; i++) { if (s[i] == 8) continue;//白块不加入计算，少计算一次 distance = _abs(s[i] - i); distance = distance / 3 + distance % 3; H += distance;//曼哈顿距离 } return H; } //判断节点是在哪个表中,返回正值在open中，负值在close中，0不在两个表中.时间复杂度为O(9n)*2，n为当前open中的结点数 int Exist(ENode node) { int i, j; int H = 0; //执行后H如果为0，则证明给函数的节点在表中已存在 for (i = 0; i <= open - 1; i++) //判断是否在OPEN表. { for (j = 0; j <= 8; j++) { if (node.status[j] != OPEN[i].status[j]) { H++; } } if (H == 0) //H=0证明在表中找到该节点 { return i; //如果在OPEN表中，返回i,节点在OPEN的位置 } H = 0; //扫描完一个节点后重置H } for (i = 0; i <= close - 1; i++) //判断是否在CLOSE表 { for (j = 0; j <= 8; j++) { if (node.status[j] != CLOSE[i].status[j]) { H++; } } if (H == 0) //H=0证明在表中找到该节点 { return (-i); //如果在CLOSE表中，返回-i（i为节点在CLOSE的位置） } H = 0; //扫描完一个节点后重置H } return 0; } //对OpEN进行排序 //查找插入位置 int OpenSearch(int x) { int mid; int low = 0, high = open - 1; while (low <= high) { mid = (low + high) / 2; if (OPEN[mid].F == x) return mid;//后来居上，即新加入的结点优先进行拓展 if (OPEN[mid].F < x) low = mid + 1; if (OPEN[mid].F > x) high = mid - 1; } return low; } //将新节点插入OPEN表 void Insert(ENode newNode) { int index = OpenSearch(newNode.F); for (int i = open - 1; i >= index; i--) OPEN[i + 1] = OPEN[i]; OPEN[index] = newNode; open++; } //初始化节点 void ENodeInit(ENode* Temp, int* status, int white, int g, ENode* parent, int step) { int i; for (i = 0; i <= 8; i++) { Temp->status[i] = status[i]; } Temp->White = white; Temp->G = g; Temp->H = CountH(status); Temp->F = Temp->G + Temp->H; Temp->Parent = parent; Temp->step = step; } //判断子节点是否在OPEN或CLOSE中，并进行对应的操作 void ExistAndOperate(ENode newNode) { int i; int inList; //定义表示新生成节点是否在OPEN表或CLOSE表中, 值为0 均不在，值>0 只在OPEN表，值<0 只在CLOSE表 if (newNode.G == 1) //如果是第一步的节点，直接加入OPEN中，返回 { Insert(newNode); return; } inList = Exist(newNode); //判断新节点是否在OPEN或CLOSE中 if (inList == 0) //如果均不在两个表中，将节点加入OPEN表中 { Insert(newNode); } else if (inList > 0) //如果在OPEN中，说明从初始节点到该节点找到了两条路径，保留耗散值短的那条路径 { if (OPEN[inList].F > newNode.F) //如果表内节点F值大于新节点F值，用新节点代替表内节点 { for (i = inList; i < open - 1; i++) OPEN[i] = OPEN[i + 1]; open--; Insert(newNode); } } } //寻找最佳路径 ENode* Search() { int i, j, temp; int status[9]; ENode* Temp = new ENode; ENode* Node; while (1) //一直循环知道找到解结束 { Node = new ENode; *Node = OPEN[0]; //从OPEN表中取出第一个元素（F值最小）进行扩展 //循环出口 if (Node->H == 0) //判断该节点是否是目标节点，若是，则不在位的将牌数为0，算法结束 { break; } CLOSE[close] = *Node; //将扩展过的节点放入CLOSE close++; for (i = 0; i <= open - 1; i++) //将扩展的节点从OPEN中释放 { OPEN[i] = OPEN[i + 1]; } open--; //对结点进行拓展，得到子节点 if ((Node->White) % 3 >= 1) //如果能左移，则进行左移创造新结点 { for (i = 0; i <= 8; i++) { status[i] = Node->status[i]; } temp = status[Node->White - 1]; status[Node->White - 1] = 8; status[Node->White] = temp; ENodeInit(Temp, status, Node->White - 1, (Node->G) + 1, Node, 1); //初始化新结点 ExistAndOperate(*Temp); //判断子节点是否在OPEN或CLOSE中，并进行对应的操作 } if ((Node->White) % 3 <= 1) //如果能右移，则进行右移创造新结点 { for (i = 0; i <= 8; i++) { status[i] = Node->status[i]; } temp = status[Node->White + 1]; status[Node->White + 1] = 8; status[Node->White] = temp; ENodeInit(Temp, status, Node->White + 1, (Node->G) + 1, Node, 2); //初始化新结点 ExistAndOperate(*Temp); //判断子节点是否在OPEN或CLOSE中，并进行对应的操作 } if (Node->White >= 3) //如果能上移，则进行上移创造新结点 { for (i = 0; i <= 8; i++) { status[i] = Node->status[i]; } temp = status[Node->White - 3]; status[Node->White - 3] = 8; status[Node->White] = temp; ENodeInit(Temp, status, Node->White - 3, (Node->G) + 1, Node, 3); //初始化新结点 ExistAndOperate(*Temp); //判断子节点是否在OPEN或CLOSE中，并进行对应的操作 } if (Node->White <= 5) //如果能下移，则进行下移创造新结点 { for (i = 0; i <= 8; i++) { status[i] = Node->status[i]; } temp = status[Node->White + 3]; status[Node->White + 3] = 8; status[Node->White] = temp; ENodeInit(Temp, status, Node->White + 3, (Node->G) + 1, Node, 4); //初始化新结点 ExistAndOperate(*Temp); //判断子节点是否在OPEN或CLOSE中，并进行对应的操作 } if (open == 0) //如果open=0， 证明算法失败， 没有解 { return NULL; } } return Node; } //展示具体步骤 void ShowStep(ENode* Node) { int STEP[MAXSTEPSIZE]; int STATUS[MAXSTEPSIZE][9]; int step = 0; int i, j; int totalStep = Node->G; while (Node) { STEP[step] = Node->step; for (i = 0; i <= 8; i++) { STATUS[step][i] = Node->status[i]; } step++; Node = Node->Parent; } printf("----------------------\n"); printf("所需最少步数：%d步\n", totalStep); printf("----------------------\n"); for (i = step - 1; i >= 0; i--) { if (STEP[i] == 1) printf("left"); else if (STEP[i] == 2) printf("right"); else if (STEP[i] == 3) printf("up"); else if (STEP[i] == 4) printf("down"); else if (STEP[i] == 0) printf("过程:\n"); printf(" "); } printf("\n节点变化：\n----------------------\n"); for (i = step - 1; i >= 0; i--) { for (j = 0; j <= 8; j++) { printf("%d", STATUS[i][j]); if (j == 2 || j == 5 || j == 8) printf("\n"); else printf(" "); } printf("----------------------\n"); } } struct pos { int x, y; }; void Loadimage()//缩放地图 { loadimage(&image, "image.jpg", 600, 600); loadimage(&white, "white.jpg", 200, 200); } void dataprintf() { for (int i = 0; i < L; i++) { for (int j = 0; j < W; j++) { printf("%2d", map[i][j]); } printf("\n"); } printf("----------------------\n"); } void DrawMap()//绘制地图 { int i, j, xx, yy; for (i = 0; i < L; i++) { for (j = 0; j < W; j++) { if (map[i][j] == 8) { putimage(j * 200, i * 200, &white); } else { //xx，yy为原图坐标 xx = (map[i][j] % 3); yy = (map[i][j] / 3); putimage(j * 200, i * 200, 200, 200, &image, xx*200, yy*200); } } } //画出切割线 for (i = 0; i <= L; i++) { line(i * 200, 0, i * 200, W * 200); line(0, i * 200, L * 200, i * 200); } } struct pos searchwhite()//找白块坐标 { int i, j; for (i = 0; i < L; i++) for (j = 0; j < W; j++) { if (map[i][j] == 8) return { i,j }; } return { -1,-1 }; } int GameOver()//判断是否有序 { int* m = (int*)map; for (int i = 0; i < L * W-1; i++) if (m[i] > m[i + 1]) return 0; return 1; } void statics() { int fstatus[9] = { 0 }; int i, j, index = 0; //map数组转化为fstatus for (i = 0; i < 3; i++) { for (j = 0; j < 3; j++) { fstatus[index] = map[i][j]; index++; } } ENode* FNode = new ENode; ENode* EndNode; for (i = 0; i <= 8; i++) //判断0节点位置 { if (fstatus[i] == 8) break; } ENodeInit(FNode, fstatus, i, 0, NULL, 0); //初始节点 OPEN[open] = *FNode; //将初始节点放入OPEN中 open++; EndNode = Search(); //寻找最佳路径 if (!EndNode) printf("无解"); else { ShowStep(EndNode); //展示步骤 } } int main() { int i, j, mi, mj; srand((unsigned int)time(0)); ExMessage m;//鼠标类型结构体 initgraph(600, 600, EW_SHOWCONSOLE);//加载窗口 Loadimage();//缩放图片 while (!(isSolvable(map))) { initmap(); } dataprintf(); BeginBatchDraw(); while (1) { DrawMap(); if (GameOver()) { MessageBox(GetHWnd(), "You win", "YOU WIN", MB_OK); break; } peekmessage(&m, EM_MOUSE); i = searchwhite().x;//找到白块坐标 j = searchwhite().y; if (m.message == WM_LBUTTONDOWN)//鼠标左键 { mj = m.x / 200; mi = m.y / 200; if (mi == i - 1 && mj == j || mi == i + 1 && mj == j || mi == i && mj == j - 1 || mi == i && mj == j + 1) { map[i][j] = map[mi][mj]; map[mi][mj] = 8; dataprintf(); } } else if (m.message == WM_RBUTTONDOWN)//鼠标右键 { statics(); int* p = (int*)map; for (i = 0; i < L * W; i++) { for (j = 0; j < W * L - i - 1; j++) { if (p[j] > p[j + 1]) { int temp; temp = p[j]; p[j] = p[j + 1]; p[j + 1] = temp; } } } } EndBatchDraw(); } closegraph(); return 0; }##注意要分割的图片命名为image，白块命名为white，将图片和代码放在同一目录下