iDevGames Forums
Distance in a shootem up 2D - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: Distance in a shootem up 2D (/thread-7269.html)

Pages: 1 2


Distance in a shootem up 2D - Mars_999 - Feb 27, 2003 06:18 PM

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.


Distance in a shootem up 2D - Holmes - Feb 27, 2003 07:08 PM

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.


Distance in a shootem up 2D - OneSadCookie - Feb 27, 2003 07:11 PM

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.


Distance in a shootem up 2D - Mark Levin - Feb 27, 2003 07:43 PM

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.


Distance in a shootem up 2D - OneSadCookie - Feb 27, 2003 07:49 PM

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.


Distance in a shootem up 2D - David - Feb 27, 2003 07:58 PM

[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.


Distance in a shootem up 2D - Mars_999 - Feb 27, 2003 10:48 PM

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:


Distance in a shootem up 2D - Mark Levin - Feb 27, 2003 11:43 PM

The problem is that sqrt() is *slow*. What's being discussed here is ways to get a slightly less accurate result much faster.


Distance in a shootem up 2D - Mars_999 - Feb 28, 2003 04:43 PM

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!!


Distance in a shootem up 2D - Steven - Mar 1, 2003 07:48 PM

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...


Distance in a shootem up 2D - OneSadCookie - Mar 2, 2003 12:51 AM

no, frsqrte returns an estimate of 1/√x.


Distance in a shootem up 2D - Steven - Mar 2, 2003 07:27 AM

Ok, in that case 1/frsqrte(x) would be about equal to sqrt(x)...Right?
Steven


Distance in a shootem up 2D - OneSadCookie - Mar 2, 2003 12:40 PM

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.


Distance in a shootem up 2D - kberg - Mar 2, 2003 01:51 PM

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.


Distance in a shootem up 2D - OneSadCookie - Mar 2, 2003 02:16 PM

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...