RE: [pygame] 2D Vector Class
I'm a little lost on this... Someone wants a 2D vector class? I use the following I built after wrestling with the NeHe particle tutorial: class Vector2D(object): def __init__(self, x, y): self.x = x self.y = y def __add__(self, v): return Vector2D(float(self.x + v.x), float(self.y + v.y)) def __sub__(self, v): return Vector2D(float(self.x - v.x), float(self.y - v.y)) class Vector3D(Vector2D): def __init__(self, x, y, z): super(Vector3D, self).__init__(x, y) self.z = z def __add__(self, v): return Vector3D(float(self.x + v.x), float(self.y + v.y), float(self.z + v.z)) def __sub__(self, v): return Vector3D(float(self.x - v.x), float(self.y - v.y), float(self.z - v.z)) ---snip--- v1 = Vector3D(1.0, 1.0, 1.0) v2 = Vector3D(2.0, 2.0, 2.0) v3 = v1 - v2 print v3.x, v3.y, v3.z >>> -1.0, -1.0, -1.0 ---snip--- These allow me to add/subtract instances of a Vector3D class and get a Vector3D class in return. I only have add and subtract on these methods, but I could easily extend them by using the information at http://docs.python.org/ref/customization.html and http://docs.python.org/lib/module-operator.html to add more math methods. As I say, I'm a little lost and confused... I put this down to Delta/Atlanta airport yesterday and a funtastic trip from Oregon to Florida. Ignore me. -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Greg Ewing Sent: Wednesday, May 16, 2007 23:41 To: pygame-users@seul.org Subject: Re: [pygame] 2D Vector Class Ulf Ekström wrote: > > That [complex number trick] seems very smart, and I imagine it is very fast... > > Yes, and you get fast rotations with just a multiply. Only for 2D, though... unless we can persuade Guido to put quaternions in the core... :-) -- Greg Ewing, Computer Science Dept, +--+ University of Canterbury, | Carpe post meridiem! | Christchurch, New Zealand | (I'm not a morning person.) | [EMAIL PROTECTED] +--+ CONFIDENTIAL NOTICE: This email including any attachments, contains confidential information belonging to the sender. It may also be privileged or otherwise protected by work product immunity or other legal rules. This information is intended only for the use of the individual or entity named above. If you are not the intended recipient, you are hereby notified that any disclosure, copying, distribution or the taking of any action in reliance on the contents of this emailed information is strictly prohibited. If you have received this email in error, please immediately notify us by reply email of the error and then delete this email immediately.
Re: [pygame] 2D Vector Class
Ulf Ekström wrote: > That [complex number trick] seems very smart, and I imagine it is very fast... Yes, and you get fast rotations with just a multiply. Only for 2D, though... unless we can persuade Guido to put quaternions in the core... :-) -- Greg Ewing, Computer Science Dept, +--+ University of Canterbury, | Carpe post meridiem! | Christchurch, New Zealand | (I'm not a morning person.) | [EMAIL PROTECTED] +--+
Re: [pygame] 2D Vector Class
thanks :) On 5/17/07, Alex Holkner <[EMAIL PROTECTED]> wrote: Here's the head of the thread: http://aspn.activestate.com/ASPN/Mail/Message/pygame-users/3231069 and here are those benchmarks I was talking about: http://aspn.activestate.com/ASPN/Mail/Message/pygame-users/3233961 Alex. On 17/05/2007, at 10:06 AM, René Dudfield wrote: > Have you got a link to that thread? or do you remember the subject? > > On 5/17/07, Alex Holkner <[EMAIL PROTECTED]> wrote: >> >> >> >> >> >> So, I've been working on a simple physics system, and have gotten >> to the >> point where passing around a tuple just isn't cutting it. Can anybody >> suggest a good 2D vector implementation?This thread came up >> sometime last >> year, and several implementations were put forward. >> >> If you're happy to put all of your vectors into a single numpy/ >> numeric >> array, that is the fastest approach. >> >> CGKit (http://cgkit.sourceforge.net/) is a C extension which is >> the fastest >> vector-is-an-object implementation. Unless things have changed >> recently >> though, this library is a nightmare to compile and install. >> >> For pure Python, the fastest implementation is my euclid module: >> http://partiallydisassembled.net/euclid.html (some >> comparison results were posted in the previous thread). >> >> Cheers >> Alex. >
Re: [pygame] 2D Vector Class
Here's the head of the thread: http://aspn.activestate.com/ASPN/Mail/Message/pygame-users/3231069 and here are those benchmarks I was talking about: http://aspn.activestate.com/ASPN/Mail/Message/pygame-users/3233961 Alex. On 17/05/2007, at 10:06 AM, René Dudfield wrote: Have you got a link to that thread? or do you remember the subject? On 5/17/07, Alex Holkner <[EMAIL PROTECTED]> wrote: So, I've been working on a simple physics system, and have gotten to the point where passing around a tuple just isn't cutting it. Can anybody suggest a good 2D vector implementation?This thread came up sometime last year, and several implementations were put forward. If you're happy to put all of your vectors into a single numpy/ numeric array, that is the fastest approach. CGKit (http://cgkit.sourceforge.net/) is a C extension which is the fastest vector-is-an-object implementation. Unless things have changed recently though, this library is a nightmare to compile and install. For pure Python, the fastest implementation is my euclid module: http://partiallydisassembled.net/euclid.html (some comparison results were posted in the previous thread). Cheers Alex.
Re: [pygame] 2D Vector Class
Have you got a link to that thread? or do you remember the subject? On 5/17/07, Alex Holkner <[EMAIL PROTECTED]> wrote: So, I've been working on a simple physics system, and have gotten to the point where passing around a tuple just isn't cutting it. Can anybody suggest a good 2D vector implementation?This thread came up sometime last year, and several implementations were put forward. If you're happy to put all of your vectors into a single numpy/numeric array, that is the fastest approach. CGKit (http://cgkit.sourceforge.net/) is a C extension which is the fastest vector-is-an-object implementation. Unless things have changed recently though, this library is a nightmare to compile and install. For pure Python, the fastest implementation is my euclid module: http://partiallydisassembled.net/euclid.html (some comparison results were posted in the previous thread). Cheers Alex.
Re: [pygame] 2D Vector Class
So, I’ve been working on a simple physics system, and have gotten to the point where passing around a tuple just isn’t cutting it. Can anybody suggest a good 2D vector implementation? This thread came up sometime last year, and several implementations were put forward. If you're happy to put all of your vectors into a single numpy/ numeric array, that is the fastest approach. CGKit (http://cgkit.sourceforge.net/) is a C extension which is the fastest vector-is-an-object implementation. Unless things have changed recently though, this library is a nightmare to compile and install. For pure Python, the fastest implementation is my euclid module: http://partiallydisassembled.net/euclid.html (some comparison results were posted in the previous thread). Cheers Alex.
Re: [pygame] 2D Vector Class
Hi > This looks a bit slow, but on the other hand it has support for > operations I didn't even know I wanted to do on 2-vectors. > I've changed it since to use slots (stole that idea from somebody else who posted about vector classes on the mailing list) and slots is much much faster on 2.5. I'll probably update that wiki thing with that version when I'm at home. Ok, great! as far as it having lots of vector functions (like projection & interpolation), that is very deliberate. I find it results in highly readable code when doing a lot of vector operations, because the code is much shorter and appropriate math terms are used (cause they are the function names) I guess this is a matter of taste, I prefer writing z = (1-w)*x + w*y to z = x.interpolate_to(y,w) because in the first case I can see exactly what is going on. But of course the existence of interpolate_to() doesn't stop me from using the explicit formula. > looks like it doesn't support vector scaling, which is a bit of a > bummer; one reason for me to have 2-vectors is so that I can write > That code actually supports multiplication by a scalar just fine. The typeerror except falls through to scalar operations after trying a vector op with array indexing. I think the version of that code that I actually use now is much clearer about how that happens though (checking for an indexing op is faster than the try/except) Aha, ok, I am sorry. I should have tested the code before I wrote that. Getting rid of the exceptions sounds like a good idea. [snip] You're not bashing anyone. I am curious though - what qualifies as "designed for physics"? Since you have a lot of element-wise operations it looked more like a vector class for color blending or something like that, but then again I didn't understand that it could do scalar*vector multiplication, and that was my main complaint. With "designed for physics" I ment to mainly support operations which you see in a typical physics textbook. Element-wise operations are not really used when you think of vectors as physical quantities (because such operations are basis dependent), so the vector*vector operation could be defined to be the dot product, for example. But maybe it is more clear to have a .dot() method for this. Defining __abs__() to be the norm of the vector instead of the vector of absolute values of the components is another thing. > The complex number trick was very clever! > That seems very smart, and I imagine it is very fast... Yes, and you get fast rotations with just a multiply. I wonder if there is a good way to keep it fast, but also let you mix the vectors with tuples, i.e.: a = vector2(3,5) b = a + (2,2) and have that work/make sense... That would be nice. Maybe this particular syntax doesn't have to be so fast, I imagine it would mostly be used in initalization. If you are adding (2,2) a lot it's not so much work to give it a name and make it a vector2 object. Regards, Ulf
Re: [pygame] 2D Vector Class
On 5/16/07, Ulf Ekström <[EMAIL PROTECTED]> wrote: > So far I"ve found this one on the wiki (anybody know who wrote this?): > I posted the one on the wiki This looks a bit slow, but on the other hand it has support for operations I didn't even know I wanted to do on 2-vectors. I've changed it since to use slots (stole that idea from somebody else who posted about vector classes on the mailing list) and slots is much much faster on 2.5. I'll probably update that wiki thing with that version when I'm at home. as far as it having lots of vector functions (like projection & interpolation), that is very deliberate. I find it results in highly readable code when doing a lot of vector operations, because the code is much shorter and appropriate math terms are used (cause they are the function names) looks like it doesn't support vector scaling, which is a bit of a bummer; one reason for me to have 2-vectors is so that I can write That code actually supports multiplication by a scalar just fine. The typeerror except falls through to scalar operations after trying a vector op with array indexing. I think the version of that code that I actually use now is much clearer about how that happens though (checking for an indexing op is faster than the try/except) I don't mean to bash the author of that code, but a fast vector implementation which is designed for "physics" would be nice to have. You're not bashing anyone. I am curious though - what qualifies as "designed for physics"? The complex number trick was very clever! That seems very smart, and I imagine it is very fast... I wonder if there is a good way to keep it fast, but also let you mix the vectors with tuples, i.e.: a = vector2(3,5) b = a + (2,2) and have that work/make sense...
Re: [pygame] 2D Vector Class
Ulf Ekström wrote: >> I wrote a physics system using Numeric. It still wasn't fast enough. > > Do you know exactly what made it slow? Do you think it can be worked > around assuming we have fast vector operations? The way I wrote it, Numeric gave me the fast vector operations. It's in the cookbook if you want to see: http://www.pygame.org/wiki/2DGeometryEngine?parent=CookBook . Each point is stored in one big Numeric array, to which all operations are done at once. The problem with doing things that way is -- well, consider an if statement in Python. if Condition: return f(x) else: return g(x) In Numeric, the easiest way to do this is: f = ufuncs.sin(x) # or some other complicated operation g = ufuncs.cos(x) return choose(Condition, f, g) In other words, in Python you operate element-by-element and compute one or the other, but in Numeric you compute both options for all elements and pick one or the other for each element. I think that's probably why it was slow. I don't think you'll be able to get much better performance out of a pure-Python physics engine *especially* if you get fast vector operations -- the reason I tried this approach was because Greg Ewing pointed out (quite rightly, I think) that working element-at-a-time in Python is just not going to be fast enough. I also wrote a pure-Python element-by-element physics engine which was even slower than this, but I never tried using AABBs or other optimizations, so maybe you could do it if you really wanted to. I don't think it's worth it when ODE is out there, though. Ethan signature.asc Description: OpenPGP digital signature
Re: [pygame] 2D Vector Class
On 5/16/07, Ethan Glasser-Camp <[EMAIL PROTECTED]> wrote: John Krukoff wrote: > I'd guess that numeric/numpy is probably a good way to do this too, but > I've been trying to avoid pulling that in as a dependency. How about making a very simple C library, which only does vectors of doubles? I am thinking of a basic class that supports addition, subtraction, scaling and dot product for arbitrary length vectors. Then this could be used for implementing 2d and 3d vectors in Python, with the more geometrical operations implemented in python. This would be some kind of light weight numeric, I guess. I wrote a physics system using Numeric. It still wasn't fast enough. Do you know exactly what made it slow? Do you think it can be worked around assuming we have fast vector operations? Regards, Ulf
Re: [pygame] 2D Vector Class
John Krukoff wrote: > I’d guess that numeric/numpy is probably a good way to do this too, but > I’ve been trying to avoid pulling that in as a dependency. I wrote a physics system using Numeric. It still wasn't fast enough. Now I use ODE, and I'd recommend it (or something like it) if you need physics in your game -- anything more than spritecollide, basically. It doesn't have vectors, which is what you actually asked for, but I thought I'd chime in anyhow. Ethan signature.asc Description: OpenPGP digital signature
Re: [pygame] 2D Vector Class
Hi So, I've been working on a simple physics system, and have gotten to the point where passing around a tuple just isn't cutting it. Can anybody suggest a good 2D vector implementation? Unfortunately not, but if you are interested in collaborating on a little C/Python library for these kind of things please send me an email. So far I"ve found this one on the wiki (anybody know who wrote this?): http://www.pygame.org/wiki/2DVectorClass This looks a bit slow, but on the other hand it has support for operations I didn't even know I wanted to do on 2-vectors. It also looks like it doesn't support vector scaling, which is a bit of a bummer; one reason for me to have 2-vectors is so that I can write r += dt*v, where dt is a float and r and v are vectors. I don't mean to bash the author of that code, but a fast vector implementation which is designed for "physics" would be nice to have. The complex number trick was very clever! Regards, Ulf
Re: [pygame] 2D Vector Class
I implemented one but then found it to be a bit of a performance hotspot. I switched to using complex numbers instead which work wonderfully. I added a small amount of abstraction around them so that other code could remain ignorant of that implementation detail. Here's an excerpt from my vector.py module (no external dependancies): import math import cmath vector2 = complex length = abs def to_tuple(vector): return (vector.real, vector.imag) def radians(vector): return math.atan2(vector.imag, vector.real) def unit(radians): return cmath.exp(radians * 1j) def normal(vector): L = length(vector) if L == 0: return vector2() else: return vector / L def clamp(vector, max_length): L = length(vector) if L > max_length: return vector * (max_length / L) else: return vector def distance(vector1, vector2): return length(vector1 - vector2) hth, -Casey On May 16, 2007, at 12:25 PM, John Krukoff wrote: So, I’ve been working on a simple physics system, and have gotten to the point where passing around a tuple just isn’t cutting it. Can anybody suggest a good 2D vector implementation? So far I”ve found this one on the wiki (anybody know who wrote this?): http://www.pygame.org/wiki/2DVectorClass And this one as part of the game objects library on Will McGugan’s blog, which also comes with a standalone matrix implementation: http://www.willmcgugan.com/game-objects/ I’d guess that numeric/numpy is probably a good way to do this too, but I’ve been trying to avoid pulling that in as a dependency. - John Krukoff [EMAIL PROTECTED]
Re: [pygame] 2D vector class more tests
Hi
I just wondered what the fastest way would be and joined the vector fun.
I did some more test with interessting result:
To be fast write your class as explicit (and simple) as possible. As
someone stated befor, dont make any if's or try..catch in your method,
that will slow it down even more.
I can not confirm that the math operators from the operators module are
faster than the built in one (I think because of the added function
overhead?).
The overhead of the map() function is too big for 2d vectors. I think
only for long or n-dim vectors it will be faster as explicit (well for a
generic vector it is not bad perhaps, perhaps a simple for loop is
faster, I dont know).
I did not write a full featured classes, only the parts I needed (and
only the fastest one I would use to write a full featured class).
But the result speaks for its self.
I dont know exactly why the given classes are so slow, perhaps its
because of the "generic operator handlers".
My Vector2dTuple class is the fastest class, but you cant asign a single
value directly (because its a tuple). My class using slots is the second
one. But still, both are more than 2 time slower than using functions!
(even worse using psyco) The question is if it is worse to use operator
overloading or not. Perhaps it is easier to use and read but the speed
penalty is there.
I modified the script that was posted here some time ago. I only
rearranged the output to have a better overview.
Tell me about more optimisations if you can find one ( perhaps in the
"constructors" of the classes).
Perhaps I made a mistake somewhere, if you found one, please tell me. Or
if you find a faster way, I'm surely interested in. :-)
I will appreciate any suggestions, opinions or discussion.
~DR0ID
I did some back-of-the-envelope benchmarking of various
implementations of Vector operations. Attached is the program that I
used. My findings were:
- Numeric is faster than map is faster than a list comprehension
- explicitly storing two variables is even faster (not shown)
- using functions from the operator module is faster than built-in
math operators
- tuples seem to be a little faster to iterate over than lists
And some vector-unrelated findings:
- function calls are faster than method calls
- accessing a bound method is slower than accessing an instance variable
In benchmarking my game, I found that I was creating a *lot* of new
vector objects, and this does things to your performance. For this
reason my vectors are not immutable, but take advantage of in-place
operations to conserve objects.
"""
2D Vector Math Class (with operator overload goodness)
(C) Copyright 2005 James Paige and Hamster Republic Productions
"""
import operator
import math
import vec
from vec import vsub
from vec import vmul
class vec2d(object):
def __init__(self, x_or_pair, y = None):
if y == None:
try:
self.vec = [x_or_pair[0],x_or_pair[1]]
except TypeError:
raise TypeError("vec2d constructor requires a tuple or two
arguments")
else:
self.vec = [x_or_pair,y]
def get_x(self):
return self.vec[0]
def set_x(self, value):
self.vec[0] = value
x = property(get_x, set_x)
def get_y(self):
return self.vec[1]
def set_y(self, value):
self.vec[1] = value
y = property(get_y, set_y)
def set(self, x, y):
self.vec[0] = x
self.vec[1] = y
# String representaion (for debugging)
def __repr__(self):
return 'vec2d(%s, %s)' % (self.x, self.y)
# Array-style access
def __len__(self): return 2
def __getitem__(self, key):
return self.vec[key]
def __setitem__(self, key, value):
self.vec[key] = value
# Comparison
def __eq__(self, other):
return self.vec[0] == other[0] and self.vec[1] == other[1]
def __ne__(self, other):
return self.vec[0] != other[0] or self.vec[1] != other[1]
def __nonzero__(self):
return self.vec[0] or self.vec[1]
# Generic operator handlers
def _o2(self, other, f):
"Any two-operator operation where the left operand is a vec2d"
try:
return vec2d(f(self.vec[0], other[0]),
f(self.vec[1], other[1]))
except TypeError:
return vec2d(f(self.vec[0], other),
f(self.vec[1], other))
def _r_o2(self, other, f):
"Any two-operator operation where the right operand is a vec2d"
try:
return vec2d(f(other[0], self.vec[0]),
f(other[1], self.vec[1]))
except TypeError:
return vec2d(f(other, self.vec[0]),
f(other, self.vec[1]))
def _o1(self, f):
Re: [pygame] 2D vector class
On Wednesday 23 August 2006 02:57, Lenard Lindstrom wrote: > ... The instance dict is searched only if one is not > found. So having a descriptor reduces the search time. And a slot > descriptor does not do a dict lookup. So slots should be faster, > though I have not confirmed it. The function call overhead (for the getter) is much greater than the fallback to a dict lookup (which is insanely fast). We did some optimisation of function calls at the Need For Speed sprint in Iceland, but I only managed to squeeze out a 5% improvement (aka "noise") and others didn't fare much better. I'd be interested to see some *actual* numbers, but I'd be surprised if slots are faster than regular attributes. Unless there's been some slot-specific optimisation I've missed along the way :) Richard
Re: [pygame] 2D vector class
On 21 Aug 2006 at 23:48, Brian Fisher wrote: > On 8/15/06, Marius Gedminas <[EMAIL PROTECTED]> wrote: > > > [slots for performance] > > > > __slots__ is for optimizing memory usage, not speed. > > > optimizing memory usage is not mutually exclusive to optimizing speed > > One thing that It took me a long time to fully realize (years really) > as a c++ programmer, is the incredibly large impact of memory > allocations on performance - I mean like 3x or 4x times difference > kind of performance. > > From what I read about slots, it seemed like they could make it > possible for python to do much fewer allocations for an object in that > it wouldn't have to allocate properties dynamically, cause when the > object was allocated, it could allocate space for the properties at > the same time. > Slots replace memory allocated in a dictionary. But if any attribute goes into an instance dict then the benefit is probably lost. More important, slots simplify the attribute lookup process. Slots use automatically generated descriptors, one for each slot. Descriptors override normal attributes. Every attribute lookup starts with a descriptor search. The instance dict is searched only if one is not found. So having a descriptor reduces the search time. And a slot descriptor does not do a dict lookup. So slots should be faster, though I have not confirmed it. Lenard Lindstrom <[EMAIL PROTECTED]>
Re: [pygame] 2D vector class
On 8/15/06, Marius Gedminas <[EMAIL PROTECTED]> wrote: > [slots for performance] __slots__ is for optimizing memory usage, not speed. optimizing memory usage is not mutually exclusive to optimizing speed One thing that It took me a long time to fully realize (years really) as a c++ programmer, is the incredibly large impact of memory allocations on performance - I mean like 3x or 4x times difference kind of performance. From what I read about slots, it seemed like they could make it possible for python to do much fewer allocations for an object in that it wouldn't have to allocate properties dynamically, cause when the object was allocated, it could allocate space for the properties at the same time.
Re: [pygame] 2D vector class
On Mon, Aug 14, 2006 at 11:49:00AM -0700, Brian Fisher wrote: > On 8/14/06, Alex Holkner <[EMAIL PROTECTED]> wrote: > >Thanks Brian for writing the very useful benchmark script, I'll be > >keeping an eye on it during development. I expect you'll get the same > >performance I am if you use __slots__, a minor change. > > > Hmmm.. I had tried using __slots__ on the class early on, thinking it > would potentially be the best python thing you could do because then > your attributes are allocated in your object... when I tested it on > python 2.3 on WinXP it seemed to be about the same performance as > using a list member... it disappointed me at the time because I really > thought it was the best way to go... __slots__ is for optimizing memory usage, not speed. Marius Gedminas -- HOST SYSTEM NOT RESPONDING, PROBABLY DOWN. DO YOU WANT TO WAIT? (Y/N) signature.asc Description: Digital signature
Re: [pygame] 2D vector class
On Tuesday 15 August 2006 04:49, Brian Fisher wrote: > On 8/14/06, Alex Holkner <[EMAIL PROTECTED]> wrote: > > Thanks Brian for writing the very useful benchmark script, I'll be > > keeping an eye on it during development. I expect you'll get the same > > performance I am if you use __slots__, a minor change. > > Hmmm.. I had tried using __slots__ on the class early on, thinking it > would potentially be the best python thing you could do because then > your attributes are allocated in your object... when I tested it on > python 2.3 on WinXP it seemed to be about the same performance as > using a list member... it disappointed me at the time because I really > thought it was the best way to go... Until recently __slots__ could actually perform slower than regular attributes. A *lot* of optimisation effort went into Python 2.5 (including a dedicated Sprint for a week in Iceland with a dozen devs focusing on speed). Richard
Re: [pygame] 2D vector class
On 8/14/06, Alex Holkner <[EMAIL PROTECTED]> wrote: Thanks Brian for writing the very useful benchmark script, I'll be keeping an eye on it during development. I expect you'll get the same performance I am if you use __slots__, a minor change. Hmmm.. I had tried using __slots__ on the class early on, thinking it would potentially be the best python thing you could do because then your attributes are allocated in your object... when I tested it on python 2.3 on WinXP it seemed to be about the same performance as using a list member... it disappointed me at the time because I really thought it was the best way to go... ... but maybe performance sucked cause the operators were still using [] access on other vec2d's, I noticed the euclid code is using x & y on other vec2d's with an if (so it can still support adding with anything with a list interface...) now I'll have to look at slots again :)
Re: [pygame] 2D vector class
Alex Holkner wrote: I'll add another datapoint here, using the module I just announced (euclid). This is with the "_tuple" fix above, no psyco (doesn't exist on AMD64) and cgkit light (C++ one doesn't compile here). As the 'light' version of cgkit is supposed to work without a C++ compiler, its vector classes are implemented in pure Python so it's no surprise that the performance in this case is similar to the other Vec2d class. It's interesting to see that your __slots__ version makes such a difference. - Matthias - PS: Do you still know what the problem was during compilation of cgkit? Of course, I'm always interested in knowing what problems people have when trying to install the package. So feel free to mail me directly if you want to give it another try...
Re: [pygame] 2D vector class
Matthias Baas wrote: Ethan Glasser-Camp wrote: By the way, just out of curiosity I tested the vector class (http://cgkit.sourceforge.net/doc2/vec3.html) in my cgkit package (http://cgkit.sourceforge.net): I'll add another datapoint here, using the module I just announced (euclid). This is with the "_tuple" fix above, no psyco (doesn't exist on AMD64) and cgkit light (C++ one doesn't compile here). runs at 58823.5 loops/s that's 980.39 loops to fill 60 fps or 49.02 at a 5.0% budget at 60 fps runs at 6.7 loops/s that's .11 loops to fill 60 fps or 55.56 at a 5.0% budget at 60 fps runs at 100.0 loops/s that's 1.67 loops to fill 60 fps or 833.33 at a 5.0% budget at 60 fps runs at 71428.6 loops/s that's 1190.48 loops to fill 60 fps or 59.52 at a 5.0% budget at 60 fps runs at 125000.0 loops/s that's 2083.33 loops to fill 60 fps or 104.17 at a 5.0% budget at 60 fps My module, using __slots__, seems to benchmark around twice as fast as the others, excepting the straight assignment test. Results are even happier with Python 2.5 beta 3: runs at 71428.6 loops/s that's 1190.48 loops to fill 60 fps or 59.52 at a 5.0% budget at 60 fps runs at 8.3 loops/s that's 1388.89 loops to fill 60 fps or 69.44 at a 5.0% budget at 60 fps runs at 100.0 loops/s that's 1.67 loops to fill 60 fps or 833.33 at a 5.0% budget at 60 fps runs at 76923.1 loops/s that's 1282.05 loops to fill 60 fps or 64.10 at a 5.0% budget at 60 fps runs at 16.7 loops/s that's 2777.78 loops to fill 60 fps or 138.89 at a 5.0% budget at 60 fps That's a significant boost to everyone, signalling that we should all download and install Python 2.5 as soon as it's released :-) Thanks Brian for writing the very useful benchmark script, I'll be keeping an eye on it during development. I expect you'll get the same performance I am if you use __slots__, a minor change. Alex.
Re: [pygame] 2D vector class
Ethan Glasser-Camp wrote: I'm attaching the modified benchmarking script. [...] def ScreenTranslationTestVec2d(loop_count): for i in xrange(loop_count): final_pos = (TestData.object_position_tuple - TestData.screen_offset_tuple)*TestData.screen_scale def ScreenTranslationTestVec2dTuple(loop_count): for i in xrange(loop_count): final_pos = (TestData.object_position_tuple - TestData.screen_offset_tuple)*TestData.screen_scale Shouldn't the first function use the variables without the "_tuple" suffix? By the way, just out of curiosity I tested the vector class (http://cgkit.sourceforge.net/doc2/vec3.html) in my cgkit package (http://cgkit.sourceforge.net): runs at 40641.4 loops/s that's 677.36 loops to fill 60 fps or 33.87 at a 5.0% budget at 60 fps runs at 47596.5 loops/s that's 793.27 loops to fill 60 fps or 39.66 at a 5.0% budget at 60 fps runs at 700429.5 loops/s that's 11673.83 loops to fill 60 fps or 583.69 at a 5.0% budget at 60 fps runs at 171071.2 loops/s that's 2851.19 loops to fill 60 fps or 142.56 at a 5.0% budget at 60 fps It's actually a 3d vector but as it is implemented in C++ it is still more than 3 times faster than the Vec2d or tuple version (at least using your test setup which also contains those 3 attribute lookups inside the loop). I don't have a true vec2 class yet but was already considering to add one in the future. Greg Ewing wrote: Doing vector operations one at a time in Python is always going to be either slow or very slow, no matter how you go about it. IMO, the best way to make this sort of thing fast is to arrange things so that you can use Numeric to operate on multiple vectors at once. For instance, store all your object positions in one array and all the velocities in another, and then just add the two arrays together. I agree with that (at least as long as the number of objects is higher than a certain (small) threshold). I used something like this very effectively in a recent project where I wanted to find the intersection of a ray with a terrain mesh. I hope you'll apologize if I take this opportunity to mention cgkit once more. ;) There is already a ray-triangle mesh intersection method inside cgkit. This method is implemented in C/C++ and is based on the paper "Fast, minimum storage ray-triangle intersection" by Tomas Möller and Ben Trumbore. See here: http://cgkit.sourceforge.net/doc2/node152.html - Matthias -
Re: [pygame] 2D vector class
I took another quick look at performance of things, when I tested tuple-inherited vector performance, I had a typo - tuples were somewhat faster than having a list member (20%) On 8/12/06, Marius Gedminas <[EMAIL PROTECTED]> wrote: You can find my Vector class here: http://mg.pov.lt/pyspacewar/trac/browser/trunk/src/pyspacewar/world.py The class marius linked to was about 3x faster than what I originally posted to the cookbook on a simple (vector - vector)*scalar, the 2 differences were inheriting from tuple & that Marius' class has add & sub always be vector & vector, and mul and div always be scalar and vector, while the class I posted using a try-catch to try and do every op as vector X vector, and fallback to vector X scalar (so vector X scalar ops went really slow because of the catch clause) ... also I tried making some dummy class that implement the math operators as a no-op that just returns the original object, the idea being that the performance of that would represent the best you could possibly get out of a vector class, and on my test it was 1/3rdth the speed of just doing math on the variables and 1/0th the speed of just doing math on variables when using psycho. Also, it was around 2x as fast as the fastest Vector class I tested - reiterating that using any vector class is slow, and to go fast you'll just need to rewrite your performance sensitive inner loops with some other approach.
RE: [pygame] 2D vector class
Thanks for all the feedback, everyone. It's gonna take me a bit to pour over all the details. Very helpful! And, Brian, thanks for posting your vector class to the Cookbook! Much appreciated! -Scott
Re: [pygame] 2D vector class
Richard Jones wrote: Any chance of this getting into the cookbook? :) If you mean the actual code I used, it's currently embedded in a rather haphazard collection of vector algebra code that I grew for that particular game. I could look into whether it can be pulled out and made useable on its own. -- Greg
Re: [pygame] 2D vector class
On Sunday 13 August 2006 11:49, Greg Ewing wrote: > I used something like this very effectively in a > recent project where I wanted to find the intersection > of a ray with a terrain mesh. First I worked out how > to use Numeric to test the ray against just one > triangle. Then it was almost (although not quite) > trivial to extend that to handle an array of triangles. > > Presto - I could then do a hit test against my whole > terrain of hundreds of triangles almost instantaneously! Any chance of this getting into the cookbook? :) Richard
Re: [pygame] 2D vector class
Ethan Glasser-Camp wrote: It certainly isn't clear how best to take advantage of this speedup without going crazy from pos_x and pos_y variables all over the place. Doing vector operations one at a time in Python is always going to be either slow or very slow, no matter how you go about it. IMO, the best way to make this sort of thing fast is to arrange things so that you can use Numeric to operate on multiple vectors at once. For instance, store all your object positions in one array and all the velocities in another, and then just add the two arrays together. You could wrap these arrays up in custom PointArray and VectorArray classes with suitable operators, and the overhead of method calls would be far less of a problem, since you only incur it once for the whole array rather than once per vector. I used something like this very effectively in a recent project where I wanted to find the intersection of a ray with a terrain mesh. First I worked out how to use Numeric to test the ray against just one triangle. Then it was almost (although not quite) trivial to extend that to handle an array of triangles. Presto - I could then do a hit test against my whole terrain of hundreds of triangles almost instantaneously! -- Greg
Re: [pygame] 2D vector class
Brian Fisher wrote:
> so I wrote test functions to take a 2d position, subtract another
> position from it then multiply the result by a scalar (basically pan
> and zoom a position). One version uses the 2d vector with operator
> overloading, so it will allocate 2 vec2d's, each with a list member.
> Another version does explicit math operations on variables, so no
> allocations happen. I also tried converting the vec2d class to be
> inherited from tuple, thinking that maybe you could save the list
> member allocations by being a tuple to start with...
When I said "explicitly storing two variables", I meant doing more
like the following:
class Vector2D(object):
def __init__(self, dx, dy):
object.__init__(self)
self.dx = dx
self.dy = dy
def __sub__(self, v2):
return Vector(self.dx - v2.dx, self.dy - v2.dy)
def __add__(self, v2):
return Vector(self.dx + v2.dx, self.dy + v2.dy)
def __iadd__(self, v2):
self.dx = self.dx + v2.dx
self.dy = self.dy + v2.dy
return self
def __isub__(self, v2):
self.dx = self.dx - v2.dx
self.dy = self.dy - v2.dy
return self
This is the Vector class I use. I did tests with this approach and, as
you might expect, it's also much slower than just using two variables
outside of a class. I'm attaching the modified benchmarking script.
> like a 48:1 performance diff. Also the tuple inherited version was
> slower.
This is good information but really astonishing. The next step would
probably be benchmarking just to confirm that the large number of
calls to __init__ and __new__ are what are causing the slowdown. It
could also be that method calls are much slower than no function
calls. It certainly isn't clear how best to take advantage of this
speedup without going crazy from pos_x and pos_y variables all over
the place. Maybe unpacking the vectors in certain parts of the code
would be sufficient to speed things up, or maybe converting certain
operations to in-place vector modifications would be good enough.
Ethan
"""
2D Vector Math Class (with operator overload goodness)
(C) Copyright 2005 James Paige and Hamster Republic Productions
"""
import operator
import math
class vec2d(object):
def __init__(self, x_or_pair, y = None):
if y == None:
try:
self.vec = [x_or_pair[0],x_or_pair[1]]
except TypeError:
raise TypeError("vec2d constructor requires a tuple or two arguments")
else:
self.vec = [x_or_pair,y]
def get_x(self):
return self.vec[0]
def set_x(self, value):
self.vec[0] = value
x = property(get_x, set_x)
def get_y(self):
return self.vec[1]
def set_y(self, value):
self.vec[1] = value
y = property(get_y, set_y)
def set(self, x, y):
self.vec[0] = x
self.vec[1] = y
# String representaion (for debugging)
def __repr__(self):
return 'vec2d(%s, %s)' % (self.x, self.y)
# Array-style access
def __len__(self): return 2
def __getitem__(self, key):
return self.vec[key]
def __setitem__(self, key, value):
self.vec[key] = value
# Comparison
def __eq__(self, other):
return self.vec[0] == other[0] and self.vec[1] == other[1]
def __ne__(self, other):
return self.vec[0] != other[0] or self.vec[1] != other[1]
def __nonzero__(self):
return self.vec[0] or self.vec[1]
# Generic operator handlers
def _o2(self, other, f):
"Any two-operator operation where the left operand is a vec2d"
try:
return vec2d(f(self.vec[0], other[0]),
f(self.vec[1], other[1]))
except TypeError:
return vec2d(f(self.vec[0], other),
f(self.vec[1], other))
def _r_o2(self, other, f):
"Any two-operator operation where the right operand is a vec2d"
try:
return vec2d(f(other[0], self.vec[0]),
f(other[1], self.vec[1]))
except TypeError:
return vec2d(f(other, self.vec[0]),
f(other, self.vec[1]))
def _o1(self, f):
"Any unary operation on a vec2d"
return vec2d(f(self.vec[0]), f(self.vec[1]))
# Addition
def __add__(self, other):
return self._o2(other, operator.add)
__radd__ = __add__
# Subtraction
def __sub__(self, other):
return self._o2(other, operator.sub)
def __rsub__(self, other):
return self._r_o2(other, operator.sub)
# Multiplication
def __mul__(self, other):
return self._o2(other, operator.mul)
__rmul__ = __mul__
# Division
def __div__(self, other):
return self._o2(other, operator.div)
d
Re: [pygame] 2D vector class
On Fri, Aug 11, 2006 at 01:38:06PM -0500, Nelson, Scott wrote: > I've got 2 simple games roughed out (about 600 lines each) with about > 2000 lines worth of shared modules I've written. I have a somewhat full > featured 2D vector class (supports adding, subtracting, scaling, > rotation, normalizing, angle between, etc. that I use in both heavily to > represent points, velocities, etc. After using it for awhile, I've > wondered how others have approached creating a 2D vector class. Here's > my "philosophical" questions, as the class I have works well, but I want > to know how to make it better. My main goals are to keep it simple, let > it interface cleanly with Pygame's use of tuples of 2 ints for 2D > points, not be specifically tied to Pygame, and have it not be a > performance hog. > > So, here's the issues that I'd love to hear feedback on: > > #1 - Do you store the vector components internally as self.x and self.y > or as a tuple? Or subclass the vector class from a tuple? If you use > self.x and self.y, what is an efficient way to pass this as a tuple to > pygame functions? I chose to subclass tuple in pyspacewar, but I forgot why. > #2 - Do you store the values as ints (making it easier to pass to > Pygame) or floats (more accurate vector math, but need to cast to int > before passing to pygame functions that require a tuple of ints?). Or > do you not even care and just let duck-typing do it stuff? I needed floats, because I wanted the world to be scaled arbitrarily for display, and besides that I needed the accuracy for gravity calculations. You can find my Vector class here: http://mg.pov.lt/pyspacewar/trac/browser/trunk/src/pyspacewar/world.py It has unit tests, and is somewhat optimized (only those bits that showed up when profiling). Marius Gedminas -- C is for Cookies. Perl is even better for Cookies. signature.asc Description: Digital signature
Re: [pygame] 2D vector class
On 8/12/06, Alex Holkner <[EMAIL PROTECTED]> wrote: You won't be able to meaningfully overload operators if you subclass tuple (vector + tuple will not equal tuple + vector). In the code I emailed, there is a unit test for exactly that problem with a tuple inherited vector class, it works just fine. The issue of right side or left side operators has nothing to do with whether you overload tuple or not. You could overload object, and still need to support both vector + tuple and tuple + vector. In addition, Python can handle that just fine. There are seperate operators to overload for when the object is on each side (they just add r in front of the name for the right side one, so __add__ and __radd__) Finally, python seems to know to let your user classes operators win over all built in operators on either side of the operator (I don't know how it would decide what to do when two user classes overload, maybe that's where left side wins... anybody?)
Re: [pygame] 2D vector class
After reading Ethan's email, I decided to play more with the vec2d
class I posted, specifically to try to understand how bad the
allocations due to operator overloading really are - in that I want to
put it in a real context (like say how many particle positions you
could translate and still get 60 fps)... cause it doesn't matter if
you make the thing that takes 1% of your time go 1000% faster...
so I wrote test functions to take a 2d position, subtract another
position from it then multiply the result by a scalar (basically pan
and zoom a position). One version uses the 2d vector with operator
overloading, so it will allocate 2 vec2d's, each with a list member.
Another version does explicit math operations on variables, so no
allocations happen. I also tried converting the vec2d class to be
inherited from tuple, thinking that maybe you could save the list
member allocations by being a tuple to start with...
Then for performance, I ran the script in Python 2.3 on my 800Mhz p3
laptop plugged into the wall (what I consider my min spec) then
checked how many times it could do the translations a second.
Basically, using the operator overloading cut the performance by about
a factor of 18 . Also, when running psycho, the func doing math on
variables was able to run about 3x faster, but the operator
overloading routines weren't able to go significantly faster (makes
sense cause psycho doesn't help with allocation issues) making it more
like a 48:1 performance diff. Also the tuple inherited version was
slower.
So then using the loops/sec to try and figure out some context for the
perf difference, I computed how many times you could run the loop if
you had a 5% budget of cpu time for a game that ran at 60fps on my
min-spec machine - and that figure was 15/280 without psycho, or
16/760 with it. only moving around 15 objects a frame on my laptop
before dropping frames does strike me as very bad... especially when
I'd probably be pretty happy with 280 objects... but I'll still
probably keep using vec2d as a rule (although I do know where to look
first when performance drags now...)
I'm attaching the adapted code, if anyone is curious (it will run the
perf tests and print out stats)
"""
2D Vector Math Class (with operator overload goodness)
(C) Copyright 2005 James Paige and Hamster Republic Productions
"""
import operator
import math
class vec2d(object):
def __init__(self, x_or_pair, y = None):
if y == None:
try:
self.vec = [x_or_pair[0],x_or_pair[1]]
except TypeError:
raise TypeError("vec2d constructor requires a tuple or two arguments")
else:
self.vec = [x_or_pair,y]
def get_x(self):
return self.vec[0]
def set_x(self, value):
self.vec[0] = value
x = property(get_x, set_x)
def get_y(self):
return self.vec[1]
def set_y(self, value):
self.vec[1] = value
y = property(get_y, set_y)
def set(self, x, y):
self.vec[0] = x
self.vec[1] = y
# String representaion (for debugging)
def __repr__(self):
return 'vec2d(%s, %s)' % (self.x, self.y)
# Array-style access
def __len__(self): return 2
def __getitem__(self, key):
return self.vec[key]
def __setitem__(self, key, value):
self.vec[key] = value
# Comparison
def __eq__(self, other):
return self.vec[0] == other[0] and self.vec[1] == other[1]
def __ne__(self, other):
return self.vec[0] != other[0] or self.vec[1] != other[1]
def __nonzero__(self):
return self.vec[0] or self.vec[1]
# Generic operator handlers
def _o2(self, other, f):
"Any two-operator operation where the left operand is a vec2d"
try:
return vec2d(f(self.vec[0], other[0]),
f(self.vec[1], other[1]))
except TypeError:
return vec2d(f(self.vec[0], other),
f(self.vec[1], other))
def _r_o2(self, other, f):
"Any two-operator operation where the right operand is a vec2d"
try:
return vec2d(f(other[0], self.vec[0]),
f(other[1], self.vec[1]))
except TypeError:
return vec2d(f(other, self.vec[0]),
f(other, self.vec[1]))
def _o1(self, f):
"Any unary operation on a vec2d"
return vec2d(f(self.vec[0]), f(self.vec[1]))
# Addition
def __add__(self, other):
return self._o2(other, operator.add)
__radd__ = __add__
# Subtraction
def __sub__(self, other):
return self._o2(other, operator.sub)
def __rsub__(self, other):
return self._r_o2(other, operator.sub)
# Multiplication
def __mul__(self, other):
return self._o2(oth
Re: [pygame] 2D vector class
...As far as subclassing from a tuple, I don't think I really looked into that, might be a great way to go... the idea of the vector object being immutable is probably actually a good idea - just because you may pass a vector in as a function argument and not want it to change... that way the vector is more like passing in two args, in that you can't change the callee's data You won't be able to meaningfully overload operators if you subclass tuple (vector + tuple will not equal tuple + vector). Alex.
Re: [pygame] 2D vector class
Brian Fisher wrote:
> I love vector classes with operator overloading... I couldn't stand to
> code without them (even though in python, it means there's probably a
> lot of object allocation and function calls for simple vector math,
> wasting performance). Code is just so much shorter & more readable
> with them. I know that I pay for it in performance to use them, and I
> know the one I use isn't the best performing one... I'll just wait to
> care about that when it's a real problem.
I did some back-of-the-envelope benchmarking of various
implementations of Vector operations. Attached is the program that I
used. My findings were:
- Numeric is faster than map is faster than a list comprehension
- explicitly storing two variables is even faster (not shown)
- using functions from the operator module is faster than built-in
math operators
- tuples seem to be a little faster to iterate over than lists
And some vector-unrelated findings:
- function calls are faster than method calls
- accessing a bound method is slower than accessing an instance variable
In benchmarking my game, I found that I was creating a *lot* of new
vector objects, and this does things to your performance. For this
reason my vectors are not immutable, but take advantage of in-place
operations to conserve objects.
I found that it was rare that I needed to access individual elements
of a vector, but implemented __iter__ by returning iter([x, y]). This
was "good enough" and pretty straightforward.
Ethan
s = '''from operator import sub
def add1(v1, v2):
return [a + b for (a, b) in zip(v1, v2)]
def sub1(v1, v2):
return [a - b for (a, b) in zip(v1, v2)]
def sub2(v1, v2):
return [sub(a,b) for (a, b) in zip(v1, v2)]
def sub3(v1, v2):
return map(sub, v1, v2)
v1a = [4.2, 5.4]
v1b = [12.0, -4.1]
v2a = (4.2, 5.4)
v2b = (12.0, -4.1)'''
import timeit
t = timeit.Timer()
print 'baseline', t.repeat()
for i in ['sub1', 'sub2', 'sub3']:
for j in [1, 2]:
t = timeit.Timer('a = %s(v%da,v%db)'%(i,j,j), s)
print i, j, t.repeat()
s2 = '''import Numeric
def sub4(v1, v2):
return Numeric.subtract(v1, v2)
v1a = Numeric.array([4.2, 5.4])
v1b = Numeric.array([12.0, -4.1])'''
t = timeit.Timer('a = sub4(v1a, v1b)', s2)
print 'numeric', t.repeat()
s3 = '''
class C(object):
x = None
def __init__(self):
pass
def f(self, o2):
pass
def g(self):
pass
def f(o1, o2):
pass
o1 = C()
o2 = C()'''
for i in ['o1.f(o2)', 'C.f(o1, o2)', 'f(o1, o2)']:
t = timeit.Timer(i, s3)
print i, t.repeat()
for i in ['o1.x', 'o1.g', 'o1.g()']:
t = timeit.Timer(i, s3)
print i, t.repeat()
signature.asc
Description: OpenPGP digital signature
Re: [pygame] 2D vector class
I love vector classes with operator overloading... I couldn't stand to code without them (even though in python, it means there's probably a lot of object allocation and function calls for simple vector math, wasting performance). Code is just so much shorter & more readable with them. I know that I pay for it in performance to use them, and I know the one I use isn't the best performing one... I'll just wait to care about that when it's a real problem. I posted the one in the library I use to the cookbook, I figure to help get the ball rolling On 8/11/06, Nelson, Scott <[EMAIL PROTECTED]> wrote: #1 - Do you store the vector components internally as self.x and self.y or as a tuple? Or subclass the vector class from a tuple? If you use self.x and self.y, what is an efficient way to pass this as a tuple to pygame functions? I don't think this really matters as long as you provide a list interface, and your internal functions (like operators) take advantage of whatever your internal structure is. We thought that accessing as .x and .y was really important, so we provided both interfaces (indexed access and x/y), although internally we use a two element list as a property on the class, so the representation doesn't really map to either interface directly. ...As far as subclassing from a tuple, I don't think I really looked into that, might be a great way to go... the idea of the vector object being immutable is probably actually a good idea - just because you may pass a vector in as a function argument and not want it to change... that way the vector is more like passing in two args, in that you can't change the callee's data #2 - Do you store the values as ints (making it easier to pass to Pygame) or floats (more accurate vector math, but need to cast to int before passing to pygame functions that require a tuple of ints?). Or do you not even care and just let duck-typing do it stuff? I say duck-typing is the way to go. while it's true that dividing integer vectors by integer vectors could maybe have unexpected results by having integer results, dividing by vectors is such a rare case, It doesn't bug me in the least. Plus it feels like the pythonic thing to do So, after using my 2D vect class for awhile, I wasn't sure if I had taken the best approach originally. Currently, my vector class stores floats in self.x and self.y and I have 2 methods for returning tuples as follows: I say let it just be a list (by that I mean make sure __len__ __getitem__ and __setitem__ work) rather than bother with conversion routines like that def AsIntTuple(self): '''Cast values to int. Useful for Pygame''' return((int(self.x), int(self.y))) So why is a tuple containing int's specifically so useful for pygame? is it to make sure you pass ints to blit?
