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));
} 3d distance algo
Author
Hello everybody!
Found this in the ROTT code:
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.
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.
I whipped up a quick app to test this:
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)
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]
(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]
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.
Overall, the results usually seem close. With larger numbers you get a larger difference. I wouldn''t use it in my game.
Back then, I expect such an optimisation may have been worth doing. Now, I doubt it.
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
