accurate distance

[PowerDiver]

I distinctly remember someone implementing a correct distance function, and thought it made it into the V dev code. I seem to remember being pleased that radius 15 destruction actually destroyed those points within a distance of 15. However, distance() in 3.1.2 is the same hack it used to be. I checked some revs on my machine I haven't deleted, and no diff there either.

Did anyone ever release something with a correct distance function? Is there some reason not to use it?

[RogerN]

I don't know the answer to your exact question, but fast integer distance functions are pretty standard fare in all sorts of games:

static int isqrt(int num)
{
    if (num == 0)
        return 0;
    int n = (num / 2) + 1;
    int n1 = (n + (num / n)) / 2;
    while (n1 < n)
    {
        n = n1;
        n1 = (n + (num / n)) / 2;
    }
    return n;
}

static int distance(int x1, int y1, int x2, int y2)
{
    int dx = x2 - x1;
    int dy = y2 - y1;
    return isqrt(dx*dx + dy*dy);
}

[ekolis]

But unless there's some magic I'm not aware of going on in the background, it takes 1 move to move straight and 1 move to move diagonally... not 1 to move straight and sqrt(2) to move diagonally, or 2 to move straight and 3 to move diagonally... so why should distance calculations be any different from movement when it comes to detection, archery, spellcasting, and even lighting?

[Pete Mack]

btw, you don't actually have to compute the square root to do distance calculations.

x^2 + y^2 <= r^2

is a lot easier than

sqrt(x^2 + y^2) <= r

[Magnate]

I distinctly remember someone implementing a correct distance function, and thought it made it into the V dev code. I seem to remember being pleased that radius 15 destruction actually destroyed those points within a distance of 15. However, distance() in 3.1.2 is the same hack it used to be. I checked some revs on my machine I haven't deleted, and no diff there either.

Did anyone ever release something with a correct distance function? Is there some reason not to use it?

Have you checked the angband-dev ML archive? ISTR this being offered around the time I started contributing as a dev, so about a year ago, give or take a month or two. I definitely remember it too, it was quite elegant.

[PowerDiver]

Suppose dx > dy. The distance function in V is currently dx + (dy/2) .

I agree with Pete that one should just use distance_squared when possible, which is presumably all of the time. The only time I imagine non-squared distance is needed in *bands is for ball damage effects, but they don't properly work off of distance anyway, and their answer is a small lookup table or perhaps the travesty above.

These are computable in constant time, so speed is not relevant.

[d_m]

I wrote the patch to do this (modulo community suggestions), but it was before I had commit access and it never made it into V.

I will dig it up and see if it still works--it kind of dropped off my radar but I do think it would be nice.

[PowerDiver]

I think you need to change your distance function to round. Consider radius 1 and radius 2 balls. I think the current implementation is right, although familiarity does cause bias.

For a radius 1 ball, distance \sqrt{2} is inside the ball. Also, distance \sqrt{5} is inside a radius 2 ball, but distance \sqrt{8} is not. In these cases rounding works.

Of course, I don't think the distance function should be called for inclusion in a ball. Instead there should be a macro inside_ball(dx, dy, r).

The only times I know of that distance is important besides ball inclusion is for reduction in ball damage or minuses on ranged attacks. Nevertheless it might be good to be consistent.