Investigate using spatial hashing to optimize collision detection

[Jie-F]

I'm investigating this idea to speed up my own controller, and if I get promising results, I can implement this in Kessler as well.

Within kessler_game.py's update() loop, there's lots of stuff like "for each bullet, go through each asteroid" or "for each mine, go through each asteroid". There can be hundreds of asteroids so these loops are slow. If we can use spatial hashing (put each asteroid into a bucket in space) to narrow down the list of asteroids to a small subset that can potentially intersect with each bullet/mine/ship, then the loops will be made much smaller.

[Jie-F]

Did some testing with the below code (This works with asteroids/bullets/mines as dictionaries) and got worse performance than just looping through all asteroids normally 😢

class AsteroidSpatialHash:
    def __init__(self, cell_size: int = 100):
        self.cell_size = cell_size
        self.d = {}

    def _cell_coords_for_object(self, x1, y1, x2, y2):
        """Calculate the cell coordinates for an object based on its bounding box."""
        cy_start = floor(y1) // self.cell_size
        cy_end = floor(y2) // self.cell_size
        cx_start = floor(x1) // self.cell_size
        cx_end = floor(x2) // self.cell_size
        return [(cx, cy) for cy in range(cy_start, cy_end + 1) for cx in range(cx_start, cx_end + 1)]

    def add_asteroid(self, asteroid_index, asteroid):
        """Add an asteroid by index."""
        position, radius = asteroid['position'], asteroid['radius']
        x1, y1, x2, y2 = position[0] - radius, position[1] - radius, position[0] + radius, position[1] + radius
        cells = self._cell_coords_for_object(x1, y1, x2, y2)
        for c in cells:
            self.d.setdefault(c, set()).add(asteroid_index)

    def remove_asteroid(self, asteroid_index, asteroid):
        """Remove an asteroid by index."""
        position, radius = asteroid['position'], asteroid['radius']
        x1, y1, x2, y2 = position[0] - radius, position[1] - radius, position[0] + radius, position[1] + radius
        cells = self._cell_coords_for_object(x1, y1, x2, y2)
        for c in cells:
            if c in self.d:
                self.d[c].discard(asteroid_index)

    def _potential_collisions_for_object(self, x1, y1, x2, y2):
        cells = self._cell_coords_for_object(x1, y1, x2, y2)
        potentials = set()
        for c in cells:
            if c in self.d:
                potentials.update(self.d[c])
        return potentials

    def potential_collisions_for_circle(self, circle):
        """Get a set of all asteroid indices that potentially intersect the given object."""
        position, radius = circle['position'], circle['radius']
        x1, y1, x2, y2 = position[0] - radius, position[1] - radius, position[0] + radius, position[1] + radius
        return self._potential_collisions_for_object(x1, y1, x2, y2)

    def potential_collisions_for_bullet(self, bullet):
        """Get a set of all asteroid indices that potentially intersect the given object."""
        position, tail_delta = bullet['position'], bullet['tail_delta']
        x1, y1 = position[0] + (tail_delta[0] if tail_delta[0] < 0 else 0), position[1] + (tail_delta[1] if tail_delta[1] < 0 else 0)
        x2, y2 = position[0] + (tail_delta[0] if tail_delta[0] > 0 else 0), position[1] + (tail_delta[1] if tail_delta[1] > 0 else 0)
        return self._potential_collisions_for_object(x1, y1, x2, y2)

[TimArnettThales]

We've discussed this idea before and tabled it for a few reasons - we expect better performance and less overall headaches from moving to vectorized or compiled code. Not that you couldn't also do this, but those would likely increase performance enough to not have to do this for the numbers of asteroids expected in scenarios.