Why is my Cellular Automata implementation broken?

Question

I've been messing around with procedural noise lately, and decided to give a fresh stab at relearning Cellular Automata to generate cave-like maps. But I'm not sure if my implementation of 2D arrays is malformed, or if it's something in my CA implementation which is causing problems...

In GenerateCA, if you print the temp array right after copying the grid array, it's contents appear identical. But after even a single iteration through checking neighbors, all cells become DEAD. What's going on here?

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

Answer 1

As stated in the comments, I was using unsigned primitives as opposed to signed ones, and therefore the for loop in get_neighbor_count never gets executed, since it partially relies on negative values.

I was also using an online IDE which wasn't showing me any errors or warnings, of which there were plenty to be made aware of.

Answer 2

Just a quick sketch on how you can move all your memory managment to a 2d array class. Instead of using free functions and manual memory managment using new/delete. Note C++23 will have a multidimensional index operator you can use instead of the at function

#include <array>
#include <cassert>
#include <vector>

template<typename type_t>
class vector_2d_t
{
public:
    template<std::size_t rows_v, std::size_t columns_v>
    vector_2d_t(const type_t (&values)[rows_v][columns_v]) :
        vector_2d_t{ rows_v,columns_v }
    {
        std::size_t target_index{ 0ul };
        for (const auto& row : values)
        {
            for (const auto value : row)
            {
                m_data[target_index++] = value;
            }
        }
    }

    std::size_t number_of_rows() const noexcept
    {
        return m_rows;
    }

    std::size_t number_of_columns() const noexcept
    {
        return m_columns;
    }

    vector_2d_t(std::size_t rows, std::size_t columns) :
        m_rows{ rows },
        m_columns{ columns },
        m_data(rows* columns)
    {
    }

    ~vector_2d_t() = default;

    type_t& at(std::size_t row, std::size_t column) noexcept
    {
        return m_data[to_index(row, column)];
    }

    const type_t& at(std::size_t row, std::size_t column) const noexcept
    {
        return m_data[to_index(row, column)];
    }

    // C++20
    auto operator[](std::size_t row) const noexcept
    {
        assert(row < m_rows);
        return std::span<const type_t>(&m_data[row*m_columns],m_columns);
    }

    // C++20
    auto operator[](std::size_t row) noexcept
    {
        assert(row < m_rows);
        return std::span<type_t>(&m_data[row*m_columns],m_columns);
    }


private:
    inline auto to_index(std::size_t row, std::size_t column)
    {
        assert(row < m_rows);
        assert(column < m_columns);
        return (row * m_columns) + column;
    }

    std::size_t m_rows;
    std::size_t m_columns;
    std::vector<type_t> m_data;
};

int main()
{
    vector_2d_t grid{{ {1,2,3}, {4,5,6}, {7,8,9} }};
    assert(grid.at(1,2) == 6);
    grid.at(1,2) = 10;
    assert(grid.at(1,2) == 10);
    return 0;
}