[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]
[pygame] [sprite.py] BUG + fix for collide_circle methods
Hi
today I got that on #pygame on IRC:
10:33:20 FSatzger | Hi @all
10:33:52 FSatzger | i don't want to subscribe to the mailing list/bugtracker, but i've got a
bugreport along with a fix for it
10:36:47 FSatzger | it's located in sprite.py, function collide_circle
10:37:22 FSatzger | there, it's assumed that x**2+y**2==(x+y)**2 which is clearly wrong
10:38:11 FSatzger | so the return value should be "return distancesquared<
(math.sqrt(leftradiussquared) + math.sqrt(rightradiussquared))**2" instead
of "return distancesquared< leftradiussquared + rightradiussquared" and of
course, math must be imported
10:42:08 ---| User: *** okayzed is now known as okay
10:43:07 masquerade | FSatzger: I think you're possibly misunderstanding what's happening there
10:47:03 masquerade | Yeah. I looked at it, and the code as is written is correct
10:47:17 masquerade | And it doesn't assume x^2+y^2=(x+y)^2
10:47:28 FSatzger | ok then, could you please tell me what's going on here?
10:47:43 masquerade | Sure.
10:47:49 FSatzger | i assumed, that this function tries to find a collision between 2 circles
10:47:56 masquerade | It does
10:48:01 FSatzger | so if 2 circles intersect, it should fire
10:48:07 FSatzger | sorry, but it does not
10:48:19 masquerade | distancesquared is the distance between the center of the two circles
10:48:20 FSatzger | i acutally tried it - that was why i even searched for a "bug"
10:48:30 FSatzger | that's right
10:49:12 masquerade | oh, hmm, actually, let me think for one second
10:49:28 FSatzger | but i think, that distance should be< radius1+radius2 for this function to
fire
10:49:35 masquerade | I guess it should be checking if dist< r1+r2
10:49:39 FSatzger | right
10:49:43 FSatzger | thats what i thougt
10:49:46 FSatzger | +h
10:50:06 masquerade | Then yeah, you're right, sorry
10:50:07 FSatzger | but what is actually checked is, if distance**2< r1**2+r2**2
10:50:13 FSatzger | okay :)
10:50:26 FSatzger | could you please fix it or submit some "formal" bug report
10:51:05 FSatzger | i already proposed a working fix up there :)
10:51:57 masquerade | Yeah. Just wondering if it's the quickest way in terms of speed
10:52:09 FSatzger | yeah i already thought about that, too
10:52:24 FSatzger | it's actually a bit slow, if you got a precalculated radius
10:52:45 FSatzger | but it should be the fastest way if you use two sprites without "radius"
defined
10:53:06 FSatzger | or better said, it should be the only possibility (except for some sin/cos
;))
10:54:01 ---| ---> DR0ID_ [~DR0ID_@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx] has joined #pygame
10:54:14 ---| ---> DR0ID__ [~DR0ID_@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx] has joined #pygame
10:56:18 masquerade | yeah, not too much better
10:56:21 masquerade | which is a bit of a shame
10:56:44 correctinos | tell DR0ID__
10:56:46 correctinos | he's your man
10:56:49 correctinos | if anyone is
10:56:59 masquerade | Yeah. I'm not on the bugtracker or ml either
10:58:41 FSatzger | k, I have to go for some time, I'll come back later
10:59:24 ---|<<-- DR0ID__ [~DR0ID_@xxxxxxxxxxxxxxxxxxxxxxxxxxxxx] has quit (Ping
So I took a look at sprite.py at the collide_circle methods. It turns
out that FSatzger was correct! I have redone the math (see below for the
interested) and fixed the methods in sprite. Attached is the patch,
please review and/or apply to trunk (its against revision 3163).
Thanks!
~DR0ID
Math derivation:
Assuming two circles with centers at c1 and c2 and radii r1 and r2:
# distance vector
d = c2 - c1
# length of the distance vector
l = sqrt(dx**2 + dy**2)
# length squared
l**2 = dx**2 + dy**2
# collision condition (non squared), the '=' case is when they are
touching but not intersecting
if l <= r1 + r2:
collide(circle1, circle2)
# collision condition using squared distance and radii
if l**2 <= (r1 + r2) ** 2:
collide(circle1, circle2)
# calculate the diagonal of a rect
diag = sqrt(a**2 + b**2) = (a**2 + b**2) ** 0.5
# caculcating the half diagonal
half_diag = diag / 2 = sqrt(a**2 + b**2) / 2 = sqrt((a**2)/4
+ (b**2)/4) = sqrt((a/2)**2 + (b/2)**2)
# NOTES:
0.5 * x == x / 2
sqrt(x) == x ** 0.5
Index: lib/sprite.py
===================================================================
--- lib/sprite.py (revision 3163)
+++ lib/sprite.py (working copy)
@@ -1337,7 +1337,7 @@
return leftrect.colliderect(rightrect)
-def collide_circle( left, right ):
+def collide_circle(left, right):
"""detect collision between two sprites using circles
pygame.sprite.collide_circle(left, right): return bool
@@ -1357,17 +1357,27 @@
xdistance = left.rect.centerx - right.rect.centerx
ydistance = left.rect.centery - right.rect.centery
distancesquared = xdistance ** 2 + ydistance ** 2
- try:
- leftradiussquared = left.radius ** 2
- except AttributeError:
+
+ if hasattr(left, 'radius'):
+ leftradius = left.radius
+ else:
leftrect = left.rect
- leftradiussquared = (leftrect.width ** 2 + leftrect.height ** 2) / 4
- try:
- rightradiussquared = right.radius ** 2
- except AttributeError:
+ # approximating the radius of a square by using half of the diagonal,
+ # might give false positives (especially if its a long small rect)
+ leftradius = 0.5 * ((leftrect.width ** 2 + leftrect.height ** 2) ** 0.5)
+ # store the radius on the sprite for next time
+ setattr(left, 'radius', leftradius)
+
+ if hasattr(right, 'radius'):
+ rightradius = right.radius
+ else:
rightrect = right.rect
- rightradiussquared = (rightrect.width ** 2 + rightrect.height ** 2) / 4
- return distancesquared < leftradiussquared + rightradiussquared
+ # approximating the radius of a square by using half of the diagonal
+ # might give false positives (especially if its a long small rect)
+ rightradius = 0.5 * ((rightrect.width ** 2 + rightrect.height ** 2) ** 0.5)
+ # store the radius on the sprite for next time
+ setattr(right, 'radius', rightradius)
+ return distancesquared <= (leftradius + rightradius) ** 2
class collide_circle_ratio(object):
"""detect collision between two sprites using scaled circles
@@ -1386,14 +1396,15 @@
The given ratio is expected to be a floating point value used to scale
the underlying sprite radius before checking for collisions.
+
+ When the ratio is ratio=1.0, then it behaves exactly like the
+ collide_circle method.
"""
self.ratio = ratio
- # Constant value that folds in division for diameter to radius,
- # when calculating from a rect.
- self.halfratio = ratio ** 2 / 4.0
- def __call__( self, left, right ):
+
+ def __call__(self, left, right):
"""detect collision between two sprites using scaled circles
pygame.sprite.collide_circle_radio(ratio)(left, right): return bool
@@ -1413,32 +1424,25 @@
xdistance = left.rect.centerx - right.rect.centerx
ydistance = left.rect.centery - right.rect.centery
distancesquared = xdistance ** 2 + ydistance ** 2
- # Optimize for not containing radius attribute, as if radius was
- # set consistently, would probably be using collide_circle instead.
+
if hasattr(left, "radius"):
- leftradiussquared = (left.radius * ratio) ** 2
-
- if hasattr(right, "radius"):
- rightradiussquared = (right.radius * ratio) ** 2
- else:
- halfratio = self.halfratio
- rightrect = right.rect
- rightradiussquared = (rightrect.width ** 2
- + rightrect.height ** 2) * halfratio
+ leftradius = left.radius * ratio
else:
- halfratio = self.halfratio
leftrect = left.rect
- leftradiussquared = (leftrect.width ** 2
- + leftrect.height ** 2) * halfratio
+ leftradius = ratio * 0.5 * ((leftrect.width ** 2 + leftrect.height ** 2) ** 0.5)
+ # store the radius on the sprite for next time
+ setattr(left, 'radius', leftradius)
- if hasattr(right, "radius"):
- rightradiussquared = (right.radius * ratio) ** 2
- else:
- rightrect = right.rect
- rightradiussquared = (rightrect.width ** 2
- + rightrect.height ** 2) * halfratio
- return distancesquared < leftradiussquared + rightradiussquared
+ if hasattr(right, "radius"):
+ rightradius = right.radius * ratio
+ else:
+ rightrect = right.rect
+ rightradius = ratio * 0.5 * ((rightrect.width ** 2 + rightrect.height ** 2) ** 0.5)
+ # store the radius on the sprite for next time
+ setattr(right, 'radius', rightradius)
+ return distancesquared <= (leftradius + rightradius) ** 2
+
def collide_mask(left, right):
"""collision detection between two sprites, using masks.