Performance of collision detection in a grid

I have fairly simple collision checking and handling Python code which is currently bottlenecking my performance quite a bit. I haven't done too much coding in python and I'm quite sure there's something that could be done better:

Assuming I read this profiler correctly, get_nearby_entities is the biggest culprit.

Profiler output

Collision handling

In collision handling I go through all (moving) entities and find nearby entities from the collision grid (default search range is 9 closest cells).

def handle_collision():

    for first in entities:
        # Pair all possible combinations, but only once per pair
        grid.remove_entity(first)
        # all entities are readded to the grid at the start of next update
        for second in grid.get_nearby_entities(first):
            # Check and handle collision

Grid implementation:

In get_nearby_entities() I return list consisting entities from all cells within search radius. There's propably more efficient way to do this using Python.

```
import math

class Cell(object):

def __init__(self):
self.entities = []

def add_entity(self, entity):
self.entities.append(entity)

def remove_entity(self, entity):
self.entities.remove(entity)

def clear(self):
del self.entities[:]

class CollisionGrid(object):

def __init__(self, width, height, cell_size):
self.width = width
self.height = height
self.cell_size = cell_size

self.cols = int(math.ceil((self.width / cell_size)))
self.rows = int(math.ceil((self.height / cell_size)))

self.cells = [Cell() for _ in range(self.rows*self.cols)]

def add_entity(self, entity):
self.get_cell(entity.position).add_entity(entity)

def remove_entity(self, entity):
self.get_cell(entity.position).remove_entity(entity)

def get_nearby_entities(self, entity, radius = None):
if(not radius):
radius = self.cell_size
entities =

Looking at your profiling information you spend a total of 14.5s in handle_collision() out of which 3.8s is spent in get_nearby_entities. So your culprit may actually be somewhere else (I can't tell without the rest of your source).

Precalculate/Cache nearby status

You are calculating the nearby entities too many times. Consider this, you have a cluster of 100 entities that are in nearby cells. For each of those you will calculate roughly the same nearby entity list (1st list contains 100 entities, 2nd contains 100 - 1, 3rd contains 100-2 etc). This gives you O(n^2) behavior. If you'd instead cache which entities were nearby last call for this node (and properly reset this cache), you could reduce this down to amortized O(n).

Edit: Even if the number of entities per node is small you're still doing redundant work. In the picture below, consider that you're processing cell 5, which means that you're looking at entities in 0,1,2,4,5,6,8,9,10 and adding them to a list. Next iteration you're processing cell 6, now you're looking at entities in 1,2,3 5,6,7,9,10,11. Which means that you have 6 cells in common with the previous iteration. You can devise a scheme for reducing this redundancy.

+--+--+--+--+
| 0| 1| 2| 3|
+--+--+--+--+
| 4| 5| 6| 7|
+--+--+--+--+
| 8| 9|10|11|
+--+--+--+--+

Edit: Compare squared distances

As I stated in my comment, most likely there is something else in handle_collision() that takes up 10/24s of your execution time. Now that I can see the source, there is not much there except the square root operator. Determining the square root is typically slow and often times unnecessary as:

sqrt(d^2)  d^2 < (r0 + r1)^2

So I would change your handle_collision() to defer calculating the square root until it is absolutely necessary:

def handle_collision():

    statistics.num_entities = len(entities)
    statistics.collision_checks = 0
    for f in entities:
        # Pair all possible combinations, but only once per pair
        grid.remove_entity(f)
        for s in grid.get_nearby_entities(f):
            statistics.collision_checks += 1

            d = s.position - f.position
            if (not (d.x or d.y)):
                d.x += 0.1
            distance_sqr = d.x**2 + d.y**2
            radii = f.shape.radius + s.shape.radius
            if (distance_sqr < radii*radii):
                offset = d * (radii/math.sqrt(distance_sqr) - 1)
                f.velocity -= offset/2
                s.velocity += offset/2

As not all objects collide, this should save you some sqrts, and I can't see anything else in there that would take time to execute.

Pre-allocate memory(?)

I know too little of python to make a clear call on this but in get_nearby_entities() you appear to be growing a vector inside of a doubly nested for-loop, in many languages this could be slow and you could consider pre-allocating a properly sized buffer for entitites to avoid many resizes.

Edit: As was pointed out in comments, python's implementation runs in amortized O(n) time so pre allocating while saving some resizes will probably not gain you a significant amount of speed.

StackExchange Code Review Q#41907, answer score: 9