c++ - C++ Console Conway的生活游戏更新非常慢

我目前正在使用C ++的Conway的《人生游戏》的控制台版本。

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();
        }
    }
}

GetAdjacentCellCount

/* 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;
}

GetCellAtXY

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;
}

最佳答案

您可能会花很多时间来重写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填充向量会使每次迭代的每个单元发生多个堆分配。

我不知道这是否是代码的瓶颈部分，您必须进行概要分析才能知道，但这似乎是一项容易的改进。

编辑

我发布得太早了。您的问题出在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 ++。但是我喜欢指针。

有很多选择：一个2D单元格网格，您可以通过计算了解每个邻居的索引，一个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.

再次，这是非常冗长的，可以很容易地变得更紧凑，也可能更有效率，但是我想为您强调逻辑。