一起来做个生命游戏吧（一）：跑、跑起来了！
本帖最后由 dolly_yos2 于 2023-5-25 17:00 编辑一起来做个生命游戏吧（一）：跑、跑起来了！
注意事项
[*]游戏制作方面的新手
[*]自以为是的态度
[*]糟糕的 C++ 水平
[*]奇怪的措辞
[*]低下的表达能力
[*]水平奇差却执意使用的英语注释
[*]毫不犹豫的使用很新的语言特性和标准库功能
[*]几乎总是英语的参考资料
[*]已经写完了我再回来补上一条：冗长
以上这些都能接受的话还敬请继续阅读
缘起
最近看到了这样的一篇文章，用 Pygame 实现的生命游戏。再向前追溯，还有略早一些的用 Scratch 做五子棋。就像是和这份挑战书的作者的观察一样，我也对“Python,C++ 都很难做出来对吧？”的论断颇为质疑，于是产生了也动手编写一个生命游戏的想法：使用 C++，用简单的库和框架，自己动手实现更多的细节。
当然，读者可能会质疑，别人的论断是用 C++ 做五子棋很难完成，为什么动手做的是生命游戏呢？从本质上讲，这两者之间没有决定性的区别，其实现在难度上是相似的，甚至当实现其中的一个之后，将其修改为另一个同样应当是相对简单的。然而相比五子棋，果然还是看一个个细胞相互影响，诞生存活或是消亡，从简单的规则衍生出千变万化的形状更有趣一些吧，怀着这样的心情选择了这个主题。现在想来，正好我手上有一个之前实现的基于蒙特卡洛树搜索的五子棋后端，为它实现一个前端做一个带 AI 的五子棋游戏可能实际上也很有趣呢，也许会在将来吧。
虽然不免参考用 Pygame 实现的生命游戏这篇帖子，我却将这篇分类为技术交流而不是作品展示，因为我所做的远称不上值得展示的作品。更重要的是，就像标题和项目名称所意指的，我希望将预期的完整程序拆分成若干功能部分，不断向其中添加功能并为每一组添加的功能编写帖子来介绍我的设计和思路以及背后的一些细节，像这样将整个游戏逐渐完成和完善。换言之，我希望在帖子中不仅展示我所编写的内容，还展示不同功能向其中添加的顺序和在其内部的考量，我的理解和设计权衡等等，希望能和各位朋友进行交流。
本节目标：跑起来就算成功
作为第一节，也是我的第一个勉强算得上是游戏的程序，甚至是第一个有图形界面的程序，只要定一个小小的目标就好了：能跑。
具体的，让写出来的程序能自动的运行，按照规则不断更新状态呈现就好了，不必设置任何按钮、交互之类的功能。当然，为了方便，还是简单的设置一个退出键吧。
基础：游戏程序的模型
从表现形式上考虑，所谓的游戏或者说计算机图形实际上可以视为是一种图片呈现的模式。换言之，对于外部而言，游戏程序就是一个接收某些输入，同时不断绘制图像并将图像进行呈现的程序。而当我们深入到游戏程序的内部进行考量的时候，这也就是在实现一个游戏程序时所需要做的，我们需要考量如何有效的表示这些状态，如何与外部进行互动，最终如何将这些状态绘制在一张用于呈现的图像上。
对于这里实现的生命游戏，由于交互格外简单，我们可以进一步将游戏程序的主要部分表示成这样：while(not_exit){
draw_current_state();// 将当前状态绘制出来
show_image(); // 展示当前绘制的内容
update_state(); // 更新状态
sleep(...); // 等待一段时间（控制帧率）
}
其中状态的表示和处理部分我个人称之为后端，而绘制显示和（在这里尚没有的）输入获取部分我个人将其称为前端。接下来我们就将整个程序拆解为前端和后端两个部分，分别来进行分析和实现。
后端部分：有什么区别呢
当剥离了图形化显示等内容，单独来考虑后端部分，毫无疑问我们要问出这样一个问题：这和我们熟悉的 C++ 程序编写又有什么区别呢？我的看法是：没有。如果我们要表示一个生命游戏的棋盘，我们应该如何去做？想法其实很简单，用一个数组来保存每一个格子的生死状态，再记录总行列数，这就是一个完整的棋盘了，就像是这样：struct Board{
int width;
int height;
std::vector<bool> grid; // 既然长和宽是可以动态配置的，就用动态数组来记录状态吧
};
我们约定 0 表示该位置上的细胞死亡，1 表示存活。在完成了棋盘的表示之后，下一个问题就是如何对棋盘进行状态的更新。对于每一个格子，其下一状态取决于它的当前状态和八个邻居的状态，需要计数这八个格子中存活的数目。这一操作是相当简单的，然而需要注意，我们并不能简单的在计算之后直接修改当前格子的状态，而应当等所有位置上的新状态都计算完毕之后再一同更新到新的状态上，这就需要一个临时的存储空间。我们不妨在内部设计两组格子，一组为当前状态，另一组为下一状态，每次更新从当前状态里进行统计，将结果写进下一状态，待所有位置都填好后再交换当前和下一状态。于是我们将表示修改为struct Board{
int width;
int height;
std::array<std::vector<bool>, 2> grids; // 两组格子
std::vector<bool>* front; // 当前状态，指向两组格子中的一组
std::vector<bool>* back; // 下一状态，指向另一组
};
我们又注意到，在处理边界上的格子，需要避免对不存在的格子进行访问，也就是避免越界。由于我们不关心周围有多少死去的细胞，只关心活着的数量，不妨设置一个专门的小函数来帮助我们处理边界检查问题：inline bool get_cell(
const std::vector<bool> *grids,
const int width, const int height,
int i, int j
) {
if (i >= height || j >= width || i < 0 || j < 0) {
return 0; // 只要越界就返回 0
}
return (*grids);
}
利用这个函数就可以很容易的完成统计和更新操作了。然而我们并不满意：我们注意到更新细胞的数量是较多的，而每一个细胞的更新都是独立的，即其下一状态的计算操作过程中对当前状态的访问总是只读的，只会修改下一状态中当前细胞对应位置上的值，不存在任何竞争问题，这通常意味着可以使用无锁多线程进行加速处理。可以让一个主线程做控制操作，而启动一些工作线程共同完成每一轮的更新操作，充分利用硬件性能，避免“一核有难多核围观”。
在更新过程中，显然只存在一个需要同步的地方，也就是主线程需要等待所有工作线程完成当前轮次的更新才能够继续进行后续的操作。我们使用屏障来实现这一效果。屏障具有这样的同步语义：预先确定数量的一组线程可以在到达并在屏障处等待，当到达屏障的线程数达到预先设定的这一数量时，正在等待的所有线程才可以越过屏障继续前进，就像是一个检查点一样。每次更新时，创建 N 个工作线程，这些工作线程各自完成棋盘上连续的若干行的更新工作，随后在屏障处等待。主线程完成创建和任务安排后同样在屏障处等待，则屏障可以保证当主线程继续执行时，当前轮次的更新已经完成。于是工作线程可以写为static void update_worker(
const int index,
const int width, // width of grid
const int height, // height of grid
std::vector<bool> *front_grids, // the front grid, or current state
std::vector<bool> *back_grids, // the back grid, or next state to be calculated
std::barrier<> &worker_execute_barrier // barrier for syncing
) {
// calculate number of lanes this thread shall take case of in this iteration
// std::thread::hardware_concurrency() 是推测的硬件支持的并行数量，期望创建与此数量相同的线程能够达到较好的效率
const int lines = (height + std::thread::hardware_concurrency()) / std::thread::hardware_concurrency();
// convert it to a range of rows, [low, high)
const int low = index * lines;
const int high = std::min(low + lines, height);
// for each cell on each row that we take care of
for (int i = low; i < high; i++) {
for (int j = 0; j < width; j++) {
uint8_t total = 0;
for (int i_offset = -1; i_offset <= 1; i_offset++) {
for (int j_offset = -1; j_offset <= 1; j_offset++) {
if (i_offset == 0 && j_offset == 0) {
// we do not count the cell itself
continue;
}
// count the number of cells alive with the helping function
total += get_cell(front_grids, width, height, i + i_offset, j + j_offset);
}
}
// simply apply the rule and write next state of this cell to the back grid
if ((*front_grids) == 0) {
if (total == 3) {
(*back_grids) = 1;
} else {
(*back_grids) = 0;
}
} else {
if (total == 2 || total == 3) {
(*back_grids) = 1;
} else {
(*back_grids) = 0;
}
}
}
}
// done for this iteration, sync at the barrier again
//all threads, including the main thread shall sync here, and when this call returns, all working
//threads has done for this iteration
worker_execute_barrier.arrive_and_wait();
}
进一步考虑，这一方式似乎又有不妥。尽管线程相对轻量级，但每秒之内我们可能需要尝试更新数十甚至数百次，这样高强度的创建和销毁线程势必带来一定的额外开销。我们是否可以让线程一直运行从而避免反复创建和销毁？答案自然是肯定的。只要在函数最外层添加一层无限循环，就可以让工作线程一直运行更新流程而不退出。然而，如果工作线程无条件的不停运算，一方面是对资源的浪费，另一方面可能会由于数据访问竞争而损坏内部状态。重新考虑不难发现，只要再设置一个同步点就能解决问题：工作线程开始更新之前首先先进行一次同步，这就相当于是等待主线程给出一个“可以开始计算了”的信号再计算，那么当不需要计算的时候工作线程就可以乖乖的在这个屏障处等待了。我们将实现进一步修改成这样：static void update_worker(
const int index, // index of this worker, which is used to calculate the range of rows to take care of
// for the size of board, we use references since it may change after working threads are created
const int &width, // width of grid
const int &height, // height of grid
std::vector<bool> *&front_grids, // the front grid, or current state
std::vector<bool> *&back_grids, // the back grid, or next state to be calculated
std::barrier<> &worker_execute_barrier // barrier for syncing
) {
// keep threads running with a infinite loop
while (true) {
// sync at the barrier. When this call returns, all working threads are ready for calculation and the
// main thread has issued clearance to such calculation
worker_execute_barrier.arrive_and_wait();
// calculate number of lanes this thread shall take case of in this iteration
//since the size of board may change, we need to recalculate this for each iteration
const int lines = (height + std::thread::hardware_concurrency()) / std::thread::hardware_concurrency();
// convert it to a range of rows, [low, high)
const int low = index * lines;
const int high = std::min(low + lines, height);
// for each cell on each row that we take care of
for (int i = low; i < high; i++) {
for (int j = 0; j < width; j++) {
uint8_t total = 0;
for (int i_offset = -1; i_offset <= 1; i_offset++) {
for (int j_offset = -1; j_offset <= 1; j_offset++) {
if (i_offset == 0 && j_offset == 0) {
// we do not count the cell itself
continue;
}
// count the number of cells alive with the helping function
total += get_cell(front_grids, width, height, i + i_offset, j + j_offset);
}
}
// simply apply the rule and write next state of this cell to the back grid
if ((*front_grids) == 0) {
if (total == 3) {
(*back_grids) = 1;
} else {
(*back_grids) = 0;
}
} else {
if (total == 2 || total == 3) {
(*back_grids) = 1;
} else {
(*back_grids) = 0;
}
}
}
}
// done for this iteration, sync at the barrier again
//all threads, including the main thread shall sync here, and when this call returns, all working
//threads has done for this iteration
worker_execute_barrier.arrive_and_wait();
}
}
至此，工作线程的实现完成，主线程中的更新操作也就非常简单了：// update state, calculate next state of front grid and save to back grid
void update() {
// trigger all working threads for calculation
worker_execute_barrier.arrive_and_wait();
// wait for the calculation
worker_execute_barrier.arrive_and_wait();
// swap front and back grid
std::swap(back_grids, front_grids);
}
后端的部分到此为止宣告完成。
前端部分：总之就是安排每一个像素的颜色
框架选择
图形界面的框架很多，而我选择了 SDL。相比 Qt 等框架，SDL 同样跨平台且提供明显更底层的访问接口，我们可以更深入到内部细节中去并获得更大的控制能力。当然，也许会问既然如此为什么不选用 Vulkan 之类的更底层的方式来处理图形呢？答案当然是太硬核了顶不住了啦。
SDL 是一个轻量级的框架，由于其在不同平台上进行安装和使用的方式存在较多出入，我们不会在这里讨论其安装方式，请自行参考官方文档。
整体结构
就像先前所说的，对于这一简单的任务，使用一个简单的主循环就可以解决了。整体的框架即为首先初始化 SDL，随后创建窗口和向窗口进行绘制的渲染器，初始化棋盘，之后陷入主循环开始重复绘制、展示、更新、等待的操作。主函数部分的代码表示如下：int main() {
// initialize SDL
SDL_Init(SDL_INIT_VIDEO | SDL_INIT_EVENTS);
// create a window
auto window = SDL_CreateWindow(
"Game of Life", // title of window
SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, // do not specify the initial position of window
InitialWindowWidth, InitialWindowHeight, // initial size of window
// this window shall be shown, backed by Vulkan, with HighDPI support and resizable
SDL_WINDOW_SHOWN | SDL_WINDOW_VULKAN | SDL_WINDOW_ALLOW_HIGHDPI | SDL_WINDOW_RESIZABLE
);
// create a renderer for the window we just created
auto renderer = SDL_CreateRenderer(
window, // the window
-1, // any rendering driver SDL sees suitable
SDL_RENDERER_ACCELERATED // try to request for hardware accelerate
);
// initialize the board
Board board(BoardWidth, BoardHeight);
SDL_Event event;
bool running = true;
while (running) { // main loop
while (SDL_PollEvent(&event) == 1) { // 额外的事件处理部分：当发现 Q 键被按下时终止循环，进入退出流程
if (event.type == SDL_KEYDOWN) {
if (event.key.keysym.sym == SDLK_q) {
running = false; // stop running is Q is pressed
break;
}
}
}
// set background to some color
SDL_SetRenderDrawColor(renderer, 87, 124, 138, SDL_ALPHA_OPAQUE);
// clear the window with this color by renderer
SDL_RenderClear(renderer);
// draw the board
board.draw(renderer);
// show what we have drawn on the window with the renderer
//the result of render will not show up without this call
SDL_RenderPresent(renderer);
// update border to next state
board.update();
using namespace std::chrono_literals;
// sleep for a while, a naive way to control FPS
std::this_thread::sleep_for(34ms);
}
// do some cleanup
SDL_DestroyRenderer(renderer);
SDL_DestroyWindow(window);
SDL_Quit();
return 0;
}
从代码里可以清晰的看到上述的主循环结构。至此，剩余的问题就是如何将棋盘绘制出来。
绘制棋盘
SDL 提供的接口相当简单，我们需要手动控制其上所有细节的绘制安排，也就是标题所说的，不过是安排每一个像素的颜色罢了。
为了表示网格，我们需要绘制网格线，而每一个格子内部使用填充的色彩表示生死状态。简单起见，用黑色表示死，白色表示生。美观起见，我们在窗体边框到内容之间设置了内间距，同时用于标注棋盘格子的网格线到内部具体表示网格细胞生死的色彩填充之间也设置了间距，且网格线本身亦需要占据一定的宽度，因此为让网格看起来符合直觉，需要计算相关的坐标位置。
首先计算去除窗口填充后剩余的空间大小，再减去边框和内填充占用的总空间，剩余的空间需要均分给所有格子。通常而言，格子是正方形的，不同方向均分得到的长度可能不一样，因此需要选择其边长，这一选择也是非常简单的：选择在另一个方向上不会出现超出可用空间的长度作为边长。
有了所有的尺寸信息之后，就可以安心的把所有内容都作为矩形绘制出来了，只要注意起始坐标和步进方向、长度就好了。因为所有绘制安排都需要我们自行设置起止位置，就需要对坐标、位置占用情况心中有数，画一幅示意图对照编写可能会轻松一些。详细实现就参见完整实现吧。
本节的完整实现
本节的完整实现可以在 Codeberg 访问到，仓库为 https://codeberg.org/jonabom881/pGoL。Codeberg 是一个类似 GitHub 的平台，因此推荐通过克隆仓库的方式进行访问以便之后获取更新。但愿这个系列能够继续直到完结。
这一节所使用到的代码用标签标记为 c1，可以 checkout 到上面进行查看。相比文中给出的代码，最终实现有所区别：Board 被设计成了一个类，一些相关的信息存储为其成员，并加入了默认的随机初始化。同时也能注意到一些类型的设置发生了变化，最大的区别可能是网格中的每一个元素的状态从 bool 变成了 uint8_t，我们专门在注释中对此提出了一个问题，回答就留给读者或者之后吧。
与这些变动对应，参数类型等也就需要在各个方法中进行调整，这也就是为何不复制和粘贴绘图部分代码的原因：事实上，尽管整体结构不变，实际完整实现中的代码和本文中的代码在类型上还是有着不少的区别的。
由于规模较小，单文件组织就已经足够了，编译也简单，只要额外链接 SDL。运行起来就能看到细胞们啦（按 Q 退出哦）！
https://i.pixl.li/GoL0d6b9af6e4cc509a2.png
至于以后，还有什么值得添加的功能吗？
跑起来了！但是似乎只是跑起来了而已！之后再慢慢的加上这些吧（大概？）！
[*]暂停和继续
[*]单步进行
[*]控制自动进行速度
[*]保存和加载
[*]点击修改细胞状态
[*]（……）
加油，给你评分啦~祝愿早日精华! 歌者文明清理员 发表于 2023-5-25 17:00
加油，给你评分啦~祝愿早日精华!
好快！我还在调图像尺寸的问题呢就已经看到了！ dolly_yos2 发表于 2023-5-25 17:02
好快！我还在调图像尺寸的问题呢就已经看到了！
刚放学{:10_333:} 要不试试在这个图灵完备的系统里面搞个计算机{:10_256:} 膜拜大佬 厉害！写的好详细，如果能完整实现应该会很棒！ 太棒了{:10_257:}
但是我认为生命游戏C++完全可以制作成一个输出程序，用不着图形{:10_256:}
还有一个，C++如何编写图形化游戏呢？是需要下载什么吗？{:10_291:} 大佬厉害！ 歌者文明清理员 发表于 2023-5-25 17:00
加油，给你评分啦~祝愿早日精华!
膜拜大佬 本帖最后由 歌者文明清理员 于 2023-5-26 19:11 编辑
元豪 发表于 2023-5-25 18:38
太棒了
但是我认为生命游戏C++完全可以制作成一个输出程序，用不着图形
easyx 歌者文明清理员 发表于 2023-5-25 19:33
easyx
404了 元豪 发表于 2023-5-25 19:40
404了
手动在浏览器中输入easyx.cn 元豪 发表于 2023-5-25 18:38
太棒了
但是我认为生命游戏C++完全可以制作成一个输出程序，用不着图形
把前端换掉就很轻松的变成字符/控制台输出的程序了。如果不考虑结构化的话，简单的修改主函数（去掉 SDL）、重写 draw 方法就好了
这个程序使用的是 SDL，实现像这样的微型游戏还是不会有问题的，但因为较为底层所以如果需要使用高级功能基本要自己实现，比如碰撞检测、精灵动画、场景管理之类，如果要做比较大体量的游戏的话还是建议看看常见的游戏开发框架吧 元豪 发表于 2023-5-25 19:40
404了
www.easyx.cn 我想起了童晶老师
页:
[1]