From eed0de88f98b23ecb25507b47a507e2791861334 Mon Sep 17 00:00:00 2001 From: Joe Wreschnig Date: Fri, 23 Apr 2010 01:26:33 -0700 Subject: [PATCH] Rewrite collision extension to not require pyrex. Aside from removing the dependency collision checking is >10% faster in simple benchmarks. --- bulletml/__init__.py | 6 +- bulletml/_collision.c | 241 ++++++++++++++++++++++++++++++++++++++++ bulletml/_collision.pyx | 178 ----------------------------- setup.py | 18 +-- 4 files changed, 249 insertions(+), 194 deletions(-) create mode 100644 bulletml/_collision.c delete mode 100644 bulletml/_collision.pyx diff --git a/bulletml/__init__.py b/bulletml/__init__.py index c31dce7..0d4cd94 100644 --- a/bulletml/__init__.py +++ b/bulletml/__init__.py @@ -36,11 +36,11 @@ attributes that can be used to influence it. from bulletml.parser import BulletML from bulletml.impl import Bullet -from bulletml.collision import overlaps, collides +from bulletml.collision import overlaps, collides, collides_all -VERSION = (1,) +VERSION = (2,) VERSION_STRING = ".".join(map(str, VERSION)) __all__ = ["VERSION", "VERSION_STRING", "Bullet", "BulletML", - "overlaps", "collides"] + "overlaps", "collides", "collides_all"] diff --git a/bulletml/_collision.c b/bulletml/_collision.c new file mode 100644 index 0000000..9b220a4 --- /dev/null +++ b/bulletml/_collision.c @@ -0,0 +1,241 @@ +#include "Python.h" + +#define STR_AND_SIZE(s) s, sizeof(s) - 1 +#define DOT(x1, y1, x2, y2) ((x1) * (x2) + (y1) * (y2)) +#define NEARZERO(d) ((d) < 0.0001 && (d) > -0.0001) + +static const char *s_pchModDoc = "Optimized collision detection functions."; + +static PyObject *s_ppykX; +static PyObject *s_ppykY; +static PyObject *s_ppykPX; +static PyObject *s_ppykPY; +static PyObject *s_ppykRadius; + +static const char s_achOverlapsDoc[] = ( + "Return true if two circles are overlapping.\n\n" + "Usually, you\'ll want to use the \'collides\' method instead, but\n" + "this one can be useful for just checking to see if the player has\n" + "entered an area or hit a stationary oject.\n\n" + "(This function is optimized.)\n\n"); + +static const char s_achCollidesDoc[] = ( + "Return true if the two moving circles collide.\n\n" + "The circles should have the following attributes:\n\n" + " x, y - required, current position\n" + " px, py - not required, defaults to x, y, previous frame position\n" + " radius - not required, defaults to 0.5\n\n" + "(This function is optimized.)\n\n"); + +static const char s_achCollidesAllDoc[] = ( + "Filter the second argument to those that collide with the first.\n\n" + "This is equivalent to filter(lambda o: collides(a, o), others),\n" + "but is much faster when the compiled extension is available (which\n" + "it is currently).\n\n"); + +// Get the attributes from a Python moving circle object. +static int GetCircle(PyObject *ppy, double *pdX, double *pdY, + double *pdPX, double *pdPY, double *pdR) +{ + PyObject *ppyf; + + if (!ppy) + return 0; + + ppyf = PyObject_GetAttr(ppy, s_ppykX); + if (ppyf) + { + *pdX = PyFloat_AsDouble(ppyf); + Py_DECREF(ppyf); + } + + ppyf = PyObject_GetAttr(ppy, s_ppykY); + if (ppyf) + { + *pdY = PyFloat_AsDouble(ppyf); + Py_DECREF(ppyf); + } + + // Catch X or Y or failure to convert, any one of the four cases + // is equally fatal. We don't need to check after each one. + if (PyErr_Occurred()) + return 0; + + ppyf = PyObject_GetAttr(ppy, s_ppykPX); + if (ppyf) + { + *pdPX = PyFloat_AsDouble(ppyf); + Py_DECREF(ppyf); + if (PyErr_Occurred()) + return 0; + } + else + { + PyErr_Clear(); + *pdPX = *pdX; + } + + ppyf = PyObject_GetAttr(ppy, s_ppykPY); + if (ppyf) + { + *pdPY = PyFloat_AsDouble(ppyf); + Py_DECREF(ppyf); + if (PyErr_Occurred()) + return 0; + } + else + { + PyErr_Clear(); + *pdPY = *pdY; + } + + ppyf = PyObject_GetAttr(ppy, s_ppykRadius); + if (ppyf) + { + *pdR = PyFloat_AsDouble(ppyf); + Py_DECREF(ppyf); + if (PyErr_Occurred()) + return 0; + } + else + { + PyErr_Clear(); + *pdR = 0.5; + } + + return 1; +} + +static int Collides(double dXA, double dXB, double dYA, double dYB, + double dPXA, double dPXB, double dPYA, double dPYB, + double dRA, double dRB) +{ + // Translate B's position to be relative to A's start. + double dDirX = dPXA + (dXB - dXA) - dPXB; + double dDirY = dPYA + (dYB - dYA) - dPYB; + // Now A doesn't move. Treat B as a point by summing the radii. + double dR = dRA + dRB; + // Now the problem is just circle/line collision. + + double dDiffX = dPXA - dPXB; + double dDiffY = dPYA - dPYB; + + // B didn't move relative to A, so early-out by doing point/circle. + if (NEARZERO(dDirX) && NEARZERO(dDirY)) + return dDiffX * dDiffX + dDiffY * dDiffY <= dR * dR; + else + { + double dT = (DOT(dDiffX, dDiffY, dDirX, dDirY) + / DOT(dDirX, dDirY, dDirX, dDirY)); + double dDistX; + double dDistY; + if (dT < 0.0) dT = 0.0; + else if (dT > 1.0) dT = 1.0; + + dDistX = dPXA - (dPXB + dDirX * dT); + dDistY = dPYA - (dPYB + dDirY * dT); + + return dDistX * dDistX + dDistY * dDistY <= dR * dR; + } +} + +static PyObject *py_overlaps(PyObject *ppySelf, PyObject *ppyArgs) { + double dXA, dYA, dPXA, dPYA, dRA; + double dXB, dYB, dPXB, dPYB, dRB; + PyObject *ppyA, *ppyB; + if (PyArg_ParseTuple(ppyArgs, "OO", &ppyA, &ppyB) + && GetCircle(ppyA, &dXA, &dYA, &dPXA, &dPYA, &dRA) + && GetCircle(ppyB, &dXB, &dYB, &dPXB, &dPYB, &dRB)) + { + double dX = dXA - dXB; + double dY = dYA - dYB; + double dR = dRA + dRB; + + if (dX * dX + dY * dY <= dR * dR) + { + Py_RETURN_TRUE; + } + else + { + Py_RETURN_FALSE; + } + } + else + return NULL; +} + +static PyObject *py_collides(PyObject *ppySelf, PyObject *ppyArgs) +{ + double dXA, dYA, dPXA, dPYA, dRA; + double dXB, dYB, dPXB, dPYB, dRB; + PyObject *ppyA, *ppyB; + if (PyArg_ParseTuple(ppyArgs, "OO", &ppyA, &ppyB) + && GetCircle(ppyA, &dXA, &dYA, &dPXA, &dPYA, &dRA) + && GetCircle(ppyB, &dXB, &dYB, &dPXB, &dPYB, &dRB)) + { + if (Collides(dXA, dXB, dYA, dYB, dPXA, dPXB, dPYA, dPYB, dRA, dRB)) + { + Py_RETURN_TRUE; + } + else + { + Py_RETURN_FALSE; + } + } + else + return NULL; +} + +static PyObject *py_collides_all(PyObject *ppySelf, PyObject *ppyArgs) +{ + double dXA, dYA, dPXA, dPYA, dRA; + PyObject *ppyA, *ppyOthers; + if (PyArg_ParseTuple(ppyArgs, "OO", &ppyA, &ppyOthers) + && GetCircle(ppyA, &dXA, &dYA, &dPXA, &dPYA, &dRA)) + { + PyObject *ppyRet = PyList_New(0); + Py_ssize_t pyszLen = ppyRet ? PySequence_Length(ppyOthers) : -1; + if (pyszLen >= 0) + { + Py_ssize_t sz; + for (sz = 0; sz < pyszLen; sz++) + { + double dXB, dYB, dPXB, dPYB, dRB; + PyObject *ppyB = PySequence_GetItem(ppyOthers, sz); + if (!GetCircle(ppyB, &dXB, &dYB, &dPXB, &dPYB, &dRB)) + { + Py_XDECREF(ppyB); + return NULL; + } + else if (Collides(dXA, dXB, dYA, dYB, dPXA, dPXB, dPYA, dPYB, + dRA, dRB)) + PyList_Append(ppyRet, ppyB); + Py_DECREF(ppyB); + } + return ppyRet; + } + else + return NULL; + } + else + return NULL; +} + +static struct PyMethodDef s_apymeth[] = { + {"overlaps", py_overlaps, METH_VARARGS, s_achOverlapsDoc }, + {"collides", py_collides, METH_VARARGS, s_achCollidesDoc }, + {"collides_all", py_collides_all, METH_VARARGS, s_achCollidesAllDoc }, + {NULL, NULL, 0, NULL} +}; + +PyMODINIT_FUNC init_collision(void) +{ + s_ppykX = PyString_FromStringAndSize(STR_AND_SIZE("x")); + s_ppykY = PyString_FromStringAndSize(STR_AND_SIZE("y")); + s_ppykPX = PyString_FromStringAndSize(STR_AND_SIZE("px")); + s_ppykPY = PyString_FromStringAndSize(STR_AND_SIZE("py")); + s_ppykRadius = PyString_FromStringAndSize(STR_AND_SIZE("radius")); + + if (s_ppykX && s_ppykY && s_ppykPX && s_ppykPY && s_ppykRadius) + Py_InitModule3("bulletml._collision", s_apymeth, s_pchModDoc); +} diff --git a/bulletml/_collision.pyx b/bulletml/_collision.pyx deleted file mode 100644 index b057022..0000000 --- a/bulletml/_collision.pyx +++ /dev/null @@ -1,178 +0,0 @@ -"""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 - - radius_a = getattr3(a, 'radius', 0.5) - radius_b = getattr3(b, 'radius', 0.5) - radius = radius_a + radius_b - - 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/setup.py b/setup.py index 54a86d1..fb4b2e3 100755 --- a/setup.py +++ b/setup.py @@ -6,16 +6,6 @@ import shutil import sys from distutils.core import setup, Command, Extension - -try: - from Pyrex.Distutils import build_ext -except ImportError: - from distutils.command.build_ext import build_ext - ext_modules = [] -else: - ext_modules = [Extension( - 'bulletml._collision', [os.path.join('bulletml', '_collision.pyx')])] - from distutils.command.clean import clean as distutils_clean from distutils.command.sdist import sdist as distutils_sdist @@ -114,8 +104,8 @@ class test_cmd(Command): if __name__ == "__main__": setup(cmdclass=dict(clean=clean, test=test_cmd, coverage=coverage_cmd, - sdist=sdist, build_ext=build_ext), - name="python-bulletml", version="1", + sdist=sdist), + name="python-bulletml", version="2", url="http://code.google.com/p/python-bulletml/", description="parse and run BulletML scripts", author="Joe Wreschnig", @@ -124,7 +114,9 @@ if __name__ == "__main__": packages=["bulletml"], data_files=glob.glob("examples/*/*.xml") + ["examples/template.xml"], scripts=["bulletml-runner", "bulletml-to-bulletyaml"], - ext_modules=ext_modules, + ext_modules=[Extension( + 'bulletml._collision', + [os.path.join('bulletml', '_collision.c')])], long_description="""\ BulletML is the Bullet Markup Language. BulletML can describe the barrage of bullets in shooting games. (For example Progear, Psyvariar, -- 2.30.2