SpatialHashGrid.java

/*
* Authors: Jerry Li & Victor Jiang
* Date: June 13, 2025
* Description: This class is used to optimize collision detection by dividing the world into cells so that lookup of nearby
* possible collision objects is more efficient
*/

import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;
import java.util.function.LongConsumer;

/**
 * Generic spatial hash grid for efficient proximity queries.
 */
public class SpatialHashGrid<T> {
    private Map<Long, CopyOnWriteArrayList<T>> grid = new HashMap<>();
    private float cellSize;
    private HashSet<T> querySet = new HashSet<>();
    private CopyOnWriteArrayList<T> queryList = new CopyOnWriteArrayList<>();

    public SpatialHashGrid(float cellSize) {
        this.cellSize = cellSize;
    }

    /** Clears all cells. */
    public void clear() {
        grid.clear();
    }

    private static long cellKey(int cx, int cy) {
        return ((long) cx << 32) ^ (cy & 0xffffffffL);
    }

    private void foreachCell(float x, float y, float radius, LongConsumer fn) {
        int minX = 0;
        int maxX = 0;
        int minY = 0;
        int maxY = 0;
        int cx = 0;
        int cy = 0;
        minX = (int) Math.floor((x - radius) / cellSize);
        maxX = (int) Math.floor((x + radius) / cellSize);
        minY = (int) Math.floor((y - radius) / cellSize);
        maxY = (int) Math.floor((y + radius) / cellSize);
        for (cx = minX; cx <= maxX; cx++) {
            for (cy = minY; cy <= maxY; cy++) {
                fn.accept(cellKey(cx, cy));
            }
        }
    }

    /** Inserts obj into all cells overlapped by its radius at (x,y). */
    public void insert(T obj, float x, float y, float radius) {
        foreachCell(x, y, radius, key -> {
            grid.computeIfAbsent(key, k -> new CopyOnWriteArrayList<>()).add(obj);
        });
    }

    /** Removes obj from cells overlapped by its radius at (x,y). */
    public void remove(T obj, float x, float y, float radius) {
        foreachCell(x, y, radius, key -> {
            CopyOnWriteArrayList<T> list = grid.get(key);
            if (list != null) {
                list.remove(obj);
                if (list.isEmpty()) grid.remove(key);
            }
        });
    }

    /** Updates obj from old to new position. */
    public void update(T obj, float oldX, float oldY, float newX, float newY, float radius) {
        remove(obj, oldX, oldY, radius);
        insert(obj, newX, newY, radius);
    }

    /** Returns all objects within radius of the given position. */
    public List<T> queryNearby(float x, float y, float radius) {
        querySet.clear();
        foreachCell(x, y, radius, key -> {
            CopyOnWriteArrayList<T> list = grid.get(key);
            if (list != null) querySet.addAll(list);
        });
        queryList.clear();
        queryList.addAll(querySet);
        return queryList;
    }
}