accurate distance

Collapse
X
 
  • Time
  • Show
Clear All
new posts
  • PowerDiver
    Prophet
    • Mar 2008
    • 2820

    accurate distance

    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
    Swordsman
    • Jul 2008
    • 308

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

    Code:
    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);
    }

    Comment

    • ekolis
      Knight
      • Apr 2007
      • 921

      #3
      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?
      You read the scroll labeled NOBIMUS UPSCOTI...
      You are surrounded by a stasis field!
      The tengu tries to teleport, but fails!

      Comment

      • Pete Mack
        Prophet
        • Apr 2007
        • 6883

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

        Comment

        • Magnate
          Angband Devteam member
          • May 2007
          • 5110

          #5
          Originally posted by 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?
          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.
          "Been away so long I hardly knew the place, gee it's good to be back home" - The Beatles

          Comment

          • PowerDiver
            Prophet
            • Mar 2008
            • 2820

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

            Comment

            • d_m
              Angband Devteam member
              • Aug 2008
              • 1517

              #7
              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.
              linux->xterm->screen->pmacs

              Comment

              • PowerDiver
                Prophet
                • Mar 2008
                • 2820

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

                Comment

                Working...
                😀
                😂
                🥰
                😘
                🤢
                😎
                😞
                😡
                👍
                👎