Jump to content
  • Advertisement

Archived

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

Ersvik

3d distance algo

This topic is 5839 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!