项目1：snek（贪吃蛇）

截止日期：2月12日星期四，晚上11:59:59 PT

欢迎来到61C的第一个项目！在这个项目中，您将通过创建一个可玩的贪吃蛇游戏来练习C编程。如果您不熟悉贪吃蛇游戏，可以通过此链接尝试演示。

开始此项目前，请确保已完成实验0的设置。

项目1需要实验1-2的知识。建议学习讲座2-4，以及讲座5中的内存管理/布局部分。建议参与讨论课1和2。

我们要求所有学生在为项目1提交工单之前证明他们尝试过调试。如果没有进行调试尝试，或者显然您不理解如何调试，我们将要求您完成实验2后重新提交工单。

一般测试和调试提示可以在后面的编译、测试和调试部分以及我们的常见错误页面上找到。

设置

本作业可以单独完成或与合作伙伴一起完成。

您必须在hive机器上完成此项目（而不是您的本地机器）。如果需要重新设置hive机器，请参见实验0。

警告：在Gradar上创建小组后，您将无法更改（添加、删除或交换）此项目的合作伙伴，因此请在开始项目前确认您的合作伙伴。您必须在Gradar和每个Gradescope提交中添加您的合作伙伴。

如果有特殊情况需要更换合作伙伴（例如，您的合作伙伴退课、您的合作伙伴没有响应），请私下联系我们。

  1. 访问 Gradar。登录并注册您的项目1小组（并添加您的合作伙伴，如果有的话），然后为您或您的小组创建一个GitHub仓库。如果您有合作伙伴，一个合作伙伴应创建一个小组并邀请另一个合作伙伴加入该仓库。另一个合作伙伴应接受邀请而不创建自己的小组。

  2. 在hive机器上克隆仓库。

    git clone git@github.com:61c-student/sp26-proj1-USERNAME.git 61c-proj1

（替换 sp26-proj1-USERNAME 为您的GitHub仓库名称）

  1. 导航到您的仓库：

    cd 61c-proj1

  2. 添加starter仓库作为远程仓库：

    git remote add starter https://github.com/61c-teach/sp26-proj1-starter.git

  3. 从starter仓库拉取代码：

    git pull starter main

概念概述

蛇

贪吃蛇游戏可以用字符网格表示。网格包含墙壁、水果和一条或多条蛇。下面显示了一个游戏示例：

##############
#            #
#    dv      #
#     v   #  #
#     v   #  #
#   s >>D #  #
#   v     #  #
# *A<  *  #  #
#            #
##############

网格包含以下特殊字符：

  • # 表示墙壁。
  • （空格字符）表示空白区域。
  • * 表示水果。
  • wasd 表示蛇的尾巴。
  • ^<v> 表示蛇的身体。
  • WASD 表示蛇的头部。
  • x 表示死亡的蛇头。

蛇的每个字符表示蛇当前的移动方向：

  • w、W 或 ^ 表示向上
  • a、A 或 < 表示向左
  • s、S 或 v 表示向下
  • d、D 或 > 表示向右

在每个时间步长，每条蛇按照以下规则移动：

  • 每条蛇向其头部方向移动一步。
  • 如果头部撞到蛇的身体或墙壁，蛇死亡并停止移动。蛇死亡时，头部被替换为 x。
  • 如果头部移动到水果上，蛇吃掉水果并增长1个单位长度。每次消耗水果后，会在棋盘上生成一个新水果。

在上面的示例中，经过一个时间步长后，棋盘将如下所示：

##############
#         *  #
#     s      #
#     v   #  #
#     v   #  #
#   s >>>D#  #
#   v     #  #
# A<<  *  #  #
#            #
##############

再经过一个时间步长后，棋盘将如下所示：

##############
#         *  #
#     s      #
#     v   #  #
#     v   #  #
#     >>>x#  #
#   s     #  #
#A<<<  *  #  #
#            #
##############

蛇的长度保证至少为三个单位。

蛇的编号

棋盘上的每条蛇根据其尾巴的位置编号，按照尾巴在文件中出现的顺序（从上到下，然后从左到右）。例如，考虑以下包含四条蛇的棋盘：

#############
#  s  d>>D  #
#  v   A<a  #
#  S    W   #
#       ^   #
#       w   #
#############

蛇0是尾巴为 s 的蛇，蛇1的尾巴为 d，蛇2的尾巴为 a，蛇3的尾巴为 w。

一旦蛇从初始位置编号，蛇的编号在整个游戏过程中不会改变。

游戏板

游戏板是字符网格，不一定是矩形的。以下是非矩形板的示例：

##############
#            #######
#####             ##
#   #             ##
#####             ######
#                 ##   #
#                 ######
#                 ##
#                  #
#      #####       #
########   #########

请注意，每行可以有不同数量的字符，但必须以墙壁（#）开头和结尾。您还可以假设棋盘是一个封闭空间，因此蛇不能在任何方向无限移动。

game_t结构体

贪吃蛇游戏在内存中存储为game_t结构体，定义在game.h中。该结构体包含以下字段：

  • unsigned int num_rows：游戏板的行数。
  • char** board：内存中的游戏板。board数组的每个元素是一个char*指针，指向包含棋盘一行的字符数组。每行必须以换行符结尾，并且必须是有效的字符串。
  • unsigned int num_snakes：棋盘上的蛇数量。
  • snake_t* snakes：snake_t结构体的数组。

snake_t结构体

同样定义在game.h中，每个snake_t结构体包含以下字段：

  • unsigned int tail_row：蛇尾巴所在的行。
  • unsigned int tail_col：蛇尾巴所在的列。
  • unsigned int head_row：蛇头所在的行。
  • unsigned int head_col：蛇头所在的列。
  • bool live：如果蛇活着为true，如果蛇死亡为false。

请勿修改提供的结构体定义。在本项目中，您只需要修改game.c、snake.c和custom_tests.c。

编译、测试和调试

在本项目中，我们提供了一个Makefile，因为一些编译命令比较复杂。请不要自己调用gcc！

本项目涉及两个可执行文件：

  • unit-tests：此可执行文件包含所有单元测试，为任务1到6提供。
  • snake：此可执行文件包含完整的贪吃蛇游戏，参与任务7中的集成测试。

要编译可执行文件，您可以运行make executable-name。例如，要编译unit-tests，运行make unit-tests。然后您可以使用./unit-tests运行可执行文件，或对可执行文件调用cgdb和valgrind。修改代码后务必重新编译！

请注意，单元测试不是全面的，通过它们并不保证您的实现完全正确。但是，它们应该有助于您开始调试。

测试和调试提示

如果您的实现不起作用，是时候开始调试了。您可以在代码中添加printf语句来在代码执行期间打印变量，然后重新编译并运行单元测试以查看打印语句的输出。

在CGDB中，您可以在自己的代码中设置断点（提示：请参阅GDB参考卡了解如何在不同文件中设置断点）。然后输入run或r启动程序，它将在断点处暂停。

提示：如果您看到"Segmentation fault (core dumped)"，这意味着您的程序崩溃了。开始调试的一种方法是启动CGDB，不带断点run程序，然后输入backtrace或bt查看程序崩溃的代码行。

您还可以在cgdb调试时使用p print_board(game, stdout)打印整个棋盘。

任务1：create_default_game

在game.c中实现create_default_game函数。此函数应在内存中创建一个默认的贪吃蛇游戏，使用以下起始游戏（您可以硬编码），并返回指向新创建的game_t结构体的指针。

####################
#                  #
# d>D    *         #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
#                  #
####################
create_default_game
参数 无
返回值 game_t * 指向新创建的game_t结构体的指针。

提示

  • 棋盘有18行，每行有20列。水果位于第2行第9列（从零开始索引）。尾巴位于第2行第2列，头部位于第2行第4列。
  • 新游戏应该存储在内存的哪个部分（代码段、静态区、栈、堆）？
  • strcpy可能会有帮助。
  • 棋盘的每行必须以换行符结尾，并且必须是有效的字符串。

测试和调试

此任务提供了单元测试，可以通过unit-tests可执行文件运行。有关编译和调试，请参阅编译、测试和调试。

任务2：free_game

在game.c中实现free_game函数。此函数应释放为给定游戏分配的所有内存，包括所有snake结构体和所有game->board内容。

free_game
参数 game_t* game 指向要释放的game_t结构体的指针
返回值 无

测试和调试

要测试我们是否正确释放了游戏的内存，运行make valgrind-test-free-game检查内存泄漏。如果没有泄漏，那么您就通过了此任务的单元测试。

任务3：print_board

在game.c中实现print_board函数。此函数应将给定的游戏板打印到给定的文件指针。

print_board
参数 game_t* game 指向要打印的game_t结构体的指针
FILE* fp 指向要打印棋盘的文件对象的指针
返回值 无

提示

  • fprintf函数将帮助您将字符和/或字符串打印到给定的文件指针。

测试和调试

此任务提供了单元测试，可以通过unit-tests可执行文件运行。有关编译和调试，请参阅编译、测试和调试。

如果您的函数执行成功（没有段错误或崩溃）但打印的输出不正确，您打印的棋盘将在unit-test-out.snk中。正确打印的棋盘应与任务1中的默认棋盘匹配。

任务4：update_game

在game.c中实现update_game函数。此函数应根据游戏规则将蛇移动一个时间步长。

辅助函数不计分；对于此任务，我们只检查update_game是否正确。

任务4.1：辅助函数

我们提供了以下辅助函数定义，您可以实现它们。这些函数完全独立于任何游戏板或蛇；它们只接受单个字符并输出有关该字符的一些信息。

  • bool is_tail(char c)：如果c是蛇尾巴的一部分，则返回true。蛇的尾巴由以下字符组成：wasd。否则返回false。
  • bool is_head(char c)：如果c是蛇头的一部分，则返回true。蛇的头部由以下字符组成：WASDx。否则返回false。
  • bool is_snake(char c)：如果c是蛇的一部分，则返回true。蛇由以下字符组成：wasd^<v>WASDx。否则返回false。
  • char body_to_tail(char c)：将蛇身体中的字符（^<v>）转换为表示蛇尾巴的匹配字符（wasd）。对于非蛇身体的字符，输出可能未定义。
  • char head_to_body(char c)：将蛇头中的字符（WASD）转换为表示蛇身体的匹配字符（^<v>）。对于非蛇头的字符，输出可能未定义。
  • unsigned int get_next_row(unsigned int cur_row, char c)：如果c是v或s或S，返回cur_row + 1。如果c是^或w或W，返回cur_row - 1。否则返回cur_row。
  • unsigned int get_next_col(unsigned int cur_col, char c)：如果c是>或d或D，返回cur_col + 1。如果c是<或a或A，返回cur_col - 1。否则返回cur_col。

这些辅助函数没有提供单元测试，因此您必须在custom_tests.c中编写自己的测试，以确保它们按预期工作。确保这些测试全面测试您的辅助函数——我们的自动评分器将在有bug的实现上运行您的测试，以确保您的测试能够捕获bug！

编写单元测试时，如果测试失败，测试函数应返回false；如果测试通过，则返回true。您可以使用printf打印调试语句。asserts.h中的一些断言辅助函数可能会有用。

编写完自己的单元测试后，您可以使用make custom-tests编译它们，这会生成custom-tests可执行文件，您可以运行或调试它。

任务4.2：next_square

在game.c中实现next_square辅助函数。此函数返回给定蛇即将移动到的单元格中的字符。此函数不应修改内存中存储的游戏中的任何内容。

next_square
参数 game_t* game 指向要分析的game_t结构体的指针
int snum 要分析的蛇的索引
返回值 char 给定蛇即将移动到的单元格中的字符

例如，考虑以下棋盘：

##############
#            #
#            #
#            #
#   d>D*     #
#            #
#       s    #
#       v    #
#       S    #
##############

假设game是指向此game_t的指针，则next_square(game, 0)应返回*，因为蛇0的头部正在移动到包含*的单元格中。类似地，对于蛇1，next_square(game, 1)应返回#。

您之前编写的辅助函数可能对此函数（以及此任务的其余部分）有帮助。另外，请查看get_board_at和set_board_at，这是我们为您编写的辅助函数。

使用make unit-tests编译提供的单元测试。您还可以在cgdb调试时使用p print_board(game, stdout)打印整个棋盘。

任务4.3：update_head

在game.c中实现update_head函数。此函数将更新蛇的头部。

请记住，您需要在游戏板和snake_t结构体中都更新头部。在游戏板上，在蛇即将移动到的位置添加新头部，并将旧头部从头部字符（WASD）更改为身体字符（^）。在snake_t结构体中，更新头部的行和列。

update_head
参数 game_t* game 指向要更新的game_t结构体的指针
int snum 要更新的蛇的索引
返回值 无

例如，考虑以下棋盘：

##############
#   d>D      #
#        *   #
#        W   #
#        ^   #
#        ^   #
#        w   #
#            #
#            #
##############

假设game是指向此game_t的指针，则update_head(game, 0)将移动蛇0的头部，保持所有其他蛇不变。在对应于蛇0的snake_t结构体中，head_col值应从6更新为7，head_row值应保持不变为1。新棋盘将如下所示：

##############
#   d>>D     #
#        *   #
#        W   #
#        ^   #
#        ^   #
#        w   #
#            #
#            #
##############

请注意，此函数在移动头部时忽略食物、墙壁和蛇身体。

使用make unit-tests编译提供的单元测试。您还可以在cgdb调试时使用p print_board(game, stdout)打印整个棋盘。

任务4.4：update_tail

在game.c中实现update_tail函数。此函数将更新蛇的尾部。

请记住，您需要在游戏板和snake_t结构体中都更新尾部。在游戏板上，清除当前尾部，并将新尾部从身体字符（^<v>）更改为尾部字符（wasd）。在snake_t结构体中，更新尾部的行和列。

update_tail
参数 game_t* game 指向要更新的game_t结构体的指针
int snum 要更新的蛇的索引
返回值 无

例如，考虑以下棋盘：

##############
#   d>D      #
#        *   #
#        W   #
#        ^   #
#        ^   #
#        w   #
#            #
#            #
##############

假设game是指向此game_t的指针，则update_tail(game, 1)将移动蛇1的尾部，保持所有其他蛇不变。在对应于蛇1的snake_t结构体中，tail_row值应从6更新为5，tail_col值应保持不变为9。新棋盘将如下所示：

##############
#   d>D      #
#        *   #
#        W   #
#        ^   #
#        w   #
#            #
#            #
#            #
##############

使用make unit-tests编译提供的单元测试。您还可以在cgdb调试时使用p print_board(game, stdout)打印整个棋盘。

任务4.5：update_game

使用您创建的辅助函数，在game.c中实现update_game。

提醒一下，蛇移动的规则如下：

  • 每条蛇向其头部方向移动一步。
  • 如果头部撞到蛇的身体或墙壁，蛇死亡并停止移动。蛇死亡时，头部被替换为 x。
  • 如果头部移动到水果上，蛇吃掉水果并增长1个单位长度。（您可以通过更新头部而不更新尾部来实现增长1个单位。）每次消耗水果后，会在棋盘上生成一个新水果。

int (*add_food)(game_t* game)参数是一个函数指针，这意味着add_food是指向内存代码段的指针。add_food指向的代码是一个接受game_t* game作为参数并返回int的函数。您可以使用add_food(x)调用此函数（将x替换为您的参数），以向棋盘添加水果。

update_game
参数 game_t* game 指向要更新的game_t结构体的指针
int (*add_food)(game_t* game) 指向将水果添加到棋盘的函数的指针
返回值 无

测试和调试

仅为update_game提供了单元测试，可以通过unit-tests可执行文件运行。有关编译和调试，请参阅编译、测试和调试。

任务5：load_board

在game.c中实现load_board函数。此函数将从流（FILE *）读取游戏板到内存中。您的load_board实现必须支持从stdin和任何其他流读取，因此请不要使用不支持stdin的任何操作，例如查找、倒带或重新打开。

请记住，游戏板的每行可能有不同数量的列。您的实现应该是内存高效的，不应分配比存储棋盘所需的内存多得多的内存。例如，如果一行有3个字符，您不应该为该行分配100字节的空间。

您必须使用fgets从文件指针读取。如果您使用fgets以外的函数从file读取，我们保留手动重新评分您的提交的权利。其他字符串函数，如strchr，在这里也可能有帮助！不必担心fgets调用的错误处理。

提示：realloc可能对此任务有帮助。

任务5和任务6结合将在内存中创建一个game_t结构体，并设置其所有字段。在此任务中，请将num_snakes设置为0，并将snakes数组设置为NULL，因为这些将在任务6中初始化。

任务5.1：read_line

在game.c中实现read_line函数。给定一个FILE * file，从file读取一行并将字符串存储在堆上。如果fgets出错，返回NULL。

read_line
参数 FILE* file 可以从中读取字符串的文件指针
返回值 char * 指向新读取的字符串的指针。如果有任何错误或到达EOF，则为NULL。

任务5.2：load_board

使用read_line，在game.c中实现load_board函数。

load_board
参数 FILE* file 可以从中读取棋盘的文件指针
返回值 game_t * 指向新创建的game_t结构体的指针。如果有任何错误，则为NULL。

测试和调试

此任务提供了单元测试，可以通过unit-tests可执行文件运行。有关编译和调试，请参阅编译、测试和调试。

任务6：initialize_snakes

在game.c中实现initialize_snakes函数。此函数接收游戏板并创建snake_t结构体数组。

任务6.1：find_head

在game.c中实现find_head函数。给定一个已填写尾部行和列的snake_t结构体，此函数遍历棋盘以找到头部行和列，并在结构体中填写头部行和列。

find_head
参数 game_t* game 指向要分析的game_t结构体的指针
int snum 要分析的蛇的索引
返回值 无

例如，考虑以下棋盘：

##############
#            #
#        *   #
#            #
#   d>v      #
#     v      #
#  W  v      #
#  ^<<<      #
#            #
##############

假设game是指向此game_t的指针，则find_head(game, 0)将分别用6和3填充蛇0结构体的head_row和head_col字段。

任务6.2：initialize_snake

使用find_head，在game.c中实现initialize_snake函数。您可以假设传入此函数的游戏是调用load_board的结果，但您不能假设snakes数组已定义。这意味着与棋盘相关的字段已经填写完毕，您只需要填写num_snakes并创建snakes数组。

您可以假设棋盘上的所有蛇一开始都是活的。

initialize_snakes
参数 game_t* game 指向要填写的game_t结构体的指针
返回值 game_t* game 指向已填写字段的game_t结构体的指针。这可以与传入的结构体相同（您可以就地修改结构体）。

测试和调试

此任务提供了单元测试，可以通过unit-tests可执行文件运行。有关编译和调试，请参阅编译、测试和调试。

任务7：main

使用您在所有先前任务中实现的函数，填写snake.c中的空白。每次运行snake.c程序时，棋盘将更新一个时间步长。

要测试您的完整实现，请运行make run-integration-tests。这将通过内部调用make snake为您编译程序。

要调试您的实现，请运行cgdb --args ./snake -i tests/TESTNAME-in.snk -o tests/TESTNAME-out.snk。要检查内存泄漏或越界读写，您可以运行valgrind ./snake -i tests/TESTNAME-in.snk -o tests/TESTNAME-out.snk。将TESTNAME替换为tests文件夹中的一个测试名称：

  • 01-simple
  • 02-direction
  • 03-tail
  • 04-food
  • 05-wall
  • 06-small
  • 07-medium
  • 08-multisnake
  • 09-everything
  • 10-filled
  • 11-manyclose
  • 12-corner
  • 13-sus
  • 14-orochi
  • 15-hydra
  • 16-huge
  • 17-wide
  • 18-tall
  • 19-101-127
  • 20-long-line
  • 21-bigL

类似地，您可以通过运行./snake --stdin -o tests/TESTNAME-out.snk < tests/TESTNAME-in.snk来测试从stdin加载，然后运行diff tests/TESTNAME-ref.snk tests/TESTNAME-out.snk。要调试，请运行cgdb ./snake，然后运行set args --stdin -o tests/TESTNAME-out.snk < tests/TESTNAME-in.snk，或者运行valgrind ./snake --stdin -o tests/TESTNAME-out.snk < tests/TESTNAME-in.snk。注意：此行为不会通过单元测试或make run-integration-tests显式测试，但将在自动评分器上测试。

如果您对代码进行了更改，请确保在运行其他命令之前重新编译（make run-integration-tests除外）！

您还可以运行make run-nonexistent-input-file-test来确保如果输入文件不存在，您的程序会正确以错误代码-1退出。

任务8：合作伙伴/反馈表

恭喜完成项目！这是一个相对较新的项目，因此我们很乐意听取您对未来学期可以改进的方面的反馈。

请填写此简短表单，您可以在此提供对项目的想法以及（如适用）您的合作体验。您提供的任何反馈都不会影响您的成绩，因此请放心诚实地提供建设性意见。

提交和评分

将您的代码提交到Project 1 Gradescope作业。确保您只修改了snake.c、game.c和custom_tests.c。您可以根据需要多次提交到Gradescope，您在Gradescope上看到的分数将是您此项目的最终分数。

仅供娱乐：玩贪吃蛇

现在您可以通过运行make interactive-snake，然后运行./interactive-snake，使用您编写的代码玩游戏。使用wasd键控制您的蛇！

要加快或减慢游戏速度，您可以运行./interactive-snake -d 0.5（将0.5替换为时间步之间的秒数）。在游戏过程中，您还可以按]加快速度，按[减慢速度。