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; } }
' "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