From 7b73a60799150ec3df407a8a1620a613aad5f59c Mon Sep 17 00:00:00 2001 From: Joe Wreschnig Date: Mon, 22 Mar 2010 22:12:56 -0700 Subject: [PATCH] Optional Pyrex extension for the collision module. More than doubles its speed. --- bulletml-runner | 7 +- bulletml/_collision.pyx | 182 ++++++++++++++++++++++++++++++++++++++++ bulletml/collision.py | 22 +++++ setup.py | 10 ++- 4 files changed, 215 insertions(+), 6 deletions(-) create mode 100644 bulletml/_collision.pyx diff --git a/bulletml-runner b/bulletml-runner index 25fa50b..7c262b0 100755 --- a/bulletml-runner +++ b/bulletml-runner @@ -8,7 +8,7 @@ import pygame import bulletml import bulletml.bulletyaml -from bulletml.collision import collides +from bulletml.collision import collides_all try: import yaml @@ -16,7 +16,7 @@ except ImportError: yaml = None try: - import psyco + import psycox 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) - collides(obj, lactive[0]) + if lactive: + collides_all(lactive[0], lactive) elapsed = time.time() - start frames += 1 diff --git a/bulletml/_collision.pyx b/bulletml/_collision.pyx new file mode 100644 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 --- 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. +If Pyrex was available when installing, this will used optimized +versions of the functions. + 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. + + (This function is unoptimized.) """ 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 + (This function is unoptimized.) + """ # 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 + +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 --- a/setup.py +++ b/setup.py @@ -5,7 +5,9 @@ import os 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 @@ -103,8 +105,8 @@ class test_cmd(Command): 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", @@ -114,6 +116,8 @@ if __name__ == "__main__": 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, -- 2.20.1