How to implement Conway’s Game of Life using a quadtree in Java?

Question

I am trying to implement Conway’s Game of Life using a quadtree data structure in Java. I have a QuadTree class that stores points in a two-dimensional space, and each point has a Cell object as its data that stores its state (isAlive) and the number of live neighbors (liveNeighbors). I have three methods that insert a pattern of points into the quadtree, update the liveNeighbors field of each point based on the query() method of the quadtree, and update the isAlive field of each point based on the rules of the game.

However, when I run my code with a simple blinker pattern (a vertical line of three alive cells in the middle of a 5x5 grid), I get incorrect results. The expected behavior is that the blinker should oscillate between a vertical and a horizontal line every generation, but instead, all the cells die and no new cells are born. I noticed that some points have incorrect values for their liveNeighbors field, which affects the updateState() method. For example, the point (1,2) should have 8 neighbors and 3 live neighbors, but it only has 1 neighbor and 1 live neighbor.

import java.util.*;

public class CellularAutomations {
    static class Point {
        float x;
        float y;
        Object data;
        int liveNeighbors = 0;

        public String toString() {
            return String.format("(%.3f,%.3f)", this.x, this.y);
        }

        Point(float x, float y, Object data) {
            this.x = x;
            this.y = y;
            this.data = data;
        }
    }

    static class Cell {
        boolean isAlive = false;
        int liveNeighbors = 0;

        public String toString() {
            return "(" + this.isAlive + "," + this.liveNeighbors + ")";
        }

        Cell(boolean isAlive) {
            this.isAlive = isAlive;
        }
    }

    static class Boundary {
        Point center;
        float halfWidth;
        float halfHeight;

        public String toString() {
            return String.format("x:(%.3f,%.3f) y:(%.3f,%.3f)", this.center.x - halfWidth, this.center.x + halfWidth,
                    this.center.y - halfHeight, this.center.y + halfHeight);
        }

        Boundary(Point center, float halfWidth, float halfHeight) {
            this.center = center;
            this.halfWidth = halfWidth;
            this.halfHeight = halfHeight;
        }

        boolean contains(Point p) {
            return (this.center.x - halfWidth <= p.x && this.center.x + halfWidth >= p.x
                    && this.center.y - halfHeight <= p.y && this.center.y + halfHeight >= p.y);
        }

        boolean intersects(Boundary other) {
            if (this.center.x - this.halfWidth > other.center.x + other.halfWidth ||
                    this.center.x + this.halfWidth < other.center.x - other.halfWidth ||
                    this.center.y - this.halfHeight > other.center.y + other.halfHeight ||
                    this.center.y + this.halfHeight < other.center.y - other.halfHeight)
                return false;
            return true;
        }
    }

    public static void main(String[] args) {
        boolean[][] arr = {
                { false, false, false, false, false },
                { false, false, true, false, false },
                { false, false, true, false, false },
                { false, false, true, false, false },
                { false, false, false, false, false }
        };
        QuadTree qt = new QuadTree(
                new Boundary(new Point(arr.length / 2f, arr[0].length / 2f, null), arr[0].length / 2, arr.length / 2),
                4);
        CellularAutomations n = new CellularAutomations();
        n.startSimulation(qt, arr, arr[0].length, arr.length);
    }

    static void updateNeighbors(QuadTree node) {
        if (node == null)
            return;
        for (Point point : node.points) {
            Boundary boundary = new Boundary(point, 1.5f, 1.5f);
            ArrayList<Point> neighbors = node.query(boundary);
            neighbors.remove(point);
            int liveNeighbors = 0;
            for (Point neighbor : neighbors) {
                Cell cell = (Cell) neighbor.data;
                if (cell.isAlive)
                    liveNeighbors++;
            }
            Cell cell = (Cell) point.data;
            cell.liveNeighbors = liveNeighbors;
            point.data = cell;
        }
        if (node.divided) {
            updateNeighbors(node.northwest);
            updateNeighbors(node.northeast);
            updateNeighbors(node.southwest);
            updateNeighbors(node.southeast);
        }
    }

    static void updateState(QuadTree node) {
        if (node == null)
            return;
        for (Point point : node.points) {
            Cell cell = (Cell) point.data;
            if (cell.isAlive) {
                if (cell.liveNeighbors < 2 || cell.liveNeighbors > 3)
                    cell.isAlive = false;
            } else if (cell.liveNeighbors == 3)
                cell.isAlive = true;
            point.data = cell;
        }
        if (node.divided) {
            updateState(node.northwest);
            updateState(node.northeast);
            updateState(node.southwest);
            updateState(node.southeast);
        }
    }

    public void printGrid(QuadTree node, int width, int height) {
        int[][] grid = new int[height][width];
        fillGrid(node, grid);
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                System.out.print(grid[i][j] + " ");
            }
            System.out.println();
        }
    }

    private void fillGrid(QuadTree node, int[][] grid) {
        if (node == null)
            return;
        for (Point point : node.points) {
            Cell cell = (Cell) point.data;
            grid[(int) point.y][(int) point.x] = cell.isAlive ? 1 : 0;
        }
        if (node.divided) {
            fillGrid(node.northwest, grid);
            fillGrid(node.northeast, grid);
            fillGrid(node.southwest, grid);
            fillGrid(node.southeast, grid);
        }
    }

    public void startSimulation(QuadTree root, boolean[][] pattern, int width, int height) {
        insertPattern(root, pattern);
        while (true) {
            printGrid(root, width, height);
            System.out.println();
            updateNeighbors(root);
            updateState(root);
            try {
                Thread.sleep(5000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    private void insertPattern(QuadTree root, boolean[][] pattern) {
        for (int i = 0; i < pattern.length; i++) {
            for (int j = 0; j < pattern[i].length; j++) {
                root.insert(new Point(j, i, new Cell(pattern[i][j])));
            }
        }
    }

    static class QuadTree {
        ArrayList<Point> points;
        int capacity;
        Boundary boundary;
        QuadTree northwest;
        QuadTree northeast;
        QuadTree southwest;
        QuadTree southeast;
        QuadTree parent;

        QuadTree(Boundary boundary, int capacity) {
            this.boundary = boundary;
            this.capacity = capacity;
            this.points = new ArrayList<Point>(capacity);
            this.northwest = this.southeast = this.southwest = this.northeast = this.parent = null;
        }

        void subdivide() {
            float w = this.boundary.halfWidth / 2;
            float h = this.boundary.halfHeight / 2;
            Point center = this.boundary.center;
            Object data = null;
            this.northwest = new QuadTree(new Boundary(new Point(center.x - w, center.y + h, data), w, h),
                    this.capacity);
            this.northwest.parent = this;
            this.northeast = new QuadTree(new Boundary(new Point(center.x + w, center.y + h, data), w, h),
                    this.capacity);
            this.northeast.parent = this;
            this.southwest = new QuadTree(new Boundary(new Point(center.x - w, center.y - h, data), w, h),
                    this.capacity);
            this.southwest.parent = this;
            this.southeast = new QuadTree(new Boundary(new Point(center.x + w, center.y - h, data), w, h),
                    this.capacity);
            this.southeast.parent = this;
            this.divided = true;
        }

        boolean divided = false;

        boolean insert(Point p) {
            if (!this.boundary.contains(p))
                return false;
            if (this.points.size() < this.capacity) {
                this.points.add(p);
                return true;
            } else if (!this.divided) {
                this.subdivide();
            }
            if (this.northwest.insert(p))
                return true;
            else if (this.northeast.insert(p))
                return true;
            else if (this.southwest.insert(p))
                return true;
            else if (this.southeast.insert(p))
                return true;
            return false;
        }

        ArrayList<Point> query(Boundary range) {
            ArrayList<Point> found = new ArrayList<Point>();
            if (!this.boundary.intersects(range)) {
                return found;
            }
            for (Point point : this.points)
                if (range.contains(point)) {
                    found.add(point);
                }
            if (this.divided) {
                found.addAll(this.northwest.query(range));
                found.addAll(this.northeast.query(range));
                found.addAll(this.southeast.query(range));
                found.addAll(this.southwest.query(range));
            }
            if (this.parent != null) {
                QuadTree[] siblings = { this.parent.northwest, this.parent.northeast, this.parent.southwest,
                        this.parent.southeast };
                for (QuadTree sibling : siblings) {
                    if (sibling != null && sibling != this && sibling != this.northwest && sibling != this.northeast
                            && sibling != this.southwest && sibling != this.southeast) {
                        if (range.intersects(sibling.boundary)) {
                            found.addAll(sibling.query(range));
                        }
                    }
                }
            }
            if (this.parent != null && this.parent.parent != null) {
                QuadTree[] cousins = { this.parent.parent.northwest, this.parent.parent.northeast,
                        this.parent.parent.southwest, this.parent.parent.southeast };
                for (QuadTree cousin : cousins) {
                    if (cousin != null && cousin != this && cousin != this.northwest && cousin != this.northeast
                            && cousin != this.southwest && cousin != this.southeast && cousin != this.parent) {
                        if (range.intersects(cousin.boundary)) {
                            found.addAll(cousin.query(range));
                        }
                    }
                }
            }
            return found;
        }
    }
}

Can anyone help me with this problem? How can I make sure that all the neighbors of a point are counted by the query() method? Is there a better way to implement Conway’s Game of Life using a quadtree? Any suggestions or feedback would be appreciated.

I tried to modify the query() method to check not only the current node and its children, but also its siblings and cousins (the other quadtrees that share a common parent or grandparent with the current node), but I got a stackoverflow error. I think that the recursive calls of the query() method are exceeding the maximum depth of the call stack, but I don’t know how to fix this.