Testing for Range - GameCreators Forum

Author

Message

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 20:04

Link

I've been doing some experiments on speed testing for ranges.

The three functions I tested are:

The Test
Compare the range between point A & point B defined as a 2D co-ordinate.

range()
This is a 1D testing method, so here I have simply added the results of the 2 axis together in order to compare it. Results are not terribly accurate but on the whole fairly speedy.

range3D()
Traditional square root method of calculating range. I noticed some alarming innacuracies with large numbers (100,000) or so making me wonder if I typed the algorythm in wrong? Anyway the results are varied, normally the slowest and sometimes significantly slower than the other methods.

fastRange3D
I wrote this especially for the test to see how accurately I could calculate the range of a 2D co-ordinate using 1D maths. I was shocked to see this return the most accurate results and it was consistently the fastest routine! It will now be my standard range calculation method from now on!

The Test Code

sync on

cls 0
text 20,20,"PRESS KEY TO START"
sync : sync
wait key

rem position A
aX=50 : aZ=150
rem position B
bX=0 : bZ=500
rem Intensity of test
testAccuracy#=5000000

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=range(aX,bX)+range(aZ,bZ)
next speed
finish=timer()
cls 0
report(start,finish,testAccuracy#,totalRange)

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=range3D(aX,aZ,bX,bZ)
next speed
finish=timer()
report(start,finish,testAccuracy#,totalRange)

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=fastRange3D(aX,aZ,bX,bZ)
next speed
finish=timer()
report(start,finish,testAccuracy#,totalRange)
end

`* The different range commands
function fastRange3D(aX,aZ,bX,bZ)
   rngX#=abs(aX-bX)
   rngZ#=abs(aZ-bZ)
   if rngX#>rngZ#
      result#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      result#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf
endfunction result#
function Range(val1,val2)
   result=abs(val1-val2)
endfunction result
function Range3D(aX,aZ,bX,bZ)
   result=sqrt(((aX-bX)^2)+((aZ-bZ)^2))
endfunction result

`* Report Results
function report(start,finish,testAccuracy#,totalRange)
   calculation#=finish-start
   calculation#=calculation#/testAccuracy#
   text 20,20,str$(testAccuracy#)+" cycles took: "+str$(finish-start)
   text 20,40,"Each Calculation: "+str$(calculation#)
   text 20,60,"Tested Result: "+str$(totalRange)
   sync : sync
   wait key
endfunction

+ Code Snippet

sync on

cls 0
text 20,20,"PRESS KEY TO START"
sync : sync
wait key

rem position A
aX=50 : aZ=150
rem position B
bX=0 : bZ=500
rem Intensity of test
testAccuracy#=5000000

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=range(aX,bX)+range(aZ,bZ)
next speed
finish=timer()
cls 0
report(start,finish,testAccuracy#,totalRange)

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=range3D(aX,aZ,bX,bZ)
next speed
finish=timer()
report(start,finish,testAccuracy#,totalRange)

cls 0 : sync
start=timer()
for speed=1 to testAccuracy#
   totalRange=fastRange3D(aX,aZ,bX,bZ)
next speed
finish=timer()
report(start,finish,testAccuracy#,totalRange)
end

`* The different range commands
function fastRange3D(aX,aZ,bX,bZ)
   rngX#=abs(aX-bX)
   rngZ#=abs(aZ-bZ)
   if rngX#>rngZ#
      result#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      result#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf
endfunction result#
function Range(val1,val2)
   result=abs(val1-val2)
endfunction result
function Range3D(aX,aZ,bX,bZ)
   result=sqrt(((aX-bX)^2)+((aZ-bZ)^2))
endfunction result

`* Report Results
function report(start,finish,testAccuracy#,totalRange)
   calculation#=finish-start
   calculation#=calculation#/testAccuracy#
   text 20,20,str$(testAccuracy#)+" cycles took: "+str$(finish-start)
   text 20,40,"Each Calculation: "+str$(calculation#)
   text 20,60,"Tested Result: "+str$(totalRange)
   sync : sync
   wait key
endfunction

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 20:07

Link

hehe! On proof reading I notice I left the routine calculating using real numbers instead of integers and it was still fast...

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

rapscaLLion

23

Years of Service

User Offline

Joined: 29th Aug 2002

Location: Canada

Posted: 4th Apr 2003 20:13

Link

Um... is this a distance finding function? IE- Is it to find the length of a line in 3D space?

Anyway:

Quote: "function Range3D(aX,aZ,bX,bZ)
result=sqrt(((aX-bX)^2)+((aZ-bZ)^2))"

Is it just me, or is that only a 2D calculation? Nope, it's not me!

Alex Wanuch
aka rapscaLLion
Kousen Dev Progress >> Currently Working On Editors

Back to top

Profile PM

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 20:18

Link

Yeah excuse the function title and read the text where I said it's a 2D calculation

hehe... The function title is because I modified an existing routine and didn't change it.

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

Beta1

23

Years of Service

User Offline

Joined: 28th Dec 2002

Location:

Posted: 4th Apr 2003 20:20

Link

sorry to be pendantic but your 3d and fast3d functions are only measuring 2d distance... theres no y axis variable I can see.

Anyone know how to do true 3d distance? ie between x,y,z and x', y', z' where the two points dont lie along any of the axes?

Back to top

Profile PM

Beta1

23

Years of Service

User Offline

Joined: 28th Dec 2002

Location:

Posted: 4th Apr 2003 20:21

Link

whoops - x-post. That will teach me to post something then wander off, come back and hit reply!

Back to top

Profile PM

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 20:27

Link

OK here is the fastRange3D() function again but in 3D not 2D

+ Code Snippet

function fastRange3D(aX,aY,aZ,bX,bY,bZ)
   rngX#=abs(aX-bX)
   vertical#=abs(aY-bY)
   rngZ#=abs(aZ-bZ)

   if rngX#>rngZ#
      horizontal#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      horizontal#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf

   if horizontal#>vertical#
      result=horizontal#+((vertical#/horizontal#)*vertical#)
   else
      result=vertical#+((horizontal#/vertical#)*horizontal#)
   endIf
endfunction result

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 20:33 Edited at: 4th Apr 2003 20:36

Link

And for those who don't give a hoot about the subject and just want some range checking routines heres my new and complete set of range checking tools

=range (valueA , valueB)
1 Dimensional

=range2D (valueAX,value AZ , valueBX,valueBZ)
2 Dimensional
=fastrange2D (valueAX,valueAZ , valueBX,valueBZ)
2 Dimensional

=range3D (valueAX,valueAY,valueAZ , valueBX,valueBY,valueBZ)
3 Dimensional
=fastRange3D (valueAX,valueAY,valueAZ , valueBX,valueBY,valueBZ)
3 Dimensional

The fast routines will yield less accurate results but perform even quicker because they use integers instead of real numbers

function Range3D(aX,aY,aZ,bX,bY,bZ)
   rngX#=abs(aX-bX)
   vertical#=abs(aY-bY)
   rngZ#=abs(aZ-bZ)

if rngX#>rngZ#
      horizontal#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      horizontal#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf

if horizontal#>vertical#
      result#=horizontal#+((vertical#/horizontal#)*vertical#)
   else
      result#=vertical#+((horizontal#/vertical#)*horizontal#)
   endIf
endfunction result#
function Range2D(aX,aZ,bX,bZ)
   rngX#=abs(aX-bX)
   rngZ#=abs(aZ-bZ)
   if rngX#>rngZ#
      result#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      result#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf
endfunction result#
function Range(val1,val2)
   result=abs(val1-val2)
endfunction result
function fastRange3D(aX,aY,aZ,bX,bY,bZ)
   rngX=abs(aX-bX)
   vertical=abs(aY-bY)
   rngZ=abs(aZ-bZ)

if rngX>rngZ
      horizontal=rngX+((rngZ/rngX)*rngZ)
   else
      horizontal=rngZ+((rngX/rngZ)*rngX)
   endIf

if horizontal>vertical
      result=horizontal+((vertical/horizontal)*vertical)
   else
      result=vertical+((horizontal/vertical)*horizontal)
   endIf
endfunction result
function fastRange2D(aX,aZ,bX,bZ)
   rngX=abs(aX-bX)
   rngZ=abs(aZ-bZ)
   if rngX>rngZ
      result=rngX+((rngZ/rngX)*rngZ)
   else
      result=rngZ+((rngX/rngZ)*rngX)
   endIf
endfunction result#

+ Code Snippet

function Range3D(aX,aY,aZ,bX,bY,bZ)
   rngX#=abs(aX-bX)
   vertical#=abs(aY-bY)
   rngZ#=abs(aZ-bZ)

   if rngX#>rngZ#
      horizontal#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      horizontal#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf

   if horizontal#>vertical#
      result#=horizontal#+((vertical#/horizontal#)*vertical#)
   else
      result#=vertical#+((horizontal#/vertical#)*horizontal#)
   endIf
endfunction result#
function Range2D(aX,aZ,bX,bZ)
   rngX#=abs(aX-bX)
   rngZ#=abs(aZ-bZ)
   if rngX#>rngZ#
      result#=rngX#+((rngZ#/rngX#)*rngZ#)
   else
      result#=rngZ#+((rngX#/rngZ#)*rngX#)
   endIf
endfunction result#
function Range(val1,val2)
   result=abs(val1-val2)
endfunction result
function fastRange3D(aX,aY,aZ,bX,bY,bZ)
   rngX=abs(aX-bX)
   vertical=abs(aY-bY)
   rngZ=abs(aZ-bZ)

   if rngX>rngZ
      horizontal=rngX+((rngZ/rngX)*rngZ)
   else
      horizontal=rngZ+((rngX/rngZ)*rngX)
   endIf

   if horizontal>vertical
      result=horizontal+((vertical/horizontal)*vertical)
   else
      result=vertical+((horizontal/vertical)*horizontal)
   endIf
endfunction result
function fastRange2D(aX,aZ,bX,bZ)
   rngX=abs(aX-bX)
   rngZ=abs(aZ-bZ)
   if rngX>rngZ
      result=rngX+((rngZ/rngX)*rngZ)
   else
      result=rngZ+((rngX/rngZ)*rngX)
   endIf
endfunction result#

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

malcom2073

23

Years of Service

User Offline

Joined: 12th Mar 2003

Location:

Posted: 4th Apr 2003 20:42

Link

Cant 3d range be done like this:
#dist=sqrt(((aX-bX)^2)+((aY=bY)^2)+(aZ-bZ)^2))

Back to top

Profile PM

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 4th Apr 2003 21:03 Edited at: 4th Apr 2003 21:03

Link

A simple optimisation of the tradition routine runs a lot faster than the fastrange routine:

+ Code Snippet

function OptRange2D(ax,az,bx,bz)
   dx=ax-bx
   dz=az-bz
   result=sqrt( (dx*dx) + (dz+dz) )
endfunction result

When you want 3D distance, use this for the fastest way I've found:

+ Code Snippet

` Prepare a vector for later use - this goes at the top of your program
null=make vector3(1)

function VectorRange3D(x1, y1, z1, x2, y2, z2)
   set vector3 1,x1-x2,y1-y2,z1-z2
   result=length vector3(1)
endfunction result

I think I've seen someone else post this same method - maybe on this forum.

Back to top

Profile PM Email Website

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 21:40 Edited at: 4th Apr 2003 21:46

Link

OK you have me there that vector routine is mighty fine

Fast and accurate.

I still can never fathom the results of square root maths, very innacurate but I see I did get my algorythm slightly wrong at first, your revised version compares more favourably on speed but not accuracy...

These are my results over 10 million cycles:

2D
turboRange2D (combined 1D results)
Result: 499050
Elapsed Time: 14.572s

OptRange2D
Result: 1000
Elapsed Time: 15.033s

range2D (real numbers)
Result: 499000
Elapsed Time: 16.344s

fastRange2D (integer numbers)
Result: 499000
Elapsed Time: 19.868s

3D
vectorRange3D
Result: 1108648
Elapsed Time: 17.386s

turboRange3D (combined 1D results)
Result: 1489050
Elapsed Time: 18.892s

range3D (real numbers)
Result: 1241516
Elapsed Time: 25.701s

fastRange3D (integer numbers)
Result: 990000
Elapsed Time: 29.195s

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 4th Apr 2003 21:44

Link

Oops, my mis-type

- where it says '(dz+dz)' use '(dz*dz)'.

Back to top

Profile PM Email Website

Andy Igoe

23

Years of Service

User Offline

Joined: 6th Oct 2002

Location: United Kingdom

Posted: 4th Apr 2003 21:47

Link

Yeah I just spotted that too, only it returned a 0 after I correct it.... *boggle*. Timewise it was the same, but I cannot for the life of me fathom why real numbers are faster than integers?

FPU maybe? *confused*

Pneumatic Dryll, Outrageous epic cleric of EQ/Xev
God made the world in 7 days, but we're still waiting for the patch.

Back to top

Profile PM Email Website

BoB Vila

23

Years of Service

User Offline

Joined: 27th Feb 2003

Location: United States

Posted: 4th Apr 2003 22:27 Edited at: 4th Apr 2003 22:28

Link

I may be completely off in left field, but I thought that the processor handled floating point calculations in a totally different way. I just remember the whole math co-processor deal and how they would handle all floating point calculations where as the processer could still handle the integer calculations. Resulting in your floating point math always moving faster then the integers. Idunno I might be smoking to much crack or don't know what I'm talking about..

That or DB handles integers the same way it handles real numbers but truncates everything after the decimal, per calculation. I could see that giving you a slight decrease in speed.

Bobvila.com made me take off my avatar! (dunno how they found out)

Back to top

Profile PM Email

IanM

Retired Moderator

23

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 4th Apr 2003 23:04 Edited at: 4th Apr 2003 23:05

Link

Generally FP maths is as at least as fast at the simple level as integer maths. For the more complex stuff (powers etc) it can be a lot faster. But you can waste that so easily just by mixing FP and integers together.

You can see the difference with this code. It shows how all that speed can be wasted just by passing integers into floating point parameters, and vice versa.

sync on

Start=timer()
for i=1 to 5000000 : x#=FPRange2D(0.0,0.0,100.0,100.0) : next i
Finish=timer()

PrintResult("FP routine, FP Args", Finish-Start, x#)

Start=timer()
for i=1 to 5000000 : x#=FPRange2D(0,0,100,100) : next i
Finish=timer()

PrintResult("FP routine, INT Args", Finish-Start, x#)

Start=timer()
for i=1 to 5000000 : x=INTRange2D(0,0,100,100) : next i
Finish=timer()

PrintResult("INT routine, INT Args", Finish-Start, x)

Start=timer()
for i=1 to 5000000 : x=INTRange2D(0.0,0.0,100.0,100.0) : next i
Finish=timer()

PrintResult("INT routine, FP Args", Finish-Start, x)

sync
wait key

function FPRange2D(ax#,az#,bx#,bz#)
   dx#=ax#-bx#
   dz#=az#-bz#
   result#=sqrt( (dx#*dx#) + (dz#*dz#) )
endfunction result#

function INTRange2D(ax,az,bx,bz)
   dx=ax-bx
   dz=az-bz
   result=sqrt( (dx*dx) + (dz*dz) )
endfunction result

function PrintResult(Title as string, Time as integer, Value as float)
   print Title
   print "  Time : "; Time
   print "Result : "; Value
   print
   sync
endfunction

+ Code Snippet

sync on

Start=timer()
for i=1 to 5000000 : x#=FPRange2D(0.0,0.0,100.0,100.0) : next i
Finish=timer()

PrintResult("FP routine, FP Args", Finish-Start, x#)

Start=timer()
for i=1 to 5000000 : x#=FPRange2D(0,0,100,100) : next i
Finish=timer()

PrintResult("FP routine, INT Args", Finish-Start, x#)

Start=timer()
for i=1 to 5000000 : x=INTRange2D(0,0,100,100) : next i
Finish=timer()

PrintResult("INT routine, INT Args", Finish-Start, x)

Start=timer()
for i=1 to 5000000 : x=INTRange2D(0.0,0.0,100.0,100.0) : next i
Finish=timer()

PrintResult("INT routine, FP Args", Finish-Start, x)

sync
wait key

function FPRange2D(ax#,az#,bx#,bz#)
   dx#=ax#-bx#
   dz#=az#-bz#
   result#=sqrt( (dx#*dx#) + (dz#*dz#) )
endfunction result#

function INTRange2D(ax,az,bx,bz)
   dx=ax-bx
   dz=az-bz
   result=sqrt( (dx*dx) + (dz*dz) )
endfunction result

function PrintResult(Title as string, Time as integer, Value as float)
   print Title
   print "  Time : "; Time
   print "Result : "; Value
   print
   sync
endfunction

Back to top

Profile PM Email Website

the architect

23

Years of Service

User Offline

Joined: 6th Jan 2003

Location: United Kingdom

Posted: 5th Apr 2003 00:13

Link

If we are giving away functions heres one I made for a line of sight command in DB.

+ Code Snippet

function bsp_los( sx#, sy#, sz#, ex#, ey#, ez#, rad#)
if object exist(2000)  =  0  then make object plain 2000, .1, .1
position object 2000, sx#, sy# ,sz#
set bsp object collision 2, 2000, rad#, 0
position object 2000, ex#, ey#, ez#
process bsp collision 2
value  =  bsp collision hit(2)
set bsp collision off 2
endfunction value

Of course you made need to apply a different object number and collision index
to avoid conflict with your own specs.

Also dont use it too many time in frames as it may slow performance.

Back to top

Profile PM Email Website

Sorry your browser is not supported!

DarkBASIC Professional Discussion / Testing for Range