Go to notes and algorithms index. ~ Go to home page.

distance_2D() and length_2D()


Integer Version, using a look-up table.

The first function finds the distance between two points, and the second function finds the length of a vector line.

The most obvious method you can use to find the length of a line in a co-ordinate system is pythagoras (because you can easily find the length of the other two sides as dx and dy)... but to perform the pythagoras calculation you need to do (for a 2D line) two multiplies (to get the squares of the dx and dy) and then, worst of all, a square root, which tends to be quite CPU intensive. Since we're dealing with video games (a world where geometry usually only needs to be a good approximation rather than spot-on) we could use some sort of square root approximation function to speed things-up ... however I decided to look at the problem from the other perspective and use trigonometry. I thought by using trig I could probably write a more efficient routine because I would only need to a look-up table for gradients of dy/dx or dx/dy for the equivelent of 0 to 45 degrees, whereas if I had used pythagoras I would need to emulate the square-root function for a huge range of values (needing a bigger look-up table or a more complex routine).

By the way... if you only want to compare distances or compare line lengths then the pythagoras method does come into its own because you can just compare the squared length of, say, two lines to see which is longest -- you do not need to do the square root unless you want to know the actual linear length of the lines. This quick method is sometimes used for simple collision detection: for example you could tell if one co-ordinate was closer to another than say 10 units by doing:
if ( dx * dx + dy * dy < 100 ) printf( "Too close" );

Anyway, this routine should be quicker than doing pythagorus (needing two multiplies and one square root) because it only does one multiply, one divide and then another (unseen) multiply when it references the look-up table.... the rest of the stuff are things like add, subract and bit shifts which are done in one or less CPU cycle on most CPUs.



static const unsigned char distance_table[1025] = {
      0,   1,   2,   3,   4,   5,   6,   7,   8,   9,  10,  11,  12,  13,  14,  15,
     16,  16,  17,  18,  19,  20,  21,  22,  23,  24,  25,  26,  26,  27,  28,  29,
     30,  31,  32,  33,  33,  34,  35,  36,  37,  38,  39,  39,  40,  41,  42,  43,
     44,  44,  45,  46,  47,  48,  48,  49,  50,  51,  51,  52,  53,  54,  54,  55,
     56,  57,  58,  58,  59,  60,  60,  61,  62,  63,  63,  64,  65,  65,  66,  67,
     68,  68,  69,  70,  70,  71,  72,  72,  73,  74,  74,  75,  76,  76,  77,  77,
     78,  79,  79,  80,  81,  81,  82,  82,  83,  84,  84,  85,  85,  86,  86,  87,
     88,  88,  89,  89,  90,  90,  91,  91,  92,  93,  93,  94,  94,  95,  95,  96,
     96,  97,  97,  98,  98,  99,  99, 100, 100, 101, 101, 101, 102, 102, 103, 103,
    104, 104, 105, 105, 105, 106, 106, 107, 107, 108, 108, 108, 109, 109, 110, 110,
    110, 111, 111, 111, 112, 112, 113, 113, 113, 114, 114, 114, 115, 115, 115, 116,
    116, 116, 117, 117, 117, 118, 118, 118, 118, 119, 119, 119, 120, 120, 120, 120,
    121, 121, 121, 121, 122, 122, 122, 122, 123, 123, 123, 123, 124, 124, 124, 124,
    124, 125, 125, 125, 125, 125, 126, 126, 126, 126, 126, 126, 127, 127, 127, 127,
    127, 127, 127, 128, 128, 128, 128, 128, 128, 128, 128, 129, 129, 129, 129, 129,
    129, 129, 129, 129, 129, 129, 129, 130, 130, 130, 130, 130, 130, 130, 130, 130,
    130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130,
    130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 130, 129, 129, 129, 129, 129,
    129, 129, 129, 129, 129, 129, 129, 128, 128, 128, 128, 128, 128, 128, 128, 127,
    127, 127, 127, 127, 127, 127, 126, 126, 126, 126, 126, 126, 125, 125, 125, 125,
    125, 124, 124, 124, 124, 124, 123, 123, 123, 123, 123, 122, 122, 122, 122, 121,
    121, 121, 121, 120, 120, 120, 120, 119, 119, 119, 118, 118, 118, 118, 117, 117,
    117, 116, 116, 116, 116, 115, 115, 115, 114, 114, 114, 113, 113, 113, 112, 112,
    112, 111, 111, 110, 110, 110, 109, 109, 109, 108, 108, 107, 107, 107, 106, 106,
    105, 105, 105, 104, 104, 103, 103, 103, 102, 102, 101, 101, 100, 100,  99,  99,
     99,  98,  98,  97,  97,  96,  96,  95,  95,  94,  94,  93,  93,  92,  92,  91,
     91,  90,  90,  89,  89,  88,  88,  87,  87,  86,  86,  85,  85,  84,  84,  83,
     82,  82,  81,  81,  80,  80,  79,  78,  78,  77,  77,  76,  76,  75,  74,  74,
     73,  73,  72,  71,  71,  70,  69,  69,  68,  68,  67,  66,  66,  65,  64,  64,
     63,  62,  62,  61,  60,  60,  59,  58,  58,  57,  56,  56,  55,  54,  54,  53,
     52,  52,  51,  50,  50,  49,  48,  47,  47,  46,  45,  44,  44,  43,  42,  42,
     41,  40,  39,  39,  38,  37,  36,  36,  35,  34,  33,  32,  32,  31,  30,  29,
    241, 241, 241, 241, 241, 242, 242, 242, 242, 242, 243, 243, 243, 243, 243, 243,
    244, 244, 244, 244, 244, 244, 245, 245, 245, 245, 245, 245, 245, 245, 246, 246,
    246, 246, 246, 246, 246, 246, 247, 247, 247, 247, 247, 247, 247, 247, 247, 247,
    248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248,
    248, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249,
    249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 249, 248, 248,
    248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 248, 247,
    247, 247, 247, 247, 247, 247, 247, 247, 247, 247, 246, 246, 246, 246, 246, 246,
    246, 246, 246, 245, 245, 245, 245, 245, 245, 245, 244, 244, 244, 244, 244, 244,
    244, 243, 243, 243, 243, 243, 243, 242, 242, 242, 242, 242, 242, 241, 241, 241,
    241, 241, 240, 240, 240, 240, 240, 239, 239, 239, 239, 238, 238, 238, 238, 238,
    237, 237, 237, 237, 236, 236, 236, 236, 235, 235, 235, 235, 234, 234, 234, 234,
    233, 233, 233, 233, 232, 232, 232, 231, 231, 231, 231, 230, 230, 230, 229, 229,
    229, 229, 228, 228, 228, 227, 227, 227, 226, 226, 226, 225, 225, 225, 224, 224,
    224, 223, 223, 223, 222, 222, 222, 221, 221, 221, 220, 220, 220, 219, 219, 219,
    218, 218, 217, 217, 217, 216, 216, 216, 215, 215, 214, 214, 214, 213, 213, 212,
    212, 212, 211, 211, 210, 210, 210, 209, 209, 208, 208, 207, 207, 207, 206, 206,
    205, 205, 204, 204, 204, 203, 203, 202, 202, 201, 201, 200, 200, 200, 199, 199,
    198, 198, 197, 197, 196, 196, 195, 195, 194, 194, 193, 193, 193, 192, 192, 191,
    191, 190, 190, 189, 189, 188, 188, 187, 187, 186, 186, 185, 184, 184, 183, 183,
    182, 182, 181, 181, 180, 180, 179, 179, 178, 178, 177, 177, 176, 175, 175, 174,
    174, 173, 173, 172, 172, 171, 170, 170, 169, 169, 168, 168, 167, 167, 166, 165,
    165, 164, 164, 163, 162, 162, 161, 161, 160, 160, 159, 158, 158, 157, 157, 156,
    155, 155, 154, 153, 153, 152, 152, 151, 150, 150, 149, 149, 148, 147, 147, 146,
    145, 145, 144, 143, 143, 142, 142, 141, 140, 140, 139, 138, 138, 137, 136, 136,
    135, 134, 134, 133, 132, 132, 131, 130, 130, 129, 128, 128, 127, 126, 126, 125,
    124, 124, 123, 122, 121, 121, 120, 119, 119, 118, 117, 117, 116, 115, 114, 114,
    113, 112, 112, 111, 110, 109, 109, 108, 107, 107, 106, 105, 104, 104, 103, 102,
    101, 101, 100,  99,  99,  98,  97,  96,  96,  95,  94,  93,  93,  92,  91,  90,
     90,  89,  88,  87,  86,  86,  85,  84,  83,  83,  82,  81,  80,  80,  79,  78,
     77,  76,  76,  75,  74,  73,  72,  72,  71,  70,  69,  68,  68,  67,  66,  65,
     64,  64,  63,  62,  61,  60,  60,  59,  58,  57,  56,  56,  55,  54,  53,  52,
     51   };
// ... this array was output from a program: DISL_2D.BAS  (Jon P)


long distance_2D( long v_x1, long v_y1, long v_x2, long v_y2 )
{
   // Jon P  7-Nov-2001
   //
   // Return the distance between the two specified points.
   //
   // Sorry about the lack of meaningful variable names -- I'm keeping the
   // number of variables to 2 to reduce the amount of loading registers to/from
   // memory.
   //
   // If dx and dy is already known then call "length_2D( dx, dy )" instead of this routine.
   //
   //  V1.1 18-Aug-2006  fix zero distance bug.

   static long temp, temp2;
   
   
   temp = v_x1 - v_x2;  // = dx
   if ( temp < 0 ) temp = 0 - temp;

   temp2 = v_y1 - v_y2;  // = dy
   if ( temp2 < 0 ) temp2 = 0 - temp2;
   
   
   if ( temp > temp2 )
   {
      temp2 = ( temp2 << 12 ) / temp;
      // 'temp2' now holds the gradient between 0 and 4096 (equivelent
      // to 0.0 to 1.0 --- i.e. 0 to 45 degrees)
      // 'temp' now holds the largest of either the absolute value dx or dy
      if ( temp2 < 2048 )
      {
         temp2 >>= 2;
         temp *= temp2 + 4096 - distance_table[temp2];
      }
      else
      {
         temp *= ( temp2 >> 1 ) + 3796 - distance_table[ temp2 >> 2 ];
      }
      temp += 2048; // round to the nearest
      temp >>= 12;
      return temp;
   }
   else
   {
      temp <<= 12;
      if ( !temp2 ) return temp2;   // zero distance  (v1.1)
      temp /= temp2;
      // 'temp' now holds the gradient between 0 and 4096 (equivelent
      // to 0.0 to 1.0 --- i.e. 0 to 45 degrees)
      // 'temp2' now holds the largest of either the absolute value dx or dy
      if ( temp < 2048 )
      {
         temp >>= 2;
         temp2 *= temp + 4096 - distance_table[temp];
      }
      else
      {
         temp2 *= ( temp >> 1 ) + 3796 - distance_table[ temp >> 2 ];
      }
      temp2 += 2048;
      temp2 >>= 12;
      return temp2;
   }
     
}


long length_2D( long v_dx, long v_dy )
{
   // Jon P  12-Nov-2001
   //
   // Return the length of the line defined by the supplied dx and dy.
   //
   // ( See also the routine distance_2D() if you prefer to specify
   //              two points instead of dx and dy )
   //
   // Sorry about the lack of meaningful variable names -- I'm keeping the
   // number of variables to 2 to reduce the amount of loading registers to/from
   // memory.
   // 
   //  V1.1 18-Aug-2006  fix zero distance bug.

   static long temp, temp2;
   
   
   temp = v_dx;
   if ( temp < 0 ) temp = 0 - temp;

   temp2 = v_dy;
   if ( temp2 < 0 ) temp2 = 0 - temp2;
   
   
   if ( temp > temp2 )
   {
      temp2 = ( temp2 << 12 ) / temp;
      // 'temp2' now holds the gradient between 0 and 4096 (equivelent
      // to 0.0 to 1.0 --- i.e. 0 to 45 degrees)
      // 'temp' now holds the largest of either the absolute value dx or dy
      if ( temp2 < 2048 )
      {
         temp2 >>= 2;
         temp *= temp2 + 4096 - distance_table[temp2];
      }
      else
      {
         temp *= ( temp2 >> 1 ) + 3796 - distance_table[ temp2 >> 2 ];
      }
      temp += 2048; // round to the nearest
      temp >>= 12;
      return temp;
   }
   else
   {
      temp <<= 12;
      if ( !temp2 ) return temp2;  // zero distance  (v1.1)
      temp /= temp2;
      // 'temp' now holds the gradient between 0 and 4096 (equivelent
      // to 0.0 to 1.0 --- i.e. 0 to 45 degrees)
      // 'temp2' now holds the largest of either the absolute value dx or dy
      if ( temp < 2048 )
      {
         temp >>= 2;
         temp2 *= temp + 4096 - distance_table[temp];
      }
      else
      {
         temp2 *= ( temp >> 1 ) + 3796 - distance_table[ temp >> 2 ];
      }
      temp2 += 2048;
      temp2 >>= 12;
      return temp2;
   }
     
}

Incase it is of interest to you I have pasted the Quick BASIC program below that I used to create the look-up table:
' "distL_2D"
'
' Jon P      (environment: MS Quick BASIC)
'
' This is a dvelopment/test prog to develop a routine to calc the
' length of a 2D line by looking-up the value a pre-calculated array
' which is used to multiply the longest measurement (either dx or dy)
' to get the required length. It will get the value from the array
' subscript according to the gradient  (either dex/dy or dy/dx
' -- which ever is <= 1 )
'
' The primary purpose of this program is to produce the
' precaclulated look-up table array.
'
' ( This is "distL_2D.BAS" -- used to develop the precalculated look-up
'   version, whereas "dist_2D.BAS" is a prog used to develope a formulae
'   version. )
'
' ** NOTE: the data file produced by this prog (of the array data)
'    gets put into C:\Qbasic\dis_tab.txt
'


' This is the C code used in the acual routine to reconstitute the number
' in the look-up table to the required result...
'
'if ( temp2 < 2048 )
'{
'   temp2 >>= 2;
'   temp *= temp2 + 4096 - distance_table[temp2];
'}
'else
'{
'   temp *= ( temp2 >> 1 ) + 3796 - distance_table[ temp2 >> 2 ];
'}
'temp += 2048; // round to the nearest
'temp >>= 12;
'                                                                                  return temp;
'



DECLARE SUB plotat (x!, y!)
DIM goodcolours%(50)

PI = 3.14159
halfPI = PI / 2  ' 90 degrees
twoPI = PI * 2  '360 degrees

colour% = 0
maxcolour% = 12
FOR i% = 0 TO 50
  IF colour% > maxcolour% THEN colour% = 0
  IF colour% = 0 THEN colour% = colour% + 1
  IF colour% = 1 THEN colour% = colour% + 1
  IF colour% = 4 THEN colour% = colour% + 1
  IF colour% = 8 THEN colour% = colour% + 1
  goodcolours%(i%) = colour%
  colour% = colour% + 1
NEXT i%


t1& = 0
t2& = 0



SCREEN 12
CLS


CLS
GOSUB Drawit


END


Drawit:



OPEN "dis_tab.txt" FOR OUTPUT AS #1


' Do a sweep plot of the gradient which is from
' 0 to 4096 which is equivelent to 0.0 to 1.0
' where the max gradient is equal to 1 in 1   i.e. 45 degrees.

' To enable the array to be stored in bytes and not
' short words (and hence saving half the memory)...
' the gradient is subtracted/added to the result so that
' the array is made of relative values, yet there is no
' loss of accuracy.  In the first half of the array
' the values are relative to the gradient >> 2 and in the
' second half of the array they are relative to the
' gradient >> 1 - 300.






coloumncount% = 0
scale = 2
PRINT #1, "static const unsigned char distance_table[1025] = {"
PRINT #1, "   ";
FOR grad& = 0 TO 4096 STEP 4
   '       STEP 4: sample every 4th value because the curve
   '       only changes gradually compared with the
   '       gradient line -- it was found that the values rarely changed
   '       within 4/4096 of 45 degrees.


   ' calculate an equiv grad from 0 to 1.0
   realgrad = grad&
   realgrad = realgrad / 4096
 

   realhyp = SQR((realgrad * realgrad) + 1!)
   COLOR goodcolours%(1)
   CALL plotat(realgrad, (realhyp - 1!) * scale)

   temp = realhyp * 4096
   hyp& = temp

   IF grad& < 2048 THEN
      COLOR goodcolours%(0)
      subtractor& = grad& \ 4
      temp = subtractor&
      temp = temp / 4096
      CALL plotat(realgrad, temp * scale)

      COLOR goodcolours%(2)
      subtractor2& = grad& \ 4
      subtractor2& = subtractor2& - 256
      temp = subtractor2&
      temp = temp / 4096
      CALL plotat(realgrad, temp * scale)

      outputvalue& = (grad& \ 4) - (hyp& - 4096&)


   ELSE

      COLOR goodcolours%(0)
      subtractor& = grad& \ 2
      subtractor& = subtractor& - 300
      temp = subtractor&
      temp = temp / 4096
      CALL plotat(realgrad, temp * scale)

      COLOR goodcolours%(2)
      subtractor2& = grad& \ 2
      subtractor2& = subtractor2& - 300
      subtractor2& = subtractor2& - 256
      temp = subtractor2&
      temp = temp / 4096
      CALL plotat(realgrad, temp * scale)

      outputvalue& = (grad& \ 2) - 300 - (hyp& - 4096&)
  
  
   END IF






   outputstring$ = STR$(outputvalue&)
   IF LEN(outputstring$) < 4 THEN outputstring$ = SPACE$(4 - LEN(outputstring$)) + outputstring$
   PRINT #1, outputstring$;
   IF grad& < 4096 THEN PRINT #1, ",";

   coloumncount% = coloumncount% + 1
   IF (coloumncount% >= 16) THEN
      coloumncount% = 0
      PRINT #1, ""      ' New line.
      PRINT #1, "   ";  ' Indentation.
   END IF
 

NEXT grad&

PRINT #1, "   };"
PRINT #1, "// ... this array was output from a program: DISL_2D.BAS  (Jon P)"
PRINT #1, ""


 



COLOR 7


CLOSE #1

RETURN