我的Cellular Automata实现为何失效？迭代后单元格全变为DEAD

近期研究过程式噪声，重新学习Cellular Automata生成类洞穴地图时遇到问题：GenerateCA函数中，刚复制grid得到的temp数组和原数组内容一致，但仅一轮邻居检查迭代后，所有单元格都变成DEAD，不确定是二维数组实现错误还是CA逻辑问题。

问题代码 #

#include <iostream>
#include <time.h>

#define UCHAR unsigned char
const UCHAR DEAD = 0;
const UCHAR ALIVE = 1;
const uint32_t MAPSIZE_X = 20;
const uint32_t MAPSIZE_Y = 8;
const uint8_t NOISEDENSITY = 80;
const uint32_t ITERATIONS = 3;

// Creates a new array
template <typename T>
T** AllocateArray2D(uint32_t size_x, uint32_t size_y) {
    T** arr = new UCHAR*[size_x];
    for (auto i = 0; i < size_x; i++)
        arr[i] = new T[size_y];
    return arr;
}

// Creates a shallow copy of an existing array
template <typename T>
T** CopyArray2D(T** arrSource, uint32_t size_x, uint32_t size_y) {
    auto arr = AllocateArray2D<T>(size_x, size_y);
    for(auto y = 0; y < size_y; y++) {
        for(auto x = 0; x < size_x; x++) {
            arr[x][y] = arrSource[x][y];
        }
    }
    return arr;
}

// Prints the cell state of each element of the array
template <typename T>
void PrintArray2D(T** arr, uint32_t size_x, uint32_t size_y, bool bAddHorizontalRule = true) {
    for(auto y = 0; y < size_y; y++) {
        for(auto x = 0; x < size_x; x++) {
            std::cout << (arr[x][y] == DEAD ? " " : "#");
        }
        std::cout << std::endl;
    }
    std::cout << std::endl;
    
    if(bAddHorizontalRule) {
        for(auto x = 0; x < size_x; x++) {
            std::cout << "=";
        }
        std::cout << std::endl;
    }
}

// Frees an array from memory
template <typename T>
void FreeArray2D(T** arr, uint32_t size_x) {
    for (int i = 0; i < size_x; i++) {
        delete[] arr[i];
        arr[i] = nullptr;
    }
    delete[] arr;
    arr = nullptr;
}

// Creates a random grid of dead/alive cells based on a threshold between 1-100
UCHAR** GenerateGrid(uint32_t size_x, uint32_t size_y, uint32_t noiseDensity = 50) {
    auto grid = AllocateArray2D<UCHAR>(MAPSIZE_X, MAPSIZE_Y);
    
    for(auto y = 0; y < MAPSIZE_Y; y++) {
        for(auto x = 0; x < MAPSIZE_X; x++) {
            auto density = rand() % 100 + 1;
            if(density < noiseDensity)
                grid[x][y] = ALIVE;
            else
                grid[x][y] = DEAD;
        }
    }
    
    PrintArray2D<UCHAR>(grid, MAPSIZE_X, MAPSIZE_Y);
    return grid;
}

// Returns the number of neighboring cells (from [x, y]) which are alive
uint32_t get_neighbor_count(UCHAR** grid, uint32_t x, uint32_t y) {
    uint32_t count = 0;
    for(auto yy = y - 1; yy <= y + 1; yy++) {
        for(auto xx = x - 1; xx <= x + 1; xx++) {
            if(yy > -1 && yy < MAPSIZE_Y && xx > -1 && xx < MAPSIZE_X) {
                if (yy != y || xx != x) {
                    if(grid[xx][yy] == ALIVE)
                        count++;
                }
            }
        }
    }
    return count;
}

// Performs Cellular Automata based on an existing grid, returning a new grid
UCHAR** GenerateCA(UCHAR** grid, uint32_t iterations, uint8_t neighborThreshold = 4) {
    auto temp = CopyArray2D<UCHAR>(grid, MAPSIZE_X, MAPSIZE_Y);
    
    for(auto it = 0; it < iterations; it++) {
        for(auto y = 0; y < MAPSIZE_Y; y++) {
            for(auto x = 0; x < MAPSIZE_X; x++) {
                auto neighborCount = get_neighbor_count(temp, x, y);
                if (neighborCount >= neighborThreshold)
                    temp[x][y] = ALIVE;
                else
                    temp[x][y] = DEAD;
            }
        }
        PrintArray2D<UCHAR>(temp, MAPSIZE_X, MAPSIZE_Y);
    }

    return temp;
}

int main()
{
    srand(time(NULL));
    
    auto grid = GenerateGrid(MAPSIZE_X, MAPSIZE_Y, NOISEDENSITY);
    auto grid_ca = GenerateCA(grid, ITERATIONS);

    FreeArray2D<UCHAR>(grid_ca, MAPSIZE_X);
    FreeArray2D<UCHAR>(grid, MAPSIZE_X);
    
    return 0;
}

核心问题分析 #

1. 迭代时直接修改原数组：GenerateCA中直接在temp数组上修改单元格状态，导致后续单元格的邻居计算使用的是已经更新后的状态，而非当前迭代的初始状态，这会快速把整个网格覆盖为DEAD。
2. 无符号整数边界判断失效：get_neighbor_count中使用yy > -1和xx > -1，但yy、xx是无符号整数（uint32_t），当y=0时y-1会变成uint32_t的最大值，导致边界判断完全错误，影响邻居计数。
3. CA规则不符合洞穴生成逻辑：原规则是所有细胞只要邻居数≥4就存活，否则死亡，这种规则无法生成合理的洞穴结构，反而容易导致全死。

修复方案 #

1. 双数组分离当前/下一状态

修改GenerateCA，每次迭代基于当前状态计算下一状态，避免修改原数组影响后续计算：

UCHAR** GenerateCA(UCHAR** grid, uint32_t iterations, uint8_t neighborThreshold = 4) {
    auto current = CopyArray2D<UCHAR>(grid, MAPSIZE_X, MAPSIZE_Y);
    auto next = AllocateArray2D<UCHAR>(MAPSIZE_X, MAPSIZE_Y);
    
    for(auto it = 0; it < iterations; it++) {
        for(auto y = 0; y < MAPSIZE_Y; y++) {
            for(auto x = 0; x < MAPSIZE_X; x++) {
                auto neighborCount = get_neighbor_count(current, x, y);
                // 经典洞穴生成规则
                if (current[x][y] == ALIVE) {
                    // 存活细胞：邻居数≥4则保持存活
                    next[x][y] = (neighborCount >= 4) ? ALIVE : DEAD;
                } else {
                    // 死亡细胞：邻居数≥5则复活
                    next[x][y] = (neighborCount >= 5) ? ALIVE : DEAD;
                }
            }
        }
        // 交换数组，准备下一轮迭代
        std::swap(current, next);
        PrintArray2D<UCHAR>(current, MAPSIZE_X, MAPSIZE_Y);
    }
    // 释放无用数组
    FreeArray2D<UCHAR>(next, MAPSIZE_X);
    return current;
}

2. 修复边界判断错误

修改get_neighbor_count，将循环变量转为有符号整数，避免无符号下溢：

uint32_t get_neighbor_count(UCHAR** grid, uint32_t x, uint32_t y) {
    uint32_t count = 0;
    // 转为int避免无符号下溢
    for(int yy = static_cast<int>(y) - 1; yy <= static_cast<int>(y) + 1; yy++) {
        for(int xx = static_cast<int>(x) - 1; xx <= static_cast<int>(x) + 1; xx++) {
            if(yy >= 0 && yy < static_cast<int>(MAPSIZE_Y) && xx >=0 && xx < static_cast<int>(MAPSIZE_X)) {
                if (yy != static_cast<int>(y) || xx != static_cast<int>(x)) {
                    if(grid[xx][yy] == ALIVE)
                        count++;
                }
            }
        }
    }
    return count;
}

3. 调整CA规则为经典洞穴生成逻辑

使用上述代码中的规则：

• 存活细胞：周围有≥4个存活邻居时保持存活
• 死亡细胞：周围有≥5个存活邻居时复活
  该规则能生成自然连通的洞穴结构。

内容的提问来源于stack exchange，提问作者RectangleEquals