Distance in a shootem up 2D

Mars_999
Unregistered
 
Post: #1
Am I going about this in the right way? I am going to use the distance formula to determine the distance on the enemies and the player in my game.

d = sqrt((x1-x2)^2 + (y1-y2)^2) or is their someother way or faster way to do it? Thanks.
Quote this message in a reply
Member
Posts: 142
Joined: 2002.11
Post: #2
Quote:Originally posted by Mars_999
Am I going about this in the right way? I am going to use the distance formula to determine the distance on the enemies and the player in my game.

d = sqrt((x1-x2)^2 + (y1-y2)^2) or is their someother way or faster way to do it? Thanks.


Yes, that is correct. This is the fastest way (that I know of), unless your want to merely compare distances where you can write something like:

if d^2 > (x1-x2)^2+(y1-y2)^2

But obviously writing d^2 = ... will give you an l value error.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #3
That's the only way to get an accurate result.

If you don't need accuracy, there may be faster approximations.

If you don't need to know the distance, only to compare distances, you don't need the square root -- comparing the squares will give the same result.
Quote this message in a reply
Member
Posts: 177
Joined: 2002.08
Post: #4
The most common approximation is a lookup table, possibly with interpolation if you want to trade some speed for a bit more accuracy.

Shikari will nag you about using PPC instructions designed for square root acceleration, but I have no experience with this.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #5
The sqrt-related PowerPC instructions that are available on Macs are only for reciprocal square roots, so they're seldom any use for distance formulae.
Quote this message in a reply
Member
Posts: 164
Joined: 2002.04
Post: #6
[SOURCECODE]
float fast_sqrt (register float arg)
{
// Can replace with slower return std::sqrt(arg);
register float result;

if (arg == 0.0) return 0.0;

asm {
frsqrte result,arg // Calculate Square root
}

// Newton Rhapson iterations.
result = result + 0.5 * result * (1.0 - arg * result * result);
result = result + 0.5 * result * (1.0 - arg * result * result);

return result * arg;
}
[/SOURCECODE]

As far as I know this was written by Tod Baudais. It runs several times faster than sqrt and gives the same result.
Quote this message in a reply
Mars_999
Unregistered
 
Post: #7
Quote:Originally posted by OneSadCookie
The sqrt-related PowerPC instructions that are available on Macs are only for reciprocal square roots, so they're seldom any use for distance formulae.


Confused on what your getting at here? The sqrt() math.h function is not totally accurate? Or am I missing the point here? Square root is a square root unless its a cube root? :sorry:
Quote this message in a reply
Member
Posts: 177
Joined: 2002.08
Post: #8
The problem is that sqrt() is *slow*. What's being discussed here is ways to get a slightly less accurate result much faster.
Quote this message in a reply
Mars_999
Unregistered
 
Post: #9
Quote:Originally posted by Mark Levin
The problem is that sqrt() is *slow*. What's being discussed here is ways to get a slightly less accurate result much faster.


Ok, yes I agree with that sqrt() is slow. Now everything is clear!!
Quote this message in a reply
Member
Posts: 370
Joined: 2002.04
Post: #10
Quote:Originally posted by Mars_999
Confused on what your getting at here? The sqrt() math.h function is not totally accurate? Or am I missing the point here? Square root is a square root unless its a cube root? :sorry:


I would assume that reciprocal square roots would have something to do with taking the square root of numbers such as 1/5 (.2)...
But don't trust me on that...

Did you ever wonder why we had to run for shelter when the promise of a brave new world unfurled beneath the clear blue sky?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #11
no, frsqrte returns an estimate of 1/√x.
Quote this message in a reply
Member
Posts: 370
Joined: 2002.04
Post: #12
Ok, in that case 1/frsqrte(x) would be about equal to sqrt(x)...Right?
Steven

Did you ever wonder why we had to run for shelter when the promise of a brave new world unfurled beneath the clear blue sky?
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #13
Um, yeah, but frsqrte isn't particularly accurate, and division and loading floating point constants is pretty slow. That's why the code David posted is done the way it is.

It uses frsqrte to get an approximation to the right answer, two steps of Newton-Raphson to make that approximation more accurate (probably to about the precision of a float?), and then does x ⋅ 1/√x (≈ √x) to turn the approximation to the inverse into something more useful. Multiplication is much faster than division, and since x is already in a register, there's no need to load any floating point constants.
Quote this message in a reply
kberg
Unregistered
 
Post: #14
Quote:Originally posted by David
[SOURCECODE]
float fast_sqrt (register float arg)
{
<..snip..>
}
[/SOURCECODE]

As far as I know this was written by Tod Baudais. It runs several times faster than sqrt and gives the same result.

I have been trying for some time to get frsqrte working inside project builder. I've done some reading, and gotten this function to compile; but it then produces the following error:

{standard input}:1215:instruction is optional for the PowerPC (not allowed without -force_cpusubtype_ALL option)

the code I've been mucking around with is this:
[SOURCECODE]
float qsqrt(register float arg)
{
register float res;

if (arg == 0.0f)
return 0.0f;
__asm__ __volatile__ ("frsqrte %0, %1" : "=f" (res) : "f" (arg));
res += 0.5f * res * (1.0f - arg * res * res);
res += 0.5f * res * (1.0f - arg * res * res);
return res * arg;
}
[/SOURCECODE]

Any help would this would be really useful to me, as a lot of my vector normalisation doesn't require absolute precision.
Quote this message in a reply
Luminary
Posts: 5,143
Joined: 2002.04
Post: #15
If you #include <ppc_intrinsics.h>, you get a pair of macros __frsqrte and __frsqrtes which act like functions but expand out to the assembly. Much easier Smile

As it says, you can't rely on frsqrte being available on the PowerPC, although it is on all* PowerPCs Apple has ever used. To placate the compiler, you'll need to add the option it suggests to your OTHER_CFLAGS in the target settings.

*except maybe like the 601 or something...

Note that if you're using this for vector normalization, you'll be dividing by the result of the square root, so you might as well multiply by the inverse of the square root, and avoid a multiply and a divide...
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Fast Distance formula? mikey 11 7,069 Nov 23, 2009 10:43 AM
Last Post: mikey
  calculating X and Y coordinates w/ an angle and distance ferum 13 14,457 Jun 25, 2008 10:53 PM
Last Post: rosenth
  Signed distance fields imikedaman 16 9,015 Jul 20, 2007 07:13 PM
Last Post: imikedaman
  Speed distance velocity and other headaches Thinker 6 3,524 Jul 3, 2003 09:55 AM
Last Post: Thinker