More accurate distance algorithm?

[d_m]

The current distance calculation in HEAD uses:

max(dx, dy) + min(dx, dy) / 2

As the comments say, it tends to over-estimate distance by about 1 grid for every 15 grids of actual distance. Is there any good reason not to use a better distance function, for instance:

ceil(sqrt(dy ** 2 + dx ** 2))

I have an implementation together. It only requires some minor tweaks to cave.c to work. I'm going to try to do some profiling and see how much slower it is. The only problems I can imagine are:

1. adding more floating-point math to angband
2. signficantly slower calculation
3. people will hate the drastic increase in ranges

Anway, what do you all think?

[Pete Mack]

Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots.

It's not a bad idea, but I mostly don't even notice the non-standard distance metric.

[PowerDiver]

Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots.

It's not a bad idea, but I mostly don't even notice the non-standard distance metric.

Every so often I try to plan a destruction radius, and I when the radius isn't what I thought it would be I wonder about my ability to do arithmetic. It's nice to see my problem is that the effect is not really a radius.

[d_m]

Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots.

So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written.

Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this.

On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?

[takkaria]

So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written.

Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this.

On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?

Where? I can only see it being used in frontends and in wiz-stats.c, where it's fine.

[d_m]

Where? I can only see it being used in frontends and in wiz-stats.c, where it's fine.

Ooops! I guess I was just looking at wiz-stats.c.

As long as you're here, how would you feel about an improved distance algorithm? Especially if distances over 20 aren't important, it should be easy to implement a fast integer-sqrt algorithm.

[takkaria]

Ooops! I guess I was just looking at wiz-stats.c.

As long as you're here, how would you feel about an improved distance algorithm? Especially if distances over 20 aren't important, it should be easy to implement a fast integer-sqrt algorithm.

Yeah, I'm happy to have a better distance() algorithm iff it's integer-based.

[d_m]

Yeah, I'm happy to have a better distance() algorithm iff it's integer-based.

Great. I just tested an integer-based sqrt algorithm between 0 and 10,000; I will be sending a patch to dev shortly. Thanks.

[Pete Mack]

So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written.

Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this.

On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?

That's not what I meant, sorry

dx^2 + dy^2 <= r^2

gives the same results as

sqrt(dx^2 + dy^2) <= r

but it doesn't require taking a root. (There's already code like this for stealth computation.)