Open Jie-F opened 7 months ago
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)
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.
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.