How distance_approx() works??

SGDK only sub forum

Moderator: Stef

Post Reply
nolddor
Very interested
Posts: 101
Joined: Sun Jun 02, 2013 1:35 pm
Location: Spain

How distance_approx() works??

Post by nolddor » Wed Nov 11, 2015 10:21 pm

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
Very interested
Posts: 66
Joined: Fri Jun 13, 2014 1:26 pm
Location: US
Contact:

Re: How distance_approx() works??

Post by Grind » Wed Nov 11, 2015 11:05 pm

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
Very interested
Posts: 3004
Joined: Thu Nov 30, 2006 9:46 pm
Location: France - Sevres
Contact:

Re: How distance_approx() works??

Post by Stef » Thu Nov 12, 2015 4:10 pm

@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
Very interested
Posts: 77
Joined: Wed Sep 05, 2012 3:30 pm

Re: How distance_approx() works??

Post by Manveru » Fri Nov 13, 2015 5:31 am

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 )
The man who moves a mountain begins by carrying away small stones. Confucius, 551-479 BC

nolddor
Very interested
Posts: 101
Joined: Sun Jun 02, 2013 1:35 pm
Location: Spain

Re: How distance_approx() works??

Post by nolddor » Fri Nov 13, 2015 7:35 am

Thanks everybody for your advices =)

Post Reply