Optional Pyrex extension for the collision module. More than doubles its speed.

diff --git a/bulletml-runner b/bulletml-runner
index 25fa50b..7c262b0 100755 (executable)
--- a/bulletml-runner
+++ b/bulletml-runner
@@ -8,7 +8,7 @@ import pygame
 
 import bulletml
 import bulletml.bulletyaml
 
 import bulletml
 import bulletml.bulletyaml

-from bulletml.collision import collides
+from bulletml.collision import collides_all

 
 try:
     import yaml
 
 try:
     import yaml


@@ -16,7 +16,7 @@ except ImportError:
     yaml = None
 
 try:
     yaml = None
 
 try:

-    import psyco
+    import psycox

 except ImportError:
     pass
 else:
 except ImportError:
     pass
 else:


@@ -94,7 +94,8 @@ def main(argv):
                         or not (-50 < obj.x < 350)
                         or not (-50 < obj.y < 350)):
                         active.remove(obj)
                         or not (-50 < obj.x < 350)
                         or not (-50 < obj.y < 350)):
                         active.remove(obj)

-                    collides(obj, lactive[0])
+                if lactive:
+                    collides_all(lactive[0], lactive)

                 elapsed = time.time() - start
 
                 frames += 1
                 elapsed = time.time() - start
 
                 frames += 1

diff --git a/bulletml/_collision.pyx b/bulletml/_collision.pyx
new file mode 100644 (file)
index 0000000..2011e98
--- /dev/null
+++ b/bulletml/_collision.pyx
@@ -0,0 +1,182 @@
+"""Optimized collision detection functions."""
+
+def overlaps(a, b):
+    """Return true if two circles are overlapping.
+
+    Usually, you'll want to use the 'collides' method instead, but
+    this one can be useful for just checking to see if the player has
+    entered an area or hit a stationary oject.
+
+    (This function is optimized.)
+
+    """
+
+    cdef float ax
+    cdef float bx
+    cdef float ay
+    cdef float by
+    cdef float dx
+    cdef float dy
+    cdef float radius_a
+    cdef float radius_b
+    cdef float radius
+
+    ax = a.x
+    bx = b.x
+    ay = a.y
+    by = b.y
+
+    dx = ax - bx
+    dy = ay - by
+    try:
+        radius = a.radius
+    except AttributeError:
+        radius = 0.5
+    try:
+        radius += b.radius
+    except AttributeError:
+        radius += 0.5
+
+    return dx * dx + dy * dy <= radius * radius
+
+
+cdef int _collides(float xa, float xb, float ya, float yb,
+               float pxa, float pxb, float pya, float pyb,
+               float radius_a, float radius_b):
+    
+    """Check collision for two moving circles."""
+
+    cdef float dir_x
+    cdef float dir_y
+
+    cdef float diff_x
+    cdef float diff_y
+    cdef float dist_x
+    cdef float dist_y
+
+    cdef float dx
+    cdef float dy
+    cdef float t
+
+    cdef float radius
+
+    radius = radius_a + radius_b
+
+    # Translate b's final position to be relative to a's start.
+    # And now, circle/line collision.
+    dir_x = pxa + (xb - xa) - pxb
+    dir_y = pya + (yb - ya) - pyb
+
+    if (dir_x < 0.0001 and dir_x > -0.0001
+        and dir_y < 0.0001 and dir_y > -0.0001):
+        # b did not move relative to a, so do point/circle.
+        dx = pxb - pxa
+        dy = pyb - pya
+        return dx * dx + dy * dy < radius * radius
+
+    diff_x = pxa - pxb
+    diff_y = pya - pyb
+
+    # dot(diff, dir) / dot(dir, dir)
+    t = (diff_x * dir_x + diff_y * dir_y) / (dir_x * dir_x + dir_y * dir_y)
+    if t < 0:
+        t = 0
+    elif t > 1:
+        t = 1
+
+    dist_x = pxa - (pxb + dir_x * t)
+    dist_y = pya - (pyb + dir_y * t)
+
+    # dist_sq < radius_sq
+    return dist_x * dist_x + dist_y * dist_y <= radius * radius
+
+def collides(a, b):
+    """Return true if the two moving circles collide.
+
+    a and b should have the following attributes:
+
+    x, y - required, current position
+    px, py - not required, defaults to x, y, previous frame position
+    radius - not required, defaults to 0.5
+
+    (This function is optimized.)
+
+    """
+    cdef float xa
+    cdef float xb
+    cdef float ya
+    cdef float yb
+
+    cdef float pxa
+    cdef float pya
+    cdef float pxb
+    cdef float pyb
+
+    cdef float radius_a
+    cdef float radius_b
+
+    xa = a.x
+    xb = b.x
+    ya = a.y
+    yb = b.y
+
+    radius_a = getattr3(a, 'radius', 0.5)
+    radius_b = getattr3(b, 'radius', 0.5)
+
+    pxa = getattr3(a, 'px', xa)
+    pya = getattr3(a, 'py', ya)
+    pxb = getattr3(b, 'px', xb)
+    pyb = getattr3(b, 'py', yb)
+
+    return _collides(xa, xb, ya, yb, pxa, pxb, pya, pyb, radius_a, radius_b)
+
+def collides_all(a, others):
+    """Filter the second argument to those that collide with the first.
+
+    This is equivalent to filter(lambda o: collides(a, o), others),
+    but is much faster when the compiled extension is available (which
+    it is currently).
+
+    """
+    cdef float xa
+    cdef float xb
+    cdef float ya
+    cdef float yb
+
+    cdef float pxa
+    cdef float pya
+    cdef float pxb
+    cdef float pyb
+
+    cdef float radius_a
+    cdef float radius_b
+
+    cdef list bs
+    cdef int length
+
+    cdef list colliding
+
+    cdef int coll
+
+    colliding = []
+
+    xa = a.x
+    ya = a.y
+    radius_a = getattr3(a, 'radius', 0.5)
+    pxa = getattr3(a, 'px', xa)
+    pya = getattr3(a, 'py', ya)
+
+    bs = list(others)
+    length = len(bs)
+
+    for 0 <= i < length:
+        b = others[i]
+        xb = b.x
+        yb = b.y
+        radius_b = getattr3(b, 'radius', 0.5)
+        pxb = getattr3(b, 'px', xb)
+        pyb = getattr3(b, 'py', yb)
+
+        if _collides(xa, xb, ya, yb, pxa, pxb, pya, pyb, radius_a, radius_b):
+            colliding.append(b)
+    return colliding

diff --git a/bulletml/collision.py b/bulletml/collision.py
index f185745..0394ed3 100644 (file)
--- a/bulletml/collision.py
+++ b/bulletml/collision.py
@@ -4,6 +4,9 @@ This module provides simple collision checking appropriate for
 shmups. It provides a routine to check whether two moving circles
 collided during the past frame.
 
 shmups. It provides a routine to check whether two moving circles
 collided during the past frame.
 

+If Pyrex was available when installing, this will used optimized
+versions of the functions.
+

 Basic Usage:
 
     from bulletml.collision import collides
 Basic Usage:
 
     from bulletml.collision import collides


@@ -20,6 +23,8 @@ def overlaps(a, b):
     Usually, you'll want to use the 'collides' method instead, but
     this one can be useful for just checking to see if the player has
     entered an area or hit a stationary oject.
     Usually, you'll want to use the 'collides' method instead, but
     this one can be useful for just checking to see if the player has
     entered an area or hit a stationary oject.

+
+    (This function is unoptimized.)

     """
 
     dx = a.x - b.x
     """
 
     dx = a.x - b.x


@@ -37,6 +42,8 @@ def collides(a, b):
     px, py - not required, defaults to x, y, previous frame position
     radius - not required, defaults to 0.5
 
     px, py - not required, defaults to x, y, previous frame position
     radius - not required, defaults to 0.5
 

+    (This function is unoptimized.)
+

     """
     # Current locations.
     xa = a.x
     """
     # Current locations.
     xa = a.x


@@ -79,3 +86,18 @@ def collides(a, b):
 
     # dist_sq < radius_sq
     return dist_x * dist_x + dist_y * dist_y <= radius * radius
 
     # dist_sq < radius_sq
     return dist_x * dist_x + dist_y * dist_y <= radius * radius

+
+def collides_all(a, others):
+    """Filter the second argument to those that collide with the first.
+
+    This is equivalent to filter(lambda o: collides(a, o), others),
+    but is much faster when the compiled extension is available (which
+    it is not currently).
+
+    """
+    return filter(lambda o: collides(a, o), others)
+
+try:
+    from bulletml._collision import collides, overlaps, collides_all
+except ImportError:
+    pass

diff --git a/setup.py b/setup.py
index 842c7e4..ba5af94 100755 (executable)
--- a/setup.py
+++ b/setup.py
@@ -5,7 +5,9 @@ import os
 import shutil
 import sys
 
 import shutil
 import sys
 

-from distutils.core import setup, Command
+from distutils.core import setup, Command, Extension
+from Pyrex.Distutils import build_ext
+

 from distutils.command.clean import clean as distutils_clean
 from distutils.command.sdist import sdist as distutils_sdist
 
 from distutils.command.clean import clean as distutils_clean
 from distutils.command.sdist import sdist as distutils_sdist
 


@@ -103,8 +105,8 @@ class test_cmd(Command):
             raise SystemExit("Test failures are listed above.")
 
 if __name__ == "__main__":
             raise SystemExit("Test failures are listed above.")
 
 if __name__ == "__main__":

-    setup(cmdclass=dict(
-            clean=clean, test=test_cmd, coverage=coverage_cmd, sdist=sdist),
+    setup(cmdclass=dict(clean=clean, test=test_cmd, coverage=coverage_cmd,
+                        sdist=sdist, build_ext=build_ext),

           name="python-bulletml", version="1",
           url="http://code.google.com/p/python-bulletml/",
           description="parse and run BulletML scripts",
           name="python-bulletml", version="1",
           url="http://code.google.com/p/python-bulletml/",
           description="parse and run BulletML scripts",


@@ -114,6 +116,8 @@ if __name__ == "__main__":
           packages=["bulletml"],
           data_files=glob.glob("examples/*/*.xml") + ["examples/template.xml"],
           scripts=["bulletml-runner", "bulletml-to-bulletyaml"],
           packages=["bulletml"],
           data_files=glob.glob("examples/*/*.xml") + ["examples/template.xml"],
           scripts=["bulletml-runner", "bulletml-to-bulletyaml"],

+          ext_modules=[
+              Extension('bulletml._collision', ['bulletml/_collision.pyx'])],

           long_description="""\
 BulletML is the Bullet Markup Language. BulletML can describe the
 barrage of bullets in shooting games. (For example Progear, Psyvariar,
           long_description="""\
 BulletML is the Bullet Markup Language. BulletML can describe the
 barrage of bullets in shooting games. (For example Progear, Psyvariar,