TheGameCreators - CodeBase - 2/3 time 2D distance computing

Category: Functions

Version: 1.0

Information

Uploaded: 29th Nov 2011 13:12

Modified: 29th Nov 2011 13:56

Author: Naphier

Summary

Approximates the distance between 0,0 and x,y 30% faster than euclidean squares method because no square root calculation (approximation) is needed

Full Description

Also includes the formula for 3D point distance calculation, but it doesn't work well. Deviation is around 60%.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

`The approx_distance(x,y) function is a linear calculation for distance.

`It is around 30% faster than the pythagorean squares method and has around 2% deviation.

`-------------------------------------------Test Drivers---------------------------------------------

`uncomment the sections you'd like to use for testing

// 	`---Declarations needed for any test driver---

// 	#constant iter = 100

// 	set text font "Courier"

// 	randomize timer()

// 	`---Deviation Test---

// 		for n = 0 to iter

// 			x# = (rnd(100) - 50.0)/3

// 			y# = (rnd(100) - 50.0)/3

// 			z# = (rnd(100) - 50.0)/3

// 			//sum_diff# = sum_diff# + abs(approx_distance(x#,y#) - true_distance(x#,y#)) / true_distance(x#,y#)

// 			sum_diff# = sum_diff# + abs(approx3d_distance(x#,y#,z#) - true3d_distance(x#,y#,z#)) / true3d_distance(x#,y#,z#)

//  			print "approx = ",approx3d_distance(x#,y#,z#)

//  			print "true   = ",true3d_distance(x#,y#,z#)

// 		next n

// 		avg# = sum_diff# / iter

// 		print "Error rate:"

// 		print "    Average deviation = ", avg#

// 		print

// 	`---Computing Time Test---

// 		print "Computing Time comparison:"

// 		t0 = timer()

// 		for n = 0 to iter

// 			x# = (rnd(100000) - 50000.0)/3

// 			y# = (rnd(100000) - 50000.0)/3

// 			z# = (rnd(100000) - 50000.0)/3

// 			//approx_distance(x#,y#)

// 			approx3d_distance(x#,y#,z#)

// 		next n

// 		t1 = timer()

// 		time# = (t1 - t0)/1000.0

// 		print "    Approx Distance function time: ", time#, " seconds"

// 		print

// 		t0 = timer()

// 		for n = 0 to iter

// 			x# = (rnd(100000) - 50000.0)/3

// 			y# = (rnd(100000) - 50000.0)/3

// 			z# = (rnd(100000) - 50000.0)/3

// 			//true_distance(x#,y#)

// 			true3d_distance(x#,y#,z#)

// 		next n

// 		t1 = timer()

// 		time2# = (t1 - t0)/1000.0

// 		print "    True Distance function time: ", time2#, " seconds"

// 		print

// 		print "    Time Difference = ", time2# - time#, " seconds ";

// 		print "over ", iter," iterations"

// 		print "    Time per calculation = ", (time2# - time#)/iter, " seconds "

// 		print "    Percent time saved = ", (100*(time2# - time#)/time2#),"%"

// wait key : end

function approx_distance(x as float,y as float)

if x < 0 then x = -x

if y < 0 then y = -y

if x < y

min = x

max = y

else

min = y

max = x

endif

approx = ( max * 1007 ) + ( min * 441 )

if ( max < ( min << 4 ) )

approx = approx - ( max * 40 )

endif

result = ( ( approx + 512 ) >> 10 )

// actual calculation is [1007 * max(|x|,|y|) + 441 * min(|x|,|y|)]/1024

//  or 0.5 * [1 + 1/(4 - 2 * 2^0.5)] * min [ (|X|+|Y|) / 2^0.5 , max(|X|,|Y|) ]

endfunction result

// function true_distance(x as float,y as float)

// 	result = ( x^2 + y^2 )^0.5

// endfunction result

// function true3d_distance(x as float,y as float, z as float)

// 	result = ( x^2 + y^2 + z^2 )^0.5

// endfunction result

// 3D distance approximation formula

// 0.5 * [1 + (1 / (3^.25))] * min[ (|X|+|Y|+|Z|)/3^0.5 , max (|X|,|Y|,|Z|) ]

// 0.57216878364870322056364359756274 * min[ (|X|+|Y|+|Z|)/1.7320508075688772935274463415059 , max (|X|,|Y|,|Z|) ]

// should give about 16% error

// meh this doesn't work very well i'm getting 30+ % deviation

// function approx3d_distance(x as float,y as float, z as float)

// 	if x < 0 then x = -x

// 	if y < 0 then y = -y

// 	if z < 0 then z = -z

// 	if x >= y and x >= z then max# = x

// 	if y >= x and y >= z then max# = y

// 	if z >= y and z >= x then max# = z

// 	sumXYZoverQ = (x + y + z)/1.7320508075688772935274463415059

// 	if sumXYZoverQ < max#

// 		min# = sumXYZoverQ

// 	else

// 		min# = max#

// 	endif

// 	result = 0.87991784282579627366559387532727 * min#

// endfunction result

Download

Please login to download

Comments

No comments yet.

Author Name:	Naphier
CodeBase Entries:	8

CodeBase - 2/3 time 2D distance computing

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments