9
\$\begingroup\$

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

        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()

Picture of few entities in collision grid:

few entities in collision grid

It is after 200 entities when simulation really starts to slow down:

few more entities

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:
        grid.add_entity(e)


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)
            radii = f.shape.radius + s.shape.radius
            if (distance < radii):
                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.radius = Entity.SIZE/2
        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.shape.position = self.position - self.shape.radius
        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)
\$\endgroup\$
6
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 17, 2014 at 20:42
  • \$\begingroup\$ @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) \$\endgroup\$
    – warbaque
    Feb 17, 2014 at 21:26
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 17, 2014 at 21:31
  • \$\begingroup\$ Thanks for posting some test code. But I can't run it: you haven't posted the code for the Entity class. \$\endgroup\$ Feb 18, 2014 at 10:29
  • \$\begingroup\$ @GarethRees I added Entity class and 2 utility methods it uses during update-step \$\endgroup\$
    – warbaque
    Feb 18, 2014 at 11:15

3 Answers 3

9
\$\begingroup\$

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
            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.

\$\endgroup\$
13
  • \$\begingroup\$ 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. \$\endgroup\$ Feb 17, 2014 at 22:54
  • \$\begingroup\$ As I said I'm no python coder :) I'll edit my post. \$\endgroup\$
    – Emily L.
    Feb 17, 2014 at 23:04
  • \$\begingroup\$ @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 \$\endgroup\$
    – warbaque
    Feb 17, 2014 at 23:04
  • \$\begingroup\$ Okay then would you please clarify the original post with more information about what quantities of entities and cells we're talking about? \$\endgroup\$
    – Emily L.
    Feb 17, 2014 at 23:08
  • \$\begingroup\$ 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. \$\endgroup\$
    – Emily L.
    Feb 17, 2014 at 23:16
5
\$\begingroup\$

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)

def get_address(entity, scale, offset):
    '''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)
    return address_x, address_y

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

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

    for item in addenda:
        oldx, oldy = addenda[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.

\$\endgroup\$
3
\$\begingroup\$

Minor improvements

Just looking at get_nearby_entities I see several (probably minor) improvements possibilities:

  • transform it to a generator (it should save some memory space)
  • remove some branching (I had some experience, where the branching misprediction was really slowing down my program )
  • you are doing an (larger) approximation with you max variables: maybe it will improve if you do a finer computation

    def get_nearby_entities(self, entity, radius = None):
        if(not radius):
            radius = self.cell_size
    
        min_x = max(int((entity.position.x - radius) / self.cell_size), 0)
        min_y = max(int((entity.position.y - radius) / self.cell_size), 0)
        max_x = min(int((entity.position.x + radius) / self.cell_size), self.cols)
        max_y = min(int((entity.position.y + radius) / self.cell_size), self.rows)
    
        for y in range(min_y, max_y):
            for x in range(min_x, max_x):
                yield from self.cells[self.cols*y + x].entities
    

Grid entity removal

Maybe instead of actually removing the entities, you could mark them as 'visited' (via a boolean property). It might prevent some heavy memory usage.

\$\endgroup\$
2
  • \$\begingroup\$ (I just realized, that this question is more than a year old...sorry for that) \$\endgroup\$
    – oliverpool
    Dec 15, 2015 at 8:28
  • \$\begingroup\$ Good points anyway :) I'll propably revisit this code at some point for some improvements. \$\endgroup\$
    – warbaque
    Feb 9, 2016 at 2:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.