[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[pygame] Observations on collisions
Hi,
Recently, I did some benchmarking on the various ways to do Rect collision detections using Pygame. I mentioned some of
this on the IRC channel a couple weeks ago, and they said that some of you on this list may be interested.
In the past, I have always stored the location of my sprites in a ((x, y), (w, h)) tuple, in a .rect attribute, because
I knew Pygame would automatically convert these to Rects as needed. It occured to me that it may be more efficient to
instead store them as actual Rects, so I decided to do some testing.
I got some surprising results, so I did more testing, and here's what I found when colliding a single item against 100
items (with 100 000 interations):
a rect and a list of tuples 1.12 seconds, 5.9x
a rect and a list of objects containg tuples 3.19 seconds, 16.9x
a rect and a list of rects 0.19 seconds, 1.0x
a rect and a list of subclassed rects 1.00 seconds, 5.3x
a rect and a list of objects containing rects 2.19 seconds, 11.6x
a sprite and a group of sprites 1.70 seconds, 9.0x
a sprite and an ordered group of sprites 1.55 seconds, 8.2x
The fastest way to do collisions was to do a Rect.collidelistall(). The surprising thing to me was how much slower my
chosen method was (Storing tuple in the .rect attributes of my classes). Up to twenty times slower on some tests.
Other things I found interesting:
Using the collisions offered by the Sprite class is convenient, but quite slow.
Subclassing the Rect and using that for your own sprites causes quite a loss of speed (5x slower).
The extra lookup to extract the .rect attribute from an object is quite expensive in Python.
Creating a (pos, size) tuple is marginally slower than creating a Rect, but the advantages of the Rect far outweigh that
cost.
Conclusions:
Well, testing shows I was doing things The Wrong Way (tm) :) A lot of this is probably familiar to those of you who are
familiar with Pygame internals, but the scale of the difference was a shock to me. The relative advantage of the list of
Rects improves even more as you add more objects to collide with. At 200 objects, it was 20x times faster the my
original method.
There is also the issue of /relevance/. Collision probably aren't the biggest slice of your game's time, but if you are
aiming for 60 FPS, my method was eating up 3.2 milliseconds each frame. That's a significant proportion of the 16ms budget.
I have attached the code that produced these results.
Regards,
Peter Finlayson
#!/usr/bin/python -u
"""Test the performance of the various ways to do collisions
Usage: collision-test.py [count] [iterations] [repeat]
"""
from __future__ import division
import sys
import os
import random
from timeit import Timer
import pygame
count = 100
iterations = 100000
repeat = 2
filename = None
tuple_list = []
tuple_obj_list = []
rect_list = []
rect_obj_list = []
rect_subclass_list = []
sprite_group = pygame.sprite.Group()
ordered_sprite_group = pygame.sprite.OrderedUpdates()
# classes
class TestTuple(object):
"""Used in testing the performance of a tuple used as a .rect"""
def __init__(self, x, y, w, h):
self.rect = ((x, y), (w, h))
class TestRect(object):
"""Used in testing the performance of a tuple used as a .rect"""
def __init__(self, x, y, w, h):
self.rect = pygame.Rect(x, y, w, h)
class TestRectSubclass(pygame.Rect):
def __init__(self, x, y=None, w=None, h=None):
if y is None:
# pygame.Rect(object)
pygame.Rect.__init__(self, x)
elif w is None:
# pygame.Rect((left, top), (width, height))
pygame.Rect.__init__(self, x, y)
else:
# pygame.Rect(left, top, width, height)
pygame.Rect.__init__(self, x, y, w, h)
hp = 100
# test functions
def test_tuples(iterations, repeat):
"""a rect and a list of tuples"""
setup = """from __main__ import tuple_list, rect_target"""
t = Timer("rect_target.collidelistall(tuple_list)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_tuples_obj(iterations, repeat):
"""a rect and a list of objects containg tuples"""
setup = """from __main__ import tuple_obj_list, rect_target"""
t = Timer("rect_target.collidelistall(tuple_obj_list)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_rects(iterations, repeat):
"""a rect and a list of rects"""
setup = """from __main__ import rect_list, rect_target"""
t = Timer("rect_target.collidelistall(rect_list)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_rects_obj(iterations, repeat):
"""a rect and a list of objects containing rects"""
setup = """from __main__ import rect_obj_list, rect_target"""
t = Timer("rect_target.collidelistall(rect_obj_list)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_rects_subclass(iterations, repeat):
"""a rect and a list of subclassed rects"""
setup = """from __main__ import rect_subclass_list, rect_target"""
t = Timer("rect_target.collidelistall(rect_subclass_list)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_sprites(iterations, repeat):
"""a sprite and a group of sprites"""
setup = """from __main__ import pygame, sprite_group, sprite_target"""
t = Timer("pygame.sprite.spritecollide(sprite_target, sprite_group, dokill=False)", setup)
return t.repeat(number=iterations, repeat=repeat)
def test_ordered_sprites(iterations, repeat):
"""a sprite and an ordered group of sprites"""
setup = """from __main__ import pygame, ordered_sprite_group, sprite_target"""
t = Timer("pygame.sprite.spritecollide(sprite_target, ordered_sprite_group, dokill=False)", setup)
return t.repeat(number=iterations, repeat=repeat)
def main():
print("Using a list of %d entries and %d iterations repeated %d times:" % (count, iterations, repeat))
tests = (test_tuples,
test_tuples_obj,
test_rects,
test_rects_subclass,
test_rects_obj,
test_sprites,
test_ordered_sprites)
average_results = {}
# run the tests
max_name_len = 0
for test_func in tests:
test_name = test_func.__doc__
print("Testing %s..." % test_name)
max_name_len = max((max_name_len, len(test_name)))
results = test_func(iterations, repeat)
for result in results:
print("Result: %f seconds" % result)
average_results[test_func] = sum(results) / len(results)
print("")
# calculate some stats
min_result = min(average_results.values())
print("Time factors:")
for test_func in tests:
test_name = test_func.__doc__
print("%s\t%0.2f seconds,\t%0.1fx" % \
(test_name.ljust(max_name_len, " "),
average_results[test_func],
average_results[test_func] / min_result))
# write the output file
if filename is not None:
print("")
print("Writing results to file '%s'" % filename)
lines = []
if not os.path.isfile(filename):
lines.append("count,")
lines.append(",".join([ '"%s"' % x.__doc__ for x in tests]) + "\n")
lines.append("%d," % count)
lines.append(",".join([ str(average_results[x]) for x in tests ]) + "\n")
with open(filename, "a") as f:
f.writelines(lines)
if __name__ == "__main__":
# check the command line
try:
if len(sys.argv) >= 2:
count = int(sys.argv[1])
if len(sys.argv) >= 3:
iterations = int(sys.argv[2])
if len(sys.argv) >= 4:
repeat = int(sys.argv[3])
if len(sys.argv) >= 5:
filename = sys.argv[4]
except ValueError:
print(" *** Error processing command line")
raise
# prepare the data
for i in range(count):
# make the bulk data
x, y, w, h = random.randint(0, 1024), random.randint(0,768), 32, 32
tuple_list.append( ((x,y), (w,h)) )
tuple_obj_list.append(TestTuple( x, y, w,h))
rect_list.append(pygame.Rect(x, y, w, h))
rect_obj_list.append(TestRect(x, y, w, h))
rect_subclass_list.append(TestRectSubclass(x, y, w, h))
spr = pygame.sprite.Sprite(sprite_group, ordered_sprite_group)
spr.rect = pygame.Rect(x, y, w, h)
# make the data to be checked against
x, y, w, h = random.randint(0, 1024), random.randint(0,768), 32, 32
rect_target = pygame.Rect(x, y, w, h)
sprite_target = pygame.sprite.Sprite()
sprite_target.rect = rect_target
main()