jkilopu's blog
0%

mysnake——基于Linux、C语言的控制台小游戏

发表于 更新于

翻出了今年二月份写的一个小游戏，这也是我的第一个独立完成的编程小项目。不做一些分析和总结的话，就太可惜了。

贪吃蛇

在我的童年时期，拼图、推箱子和贪吃蛇几乎翻盖手机中必有的也是唯一的小游戏了。现在，这种“老年机”早已被时代淘汰，而贪吃蛇得益于其知名度和网上繁多的资源、教程，成为大学C语言课程期末作业的常客。（老师们也看烦了吧哈哈）实际上，如果你能独立完成一个能玩的版本，说明你对C语言的运用已经入门了。下面我们就来分析一下贪吃蛇的基本组成要素。

  • （2020/07/25更新）

近来在读《深入理解计算机系统》，前面学习汇编相关章节时，Bomb Lab和Attack Lab做得很爽。不过到存储器这一章，实践的内容便大幅减少。再加上链接看得云里雾里（于是打算看看《程序员的自我修养——链接、装载与库》），便想回过头来搞搞贪吃蛇的计分板模块。

这才发现，原来的代码全都集中在两三个源文件和头文件中。为了理清结构和逻辑，改变了项目的结构，全部完成后如下图：

这样感觉清晰多了。也许是受到了cs61b课程的影响，有点模块化的感觉了。

接下来将计分板的部分完成，详情请看下面的介绍，最后修复了一些bug。

添加了一些图片。

游戏的结构

在这里，我们并不关心一些细节问题，只是对各个元素的特点进行分析。

  1. 有边界的地图

    地图的实现可以基于字符界面和图形界面，基于以下几个因素我选择了字符界面

    1. 蛇的移动只有四个方向，使用字符界面就可以实现。
    2. 学习图形界面的时间成本较高。

  2. 能在屏幕上朝特定方向移动的蛇

    我们看到游戏中角色的“移动”通常是由在短时间内改变屏幕像素的颜色来实现（利用人的视觉暂留效应制造移动的假象）。而对于字符界面来说，像素颜色的改变对应着终端格子中字符的变化。因此，蛇的移动本质上是屏幕上字符的打印。然而C标准库的标准输入输出函数并不能满足我们的全部需求，因为蛇的移动方向包括上和下，单纯用printf十分不方便。
    于是我在Linux上找到了一个操纵字符界面的库——ncurses。详细的介绍，请看这篇文章。也可以在man page中阅读官方文档：

    1
    $ man ncurses

  3. 随机生成的食物

    利用C中最基础的随机数生成函数，我们很容易模拟食物随机生成

  4. 计分板（2020/07/25更新）

    我想要的效果如下：计分板会展示前八名玩家的最高分数，以及当前玩家的实时分数与排名。可以说是一个动态的计分板。

    有三点需要注意：排名、保存数据和读取数据

    1. 排名

      一开始还以为要用到排序，实际上只要将当前玩家插入到有序序列的合适位置即可

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      /* 遍历后全部重新打印 */
      unsigned int ShowScoreboardWithCurrentRecord(Scoreboard sc, Record cr, int y, int x)
      {
          bool showed = false;
          unsigned int i, number = 0;
          for (i = 0; i < sc->size; i++)
          {
              if (!showed && cr->score > sc->records[i]->score)
              {
                  number = i + 1;
                  if (i < SHOWED_MAX_NUM)
                      ShowRecord(cr, number, y + i, x);
                  showed = true;
              }
              if (i + showed < SHOWED_MAX_NUM)
                  ShowRecord(sc->records[i], i + 1 + showed, y + i + showed, x);
          }
          if (!showed)
          {
              number = i + 1;
              if (i < SHOWED_MAX_NUM)
                  ShowRecord(cr, number, y + i, x);
          }
          return number;
      }

      Scoreboard结构体中有Record数组（这里没有考虑用其他数据结构），Record结构体包含玩家的名称和分数。

      时间复杂度为Ω(N)，因为遍历了整个数组，而不是仅交换两个Record的位置。此外，对于数组这种数据结构来说，插入的开销很大，所以我选择了在合适的位置直接打印。

    2. 保存数据

      涉及到了文件操作的知识，这里只需要用fsprintf库函数就行。然而文件中插入一条记录我感觉做不到（无论是用fwrite库函数还是write系统调用）因此选择了与排序相同的做法。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      /* 1. 逻辑有些复杂（为了保持有序性、以及指定的一些规则）
       * 2. 完全覆盖之前的文件内容
       * 3. 没有加密
       * 4. 效率还好吧(Ω(n))
       */
      void WriteScoreboard(Scoreboard sc, Record cr, int found)
      {
          if (sc->size > RECORD_MAX_NUM)
              FatalError("Records are full");
          FILE *fp_sc_w = fopen("score.txt", "w");
          bool written = false;
          for (int i = 0; i < sc->size; i++)
          {
              /* 只写一次 && 合适的条件（原来没有记录 || 该记录比原记录大） && 合适的位置 */
              if (!written && (found == -1 || cr->score > sc->records[found]->score ) && cr->score > sc->records[i]->score)
              {
                  fprintf(fp_sc_w, "%s %u\n", cr->name, cr->score);
                  written = true;
              }
              if (i != found || cr->score <= sc->records[found]->score)
                  fprintf(fp_sc_w, "%s %u\n", sc->records[i]->name, sc->records[i]->score);
          }
          if (!written && found == -1)
              fprintf(fp_sc_w, "%s %u\n", cr->name, cr->score);
          fclose(fp_sc_w);
      }

      这里的逻辑稍微有些复杂，需要仔细推敲（最好先写个伪代码）。文件内容如下：

    3. 读取数据

      小心异常情况：数据不完整、文件不存在等。

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      void ReadScoreboard(Scoreboard sc)
      {
          FILE *fp_sc_r = OpenScoreboardFile();
          int size = 0;
          while (size < RECORD_MAX_NUM)
          {
              int status = ReadRecord(sc->records[size], fp_sc_r);
              if (status != 2)
                  if (status != EOF)
                      FatalError("Incomplete data");
                  else
                      break;
              size++;
          }
          sc->size = size;
          if (fp_sc_r != NULL)
              fclose(fp_sc_r);
      }

      int ReadRecord(Record r, FILE *fp)
      {
          return (fp == NULL) ? EOF : fscanf(fp, "%s %u", r->name, &r->score);
      }

实现

有了想法，码代码就不是一件难事了。关键在于实现的方法和细节。下面就说说两个关键部分和可能踩的坑

蛇

关于蛇的实现有两个问题：

  1. 信息储存位置
    1. 储存在二维数组中
    2. 储存在链表中
  2. 移动方式
    1. 刷新整个地图
    2. 刷新蛇
      很明显，第二种实现方式效率更高，但实现起来要复杂一些。

我选择将蛇的信息储存在链表中，并通过刷新蛇让蛇动起来。

1
2
3
4
5
6
7
8
struct _snake
{
    List *list;
    char symbol;
    unsigned int length;
    int y_dir, x_dir; /* 上左-1，下右1 */
    int speed;
};

使用单向带tail的链表实现时，比较有趣的就是蛇的移动了。我们只操纵链表的头和尾就可以实现蛇的移动，而不需要删除蛇再打印。

还有一种选择是将各个节点的坐标改为前一个（靠近蛇头的）节点的坐标。不清楚哪一种效率更高。

1
2
3
4
5
6
7
8
9
10
11
12
/* 只操作链表的头和尾实现蛇的移动 */
void MoveSnake(Snake s)
{
    // move head
    InsertHead(s->list, s->list->head->y + s->y_dir, s->list->head->x + s->x_dir);
    mvaddch(s->list->head->y, s->list->head->x, s->symbol);
    // move tail
    mvaddch(s->list->tail->y, s->list->tail->x, BLANK);
    DeleteTail(s->list);
    // put cursor back
    move(LOWER_BONDARY, 0);
}

程序流程

程序不仅要处理游戏中事件(蛇移动、判定)，还要读入玩家的输入。而我们熟知的输入函数都是阻塞的，程序会”停”在该函数处。

常用的解决方法：

  1. 使用非阻塞的输入函数（如conio.h中的_kbhit函数），并利用轮询（Poll）。但conio.h既不在标准库中，也没有定义在ISO或POSIX中，不能再linux平台上使用。
  2. 借助信号。信号本质上是一种向一个进程通知发生异步事件的机制。在贪吃蛇中，我们可以设置一个定时信号，定时通知进程去处理游戏中事件，而在主函数中，我们只需要循环获取用户输入就可以了。
    关于信号的更详细的文章，请看这篇文章

易出的Bug（2020/07/25更新）

这里记录了我觉得易出bug，有些当时发现就修复了，有些发现了很长一段时间后才修复。

  1. 食物刷新在蛇身上

    蛇的移动区域与食物的刷新区域完全重合，冲突不可避免，导致的结果是食物短暂出现在蛇身上后就“隐身”了（被蛇身覆盖了）。有两种做法可以避免：

    1. 再刷新一次

      问题在于蛇身过长，占地图面积比例过大时，效率可能不高（没测试过）。

    2. 将蛇身排除在食物刷新区域外

      问题在于太麻烦，写起来麻烦，执行起来也麻烦。

    我选择了第一种方法（反正我玩一会就死了）。

  2. 转向操作太快导致蛇走回头路然后死掉

    我们禁止蛇走回头路，通常的方法是忽略反方向的按键（比如蛇朝右走时，只有’w‘和’s‘键能改变方向）。前面提到过，蛇每隔一段时间就移动一次（我设置的是100ms），问题就出在这100ms的间隔中。

    假设蛇正朝右走，我们按下’s‘，然后迅速按下’a’。在按下’s’后的100ms内，蛇的方向已经改变为朝下，但还未移动。这时按下的’a’不会被忽略，蛇的方向又变为朝左，100ms过后，蛇头便向左移动，一口咬到了自己的身体。

    解决方法为在这100ms内禁止方向改变，在这里我们使用sleep函数直接让程序休眠即可：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    int main(void)
    {
        setup();

        while ((key = getchar()) != 'q')
        {
            if (key == 'w' && abs(snake->y_dir) != 1)
            {
                TurnUp(snake);
                sleep(100);
            }
            if (key == 's' && abs(snake->y_dir) != 1)
            {
                TurnDown(snake);
                sleep(100);
            }
            if (key == 'a' && abs(snake->x_dir) != 1)
            {
                TurnLeft(snake);
                sleep(100);
            }
            if (key == 'd' && abs(snake->x_dir) != 1)
            {
                TurnRight(snake);
                sleep(100);
            }
        }

        wrapup();
        return 0;
    }

总结

进行分析后，我们发现贪吃蛇的实现思路是很清晰的。不过在码代码的过程中，还需要注意程序的流程以及一些细节的处理（free、指针操作、全局变量、边界状态的判定等）
下面是部分源代码（2020/07/25项目结构变动，具体请浏览项目的GitHub页面）仅作参考，不能直接使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
/* mysnake.c version 0.1 
 * usage: ./mysnake
 * 功能：（1）贪吃蛇的基本实现、（2）重新开始游戏
 * 框架：随时准备读取用户输入（处于阻断状态），利用set_ticker()函数定时（很短）发送信号，收到信号时检测蛇的状态并移动(DetectAndMove())（蛇只有在移动时才会有状态的改变）
 * 知识点:1.经典信号的部分使用
 *       2.发出信号的时间函数的使用
 *       3.链表的添加与删除
 *       4.判断状态
 *       5.malloc()与free()
 * 总结：1. 链表的操作很重要，第一个遇到的问题是没有注意蛇产生过程的特点（我的实现方法为从尾到头）
 *      2. 如果malloc的大小不对，短时间内可能没问题，最后一定会在某个奇怪的地方segmentation fault
 */

// 全局变量（好像信号处理函数不能传参，暂时用着全局变量吧）
Snake snake;
Food food;
int ch;

#include <mysnake.h>

int main(void)
{
    setup();

    while ((ch = getchar()) != 'q')
    {
        if (ch == 'w')
            if (snake->y_dir != 1)
                TurnUp(snake);
        if (ch == 's')
            if (snake->y_dir != -1)
                TurnDown(snake);
        if (ch == 'a')
            if (snake->x_dir != 1)
                TurnLeft(snake);
        if (ch == 'd')
            if (snake->x_dir != -1)
                TurnRight(snake);
    }

    wrapup();
    return 0;
}
void setup(void)
{
    initscr();
    noecho();
    crmode();
    clear();

    srand(time(NULL));
    start();
}
void start(void)
{
    // 画墙
    DrawBoundary();
    // 构建、画蛇
    snake = CreateSnake(DEFAULT_LENGTH, DEFAULT_BODY);
    PrintSnake(snake);
    // 放食物
    food = PutFood(food);
    // 设置信号
    signal(SIGALRM, DetactAndMove);
    // 设置以定时发送信号
    set_ticker(DEFAULT_SPEED);
}
void DrawBoundary(void)
{
    int i;
    // 上下边
    for (i = 0; i < RIGHT_BONDARY; i++)
    {
        mvaddch(0, i, WALL);
        mvaddch(LOWER_BONDARY - 1, i, WALL);
    }
    // 左右边
    for (i = 0; i < LOWER_BONDARY; i++)
    {
        mvaddch(i, 0, WALL);
        mvaddch(i, RIGHT_BONDARY - 1, WALL);
    }
    refresh();
}
Snake CreateSnake(int length, char symbol)
{
    Snake s;
    if (((s = (Snake)malloc(sizeof(struct _snake))) == NULL)) // 空间的大小要正确啊！不然在后面的操作就有可能segmentation fault了
        FatalError("Out of space!");
    s->length = length, s->symbol = symbol;
    if ((s->list = (List *)calloc(2, sizeof(Node *))) == NULL)
        FatalError("Out of space!");
    InitSnake(s);
    return s;
}
void InitSnake(Snake s)
{
    int i;
    for (i = 0; i < s->length; i++)
        InsertHead(s->list, INITIAL_Y, INITIAL_X + i); // 不能用Add()!!!
    s->speed = DEFAULT_SPEED;
    s->y_dir = INITIAL_DIRECTION_Y;
    s->x_dir = INITIAL_DIRECTION_X;
}
void PrintSnake(Snake s)
{
    Node *p = s->list->head;
    while (p)
    {
        mvaddch(p->y, p->x, s->symbol);
        p = p->next;
    }
    refresh();
}
void DetactAndMove(int signum)
{
    signal(SIGALRM, SIG_IGN); // 避免重入
    MoveSnake(snake);
    // show
    refresh();
    if (HitBoundary(snake) || HitBody(snake))
    {
        set_ticker(0);
        // remove food
        mvaddch(food->y, food->x, BLANK);
        // game over massage
        mvaddstr(LOWER_BONDARY / 3, RIGHT_BONDARY / 2 - 3, "Game Over! ");
        refresh();
        sleep(2);
        mvaddstr(LOWER_BONDARY / 3, RIGHT_BONDARY / 2 - 3, "Restart?  ");
        refresh();
        if ((ch = getchar()) == 'r')
        {
            mvaddstr(LOWER_BONDARY / 3, RIGHT_BONDARY / 2 - 3, "          ");
            Restart();
        }
    }
    else if (HitFood(snake, food))
    {
        // add the body to tail
        Add(snake->list, snake->list->tail->y + snake->y_dir, snake->list->tail->x + snake->x_dir);
        // remove and delete food
        free(food);
        // reput food
        food = PutFood(food);
    }
    signal(SIGALRM, DetactAndMove);
}
/* 只操作链表的头和尾实现蛇的移动 */
void MoveSnake(Snake s)
{
    // move head
    InsertHead(s->list, s->list->head->y + s->y_dir, s->list->head->x + s->x_dir);
    mvaddch(s->list->head->y, s->list->head->x, s->symbol);
    // move tail
    mvaddch(s->list->tail->y, s->list->tail->x, BLANK);
    DeleteTail(s->list);
    // put cursor back
    move(LOWER_BONDARY, 0);
}
bool HitBoundary(Snake s)
{
    if (s->list->head->y != 0 && s->list->head->y != LOWER_BONDARY - 1 && s->list->head->x != 0 && s->list->head->x != RIGHT_BONDARY - 1)
        return false;
    return true;
}
bool HitBody(Snake s)
{
    Node *p = s->list->head;
    while (p = p->next)
    {
        if (s->list->head->x == p->x && s->list->head->y == p->y)
            return true;
    }
    return false;
}
bool HitFood(Snake s, Food f)
{
    if (s->list->head->y == f->y && s->list->head->x == f->x)
        return true;
    return false;
}
Food PutFood(Food f)
{
    f = (Food)malloc(sizeof(struct _food));
    if (f == NULL)
        FatalError("Out of space!");
    f->y = rand() % (LOWER_BONDARY - 2) + 1; /* 产生1～LOWER_BONDARY-2的数字 */
    f->x = rand() % (RIGHT_BONDARY - 2) + 1;
    f->symbol = FOOD;
    mvaddch(f->y, f->x, f->symbol);
    refresh();
    return f;
}
void TurnUp(Snake s)
{
    s->y_dir = -1;
    s->x_dir = 0;
}
void TurnDown(Snake s)
{
    s->y_dir = 1;
    s->x_dir = 0;
}
void TurnLeft(Snake s)
{
    s->y_dir = 0;
    s->x_dir = -1;
}
void TurnRight(Snake s)
{
    s->y_dir = 0;
    s->x_dir = 1;
}
void EraseSnake(Snake s)
{
    Node *p = s->list->head;
    while (p)
    {
        mvaddch(p->y, p->x, BLANK);
        p = p->next;
    }
}
void DisposeSnake(Snake s)
{
    Node *p = s->list->head, *tmp;
    // delete the snake
    while (p)
    {
        tmp = p->next;
        free(p);
        p = tmp;
    }
    // delete the list
    free(s->list);
    free(s);
}
void Restart(void)
{
    // erase and delete snake
    EraseSnake(snake);
    DisposeSnake(snake);
    // delete food
    free(food);
    // set again
    start();
}
void wrapup(void)
{
    set_ticker(0);
    endwin();
    DisposeSnake(snake);
    // delete fodd
    free(food);
}

感谢浏览!