[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: [pygame] How to rotate a rect
Range should be slower because it allocates a real list, but only testing
will tell.
xrange is ususally the choice in this case (same as range, but doesn't make
a list),
but it doesn't seem to work right for floats.
If range is really faster and you don't mind the memory, you could also just
maintain a reference to the list you want to use as an iterator.
m
-----Original Message-----
From: owner-pygame-users@seul.org [mailto:owner-pygame-users@seul.org]On
Behalf Of (::) Bob Ippolito
Sent: Saturday, June 30, 2001 10:58 PM
To: pygame-users@seul.org
Subject: RE: [pygame] How to rotate a rect
I've found that fixed point scaling problems really aren't a problem in most
cases.. particularly with 2D bitmap stuff where you expect your numbers to
be pretty close to whole ones.
Then again, the bulk of my early coding experience was x86 assembler, so I'm
used to doing things myself and think in a register/bit oriented
methodology.. trying to squeeze that extra FPS out of that 286/486, where a
few cpu cycles at 16/33mhz was a big deal and using the FPU at all (when you
even had one) was shooting yourself in the foot..
just out of curiosity, would using:
for i in range(s+e,e,inc):
for j in range(s,e,inc):
# do stuff
or even:
r=range(s,e,inc)
for i in r[1:]:
for j in r:
# do stuff
be faster than those while loops at the expense of some memory (which is
unrealistically cheap and plentiful nowadays anyways)?
I've only been using python for a few weeks and haven't really dug into its
performance yet... I'm currently working on a network application that
doesn't need that kinda tuning..
-----Original Message-----
From: owner-pygame-users@seul.org [mailto:owner-pygame-users@seul.org]On
Behalf Of Michael Robin
Sent: Saturday, June 30, 2001 2:16 PM
To: pygame-users@seul.org
Subject: RE: [pygame] How to rotate a rect
>Manhattan distance is actually useful to solve certain types of problems
>(i.e, a problem where moving at an angle is not possible).. I wouldn't
say
>it's inferior, but it's not equivalent to euclidean distance and
shouldn't
>ever really be used in lieu of it.
I've used it too in a genetic algol for an optimization problem a while
back.
>another thing I've noticed is that
>distsquared=(i-j)*(k-l) + (i-j)*(k-l)
>is ~4% faster with integers, and ~3% faster with floats on a p3-800 in
>win2000.. while playing mp3s in winamp and having wincvs, pythonwin, and
>outlook running. Another thing of note, ints were faster than floats by
>~16%.. this could be due to the fact that winamp is probably using a
bunch
>of flops, but then again, I have dual cpus so chances are winamp and
python
>weren't even on the same cpu.
>this might be a bit different with objects in the picture.. I don't how
well
>python caches/compiles that sort of thing, I haven't been using it long
>enough to tell and I definitely haven't looked at python bytecode yet.
I have a feeling that int/float and even generalized exp vs x^2 won't
make much difference with Python were you're looking things up in
dictionaries,
(un)packing tuples and blitting all day. Anyway, on the Pentium, we'd
expect
FP to be at least as fast as integer, seeing the interpreter will have the
integer
unit busy already, the FP unit could be working in parallel, if
instructions
were given in an order the scheduler could do something with. (Like that's
gonna happen... there'll be hundreds of overhead instructions in the way.)
Let's see what happens for me:
-------------------------------------------------------------------
def mtest(s,e,inc):
i = s
while i < e:
j = s
i+=inc
while j < e:
t = s*s*s*3.14
t = s*s*s*3.14
t = s*s*s/inc
t = s*s*s/inc
j+=inc
def dtest(s,e,inc):
from math import sqrt
i = s
while i < e:
j = s
i+=inc
while j < e:
d = sqrt((i-j)**2 + (j-i)**2)
d = sqrt((i-j)**2 + (j-i)**2)
d = sqrt((i-j)**2 + (j-i)**2)
d = sqrt((i-j)**2 + (j-i)**2)
j+=inc
def fnoverhead(a,b):
return [a[0], b[1]]
def dtest2(s,e,inc):
from math import sqrt
class C: pass
c = C()
c.a, c.b, c.c, c.d = s, s, e-s, e+s
def fnoverhead2(a,b): return ( a[0], b[1] )
i = s
while i < e:
j = s
i+=inc
while j < e:
t = ( sqrt((c.a-c.b)**2 + (c.c-c.d)**2),
sqrt((c.a-c.b)**2 + (c.c-c.d)**2) )
t2 = ( sqrt((c.a-c.b)**2 + (c.c-c.d)**2),
sqrt((c.a-c.b)**2 + (c.c-c.d)**2) )
fnoverhead(t, t2)
fnoverhead2(t, t2)
j+=inc
import time as pytime
def time(f,msg, s,e,inc):
timeStart = pytime.time()
f(s,e,inc)
timeEnd = pytime.time() - timeStart
print 'done (%s): %f' % (msg, timeEnd)
if __name__ == '__main__':
time(mtest, 'mtest int', 1, 1000,1)
time(mtest, 'mtest float', 1.0, 100.0,0.1)
time(dtest, 'dtest int', 1, 1000,1)
time(dtest, 'dtest float', 1.0, 100,0.1)
time(dtest2, 'dtest2 int', 1, 1000,1)
time(dtest2, 'dtest2 float', 1.0, 100.0,0.1)
---------------------------------------------------------------------
Here's what I get on my Dell laptop (PIII 850):
done (mtest int): 4.366000
done (mtest float): 4.386000
done (dtest int): 11.667000
done (dtest float): 14.531000
done (dtest2 int): 22.703000
done (dtest2 float): 25.286000
So FP still seems to be a little slower - but in the basic case, not by
much.
(Intersting that dest&dtest2 int/float look like a constant overhead, not
a
percentage...)
Although dtest2 tries to do some other work, this is still *very* math
intensive
and made to accent the math code. (In this case 40,000 distance measures
per
call.)
If you put your draw loop in there, you probably won't see any difference
at
all :)
(Plus you don't have to worry about fixed-point scaling issues, which are
a
real pain.
Of course, you get a different set of problems with floats, but not
usually
the kind
that's bad for games where relative measures a used and extact reprs are
not
needed.)
mike
-----Original Message-----
From: owner-pygame-users@seul.org [mailto:owner-pygame-users@seul.org]On
Behalf Of Michael Robin
Sent: Saturday, June 30, 2001 3:02 AM
To: pygame-users@seul.org
Subject: RE: [pygame] How to rotate a rect
This is what I get for not reading your post (and my own) carefully -
nothing's worse than an overly-pedantic post that's also wrong...
The line I proposed with "*" in place of your "+" is garbage.
The Euclidian solution should be:
limitsize = object1.size1 + object2.size2 # /2 depends on radius vs.
diameter...
limitsize *= limitsize
distsquared = (object2.x - object1.x)**2 + (object2.y - object1.y)**2
if distsquared <= limitsize:
# Boom!
(Of course, remove line 2 and add a sqrt to distsquared if you really want
to know how many pixels the centers are from each other.)
This gives the "real" (spherical) distance, and also takes care of abs(),
which I beleive you'd need to add to the Manhatan equation.
The Manhattan version (useful in the days when you couldn't mult/div/sqrt
very fast, but now inferior) would be:
limitsize = object1.size1 + object2.size2 # /2 depends on radius vs.
diameter...
# optional inflation fudge-factor to average out shrunken corners
# (there's probably a real # that can be found by someone smarter than
me)
# limitsize *= 1.1
distsquared = abs(object2.x - object1.x) + abs(object2.y - object1.y)
if distsquared <= limitsize:
# Boom!
Of course, I'm sure you all know all this basic crap already - but I
thought
better to correct my own screw-up.
(And now I see that given that you named the variable "distsquared" and
you
squard limitsize, it was probably just a typo in the first place to omit
the
**2, so Manhattan nor any other bourough of NYC was ever intended... Arg.)
m
-----Original Message-----
From: owner-pygame-users@seul.org [mailto:owner-pygame-users@seul.org]On
Behalf Of Michael Robin
Sent: Friday, June 29, 2001 9:02 PM
To: pygame-users@seul.org
Subject: RE: [pygame] How to rotate a rect
I think what you described is usually called the Manhattan distance.
(Basically because your measuring the "number of blocks" between objects.)
You're right that you don't necessarily need a Sqrt at the end as you
would
for a real Euclidean distance, seeing we just want a relative measure, but
I
think you want:
...
distsquared = (object2.x - object1.x) * (object2.y - object1.y) # times
instead of plus
...
for your "squared distance".
Manhattan distance may work okay too, but the bounding box for collisions
will be kind of like a round diamond shape. (It will be smaller at the
diagnals.) Adding the "*" will make the collision area circular as you
suggest.
In all cases above your just picking a point in your box and not really
looking at the orientation of the rotated rect.
One way to do that would be to write similar fn's to Rect's collision
detection methods, but for generalized polygons.
mike
-----Original Message-----
From: owner-pygame-users@seul.org [mailto:owner-pygame-users@seul.org]On
Behalf Of Paul Sidorsky
Sent: Friday, June 29, 2001 8:43 PM
To: pygame-users@seul.org
Subject: Re: [pygame] How to rotate a rect
Leonardo Santagada wrote:
> Making the box is not the problem but how to make fast collision
detection?
This may not be suitable for your situation but I'll describe it anyhow
since I haven't seen it mentioned yet:
Give each object a radius or size and then use the distance formula. If
the distance between two objects is less than the combined radiuses (or
half the combined sizes) of the objects, they collide. To avoid
floating point, use the squared distance. Here's pseudo code:
limitsize = (object1.size1 + object2.size2) / 2
limitsize *= limitsize
distsquared = (object2.x - object1.x) + (object2.y - object1.y)
if distsquared <= limitsize:
# Boom!
This works great for spherical objects and can work for others if you
don't need 100% precision. The inaccuracy increases as the sizes get
larger. I'm not sure how practical this method is in "real" games since
I've only tried it on a small scale, but it might be worth a shot.
--
======================================================================
Paul Sidorsky Calgary, Canada
paulsid@home.com http://members.home.net/paulsid/
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org
_________________________________________________________
Do You Yahoo!?
Get your free @yahoo.com address at http://mail.yahoo.com
____________________________________
pygame mailing list
pygame-users@seul.org
http://pygame.seul.org