康韦的C ++生活游戏

#include <iostream>
#include <cstdlib>


const int gridsize = 75; //Making this a global constant to avoid array issues.

void Display(bool grid[gridsize+1][gridsize+1]){
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            if(grid[a][b] == true){
                std::cout << " *";
            }
            else{
                std::cout << "  ";
            }
            if(b == gridsize-1){
                std::cout << std::endl;
            }
        }
    }
}
//This copy's the grid for comparision purposes.
void CopyGrid (bool grid[gridsize+1][gridsize+1],bool grid2[gridsize+1][gridsize+1]){
    for(int a =0; a < gridsize; a++){
        for(int b = 0; b < gridsize; b++){grid2[a][b] = grid[a][b];}
    }
}
//Calculates Life or Death
void liveOrDie(bool grid[gridsize+1][gridsize+1]){
    bool grid2[gridsize+1][gridsize+1] = {};
    CopyGrid(grid, grid2);
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            int life = 0;
        for(int c = -1; c < 2; c++){
            for(int d = -1; d < 2; d++){
                if(!(c == 0 && d == 0)){
                    if(grid2[a+c][b+d]) {++life;}
                }
            }
        }
            if(life < 2) {grid[a][b] = false;}
            else if(life == 3){grid[a][b] = true;}
            else if(life > 3){grid[a][b] = false;}
        }
    }
}

int main(){

    //const int gridsize = 50;
    bool grid[gridsize+1][gridsize+1] = {};

    //Still have to manually enter the starting cells.
    grid[gridsize/2][gridsize/2] = true;
    grid[gridsize/2-1][gridsize/2] = true;
    grid[gridsize/2][gridsize/2+1] = true;
    grid[gridsize/2][gridsize/2-1] = true;
    grid[gridsize/2+1][gridsize/2+1] = true;

    while (true){
        //The following copies our grid.

        Display(grid);     //This is our display.
        liveOrDie(grid); //calculate if it lives or dies.
        system("CLS");
    }
}

#1 楼

有两个主要建议：首先，让我们尝试利用Conway的《人生游戏》的本质和C ++处理指针的方式来加速一切。当您评估Conway的人生游戏时，这是一个分为两个部分的过程。首先，您将所有条目复制到一个新数组中，然后参考该新数组进行计算，然后更新原始数组。此过程需要\ $ O \ left（n ^ {2} \ right）\ $，并涉及一个主要的内存副本；对于应该没问题的小尺寸，在大尺寸情况下，内存副本带来的成本将变得微不足道，因此让我们重新设计一下：

Conway的生命游戏本身就是单元自动机的应用，其中在时间t的网格状态G是在时间t-1的状态的函数。更具体地说，它将是这样的形式：G(t)=R(G(t-1))其中R()是确定哪些细胞存活以及哪些细胞死亡的一些规则函数。这种直接的依赖关系为我们提供了一个解决内存复制难题的有趣解决方案-如果我们存储两个网格，一个网格代表G(t)，另一个网格代表G(t-1)，该怎么办？然后，我们可以阅读G(t-1)，应用我们的规则并更新G(t)。但是，这使我们回到了第一个问题-然后如何更新G(t-1)？我们只复制G(t)的内存吗？ C ++实际上为我们提供了一种更方便的方法，我们可以改为交换指针：因为如果我们简单地交换两个数组的指针，则q（43）充分描述了G（t），因此G(t-1)的指针引用了G(t-1)的内存区域，并且G(t)引用了G(t)的内存区域，那么我们可以应用更新规则，将G(t-1)更新为G(t)，覆盖用于存储G(t+1)的旧内存，这可以避免我们需要复制网格，这将大大加快网格的速度。根据我的经验在n> 500的情况下进行仿真。

第二条评论是关于代码抽象的，整个细胞自动机是探索这一点的好地方，因为它是一个如此广泛的领域。不必使您的Conway的“生活游戏”代码正常工作，但是如果您想测试有趣的变体，那么它将变得更加容易。现在，您具有一个表示为单个函数G(t-1)的更新规则R()，但是可以将其重构为几个较小的任务，这具有使系统更具模块化和易于调整的优点。那么我们如何才能将这个规则分解为更小的，更多的模块化组件？让我们首先列出由update函数执行的实际过程：


遍历所有单元并更新它们
要更新单元，请查找它的邻居（在康威（Conway）的《生命游戏》中，我们使用摩尔邻里）
看一下一个细胞邻居，并决定它会生存还是死亡（将规则应用于细胞）
根据细胞规则更新细胞的内容

此任务列表使自己可以定义三个单独的功能



liveOrDie，它们将自行执行更新

void update(G(t),G(t-1))，它将返回在int neighbors(G,x,y)处索引的单元格的邻居数。 ，无论是活着的还是死的）

基本轮廓可以是这样的：

更改规则或邻居的功能oo，例如，应用周期性边界，您可以轻松地仅更改与该代码部分相关的定义。希望对您有帮助。

#2 楼

重要的一件事：不要将C数组传递给函数，因为它们会衰减到指针。在C ++中，您应该只使用存储容器（来自标准库或Boost）而不是C数组。 ，更适合将存储数据传递给函数（它们不会衰减到指针）。

您可以考虑std::vector s的二维bool： />
但是，考虑到它的某些问题，您可能必须考虑替代方法，例如std::vector的int。如果您不想冒险，可以选择带有int的那个。

如果不需要调整大小，则另一个选择是std::array（仅C ++ 11）：

std::vector<std::vector<bool> > grid;

对于您选择的任何一个，您都可以使用typedef，这样您就不必在任何地方键入整个语句：

std::array<std::array<bool, gridsize+1>, gridsize+1> grid;

typedef std::vector<std::vector<bool> > Grid;

声明将非常简短：

typedef std::array<std::array<bool, gridsize+1>, gridsize+1> Grid;

其他：


使您的函数命名保持一致。一个以小写字母开头，另两个以大写字母开头。选择您喜欢使用或需要使用的命名约定。
对"\n"优先使用std::endl，以换行。后者也会进行刷新，这会花费更长的时间。 br />
注释掉的代码很丑陋，尤其是在将代码作为最终产品展示时。函数名称已经传达了其目的。但是，如果要记录每个函数，则使其比这更正式，并提及其参数和返回值（如有）。

Grid grid;

考虑对您的评论进行校对，否则可能会使程序显得草率。

#3 楼

const int gridsize = 75; //Making this a global constant to avoid array issues.

习惯将所有大写字母用作全局常量，例如：

const int GRIDSIZE = 75;

现在它看起来像一个全局常量，则可以删除它变得毫无意义的注释。


代替：

if(grid[a][b] == true){

您可以简单地编写以下内容： ：

if (grid[a][b]) {

这种方法会更加自然和简单：

您应该使用一致的样式来命名您的方法。所有方法都应以大写字母开头，或者都不使用大写字母。我个人更喜欢使用小写和下划线命名，例如Display，live_or_die。


最好多注意编码样式：正确缩进，而不是：

if(b == gridsize-1){
    std::cout << std::endl;
}

这样写：

for (int a = 1; a < gridsize; a++) {
    for (int b = 1; b < gridsize; b++) {
        if (grid[a][b]) {
            std::cout << " *";
        } else {
            std::cout << "  ";
        }
    }
    std::cout << std::endl;
}

仅适用于Windows：

if(grid2[a+c][b+d]) {++life;}

这将在类似UNIX的系统中工作：最好以独立于平台的方式重写它。

#4 楼

如果要使用C ++进行操作，则最好使用一个类。例如，如果grid是一个类的数据成员，而各个函数是同一类的方法，则您无需将网格作为参数传递给各个函数方法。

a和b并不是不好的变量名，但是i和j会更常规地用作循环索引。或者您可以使用row和col。相当一致：您对liveOrDie使用camelCase，对for使用PascalCase。

据我所知，通过复制网格可以正确地实现规则。 >关于如何改进它的任何想法？


您可以：


进行更多测试
让用户选择起始单元格
使其在GUI中显示
使其更快
使其可变大小（或几乎无限大小）的网格

#5 楼

关于如何进行改进的任何想法？


我能想到的最大改进就是避免存储和处理整个网格。尽管有例外，但通常Conway的生活模式中有很多空白。目前，您的程序在此空白空间上花费大量时间和内存。

我建议仅存储活动单元，并据此计算下一代活动单元。例如，您可以使用无序集合（访问时间为O（1）），只考虑集合中或相邻单元格中的那些单元格。在这一代中，没有其他单元可以存活，因此您无需考虑它们。

对于大型模式，您会发现这种方法在时间和空间要求上都非常有效，而且您无需预先指定网格大小，这对于尚不知道其增长方式的新模式很有用。

#6 楼

这不是一个大问题，但是我要做的一件事是在顶部定义名为ALIVE和DEAD的宏，以便可以使用这些关键字而不是true和false。对我来说，这会使代码更清晰。

#define ALIVE true
#define DEAD false

在liveOrDie函数中，我还将变量名称life更改为更具描述性的neighbors或parents。

//Calculates Life or Death
void liveOrDie(bool grid[gridsize+1][gridsize+1]){
    bool grid2[gridsize+1][gridsize+1] = {};
    CopyGrid(grid, grid2);
    for(int a = 1; a < gridsize; a++){
        for(int b = 1; b < gridsize; b++){
            int neighbors = 0;
            for(int c = -1; c < 2; c++){
                for(int d = -1; d < 2; d++){
                    if(!(c == 0 && d == 0)){
                        if(grid2[a+c][b+d]) {++neighbors;}
                    }
                }
            }
            if(neighbors < 2) {grid[a][b] = DEAD;}
            else if(neighbors == 3) {grid[a][b] = ALIVE;}
            else if(neighbors > 3) {grid[a][b] = DEAD;}
        }
    }
}

#7 楼

@Koradalien和其他人已经捕获了整体结构的关键点，但是我要添加一些可能也有用的局部更改。 [我已经留在缓冲区复制等中。]
本质上：您可以将一堆条件语句更改为表查找，并通过将其移至外部循环来完全删除Display中的行末检查。 br />
对于Display：

void Display(bool grid[gridsize + 1][gridsize + 1])
{
    const char* cellImage[2] = { "  ", " *" };
    for (int a = 1; a < gridsize; a++)
    {
        for (int b = 1; b < gridsize; b++)
        {
            std::cout << cellImage[grid[a][b]];
        }
        std::cout << std::endl;
    }
}

类似地，在活着的时候，（或在rule中）：

int count[2][3][3] =
{
    {
        { 0, 0, 0 },
        { 0, 0, 0 },
        { 0, 0, 0 }
    },
    {
        { 1, 1, 1 },
        { 1, 0, 1 },
        { 1, 1, 1 },
    }
};
bool lives[9] = { 0, 0, 0, 1 }; // zero fills the rest.
//Calculates Life or Death
void liveOrDie(bool grid[gridsize + 1][gridsize + 1])
{
    bool grid2[gridsize + 1][gridsize + 1] = {};
    CopyGrid(grid, grid2);
    for (int a = 1; a < gridsize; a++)
    {
        for (int b = 1; b < gridsize; b++)
        {
            int life = 0;
            for (int c = -1; c < 2; c++)
            {
                for (int d = -1; d < 2; d++)
                {
                    life += count[grid2[a + c][b + d]][c + 1][d + 1];
                }
            }
            if (life != 2)
                grid[a][b] = lives[life];
        }
    }
}

好的，有人会说lives数组是过大的，但是我在这里展示了该技术。
请注意如何修改count数组以获得一些简单的规则更改。

PS具有网格数据的完整标记具有边界内建以简化规则。

关于不相关问题的另一种想法。 system("CLR");可能会引起闪烁。对于控制台应用程序，最好将光标发送到首页。查看现有问题

这给出：

void gotoxy(int x, int y) 
{
    COORD pos = { x, y };
    HANDLE output = GetStdHandle(STD_OUTPUT_HANDLE);
    SetConsoleCursorPosition(output, pos);
}

void cursorHome()
{
    gotoxy(0, 0);
}