Lab 09 Conway's Game of Life

常见问题解答

每个作业的顶部都会提供一个常见问题解答的链接。您也可以通过在网址末尾添加“/faq”来访问。Lab 09 的常见问题解答位于此处。

介绍

本次实验旨在帮助大家完成第三个项目：构建你自己的世界 (BYOW)。第一部分将教大家如何使用一组“图块”(tiles)在屏幕上生成各种形状。这会应用到第三个项目中房间、走廊和其他世界元素的构建上。下周的实验会更深入地讲解交互性的实现，这和第三个项目的一部分有关联（更多内容会在下一次实验中讲解）。

实验准备

开始本实验之前，请完成以下步骤：

• 像往常一样，运行 git pull skeleton main
• 观看上学期第三个项目的入门视频，链接如下：在此链接。
• 虽然名称和API可能略有改动，但整体思路仍然适用。
• 要明白，第三个项目是一场马拉松，不是短跑冲刺。你和你的搭档现在就应该开始考虑设计方案了。
• 阅读第一阶段的内容，或者大致浏览一下第三个项目的规范，理解其核心思想。

在本次实验的前半部分，大家会学到一些基本技巧和工具，这些对完成第三个项目很有帮助。

第一部分：了解图块渲染引擎

单调的世界

打开代码框架，查看BoringWorldDemo文件。运行后，你应该会看到如下的窗口：

这个世界主要由空白区域构成，只有一个位于底部中央附近的矩形方块。生成这个世界的代码主要分为三个部分：

• 初始化图块渲染引擎。
• 生成一个二维 TETile[][] 数组。
• 使用图块渲染引擎显示 TETile[][] 数组。

通读代码，学习图块渲染API的工作原理。创建TERenderer对象后，你需要调用initialize方法，指定世界的宽度和高度，这里的宽度和高度指的是图块的数量。每个图块是16像素 x 16像素，举例来说，如果调用ter.initialize(10, 20)，就会得到一个10个图块宽、20个图块高的世界，也就是160像素宽、320像素高。

这段代码也演示了如何使用TETile对象。你可以使用TETile构造函数从零开始创建（参考TETile.java），或者从Tileset.java文件中选择预先生成的图块。例如，BoringWorldDemo.java中的这段代码，会生成一个二维图块数组，并用预先生成的Tileset.NOTHING图块填充。

TETile[][] world = new TETile[WIDTH][HEIGHT];
for (int x = 0; x < WIDTH; x++) {
    for (int y = 0; y < HEIGHT; y++) {
        world[x][y] = Tileset.NOTHING;
    }
}

当然，我们也可以覆盖已有的图块。例如，BoringWorld.java中的这段代码，会创建一个由预先生成的Tileset.WALL图块组成的15x5的区域，并覆盖到之前循环创建的NOTHING图块上。

for (int x = 20; x < 35; x++) {
    for (int y = 5; y < 10; y++) {
        world[x][y] = Tileset.WALL;
    }
}

info

$(0, 0)$ 是位于世界左下角的位置（和大家通常习惯的左上角不同）。举例来说，对于坐标(5, 4)，我们需要先向右移动5个单位，再向上移动4个单位。本次实验中，我们会一直使用这个坐标体系。

渲染的最后一步是调用 ter.renderFrame(world) 函数。这里的 ter 是一个 TERenderer 对象。只有在调用 renderFrame 方法之后，对 tiles 数组的修改才会显示在屏幕上。

尝试将指定的 tile 更改为 Tileset 类中除了 WALL 之外的其他 tile，看看会发生什么（例如 Tileset.GRASS 或 Tileset.WATER）。 此外，尝试修改循环中的常量，观察世界会发生什么变化。

danger

Tiles 本身是不可变的！你不能直接修改 tile 的属性，例如 world[x][y].character = 'X'。请参考 TETile 类的定义来理解这一点！

info

为什么我们需要将世界初始化为 Tileset.NOTHING，而不是保持未初始化的状态？原因是 renderFrame 方法不会绘制值为 null 的 tile。 如果不这样做，在调用 renderFrame 时会抛出 NullPointerException 异常。

随机世界

现在打开 RandomWorldDemo.java。 尝试运行它，您应该会看到类似以下内容：

这个世界一片混乱——到处都是墙壁和鲜花！查看 RandomWorldDemo.java 文件，你会发现我们做了一些新的尝试：

• 我们创建并使用了一个 Random 类型的对象，它是一个“伪随机数生成器”。
• 我们使用了一种新的条件语句，称为 switch 语句。
• 我们已将工作委托给函数，而不是在 main 中完成所有操作。

随机数生成器顾名思义，会产生一个看似随机排列的无限数字流。 Random 类提供了在 Java 中生成伪随机数的功能。 例如，以下代码生成并打印 3 个随机整数：

Random r = new Random(1000);
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());

我们将 Random 称为伪随机数生成器，因为它不是真正随机的。 其底层原理是使用一些数学方法，根据先前生成的数字来计算下一个数字。 我们不会详细介绍这种数学方法，但如果您有兴趣，请参阅 Wikipedia。 更重要的是，生成的序列是确定性的。我们可以通过选择不同的“种子”来获得不同的序列。 这种伪随机性将是 Project 3 的核心部分。

在上面的代码片段中，种子是 Random 构造函数的输入，因此在本例中为 1000。 控制种子非常有用，因为它允许我们间接地控制随机数生成器的输出。 如果我们为构造函数提供相同的种子，我们将获得相同的序列值。 例如，下面的代码打印 4 个随机数，然后再次打印相同的 4 个随机数。 由于种子与之前的代码片段不同，因此这 4 个数字可能与上面打印的 3 个数字不同。 这对 Project 3 来说非常重要，因为它能提供确定性的随机性：你的世界看起来是完全随机的，但你可以通过相同的种子一致地重新创建它们，方便调试和评分。

Random r = new Random(82731);
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());
r = new Random(82731);
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());
System.out.println(r.nextInt());

如果用户/程序员没有提供种子，例如使用 Random r = new Random()，则随机数生成器会使用一些频繁变化且能产生大量唯一值的值来作为种子，例如当前时间和日期。 种子也可以通过其他一些非常规的方式生成，例如使用一堵装满熔岩灯的墙。 目前，RandomWorldDemo 使用了一个硬编码的种子值，也就是2873123。因此，每次运行它都会生成完全相同的随机世界。如果你想体验不同的随机世界，可以修改这个种子值。不过，鉴于这个世界的随机性很高，即使改变种子，可能也不会带来太大的惊喜。

最重要的一点是，我们的代码不是将所有工作都放在 main 函数中，而是将任务分解，委托给具有明确定义的行为的函数。 这对你的项目 3 体验至关重要！ 你需要不断地识别那些可以用定义清晰的方法来解决的子任务。更进一步，你的方法应该构成一个抽象的层次结构！

danger

现在，请务必确保你已经阅读并理解了 BoringWorldDemo 和 RandomWorldDemo (非常重要!)，并且大致了解了如何使用 TERenderer、TETile 和 Tileset。 在接下来的部分，我们会假设你已经基本掌握了这两个示例程序的工作原理，以及 tile 渲染相关类的用法。

第二部分：康威生命游戏

介绍

康威生命游戏 (简称生命游戏) 是由数学家约翰·霍顿·康威创建的一种细胞自动机。 细胞自动机是一种与自动机理论相关的计算模型 (自动机理论研究的是抽象机器和自动/自操作机器)。 虽然我们不需要深入了解自动机理论或细胞自动机的具体概念，但生命游戏可以很好地展示细胞如何随时间演变。 这是一个零玩家游戏，其世界是一个无限的二维细胞网格。 每个细胞都有生或死两种状态，并且在每个时间步，细胞的状态会根据其 8 个邻居的状态而发生变化 (我们将在稍后详细介绍这些规则)。 游戏效果如下所示：

游戏中未来的世代取决于初始状态。 初始状态将有效地充当未来状态的“种子”。 对于本实验，初始状态可以使用随机种子生成，也可以以文件的形式提供。

如果你想体验一下这个游戏，可以在这里玩在线版本，或者在这里观看一个精彩的演示。

实现

在开始之前，请务必花一些时间阅读 GameOfLife 文件。 熟悉代码，特别是其中提供的变量，对后续的开发至关重要。

在开始之前，请注意以下几点提醒和提示：

• 对于本实验，我们正在实现一个稍微修改过的康威生命游戏版本，我们将世界边界之外的区域视为死亡细胞，而不是无限的。
• 你可以假设板上的每个 tile 将始终是 Tileset.NOTHING 或 Tileset.CELL。
• 提醒一下，(0, 0) 是板的左下角。
• 我们在每个方法上方都提供了注释，以及你将要实现的方法的 TODO 注释形式。

danger

请确保你已阅读完上面的提示和提醒！ 我们将在下一节中假设你理解它们。

构造函数

此类中有多个构造函数。 你不应该 (也不建议) 修改它们。 一些构造函数接受一个名为 boolean test 的额外参数 - 这些构造函数主要用于不渲染的测试（因为自动评分器无法渲染/显示任何内容）。 如果你想查看游戏的视觉输出，请查看此部分。 或者，如果你在本地编写自己的测试，你也可以使用没有该附加参数的构造函数来渲染和进行可视化测试。

接下来，让我们看看需要实现哪些方法。

nextGeneration

正如我们之前提到的，康威生命游戏的世界是一个二维网格，由单元格构成，每个单元格都处于死亡或存活状态。这些单元格的状态会根据其八个邻居的状态（包括垂直、水平和对角线方向的邻居）而改变。如下图所示，其中绿色单元格是当前单元格，紫色单元格是其邻居：

info

在判断一个单元格的下一个状态时，您只需要考虑其周围八个直接相邻的单元格，如上图所示。

在每个时间步，单元格的状态将根据以下规则改变：

1. 任何存活的单元格，如果存活的邻居少于两个，就会死亡，如同因资源不足而死亡。
2. 任何存活的单元格，如果有两个或三个邻居，就会存活到下一代。
3. 任何存活的单元格，如果存活的邻居多于三个，就会死亡，如同因资源过度而死亡。
4. 任何死亡的单元格，如果恰好有三个存活的邻居，就会复活，如同繁殖一般。

在 nextGeneration 中，我们希望根据上述规则“更新”棋盘的状态。棋盘的当前状态由 TETiles[][] tiles 表示。提供的 TETile[][] newGen 代表下一个状态，并且最初填充了 Tileset.NOTHING。我们希望获取棋盘的当前状态，将下一代/状态存储在 newGen 中并返回它。

根据上述规则实现方法 nextGeneration。

持久性

在我们开始讨论您需要实现的另外两个方法之前，让我们先谈谈项目 3。在项目 3 中，您必须实现保存和加载游戏状态的功能。本实验旨在帮助您理解持久性的概念。什么是持久性？

在 Java 程序运行期间，我们会使用变量来记录数据。但是一旦程序结束，这些数据便会“消失”，无法再被访问。例如，如果我们在程序中声明一个变量，例如 int x = 50，它将只存在于程序内部 - 通过持久化，我们希望程序结束后，这些数据仍然能够保存下来。为了能够再次访问这些数据，我们需要确保程序的状态能够被保存。这称为持久性。

info

在本实验的这一部分中，我们提供了一个类 FileUtils，以帮助您将信息保存和加载到文件中。请在实现过程中使用提供的 FileUtils 类，并务必在使用前阅读其代码。

saveBoard

如果您导航到 patterns，您会看到几个包含不同初始状态的文本文件。这些特定模式代表我们可以传递的几个初始状态，并且它们以特定的格式存储，我们需要在 saveBoard 方法中实现相同的格式。让我们以其中一个 (glidergun.txt) 为例：

50 50
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000000000000
00000000000000000000000000000000000000000001100000
// 其余部分已隐藏

您看到的最初两个数字分别是棋盘的宽度和高度，并用一个空格分隔。 接下来的行代表棋盘（在上面的示例中，我们隐藏了大部分内容，因为它变得很长）。在代码中，棋盘的每个位置都是 Tileset.NOTHING 或 Tileset.CELL。在将棋盘状态保存到文本文件时，我们约定0 代表 Tileset.NOTHING，1 代表 Tileset.CELL。

这是一个相对较大的文件，所以让我们看一个来自提供的测试的较小示例。 例如，如果棋盘状态如下，

TETile[][] result = new TETile[][] {
        {Tileset.NOTHING, Tileset.CELL, Tileset.NOTHING},
        {Tileset.NOTHING, Tileset.CELL, Tileset.CELL},
        {Tileset.CELL, Tileset.NOTHING, Tileset.NOTHING},
        {Tileset.NOTHING, Tileset.CELL, Tileset.NOTHING}
};

它在文本文件中会保存成下面这样:

3 4
010
011
100
010

需要注意的是，我们改变了棋盘的坐标系，将左下角设为 (0, 0)。 最初，result 二维数组会以左上角为 (0, 0) 的方式读取，但我们已经通过转置和翻转处理了这种差异。您无需关心具体的实现方式，只需记住以左下角为 (0, 0) 的坐标系进行操作即可。

danger

再次强调，在本次实验的任何环节，您都无需进行棋盘的转置或翻转操作。

还有三项额外要求：

• 请务必保证文本文件中的棋盘方向与程序中的棋盘方向一致，即棋盘的右上角对应于文本文件中保存的右上角，如上例所示。请思考这样做的意义。 如果 (0, 0) 代表棋盘的左下角，而我们从上到下写入数据，会发生什么情况？

• 请在写入文本文件的每一行末尾添加换行符 \n，包括文件顶部的尺寸信息（虽然框架代码已经包含了这部分）。 这样做是为了确保文本文件中棋盘信息的准确性，并且对后续的 loadBoard 方法有所帮助。

• 您保存到的文本文件的名称必须称为 src/save.txt。我们已经将其作为变量提供，因此请勿删除它。

在骨架中，我们提供了 TODO 注释。您可以通过实例变量 currentState 来获取棋盘的当前状态。

实现方法 saveBoard。

loadBoard

现在，我们想要从给定的文件加载，而不是保存。加载时，您可以假设格式与前面 saveBoard 部分中提到的格式相同。也就是说，第一行是尺寸，其余行是棋盘。我们想要将此信息加载到 TETile[][] 中并返回它。

根据 saveBoard 中所述的要求，您可以假定文本文件中的每一行都以换行符 \n 分隔，并且棋盘方向正确，即左下角为 (0, 0)。（请注意，如果您的 saveBoard 方法没有遵循指定的格式，可能会影响 loadBoard 方法的正确性。） 在此过程中，您可能会发现 String 类的 split 和 charAt 方法很有用。

实现方法 loadBoard。由于我们要加载游戏，请确保初始化实例变量 width 和 height。

测试和运行游戏

我们提供了一些本地测试来帮助您验证代码的实现。 通过所有本地测试并不意味着您一定能在自动评测机上获得满分。

danger

我们在 patterns 目录下提供了一些文件，它们代表了您可以使用的初始状态。请务必不要修改这些文件！ 这些文件会被本地测试所使用，并且测试程序期望它们保持原始状态。 本地测试会检查这些文件是否被修改，如果文件内容发生改变，测试将无法正常运行。 同样，也请不要修改其他的测试文本文件（例如 patterns 目录下的文件）。

要运行游戏，可以通过执行 GameOfLife.java 文件中的 main 方法。 如果没有提供初始状态（即文本文件），程序会使用随机种子生成一个随机的初始状态。如果您想使用提供的初始状态运行游戏（或者创建您自己的初始状态！），请点击“运行”菜单，选择“编辑配置”。转到“应用程序”-->“GameOfLife”。如果它不在那里，请单击左上角的“+”并选择“应用程序”。在“主类”一栏，输入“GameOfLife”并选择出现的选项。对于您的程序参数，您需要指定文件路径，并加上“-l”这个参数。例如，如果您想使用“hammerhead.txt”作为初始状态，您需要在程序参数中输入以下内容：

-l patterns/hammerhead.txt

然后，继续运行该应用程序。

danger

如果您正在编写自己的测试用例，请务必使用方形矩阵，特别是如果您正在使用 nextGeneration 方法。提供的本地测试和自动评分器上的测试仍然可以正常运行。但是，针对nextGeneration编写的本地测试，建议使用 n x n 的方形棋盘。

项目 3 保存和加载

完成 saveBoard 和 loadBoard 后，请注意我们最终将整个棋盘保存到文件中（即每个 Tileset，我们用 0 和 1 表示它们），以及棋盘的高度和宽度。您认为这是在项目 3 中采取的最佳方法吗？

将整个棋盘迭代并保存到文本文件中，这种做法略显复杂，可能并非运行时效率最高的方案，而且在项目 3 中也未必是必要的！考虑一下保存和加载的目标是什么。我们希望确保能够加载回我们保存的世界，使其在某种程度上持续存在，即使在程序结束后也是如此。从用户角度来看，他们无需了解其内部机制（例如，他们是否能在保存的文本文件中看到整个棋盘的表示并不重要）。与其尝试将整个世界保存到文本文件中，不如将重点放在如何利用特定信息重建世界上，从而使用户感觉他们保存的世界能够以离开时的状态完全恢复。

info

您现在不必完全清楚项目 3 中保存和加载的具体方法，但现在是开始思考其设计思路的好时机。重要的是要知道您将依赖于某种伪随机生成器——虽然是随机的，但如果为生成器提供种子，则存在确定性的一面。

重申一下之前关于 `Random` 和伪随机生成器的观点：这一点在项目 3 中**_尤其重要_**，因为它能提供确定性的随机性：您的世界看起来完全随机，但您可以一致地重新创建它们以进行调试（和评分）。

提交

总结一下，您需要完成以下三个方法：

• nextGeneration
• saveBoard
• loadBoard

在提交之前，请确保您已通过所有提供的本地测试。自动评分器将测试您的加载和保存功能。

您在 Gradescope 上收到的分数是您的最终分数。