为什么我的元胞自动机实现失败了？

Question

我最近一直在处理程序噪音，并决定重新尝试重新学习元胞自动机以生成类似洞穴的地图。但我不确定我的 2D 数组实现是否格式错误，或者我的 CA 实现中是否存在问题......

在

GenerateCA

中，如果在复制

temp

数组后立即打印

grid

数组，则其内容看起来是相同的。但即使通过检查邻居进行一次迭代后，所有单元格都会变成

DEAD

。这是怎么回事？

#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

快速概述如何将所有内存管理转移到二维数组类。而不是使用自由函数和使用 new/delete 进行手动内存管理。

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

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