pygame is
Simple DirectMedia Layer is
Site Swing
Quadtree test

Quadtree test - 0.1

Dylan J. Raub (dylanjraub)



A simple example of how you can use quadtrees to speed up simulations. Quadtrees can be use for more then just collision detection, even though that's it's primary use. It can be used for rendering, compressing, sorting, and more.


Home Page:


click to view original size


Quadtree test - 0.1 - Nov 11, 2010 account Comments

If you wish to leave a comment with your account, please sign in first.

November 14, 2010 1:38pm - Shanti Pothapragada - nickname: (rgbdreamer)
geometrian- x**.5 runs slower than math.sqrt(x) for me. Any sqrt is much slower than any square, so replacing it with a square where possible is better. Also, for most game applications, we don't need precision past a few places, so writing your own, sloppy sqrt function (and sin, cos, etc!) can pay off.

raubana- sqrt((x1-x2)**2 + (y1-yx)**2) < r --> (x1-x2)**2 + (y1-yx)**2 < r**2:
def collide(self, obj):
dist = x**2 + y**2
if dist <= (self.radius + obj.radius)**2 and dist!=0:
#we collided, act apon it
November 12, 2010 12:08pm - Ian Mallett - nickname: (geometrian)
Excellent work!
math.sqrt(whatever) is slow. Try using whatever**0.5. Also, instead of whatever**2, try whatever*whatever.
November 11, 2010 5:19pm - Dylan J. Raub - nickname: (dylanjraub)
Could you please post what the code now looks like? (Just the parts you changed)
November 11, 2010 4:13pm - Shanti Pothapragada - nickname: (rgbdreamer)
I tried tweaking your code by squaring both sides of your collision test (to remove the slow sqrt operation), and the performance got way worse- my final framerate drops from ~23 to ~1, and it stops after 2 divisions instead of after 4. Out of context, python does the math almost twice as fast without the sqrt.

Do you know what's happening?
November 11, 2010 3:32pm - Shanti Pothapragada - nickname: (rgbdreamer)
Sweet stuff! Right now collisions aren't my biggest slow-down, but I'll definitely be revisiting this when I get to doing more optimization.

our projects welcomes all python game, art, music, sound, video and multimedia projects. If they use pygame or not.
recent releases
Aug 26, 2014

Aug 22, 2014

Aug 21, 2014

Aug 19, 2014

Aug 18, 2014

Aug 2, 2014

Jul 28, 2014

Jul 22, 2014

Jul 21, 2014

Jul 20, 2014

... more!
for pygame related questions, comments, and suggestions, please see help (lists, irc)