马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 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; // 既然长和宽是可以动态配置的，就用动态数组来记录状态吧
};
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)[i * width + j];
}
在更新过程中，显然只存在一个需要同步的地方，也就是主线程需要等待所有工作线程完成当前轮次的更新才能够继续进行后续的操作。我们使用屏障来实现这一效果。屏障具有这样的同步语义：预先确定数量的一组线程可以在到达并在屏障处等待，当到达屏障的线程数达到预先设定的这一数量时，正在等待的所有线程才可以越过屏障继续前进，就像是一个检查点一样。每次更新时，创建 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)[i * width + j] == 0) {
if (total == 3) {
(*back_grids)[i * width + j] = 1;
} else {
(*back_grids)[i * width + j] = 0;
}
} else {
if (total == 2 || total == 3) {
(*back_grids)[i * width + j] = 1;
} else {
(*back_grids)[i * width + j] = 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)[i * width + j] == 0) {
if (total == 3) {
(*back_grids)[i * width + j] = 1;
} else {
(*back_grids)[i * width + j] = 0;
}
} else {
if (total == 2 || total == 3) {
(*back_grids)[i * width + j] = 1;
} else {
(*back_grids)[i * width + j] = 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 退出哦）！
至于以后，还有什么值得添加的功能吗？
跑起来了！但是似乎只是跑起来了而已！之后再慢慢的加上这些吧（大概？）！
- 暂停和继续
- 单步进行
- 控制自动进行速度
- 保存和加载
- 点击修改细胞状态
- （……）
| 
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2023-5-25 16:58:33
置顶卡
千斤顶
显身卡
发表于 2023-5-25 17:00:37
楼主
发表于 2023-5-25 18:29:04
