《数据结构与算法分析》课程设计——贪吃蛇问题

中国矿业大学信控学院

 

 

/*文献参考*/

https://blog.csdn.net/fdog_/article/details/102625969

https://blog.csdn.net/dy_1024/article/details/78841757

 

一、问题描述

 

以数据结构思想设计实现贪吃蛇小游戏。

 

二、需求分析

 

首先需要考虑如何设计一个win运行窗口来实时显示结果

然后考虑到蛇的身子是一节一节的，此时最容易联想到的数据结构就是顺序表，链表，如果把蛇比做顺序表或者链表，在之后吃到食物的时候，身子肯定会变长，这就涉及到插入的操作，所以为了更高的效率，我们用链表实现我们的蛇的部分，最初我们把蛇身子按照四个结点打印在屏幕。

对于蛇的移动，在屏幕上面蛇的移动看起来是整个身子向前方平移一个单位，但是其原理是我们在屏幕的另一个地方把蛇从新打印一遍，又把之前的蛇身子去除掉。

对于食物的产生，随机的在地图中产生一个节点，在蛇的头坐标和食物的坐标重复的时候，食物消失，蛇的身子加长，也就是蛇的节点数增加一个。

蛇在其中的几种状态，正常状态：蛇头节点的坐标没有和墙的坐标以及自己身子的坐标重合，

被自己杀死：蛇头的坐标和蛇身子的坐标重合，

撞墙：蛇头的坐标和墙的坐标重合。

 

三、算法设计

 

1.相关变量。

1 1.相关变量。
2 int judgesum = 0;            //判断是否加快
3 int pause = 200000000;       //暂停速度(移动速度)
4 int * pj = &judgedirection;  //用指针传值判断移动方向
5 nakebody *end = null;        //尾节点

 

2.创建链表 ，贪吃蛇的身体如何保存是游戏的核心，所以我们需要用到链表来保存蛇的身体，这样就可以随时知道蛇身数据。

1 typedef struct snakebody
2 {
3     int x, y;          //蛇身的坐标
4     struct snakebody *next;//保存下一个蛇身的地址
5 }snakebody;           //通过typedef将 snakebody 替代 struct snakebody

 

3.记录食物出现的坐标。

1 typedef struct snakexy
2 {
3     int x;
4     int y;
5 }snakexy; //记录食物坐标

 

4.绘制初始界面和游戏地图，如图所示。

 1 #include<windows.h>
 2 #define height  20  //设置地图高度
 3 #define width   40  //设置地图宽度
 4 #define printf  printf("■");
 5 #define line    printf("\n");
 6 #define empty   printf("  "); //因为这三个语句经常用，所以我就定义成了宏
 7 void front();       //绘制初始界面
 8 void deawmap();     //绘制地图
 9 
10 void front()
11 {
12     setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red | foreground_blue);//设置红色和蓝色相加
13     movecursor(18, 15);
14     printf("请等待......");
15     for (int i = 0; i <= 3000000000; i++) {}
16     system("cls");//清屏处理
17 }
18 void deawmap()
19 {
20     for (int i = 0; i < width; i++)printf line  //打印上边框
21         for (int i = 1; i < height - 1; i++)          //打印左右边框
22         {
23             for (int j = 0; j < width; j++)
24             {
25                 if (j == 0 || j == width - 1 || j == width - 10)
26                 {
27                     printf
28                         if (j == width - 1)line
29                 }
30                 else empty
31             }
32         }
33     for (int i = 0; i < width; i++)printf line  //打印下边框
34 }

setconsoletextattribute()函数是一个api设置字体颜色和背景色的函数。参数表中使用两个属性（属性之间用，隔开），不同于system()，setconsoletextattribute()可以改变界面多种颜色，而system()只能修改为一种！。

 

5. 初始化蛇身，刚开始蛇不应该只要一个头，所以我们必须创建几个身体。

 1 snakebody *phead = null;    //存储着整个蛇身 不可更改
 2 snakebody *phead_1 = null;  //指向蛇身
 3 snakebody *pbady = null;    //创建节点
 4 void isnake();             //初始化蛇身
 5 void isnake()
 6 {
 7     for (int i = 0; i < 5; i++)//初始化蛇身拥有五个长度
 8     {
 9         pbady = (snakebody*)malloc(sizeof(snakebody));//创建节点
10         pbady->x = 5 - i;
11         pbady->y = 5;
12         if (phead == null)
13         {
14             phead = pbady;
15         }
16         else
17         {
18             end->next = pbady;
19         }
20         pbady->next = null;
21         end = pbady;
22     }
23     phead_1 = phead;
24     while (phead_1->next != null)//打印蛇身
25     {
26         movecursor(phead_1->x, phead_1->y);
27         printf
28             phead_1 = phead_1->next;
29     }
30 }

 

6.产生食物，随机产生食物，如果和蛇身体重合则再次随机产生食物。

 1 #include<time.h>
 2 int sum = 0;     //计算得分
 3 snakexy * food = null;          //保存食物位置
 4 void foodrand();    //生成食物
 5 void foodrand()
 6 {
 7     srand((int)time(0));
 8     int x = rand() % 27 + 2;//生成随机数
 9     int y = rand() % 17 + 2;
10     phead_1 = phead;
11     for (int i = 0; i <= 200; i++)
12     {
13         if (phead_1->x == x && phead_1->y == y)
14         {
15             x = rand() % 27 + 2;
16             y = rand() % 17 + 2;
17         }
18         else
19         {
20             phead_1 = phead_1->next;
21         }
22         if (phead_1->next == null)
23         {
24             break;
25         }
26     }
27     movecursor(x, y);
28     printf
29         food = (snakexy*)malloc(sizeof(snakexy));
30     food->x = x;
31     food->y = y;
32     movecursor(33, 5);
33     printf("  ");
34     showf();
35     sum++;
36     setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity);// 蓝
37 }

rand函数功能为获取一个伪随机数，如要产生[m,n]范围内的随机数num，可用int num=rand()%(n-m+1)+m;

 

7.游戏刷新和暂停 ，按回车可暂停游戏。

 1 int judgedirection = 4;   //判断方向
 2 void controlmove();    //控制移动和暂停
 3 void controlmove()
 4 {
 5     if (getasynckeystate(vk_up) && 0x8000)
 6     {
 7         if (judgedirection == 2)
 8         {
 9         }
10         else
11         {
12             judgedirection = 1;
13         }
14     }
15     if (getasynckeystate(vk_down) && 0x8000)
16     {
17         if (judgedirection == 1)
18         {
19         }
20         else
21         {
22             judgedirection = 2;
23         }
24     }
25     if (getasynckeystate(vk_right) && 0x8000)
26     {
27         if (judgedirection == 3)
28         {
29         }
30         else
31         {
32             judgedirection = 4;
33         }
34     }
35     if (getasynckeystate(vk_left) && 0x8000)
36     {
37         if (judgedirection == 4)
38         {
39         }
40         else
41         {
42             judgedirection = 3;
43         }
44     }
45     if (getasynckeystate(vk_return) && 0x0d)//判断回车
46     {
47         while (1)
48         {
49             if (getasynckeystate(vk_return) && 0x0d)//再次回车退出死循环
50             {
51                 break;
52             }
53         }
54     }
55 }

getasynckeystate（）确定用户当前是否按下了键盘上的一个键

 

8.显示分数和难度，更新分数和难度。

 1 int sum = 0;     //计算得分
 2 int hard = 0;     //计算难度
 3 void showf();                   //显分数以及难度
 4 void showf()
 5 {
 6     setconsoletextattribute(getstdhandle(std_output_handle), foreground_blue);// 蓝
 7     movecursor(33, 5);
 8     printf("得分：%d", sum);
 9     movecursor(33, 6);
10     printf("难度：%d", hard);
11 }

 

9.移动光标 ，游戏不闪的原因就是我们只绘制一次地图 然后用光标定点刷新目标点。

1 void movecursor(int x, int y); //移动光标
2 void movecursor(int x, int y)//设置光标位置(就是输出显示的开始位置)
3 {
4     coord pos = { x * 2,y };
5     handle output = getstdhandle(std_output_handle);//获得标准输出的句柄   
6     setconsolecursorposition(output, pos); //设置光标位置
7 }

coord是windows api中定义的一种结构体

 

10.检测，检测是否吃到食物，是否撞墙，是否撞到自己。

 1 void jfood();     //检测是否吃到食物
 2 void jwall();     //检测蛇头是否撞墙
 3 void jsnake();     //检测蛇头是否撞到蛇身
 4 void jfood()
 5 {
 6     phead_1 = phead;
 7     if (phead_1->x == food->x&&phead_1->y == food->y)
 8     {
 9         foodrand();
10         judgesum += 1;
11         if (judgesum == 5)
12         {
13             judgesum = 0;//如果judgesum等于5则从新判断
14             hard += 1;
15             pause -= 20000000;//每成立一次循环减少20000000
16         }
17         while (phead_1->next != null)
18         {
19             phead_1 = phead_1->next;
20         }
21         snakebody *s = (snakebody*)malloc(sizeof(snakebody));
22         s->x = food->x;
23         s->y = food->y;
24         s->next = null;
25         phead_1->next = s;
26         controlmove();
27         movecursor(phead_1->x, phead_1->y);
28         printf
29     }
30     //获取食物的坐标和蛇头做对比
31 }
32 void jwall()
33 {
34     if (phead->x == 0 || phead->x == 29 || phead->y == 0 || phead->y == 19)
35     {
36         movecursor(10, 20);
37         setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red);//设置红色
38         printf("抱歉，你撞到了自己，游戏结束!              ");
39         system("pause>nul");
40         exit(0);
41     }
42 }
43 void jsnake()
44 {
45     phead_1 = phead->next;
46     while (phead_1->next != null)
47     {
48         if ((phead->x == phead_1->x) && (phead->y == phead_1->y))
49         {
50             movecursor(10, 20);
51             setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red);//设置红色
52             printf("抱歉，你撞到了自己，游戏结束!          ");
53             system("pause>nul");
54             exit(0);
55         }
56         phead_1 = phead_1->next;
57     }
58 }

 

11.游戏循环

 1 void move();     //游戏运行
 2 void move()
 3 {
 4     while (1)
 5     {
 6         phead_1 = phead;
 7         while (phead_1->next->next != null)
 8         {
 9             phead_1 = phead_1->next;
10         }
11         phead_1->next = null;
12         for (int i = 0; i < pause; i++) {}
13         controlmove();
14         movecursor(phead_1->x, phead_1->y);
15         empty
16             //上面为消除尾部
17             snakebody *phead_2 = (snakebody*)malloc(sizeof(snakebody));
18         if (*pj == 1)
19         {
20             phead_2->x = phead->x;
21             phead_2->y = phead->y - 1;
22         }
23         if (*pj == 2)
24         {
25             phead_2->x = phead->x;
26             phead_2->y = phead->y + 1;
27         }
28         if (*pj == 3)
29         {
30             phead_2->x = phead->x - 1;
31             phead_2->y = phead->y;
32         }
33         if (*pj == 4)
34         {
35             phead_2->x = phead->x + 1;
36             phead_2->y = phead->y;
37         }
38         phead_2->next = phead;
39         phead = phead_2;
40         movecursor(phead_2->x, phead_2->y);
41         printf
42             jfood();
43         jwall();
44         jsnake();
45         movecursor(40, 20);
46     }
47 }

 

12.释放内存

 1 void free();                    //释放内存
 2 void free()
 3 {
 4     while (phead->next != null)
 5     {
 6         phead = phead->next;
 7         free(phead);
 8     }
 9     free(phead);
10 }

 

附录：完整代码

  1 #include<stdio.h>
  2 #include<time.h>
  3 #include<windows.h>
  4 #define height  20  //设置地图高度
  5 #define width   40  //设置地图宽度
  6 #define printf  printf("■");
  7 #define line    printf("\n");
  8 #define empty   printf("  ");
  9 typedef struct snakebody
 10 {
 11     int x, y;//身体的坐标
 12     struct snakebody *next;//结构指针
 13 }snakebody;//先来创建保持身体的链表，贪吃蛇的核心代码就是该如何保存蛇的身体
 14 typedef struct snakexy
 15 {
 16     int x;
 17     int y;
 18 }snakexy; //记录食物坐标
 19 int sum = 0;     //计算得分
 20 int judgesum = 0;    //判断是否加快
 21 int hard = 0;     //计算难度
 22 int pause = 200000000;   //暂停速度(移动速度)
 23 int judgedirection = 4;   //判断方向
 24 int * pj = &judgedirection;  //用指针传值判断移动方向
 25 snakebody *phead = null;  //存储着整个蛇身 不可更改
 26 snakebody *phead_1 = null;  //指向蛇身
 27 snakebody *pbady = null;  //创建节点
 28 snakebody *end = null;   //尾节点
 29 snakexy * food = null;          //保存食物位置
 30 void front();                   //游戏开始页面1
 31 void jfood();     //检测是否吃到食物1
 32 void jwall();     //检测蛇头是否撞墙1
 33 void jsnake();     //检测蛇头是否撞到蛇身1
 34 void isnake();     //初始化蛇身1
 35 void deawmap();     //绘制地图1
 36 void foodrand();    //生成食物1
 37 void controlmove();    //控制移动和暂停1
 38 void movecursor(int x, int y); //移动光标1
 39 void move();     //游戏运行1
 40 void showf();                   //显分数以及难度1
 41 void free();                    //释放内存
 42 int main()
 43 {
 44     front();
 45     setconsoletextattribute(getstdhandle(std_output_handle), foreground_green);//绿
 46     deawmap();
 47     showf();
 48     setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity);// 暗白
 49     movecursor(34, 10);
 50     printf("↑");
 51     movecursor(31, 11);
 52     printf("使用←↓→来控制");
 53     movecursor(31, 12);
 54     printf("蛇的移动，撞墙游");
 55     movecursor(31, 13);
 56     printf("戏结束，每5分增 ");
 57     movecursor(31, 14);
 58     printf("一个难度(速度)");
 59     isnake();
 60     foodrand();
 61     movecursor(40, 20);
 62     move();
 63     return 0;
 64 }
 65 void front()
 66 {
 67     setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red | foreground_blue);//设置红色和蓝色相加
 68     movecursor(18, 15);
 69     printf("请等待......");
 70     for (int i = 0; i <= 3000000000; i++) {}
 71     system("cls");
 72 }
 73 void deawmap()
 74 {
 75     for (int i = 0; i < width; i++)printf line  //上边框
 76         for (int i = 1; i < height - 1; i++)          //打印左右边框
 77         {
 78             for (int j = 0; j < width; j++)
 79             {
 80                 if (j == 0 || j == width - 1 || j == width - 10)
 81                 {
 82                     printf
 83                         if (j == width - 1)line
 84                 }
 85                 else empty
 86             }
 87         }
 88     for (int i = 0; i < width; i++)printf line  //下边框
 89 }
 90 void movecursor(int x, int y)//设置光标位置(就是输出显示的开始位置)
 91 {
 92     /*  coord是windows api中定义的一种结构体
 93     * typedef struct _coord
 94     * {
 95     * short x;
 96     * short y;
 97     * } coord;
 98     *  */
 99     coord pos = { x * 2,y };
100     handle output = getstdhandle(std_output_handle);//获得 标准输出的句柄   
101     setconsolecursorposition(output, pos); //设置控制台光标位置
102 }
103 void foodrand()
104 {
105     srand((int)time(0));
106     int x = rand() % 27 + 2;
107     int y = rand() % 17 + 2;
108     phead_1 = phead;
109     for (int i = 0; i <= 200; i++)
110     {
111         if (phead_1->x == x && phead_1->y == y)
112         {
113             x = rand() % 27 + 2;
114             y = rand() % 17 + 2;
115         }
116         else
117         {
118             phead_1 = phead_1->next;
119         }
120         if (phead_1->next == null)
121         {
122             break;
123         }
124     }
125     movecursor(x, y);
126     printf
127         food = (snakexy*)malloc(sizeof(snakexy));
128     food->x = x;
129     food->y = y;
130     movecursor(33, 5);
131     printf("  ");
132     showf();
133     sum++;
134     setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity);// 蓝
135 }
136 void controlmove()
137 {
138     if (getasynckeystate(vk_up) && 0x8000)
139     {
140         if (judgedirection == 2)
141         {
142         }
143         else
144         {
145             judgedirection = 1;
146         }
147     }
148     if (getasynckeystate(vk_down) && 0x8000)
149     {
150         if (judgedirection == 1)
151         {
152         }
153         else
154         {
155             judgedirection = 2;
156         }
157     }
158     if (getasynckeystate(vk_right) && 0x8000)
159     {
160         if (judgedirection == 3)
161         {
162         }
163         else
164         {
165             judgedirection = 4;
166         }
167     }
168     if (getasynckeystate(vk_left) && 0x8000)
169     {
170         if (judgedirection == 4)
171         {
172         }
173         else
174         {
175             judgedirection = 3;
176         }
177     }
178     if (getasynckeystate(vk_return) && 0x0d)
179     {
180         while (1)
181         {
182             if (getasynckeystate(vk_return) && 0x0d)
183             {
184                 break;
185             }
186         }
187     }
188 }
189 void isnake()
190 {
191     for (int i = 0; i < 5; i++)
192     {
193         pbady = (snakebody*)malloc(sizeof(snakebody));
194         pbady->x = 5 - i;
195         pbady->y = 5;
196         if (phead == null)
197         {
198             phead = pbady;
199         }
200         else
201         {
202             end->next = pbady;
203         }
204         pbady->next = null;
205         end = pbady;
206     }
207     phead_1 = phead;
208     while (phead_1->next != null)
209     {
210         movecursor(phead_1->x, phead_1->y);
211         printf
212             phead_1 = phead_1->next;
213     }
214 }
215 void move()
216 {
217     while (1)
218     {
219         phead_1 = phead;
220         while (phead_1->next->next != null)
221         {
222             phead_1 = phead_1->next;
223         }
224         phead_1->next = null;
225         for (int i = 0; i < pause; i++) {}
226         controlmove();
227         movecursor(phead_1->x, phead_1->y);
228         empty
229             //上面为消除尾部
230             snakebody *phead_2 = (snakebody*)malloc(sizeof(snakebody));
231         if (*pj == 1)
232         {
233             phead_2->x = phead->x;
234             phead_2->y = phead->y - 1;
235         }
236         if (*pj == 2)
237         {
238             phead_2->x = phead->x;
239             phead_2->y = phead->y + 1;
240         }
241         if (*pj == 3)
242         {
243             phead_2->x = phead->x - 1;
244             phead_2->y = phead->y;
245         }
246         if (*pj == 4)
247         {
248             phead_2->x = phead->x + 1;
249             phead_2->y = phead->y;
250         }
251         phead_2->next = phead;
252         phead = phead_2;
253         movecursor(phead_2->x, phead_2->y);
254         printf
255             jfood();
256         jwall();
257         jsnake();
258         movecursor(40, 20);
259     }
260 }
261 void jfood()
262 {
263     phead_1 = phead;
264     if (phead_1->x == food->x&&phead_1->y == food->y)
265     {
266         foodrand();
267         judgesum += 1;
268         if (judgesum == 5)
269         {
270             judgesum = 0;
271             hard += 1;
272             pause -= 20000000;
273         }
274         while (phead_1->next != null)
275         {
276             phead_1 = phead_1->next;
277         }
278         snakebody *s = (snakebody*)malloc(sizeof(snakebody));
279         s->x = food->x;
280         s->y = food->y;
281         s->next = null;
282         phead_1->next = s;
283         controlmove();
284         movecursor(phead_1->x, phead_1->y);
285         printf
286     }
287     //获取食物的坐标和蛇头做对比
288 }
289 void jwall()
290 {
291     if (phead->x == 0 || phead->x == 29 || phead->y == 0 || phead->y == 19)
292     {
293         movecursor(10, 20);
294         setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red);//设置红色
295         printf("抱歉，你撞到了自己，游戏结束!              ");
296         system("pause>nul");
297         exit(0);
298     }
299 }
300 void jsnake()
301 {
302     phead_1 = phead->next;
303     while (phead_1->next != null)
304     {
305         if ((phead->x == phead_1->x) && (phead->y == phead_1->y))
306         {
307             movecursor(10, 20);
308             setconsoletextattribute(getstdhandle(std_output_handle), foreground_intensity | foreground_red);//设置红色
309             printf("抱歉，你撞到了自己，游戏结束!          ");
310             system("pause>nul");
311             exit(0);
312         }
313         phead_1 = phead_1->next;
314     }
315 }
316 void showf()
317 {
318     setconsoletextattribute(getstdhandle(std_output_handle), foreground_blue);// 蓝
319     movecursor(33, 5);
320     printf("得分：%d", sum);
321     movecursor(33, 6);
322     printf("难度：%d", hard);
323 }
324 void free()
325 {
326     while (phead->next != null)
327     {
328         phead = phead->next;
329         free(phead);
330     }
331     free(phead);
332 }