Archived

This topic is now archived and is closed to further replies.

Ersvik

3d distance algo

Recommended Posts

Hello everybody! Found this in the ROTT code:
int Find_3D_Distance(int ix, int iy, int iz)
   {
   int   t;

   ix= abs(ix);           /* absolute values */
   iy= abs(iy);
   iz= abs(iz);

   if (ix < iy)
     SWAP(ix,iy);

   if (ix < iz)
     SWAP(ix,iz);

   t = iy + iz;

   return (ix - (ix>>4) + (t>>2) + (t>>3));
   }   
seems really interesting, although I wonder.. how accurate is this algorithm? It's accuracy seems to depend on a certain ratio between ix, iy, and iz, doesn't it? Well, just wanted to know what people think about this one. Johan Ersvik [edited by - ersvik on December 23, 2002 6:34:25 PM] [edited by - ersvik on December 23, 2002 6:35:32 PM]

Share this post


Link to post
Share on other sites
I find it amusing that the only comment in there is to say that the abs function gives the absolute value... duh! How about a comment explaining the algorithm???

Looks like a special case to me... I don''t see how adding and dividing can produce a square-root like result (which is the real way to get the linear distance from xyz differences), though I''m not a math genius.

Although think of bit shifting as dividing. x>>2 is the same as x/4, etc.

Share this post


Link to post
Share on other sites
I whipped up a quick app to test this:


(253, 144, 204)
Accurate: 355.473
Hack: 368
---------------
(218, 234, 185)
Accurate: 369.466
Hack: 361
---------------
(8, 195, 108)
Accurate: 223.054
Hack: 120
---------------
(16, 116, 13)
Accurate: 117.818
Hack: 63
---------------
(73, 133, 53)
Accurate: 160.708
Hack: 138


Lame. Doesn't even work. Won't bother profiling. Want to see the source? Tell me.

EDIT: Modified the program a little bit to find out the "margin of error." Over 10000 runs with randoms ints (0-1023), the average ratio of the hacked value to the accurate value (hacked over accurate) was 0.868301.

EDIT #2: The average ratio approached about .87. (Meaning that the hack returned 87 when it should have returned 100)

DOMAIN: 0-1 AVERAGE (HACKED/ACCURATE): 0.500005
DOMAIN: 0-3 AVERAGE (HACKED/ACCURATE): 0.578696
DOMAIN: 0-7 AVERAGE (HACKED/ACCURATE): 0.734991
DOMAIN: 0-15 AVERAGE (HACKED/ACCURATE): 0.826244
DOMAIN: 0-31 AVERAGE (HACKED/ACCURATE): 0.846238
DOMAIN: 0-63 AVERAGE (HACKED/ACCURATE): 0.856705
DOMAIN: 0-127 AVERAGE (HACKED/ACCURATE): 0.866307
DOMAIN: 0-255 AVERAGE (HACKED/ACCURATE): 0.869578
DOMAIN: 0-511 AVERAGE (HACKED/ACCURATE): 0.871254
DOMAIN: 0-1023 AVERAGE (HACKED/ACCURATE): 0.872087
DOMAIN: 0-2047 AVERAGE (HACKED/ACCURATE): 0.870829
DOMAIN: 0-4095 AVERAGE (HACKED/ACCURATE): 0.869578
DOMAIN: 0-8191 AVERAGE (HACKED/ACCURATE): 0.866411
DOMAIN: 0-16383 AVERAGE (HACKED/ACCURATE): 0.871571
DOMAIN: 0-32767 AVERAGE (HACKED/ACCURATE): 0.869586

A few more statistics:

The Hacked was within 1% of the Accurate 7.5% of the time.
The Hacked was within 5% of the Accurate 34.5% of the time.
The Hacked was within 15% of the Accurate 62.5% of the time.

[edited by - Neosmyle on December 23, 2002 7:40:37 PM]

[edited by - Neosmyle on December 23, 2002 7:44:28 PM]

Share this post


Link to post
Share on other sites
I did the same thing, created a test program. Neosmyle, your "Hack" numbers seem to be off for all but the first.

Overall, the results usually seem close. With larger numbers you get a larger difference. I wouldn''t use it in my game.

Share this post


Link to post
Share on other sites