C++ 控制台 Conway 的生命游戏更新非常缓慢

Question

我目前正在使用 C++ 开发 Conway 的 Game of Life 的控制台版本。

Repo Link

问题是我的 Draw() 方法没有尽可能快地绘制下一代。

我记得在某处读到过，与获取控制台缓冲区相比，使用 GotoXY 相当慢。

问题是我完全不知道如何实现控制台缓冲区来处理我的代码。

我不是要求你们这样做，但我只是想让你们看看我的 Draw() 和 Update() 方法，看看我是否在做一些可怕的内存占用。

我的代码可能不是最好的，因为我对 C++ 仍然“相当陌生”，所以在批评之前请记住这一点。 :')

细胞结构

struct Cell
{
int x, y; // Cell X, Y coordiantes
bool IsAlive; // Cell life state

string ToString()
{
    return "X: " + to_string(x) + "\tY" + to_string(y) + "\tAlive State: " + to_string(IsAlive);
}

void Die()
{
    IsAlive = false;
}

void Resurrect()
{
    IsAlive = true;
}
};

更新

void Update()
{
// Update Cells
CalculateNextGeneration(CellMap);
}

画画

void Draw()
{
for (auto cell : CellMap) // Iterate through all cells in CellMap vector
{
    // Draw Cell if Alive
    // If a cell was alive upto 10th generation, display cell as '1'.
    if (cell.IsAlive)
        GotoXY(cell.x, cell.y, AliveCell);
    // If a cell is dead, display cell as ' '.
    else
        GotoXY(cell.x, cell.y, DeadCell);
}
}

计算下一代

 /* 
TODO: Encapsulate IF Statements

Game Rules
1: Any Live Cell which has < 2 Live Neighbours, die [ Underpopulation ]
2: Any Live Cell which has 2 OR 3 Neighbours, live
3: Any Live Cell which has > 3 Neighbours, die [ Overpopulation ]
4: Any Dead Cell which has EXACTLY 3 Neighbours, resurrect [ Reporduciton ]

*/
void CalculateNextGeneration(vector<Cell> &map)
{
    for (auto& cell : map) // Iterate through all cells as references
    {
        if ((cell.IsAlive && GetAdjacentCellCount(cell, map) < 2) || (cell.IsAlive && GetAdjacentCellCount(cell, map) > 3)) // If current cell has < 2 neighbours OR current cell has > 3 neighbours, die [ Underpopulation & Overpopulation ] 
        {
            // Die
            cell.Die();
        }
        if (cell.IsAlive && GetAdjacentCellCount(cell, map) == 2 || GetAdjacentCellCount(cell, map) == 3) // If current cell has 2 OR 3 adjacent neighbours, live until next generation.
        {
            // Live Until Next Generation
        }
        if (!cell.IsAlive && GetAdjacentCellCount(cell, map) == 3) // If current cell has EXACTLY 3 adjacent neighbours, resurrect [ Reproduciton ]
        {
            // Resurrect
            cell.Resurrect();
        }
    }
}

获取邻接单元数

/* Count Adjacent cells

Long version of counting adjacent cells.
TODO: Clean up code.

Example:

0 = Dead Cell
1 = Alive Cell
X = Current Cell

    1   0   1
    0   X   0
    1   1   0

Return would be 4 in this case. Since There are 4 alive cells surround the current cell (X).

The function doesn't consider the current cell's life state.

*/
int GetAdjacentCellCount(Cell &currentCell, vector<Cell> &map)
{
    int aliveCount = 0;

    int currentX = currentCell.x;
    int currentY = currentCell.y;

    vector<Cell> adjacentCells; // Create temporary vector with all adjacent cells

    adjacentCells.push_back(GetCellAtXY(currentX - 1, currentY - 1, map));  // - - // TOP LEFT CELL
    adjacentCells.push_back(GetCellAtXY(currentX, currentY - 1, map));      // 0 - // TOP MIDDLE CELL
    adjacentCells.push_back(GetCellAtXY(currentX + 1, currentY - 1, map));  // + - // TOP RIGHT CELL
    adjacentCells.push_back(GetCellAtXY(currentX + 1, currentY, map));      // + 0 // MIDDLE LEFT CELL
    adjacentCells.push_back(GetCellAtXY(currentX + 1, currentY + 1, map));  // + + // MIDDLE RIGHT CELL
    adjacentCells.push_back(GetCellAtXY(currentX, currentY + 1, map));      // 0 + // BOTTOM LEFT CELL
    adjacentCells.push_back(GetCellAtXY(currentX - 1, currentY + 1, map));  // - + // BOTTOM MIDDLE CELL
    adjacentCells.push_back(GetCellAtXY(currentX - 1, currentY, map));      // - - // BOTTOM RIGHT CELL

    for (auto adjCell : adjacentCells) // Iterate through all adjacent cells
    {
        if (adjCell.IsAlive == true) // Count how many are alive
            aliveCount++;
    }

    return aliveCount;
}

获取CellAtXY

Cell GetCellAtXY(int x, int y, vector<Cell> &map)
{
    Cell retrievedCell = { 0, 0, false }; // Create a default return cell

    for (auto cell : map) // Iterate through all cells in the map
    {
        if (cell.x == x && cell.y == y) // If Cell is found at coordinate X, Y
            retrievedCell = cell; // Set found Cell to return Cell
    }

    return retrievedCell;
}

Answer 1

重写 GetAdjacentCellCount 函数可能会节省很多时间:

if (GetCellAtXY(currentX - 1, currentY - 1, map)  // - - // TOP LEFT CELL
   aliveCount++;
if (GetCellAtXY(currentX, currentY - 1, map));    // 0 - // TOP MIDDLE CELL
   aliveCount++;
if (GetCellAtXY(currentX + 1, currentY - 1, map)  // + - // TOP RIGHT CELL
   aliveCount++;
if (GetCellAtXY(currentX + 1, currentY, map)      // + 0 // MIDDLE LEFT CELL
   aliveCount++;
if (GetCellAtXY(currentX + 1, currentY + 1, map)  // + + // MIDDLE RIGHT CELL
   aliveCount++;
if (GetCellAtXY(currentX, currentY + 1, map)      // 0 + // BOTTOM LEFT CELL
   aliveCount++;
if (GetCellAtXY(currentX - 1, currentY + 1, map)  // - + // BOTTOM MIDDLE CELL
   aliveCount++;
if (GetCellAtXY(currentX - 1, currentY, map)      // - - // BOTTOM RIGHT CELL
   aliveCount++;

使用 push_back 填充 vector 会导致在每次迭代时为每个单元格分配多个堆。

我不知道这是否是您代码中的瓶颈部分，您必须分析才能知道这一点，但这似乎是一个简单的改进。

编辑

我发布得太早了。您的问题出在 GetCellAtXY 函数中。您循环(平均)一半的单元格以找到您的邻居。在每次迭代期间，您对每个单元执行 8 次!

相反，创建一个直接指向其 8 个邻居的单元格对象，例如:

struct Cell
{
  int x, y; // Cell X, Y coordiantes
  bool IsAlive; // Cell life state
  std::array<Cell*,8> neighbors;
}

然后你通过循环找到邻居一次(或者你在创建它们时填充它们，这可能更好)。请注意，当您设置 A.neighbor[left]=&B 时，您还设置了 B.neighbor[right]=&A。

我相信您会得到不使用指针的建议，因为使用指针不是正确的 C++。但我喜欢指点。

有很多选择:一个二维单元格网格，您可以通过计算知道每个邻居的索引，一个 std::map，您可以通过坐标的散列索引一个单元格，等等。

编辑

这是一种索引邻居的方法。这不一定是不太冗长的方法，但它传达了想法:

struct FieldSize {
  int x, y;
}
FieldSize fieldSize{ 40, 20 };

struct Cell {
  int x, y; // Cell X, Y coordiantes
  bool IsAlive; // Cell life state
  // ...
  bool HasLeftNeighbor() {
    return x != 0;
  }
  bool HasRightNeighbor() {
    return x != fieldSize.x-1;
  }
  bool HasTopNeighbor() {
    return y != 0;
  }
  bool HasTopLeftNeighbor() {
    return HasLeftNeighbor() && HasTopNeighbor();
  }
  // ... etc.
  int GetLeftNeighbor() {
    return (x-1) + y * fieldSize.x;
  }
  int GetTopNeighbor() {
    return x + (y-1) * fieldSize.x;
  }
  int GetTopLeftNeighbor() {
    return (x-1) + (y-1) * fieldSize.x;
  }
  // ... etc.
}

然后在 GetAdjacentCellCount 中:

if (HasLeftNeighbor() && map[GetLeftNeighbor()].IsAlive)
  aliveCount++;
// etc.

同样，这非常冗长，可以很容易地变得更紧凑，也可能更高效，但我想为您强调逻辑。