[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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.
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.
This is because python is using a general purpose exponentiating operator,
instead of something optimized to do squares. It would be kinda sweet to
get that into the official compiler though.. to turn an explicit **2 into a
multiply
I don't know how proficient you are with applied math, but if you wanted
accurate results to an arbitrarily rotated bounding quad, you could write a
modified version of any scanline algo like bresenham's (to account for
opposite lines being parallel for speed).. toss out any points not in the
bounding rectangle from (minX,minY) to (maxX,maxY), then find the scanline
involved and calculate if the point is between those two lines. It should
be an order of magnitude or two faster than per-pixel if you do it right,
but not as fast as a circular algo (even though there are no multiplies)
just cause there are so few ops involved with the circular thing.
and what you're talking about definitely isn't spherical distance, you need
a sphere for that =P This is euclidean distance in R^2, which you could
probably call "circular", but I wouldn't.
disclaimer: before I quit school, I had changed my major from compsci to
theoretical math
-bob
-----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