pygame is
Python
Simple DirectMedia Layer
 
 
pygame.org is
Site Swing
Quadtree test

Quadtree test - 0.1

Dylan J. Raub (dylanjraub)

Tags:

Description

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.

Links

Home Page: http://www.mediafire.com/?mr4i6th1ldhpbu6

Screenshot


click to view original size

Releases

Quadtree test - 0.1 - Nov 11, 2010

Pygame.org account Comments

If you wish to leave a comment with your pygame.org 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):
x=(self.pos[0]-obj.pos[0])
y=(self.pos[1]-obj.pos[1])
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.
spotlight

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

Oct 16, 2014

Oct 9, 2014

Oct 8, 2014

Oct 7, 2014

Oct 4, 2014

Oct 1, 2014

Sep 19, 2014

Sep 17, 2014

Sep 9, 2014

Sep 8, 2014

Sep 7, 2014

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