bulletml/_collision.pyx

   1 """Optimized collision detection functions."""
   2
   3 def overlaps(a, b):
   4     """Return true if two circles are overlapping.
   5
   6     Usually, you'll want to use the 'collides' method instead, but
   7     this one can be useful for just checking to see if the player has
   8     entered an area or hit a stationary oject.
   9
  10     (This function is optimized.)
  11
  12     """
  13
  14     cdef float ax
  15     cdef float bx
  16     cdef float ay
  17     cdef float by
  18     cdef float dx
  19     cdef float dy
  20     cdef float radius_a
  21     cdef float radius_b
  22     cdef float radius
  23
  24     ax = a.x
  25     bx = b.x
  26     ay = a.y
  27     by = b.y
  28
  29     dx = ax - bx
  30     dy = ay - by
  31
  32     radius_a = getattr3(a, 'radius', 0.5)
  33     radius_b = getattr3(b, 'radius', 0.5)
  34     radius = radius_a + radius_b
  35
  36     return dx * dx + dy * dy <= radius * radius
  37
  38
  39 cdef int _collides(float xa, float xb, float ya, float yb,
  40                float pxa, float pxb, float pya, float pyb,
  41                float radius_a, float radius_b):
  42
  43     """Check collision for two moving circles."""
  44
  45     cdef float dir_x
  46     cdef float dir_y
  47
  48     cdef float diff_x
  49     cdef float diff_y
  50     cdef float dist_x
  51     cdef float dist_y
  52
  53     cdef float dx
  54     cdef float dy
  55     cdef float t
  56
  57     cdef float radius
  58
  59     radius = radius_a + radius_b
  60
  61     # Translate b's final position to be relative to a's start.
  62     # And now, circle/line collision.
  63     dir_x = pxa + (xb - xa) - pxb
  64     dir_y = pya + (yb - ya) - pyb
  65
  66     if (dir_x < 0.0001 and dir_x > -0.0001
  67         and dir_y < 0.0001 and dir_y > -0.0001):
  68         # b did not move relative to a, so do point/circle.
  69         dx = pxb - pxa
  70         dy = pyb - pya
  71         return dx * dx + dy * dy < radius * radius
  72
  73     diff_x = pxa - pxb
  74     diff_y = pya - pyb
  75
  76     # dot(diff, dir) / dot(dir, dir)
  77     t = (diff_x * dir_x + diff_y * dir_y) / (dir_x * dir_x + dir_y * dir_y)
  78     if t < 0:
  79         t = 0
  80     elif t > 1:
  81         t = 1
  82
  83     dist_x = pxa - (pxb + dir_x * t)
  84     dist_y = pya - (pyb + dir_y * t)
  85
  86     # dist_sq < radius_sq
  87     return dist_x * dist_x + dist_y * dist_y <= radius * radius
  88
  89 def collides(a, b):
  90     """Return true if the two moving circles collide.
  91
  92     a and b should have the following attributes:
  93
  94     x, y - required, current position
  95     px, py - not required, defaults to x, y, previous frame position
  96     radius - not required, defaults to 0.5
  97
  98     (This function is optimized.)
  99
 100     """
 101     cdef float xa
 102     cdef float xb
 103     cdef float ya
 104     cdef float yb
 105
 106     cdef float pxa
 107     cdef float pya
 108     cdef float pxb
 109     cdef float pyb
 110
 111     cdef float radius_a
 112     cdef float radius_b
 113
 114     xa = a.x
 115     xb = b.x
 116     ya = a.y
 117     yb = b.y
 118
 119     radius_a = getattr3(a, 'radius', 0.5)
 120     radius_b = getattr3(b, 'radius', 0.5)
 121
 122     pxa = getattr3(a, 'px', xa)
 123     pya = getattr3(a, 'py', ya)
 124     pxb = getattr3(b, 'px', xb)
 125     pyb = getattr3(b, 'py', yb)
 126
 127     return _collides(xa, xb, ya, yb, pxa, pxb, pya, pyb, radius_a, radius_b)
 128
 129 def collides_all(a, others):
 130     """Filter the second argument to those that collide with the first.
 131
 132     This is equivalent to filter(lambda o: collides(a, o), others),
 133     but is much faster when the compiled extension is available (which
 134     it is currently).
 135
 136     """
 137     cdef float xa
 138     cdef float xb
 139     cdef float ya
 140     cdef float yb
 141
 142     cdef float pxa
 143     cdef float pya
 144     cdef float pxb
 145     cdef float pyb
 146
 147     cdef float radius_a
 148     cdef float radius_b
 149
 150     cdef list bs
 151     cdef int length
 152
 153     cdef list colliding
 154
 155     cdef int coll
 156
 157     colliding = []
 158
 159     xa = a.x
 160     ya = a.y
 161     radius_a = getattr3(a, 'radius', 0.5)
 162     pxa = getattr3(a, 'px', xa)
 163     pya = getattr3(a, 'py', ya)
 164
 165     bs = list(others)
 166     length = len(bs)
 167
 168     for 0 <= i < length:
 169         b = others[i]
 170         xb = b.x
 171         yb = b.y
 172         radius_b = getattr3(b, 'radius', 0.5)
 173         pxb = getattr3(b, 'px', xb)
 174         pyb = getattr3(b, 'py', yb)
 175
 176         if _collides(xa, xb, ya, yb, pxa, pxb, pya, pyb, radius_a, radius_b):
 177             colliding.append(b)
 178     return colliding