c++arraysmultidimensional-arrayprocedural-generationprocedural-programming

Why is my Cellular Automata implementation broken?


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

Solution

  • 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.