Bay 12 Games Forum

Quote from: Rafal99 on June 17, 2010, 10:58:21 am

Concerning dwarves searching for items, and checking distance to every item, if this is done that way, it should be optimized. Distance calculations should avoid sqrt() which is expensive if they don't already.

You can easily compare distances with acceptable accuracy just by using only addition, bitshifting, and Abs.

Example:
(Abs(Origin_X-Target_X) Shl 4) + (Abs(Origin_Y-Target_Y) Shl 4) + (Abs(Origin_Z-Target_Z) Shl 12)

Such comparison would be lightning fast, and would rarely assign a dwarf something that is a greater distance away. It would also help to prevent dwarves from thinking something directly above them that may or may not have nearby access is actually closer, though I do think Toady's got that covered with the current system.

How does it work?

Abs(X₁-X₂) makes the number positive. This operation is extremely fast, requiring only 3 opcodes on the x86. Abs(X₁-X₂) will henceforth be referred to as "A".

A Shl Y Is equivalent to A*2^Y. While this is far from a perfect linear distance, it would work
beautifully for mere comparisons. This operation is a single opcode on the x86.

And, lastly, adding the three A values for X, Y, and Z (shifting the bits farther left for the Z axis) is, very obviously, trivial.

Sorry for getting so technical, but if Toady sees this post, he must realize the awesomeness of this method.

ADD IT NOW, TARN! PLEASE!!
[/size]

dist = sqrt(xdist*xdist + ydist*ydist + zdist*zdist);
if (dist < minimumDist) {   //this item is closest so far, do stuff

squareDist = xdist*xdist + ydist*ydist + zdist*zdist);
if (squareDist < minimumSquareDist) {  //this item is closest so far, do stuff