How distance_approx() works??

[nolddor]

I needed to calculate the distance between two points... (x¹,y¹) and (x²,y²).

Searching for a pre-made function in SGDK I found out (in math.c) one which seems to do what I need... distance_approx() but this method only needs two parameters... so I'm not able to underestand how this method works.

(probably this method it isn't suitable for my purpose)

Code: Select all

u32 distance_approx(s32 dx, s32 dy)
{
    u32 min, max;

    if (dx < 0) dx = -dx;
    if (dy < 0) dy = -dy;

    if (dx < dy )
    {
        min = dx;
        max = dy;
    }
    else
    {
        min = dy;
        max = dx;
    }

    // coefficients equivalent to ( 123/128 * max ) and ( 51/128 * min )
    return ((max « 8) + (max « 3) - (max « 4) - (max « 1) +
             (min « 7) - (min « 5) + (min « 3) - (min « 1)) » 8;
}

[Grind]

I think this is calculating a point from the origin (0,0) so you could give it the difference between the 2 coordinates you have.

Code: Select all

u32 distance = distance_approx(x2 - x1, y2 - y1);

Don't get how the part at the end works though.

[Stef]

@grind> That is

@nolddor> Real distance computation given a DX,DY couple involve multiplication and square root operation : distance = Sqrt(DX²+DY²)
which is too slow to be used in game condition on Megadrive so the method here give you a quick approximation of the distance given the DX and DY parameters. Another solution is to use a look up table to compute X² from X (128 KB LUT for 16 bit type) then consider all distance in ² form.

[Manveru]

If you need just an approximation, you can do something like this:

Code: Select all

#define get_approx_distance( _x1, _x2, _y1, _y2 ) \
	const u16 dx = abs( (_x1) - (_x2) ); \
	const u16 dy = abs( (_y1) - (_y2) ); \
	const u16 approx_distance = MAX( dx, dy ) + ( MIN( dx, dy ) >> 2 )

[nolddor]

Thanks everybody for your advices =)