#### Archived

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

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

## 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 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 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.500005DOMAIN:  0-3      AVERAGE (HACKED/ACCURATE):  0.578696DOMAIN:  0-7      AVERAGE (HACKED/ACCURATE):  0.734991DOMAIN:  0-15      AVERAGE (HACKED/ACCURATE):  0.826244DOMAIN:  0-31      AVERAGE (HACKED/ACCURATE):  0.846238DOMAIN:  0-63      AVERAGE (HACKED/ACCURATE):  0.856705DOMAIN:  0-127      AVERAGE (HACKED/ACCURATE):  0.866307DOMAIN:  0-255      AVERAGE (HACKED/ACCURATE):  0.869578DOMAIN:  0-511      AVERAGE (HACKED/ACCURATE):  0.871254DOMAIN:  0-1023      AVERAGE (HACKED/ACCURATE):  0.872087DOMAIN:  0-2047      AVERAGE (HACKED/ACCURATE):  0.870829DOMAIN:  0-4095      AVERAGE (HACKED/ACCURATE):  0.869578DOMAIN:  0-8191      AVERAGE (HACKED/ACCURATE):  0.866411DOMAIN:  0-16383      AVERAGE (HACKED/ACCURATE):  0.871571DOMAIN:  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 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.

1. 1
2. 2
Rutin
20
3. 3
khawk
17
4. 4
A4L
14
5. 5

• 12
• 16
• 26
• 10
• 44
• ### Forum Statistics

• Total Topics
633759
• Total Posts
3013720
×