Grid.hpp

// Conway's Game of Life
// Copyright (c) 2025 Faraz Fallahi <fffaraz@gmail.com>

#pragma once

#include <array>
#include <random>

#if 1 // Enable multithreaded calculation of grid updates
#include <numeric>
#include <poolstl/poolstl.hpp>
#define PARALLEL_GRID 1
static task_thread_pool::task_thread_pool threadPool{std::thread::hardware_concurrency() / 2};
#endif

struct Point {
    const int x;
    const int y;
};

template <int SIZE>
class alignas(128) Grid {
public:
    inline bool get(const Point& p) const { return grid_[index(p)]; }
    inline void set(const Point& p, const bool value) { grid_[index(p)] = value; }
    inline void toggle(const Point& p) { const int idx = index(p); grid_[idx] = !grid_[idx]; }
    int countLiveNeighbors(const Point& p) const;
    void toggleBlock(const Point& p);
    void updateGrid(const Grid<SIZE>& current);
    void updateNeighbors();
    void addNoise(int n = 1);
    void clear();

private:
    std::array<bool, SIZE * SIZE> grid_;
    inline void updateP(const Grid<SIZE>& current, const Point& p);
    inline static int index(const Point& p) { return (p.x * SIZE) + p.y; }
#ifdef PARALLEL_GRID
    static constexpr std::array<int, SIZE> indices = [](){ std::array<int, SIZE> v; std::iota(v.begin(), v.end(), 0); return v; }();
#endif
};

// Count the number of live neighbors for the cell at (x, y)
template <int SIZE>
int Grid<SIZE>::countLiveNeighbors(const Point& p) const
{
    // Fast path for interior cells: no bounds checks and no per-neighbor index math
    if (p.x > 0 && p.x < SIZE - 1 && p.y > 0 && p.y < SIZE - 1) {
        const int idx = index(p);
        return grid_[idx - SIZE - 1]  // Top-left
             + grid_[idx - SIZE    ]  // Top
             + grid_[idx - SIZE + 1]  // Top-right
             + grid_[idx        - 1]  // Left
             + grid_[idx        + 1]  // Right
             + grid_[idx + SIZE - 1]  // Bottom-left
             + grid_[idx + SIZE    ]  // Bottom
             + grid_[idx + SIZE + 1]; // Bottom-right
    }
    // General case with bounds checks
    int liveNeighbors = 0;
    for (int i = -1; i <= 1; ++i) {
        for (int j = -1; j <= 1; ++j) {
            if (i == 0 && j == 0)
                continue; // Skip the cell itself
            const int nx = p.x + i; // (p.x + i) % SIZE;
            const int ny = p.y + j; // (p.y + j) % SIZE;
            if (nx >= 0 && nx < SIZE && ny >= 0 && ny < SIZE) {
                liveNeighbors += get({ nx, ny }) ? 1 : 0;
            }
        }
    }
    return liveNeighbors;
}

// Toggle a 3x3 block of cells at the given position
template <int SIZE>
void Grid<SIZE>::toggleBlock(const Point& p)
{
    const int size = 1;
    for (int i = -size; i <= size; ++i) {
        for (int j = -size; j <= size; ++j) {
            const Point n { p.x + i, p.y + j };
            if (n.x >= 0 && n.x < SIZE && n.y >= 0 && n.y < SIZE) {
                toggle(n);
            }
        }
    }
}

// Apply the rules of Conway's Game of Life
static inline bool gameOfLife(const bool cell, const int liveNeighbors)
{
    // A cell is alive in the next generation if it has 3 neighbors,
    // or if it is currently alive and has 2 neighbors.
    return liveNeighbors == 3 || (cell && liveNeighbors == 2);
}

template <int SIZE>
void Grid<SIZE>::updateP(const Grid<SIZE>& current, const Point& p)
{
    const int idx = index(p);
    const int live = current.countLiveNeighbors(p);
    grid_[idx] = gameOfLife(current.grid_[idx], live);
}

#ifndef PARALLEL_GRID

// Update the grid based on the rules of Conway's Game of Life
template <int SIZE>
void Grid<SIZE>::updateGrid(const Grid<SIZE>& current)
{
    for (int x = 0; x < SIZE; ++x) {
        for (int y = 0; y < SIZE; ++y) {
            const Point p { x, y };
            updateP(current, p);
        }
    }
}

#else // PARALLEL_GRID

// Parallel version of the update function
template <int SIZE>
void Grid<SIZE>::updateGrid(const Grid<SIZE>& current)
{
    // std::execution::par_unseq
    std::for_each(poolstl::par.on(threadPool), indices.begin(), indices.end(),
        [&](int x) {
            for (int y = 0; y < SIZE; ++y) {
                const Point p { x, y };
                updateP(current, p);
            }
        });
}

#endif

static std::mt19937 generator(0);
static std::uniform_int_distribution<int> distribution(0, 2'000'000'000);

// Add random noise to the grid
template <int SIZE>
void Grid<SIZE>::addNoise(int n)
{
    for (int i = 0; i < n; ++i) {
        const int x = distribution(generator) % SIZE;
        const int y = distribution(generator) % SIZE;
        toggle({ x, y });
    }
}

// Clear the grid
template <int SIZE>
void Grid<SIZE>::clear()
{
    grid_.fill(false);
}