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