# 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 = []

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 remove_entity(self, entity):
self.get_cell(entity.position).remove_entity(entity)

def get_nearby_entities(self, entity, radius = None):
entities = []

min_x = int((entity.position.x - radius) / self.cell_size)
min_y = int((entity.position.y - radius) / self.cell_size)
max_x = int(min_x + 2*radius/self.cell_size + 1)
max_y = int(min_y + 2*radius/self.cell_size + 1)

if (min_x < 0): min_x = 0
if (min_y < 0): min_y = 0
if (max_x >= self.cols): max_x = self.cols
if (max_y >= self.rows): max_y = self.rows

for y in range(min_y, max_y):
for x in range(min_x, max_x):
entities.extend(self.cells[self.cols*y + x].entities)

return entities

def get_cell(self, position):
return self.cells[int(position.x / self.cell_size) +
int(position.y / self.cell_size) * self.cols]

def clear(self):
for c in self.cells:
c.clear()


### Test main:

import sfml as sf
import math
from entity import Entity
from collision_grid import CollisionGrid

WIDTH = 1280
HEIGHT = 720
Entity.SIZE = 50

settings = sf.window.ContextSettings()
settings.antialiasing_level = 8
window = sf.RenderWindow(sf.VideoMode(WIDTH, HEIGHT), "Collision Test",
sf.Style.DEFAULT, settings)

entities = []
grid = CollisionGrid(WIDTH, HEIGHT, Entity.SIZE)
time_per_frame = sf.seconds(1/60)

class Statistics(object):

def __init__(self, font):
self.text = sf.Text()
self.update_time = sf.seconds(0)
self.num_frames = 0

self.text.font = font
self.text.position = (5, 5)
self.text.character_size = 18

self.num_entities = 0
self.collision_checks = 0

def update(self, dt):

statistics.num_frames += 1
statistics.update_time += dt

if (self.update_time >= sf.seconds(0.1)):
fps = int(self.num_frames / self.update_time.seconds)
tps = int(self.update_time.microseconds / self.num_frames)
text = "FPS: " + str(fps) + "\n"
text += "update: " + str(tps) + " us\n"
text += "entities: " + str(self.num_entities) + "\n"
text += "collision checks: " + str(self.collision_checks) + "\n"
self.text.string = text

self.update_time -= sf.seconds(0.1)
self.num_frames = 0

def draw(self, target):
target.draw(self.text)

font = sf.Font.from_file("Media/Fonts/Sansation.ttf")
statistics = Statistics(font)

def process_events():
for event in window.events:
if type(event) is sf.CloseEvent:
window.close()

elif type(event) is sf.KeyEvent and event.code is sf.Keyboard.ESCAPE:
window.close()

elif type(event) is sf.MouseButtonEvent and event.pressed:
entities.append(Entity(event.position, sf.Color.GREEN))

def update(dt):
for e in entities:
e.update(dt)
if (e.position.x < 0):
e.position.x += WIDTH
elif (e.position.x > WIDTH):
e.position.x -= WIDTH
if (e.position.y  < 0):
e.position.y += HEIGHT
elif (e.position.y > HEIGHT):
e.position.y -= HEIGHT

def render():
window.clear()
for e in entities:
e.draw(window)
grid.draw(window)
statistics.draw(window)
window.display()

def update_grid():
for e in entities:

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 = math.sqrt(d.x**2 + d.y**2)
offset = d * (radii/distance - 1)
f.velocity -= offset/2
s.velocity += offset/2

if __name__ == "__main__":

clock = sf.Clock()
time_since_last_update = sf.seconds(0)
for i in range(200):
entities.append(Entity(sf.Vector2(75+int(i%23)*50, 75+int(i/23)*50), sf.Color.GREEN))

while window.is_open:

dt = clock.restart()
time_since_last_update += dt

while time_since_last_update > time_per_frame:

time_since_last_update -= time_per_frame

process_events()

update_grid()
handle_collision()
grid.clear()
update(time_per_frame)

statistics.update(dt)
render()


### Entity

import sfml as sf
import utility

class Entity(object):

SIZE = 50

def __init__(self, position, color):
self.shape = sf.CircleShape()
self.shape.fill_color = sf.Color.TRANSPARENT
self.shape.outline_color = color
self.shape.outline_thickness = 1

self.position = position
self.velocity = sf.Vector2()

self.line = sf.VertexArray(sf.PrimitiveType.LINES, 2)

def update(self, dt):
self.position += self.velocity * dt.seconds
speed = utility.length(self.velocity)
if (speed > 0.1):
self.velocity -= utility.unit_vector(self.velocity) * 0.1
else:
self.velocity.x = 0
self.velocity.y = 0

def draw(self, target):
self.line[0].position = self.position
self.line[1].position = self.position + self.velocity
target.draw(self.shape)
target.draw(self.line)


### Utility methods used by Entity

def length(vector):
return math.sqrt(vector.x * vector.x + vector.y * vector.y)

def unit_vector(vector):
return vector / length(vector)

-
It is difficult to improve the performance of code without a runnable test case whose performance we can measure. You could help us out here by making a self-contained runnable test case. –  Gareth Rees Feb 17 at 20:42
@GarethRees I have little test case for this written with sfml. Should I upload that somewhere or try to create smaller test case. (I find it easier to test, when I actually get some visual feedback) –  Klaus Helenius Feb 17 at 21:26
pySFML is a bit inconvenient to install (there's no PyPI package), so it would best if you could simplify your test case so that it runs on plain Python, and add it to your question. –  Gareth Rees Feb 17 at 21:31
Thanks for posting some test code. But I can't run it: you haven't posted the code for the Entity class. –  Gareth Rees Feb 18 at 10:29
@GarethRees I added Entity class and 2 utility methods it uses during update-step –  Klaus Helenius Feb 18 at 11:15

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) < r0 + r1 <=> 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
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.

-
With regard to your second point, Python's list.extend(x) has amortized cost O(len(x)) so this is not a concern here. See the TimeComplexity page on the Python wiki. –  Gareth Rees Feb 17 at 22:54
As I said I'm no python coder :) I'll edit my post. –  Emily L. Feb 17 at 23:04
@EmilyL Currently cell size is same as entity size, and entities won't overlap much -> in single cell there is usually only 1 or 2 entities at most –  Klaus Helenius Feb 17 at 23:04
Okay then would you please clarify the original post with more information about what quantities of entities and cells we're talking about? –  Emily L. Feb 17 at 23:08
I looked at your profiling results again only 15% of your execution time seems to be spent in get_nearby_entities(). I believe your bottleneck may be elsewhere. –  Emily L. Feb 17 at 23:16

Python isn't fabulous at handling large numbers of math operations, but hundreds should be feasible.

I agree that this doesn't look like it's primarily the fault of the collision grid. That said, it should be possible to speed up the grid calculation. I'd switch the grid to a really crude modulus of the object's position so that you don't calculate distances accurately until you need them: instead, sort everything into buckets by just dividing the entity position X and position Y by a scale (maybe with an offset so you can 'center' your grid in the world) this is cheaper than calculating distances ( no square roots) so it makes a good crude first pass.

In the interest of simplicity I'd stick with default python lists for the grid and cells too. Plus, updating incrementally instead of a clean wipe should mean less memory shuffling. Here's a sketch of how I'd do it, though I doubt I'm covering your whole spec:

def create_grid(cells_x = 50, cells_y = 50):
'''grid is a list-of-list-of-lists in row-column-list order'''
grid =  [ [ [] for x in range(cells_x)] for y in range(cells_y)]
return grid

def get_nearby_entities( x,y, grid,  radius = 1):
'''this only checks cells, leaving detailed checks for later. It return all the entities in around x,y to <radius> cells'''
min_x = max (x - radius, 0)
max_x = min (x + radius, len( grid[0] ))

min_y = max (y - radius, 0)
max_y = min (y + radius, len(grid))

nearby_cells =  itertools.product(range (min_x, max_x + 1), range(min_y, max_y + 1))
return itertools.chain(nearby_cells)

'''get the grid address for a given position'''
address_x = math.floor ((entity.position.x + offset.x) / scale)
address_y = math.floor ((entity.position.x + offset.y) / scale)

def rebuild_grid(grid, scale, offset, *entities):
''' update the grid after every step'''
delenda = {}
for x, y in itertools.product(range (len(grid[0])), range(len(grid))):
for each_entity in grid[x][y]:
delenda[each_entity] = (x,y)

for item in delenda:
oldx, oldy = delenda[item]
grid[oldx][oldy].remove(item)

grid[oldx][oldy].append(item)


I think this will be faster than your current update routine (among other things, using itertools is usually faster than hand-written loops) -- though depending on the data the incremental update might end up slower for data that doesn't cohere in time.

The other obvious optimization would be to cache the collision checks as has been suggested. You'd maintain a dictionary of entity-entity pairs (this assumes entities are hashable, but they probably are). Inbetween steps set all existing pairs to a neutral value like None or -1; then as you do the checks for a given pair, you check the dictionary to be sure you haven't done that particular check before. I'd also do a two stage check for collision to cut out the square roots:

# pretend the collisions are stored in a dictionary called 'colliders'
def collision_check ( pair, colliders, tolerance):
''' pair is a tuple (entity1, entity2)'''
if colliders[pair] != None: return

def collide():
colliders[pair] = 1
colliders[ (pair[1], pair[0]) ] = 1

def miss():
colliders[pair] = 0
colliders[ (pair[1], pair[0]) ] = 0

deltax = abs(pair[1].x - pair[0].x)
deltay = abs(pair[1].y - pair[0].y)
squaredist  = deltax + deltay
if squaredist < tolerance:
collide()
return

if math.sqrt(math.pow(deltax,2) + math.pow(deltay, 2)) < tolerance:
collide()
return
miss()


If after all that you still can't get the perf you want, you might want to look into using numpy for the heavy duty tasks.

-