Distance

Blitz3D Forums/Blitz3D Programming/Distance

ringwraith

(Posted 2008) [#1]

Is there any quicker way to do 2D distance besides the standard formula: d = Sqr((x1 - x2)^2 + (y1 - y2)^2)? It seems like this is a bit slow especially when it is being calculated over and over again.

Dreamora

(Posted 2008) [#2]

Do not sqr it.
In 2D the distances are small so they don't exceed the float maximum when squared, so you can compare d^2 to it.

the other optimation is NOT to use ^2
Its slower than x*x, the ^x does not make sense with x < 3 performance wise.

->
xdif = x1 - x2
ydif = y1 - y2
d2 = ( xdif*xdif + ydif*ydif)

if d2 < maxDistance * maxDistance then ...

Jasu	(Posted 2008) [#3]

In these days, calculating is so much faster than writing stuff in memory. I prefer this:
dist# = Sqr((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1))
So I avoid using temporary variables.
Actually the fastest option is not to code in Blitz. It's just dead slow.

ringwraith

(Posted 2008) [#4]

Yeah, I've been hearing a lot about Blitz's speed limitations ever since I got it. Is BlitzMAX any faster or are there any other Basic languages that are faster? Or would I have to learn something like C++ for better speed?

I tried taking out the sqr operation but it didn't really seem to speed up at all. I'll try all of your suggestions together and see if it helps any.

Thanks.

Sledge

(Posted 2008) [#5]

Download Dev-C++, have it do the same maths and see for yourself how much faster it is (remember to use the results of calculations or the compiler will optimise those calculations out and you won't get a speed test at all). If you can get it to run significantly faster than B3D then let me know how because I couldn't.

In the meantime I would just use a less complex formula, like the chessboard* distance...

CityblockDist=Abs(x1-x2) + Abs(y1-y2)

...which should be accurate enough (well, might be accurate enough, depending on what you're doing!) but prove significantly faster than your original algorithm.

*At least I think that's what it's called. There's the 'City Block' distance too -- there used to be a neat page that outlined a bunch of different ways to get distance with varying degrees of speed and accuracy but it's gone now. EDIT: Oh I found a similar page -- that's cityblock distance that I posted there.

EDIT:Ah, turns out Chessboard is Max(Abs(x1-x2),Abs(y1-y2)). You'd have to write your own Max() function in B3D for that -- it just returns the higher of the two arguments supplied.

Sledge

(Posted 2008) [#6]

I tried taking out the sqr operation but it didn't really seem to speed up at all.

You're not in debug mode are you? It's the inline powering that should get you the lion's share of the speed increase -- Jasu's suggestion is the one I'd go for.

Is BlitzMAX any faster or are there any other Basic languages that are faster?

That's an interesting question so I did the following test...

B3D Version:

SeedRnd(MilliSecs())
Const SECS_TO_DELAY% = 10
Const CALCS_TO_PERFORM% = 100000000

Graphics 800,600,0,2
SetBuffer BackBuffer()

StartTime% = 0
EndTime% = 0
Calculations% = 0
Distance% = 0

x1% = Rand(0,10000) 
x2% = Rand(0,10000)
y1% = Rand(0,10000)
y2% = Rand(0,10000)

Text 10,10,"Waiting..."
Flip
Cls
Delay SECS_TO_DELAY*1000

Text 10,10,"Testing..."
Flip
StartTime = MilliSecs()
While Not (Calculations = CALCS_TO_PERFORM)
	Distance = Sqr((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))
	Calculations=Calculations+1
Wend
EndTime=MilliSecs()

Cls
Text 10,10,"Time taken: "+ (EndTime -  StartTime)
Flip
WaitKey

Max Version:

SuperStrict
SeedRnd(MilliSecs())
Const SECS_TO_DELAY:Int = 10
Const CALCS_TO_PERFORM:Int = 100000000

Graphics 800,600,0

Local StartTime:Int 
Local EndTime:Int
Local Calculations:Int
Local Distance:Int

Local x1:Int = Rand(0,10000) 
Local x2:Int = Rand(0,10000)
Local y1:Int = Rand(0,10000)
Local y2:Int = Rand(0,10000)

DrawText "Waiting...",10,10
Flip
Cls
Delay SECS_TO_DELAY*1000

DrawText "Testing...",10,10
Flip
StartTime = MilliSecs()
While Not (Calculations = CALCS_TO_PERFORM)
	Distance = Sqr((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2))
	Calculations:+1
Wend
EndTime=MilliSecs()

Cls
DrawText "Time taken: "+ (EndTime -  StartTime),10,10
Flip
WaitKey

So that's one hundred million distance calculations with the number of milliseconds it took to perform them recorded each time. Here are the results I get:

B3D
===
5114
5210
5245
5211
5062

Max
===
15924
15123
15053
15056
15100

So unless I've made a schoolboy error Max is, as you might expect of an OOP language, actually slower than its procedural counterpart. Interestingly, if I add a minimal framework to the Max code (Framework BRL.GLMax2D, Import BRL.Random) I start getting results in the region of 13000 millisecs rather than 15000.

Dreamora

(Posted 2008) [#7]

your computer must be seriously bad if it performs better with B3D than with BM as BM uses optimations not available to B3D at all (especially in MingW 5.1.X in BM 1.26+)
Or you just forgot to disable debug build :)

still: not using sqr and staying on squared distance is a several magnitudes faster.

Matty

(Posted 2008) [#8]

Unless you are doing hundreds of square roots per frame it is not going to matter.

Sledge

(Posted 2008) [#9]

your computer must be seriously bad if it performs better with B3D than with BM as BM uses optimations not available to B3D at all (especially in MingW 5.1.X in BM 1.26+)

It's a year-ish old Dell so that's exactly what the market is like right now.

still: not using sqr and staying on squared distance is a several magnitudes faster.

Can you explain that in a little more detail? I didn't really follow that bit of your first post to be honest. It's very early/late. EDIT: AH! IT JUST CLICKED!

Unless you are doing hundreds of square roots per frame it is not going to matter.

That's very true, but I assume he (ringwraith) is and it does.

Dreamora

(Posted 2008) [#10]

Sledge: In that case I would bet that you forgot to disable debug in your performance tests ...
The sqr of BM is that fast that it is even with enabled sqr still faster than B3d in squared distance comparision normally ... (its actually that fast that all approx implementations with bit shift etc I found on the net are slower than bm / MingW 5.1.X sqr ...)

Sledge

(Posted 2008) [#11]

Nope, I'm not in debug mode (I made sure to check because I suggested the same thing to ringwraith!) -- it's just that slow. MinGW 5.1.3 too.

Dreamora

(Posted 2008) [#12]

Replace the Local Distance:Int with Local Distance:Float

Should raise the performance easily be 1.5 - 4 times.
Your assignement there is massively killing BM (B3D most likely switches to a different function internally)

For me it did 1.5 ... its hard to get far further down at 4200 ms ^^

Sledge

(Posted 2008) [#13]

Ah -- good point. I was in automatic 'ints are faster' mode there. Got it down to about 7500 millisecs now... still trailing B3D though! (EDIT: Altering B3D to a float makes it faster still -- around 3700 millisecs!)

Ross C

(Posted 2008) [#14]

Interesting info there :o)

Sledge

(Posted 2008) [#15]

I'd watched everything of interest iPlayer had to offer.

jfk EO-11110

(Posted 2008) [#16]

quote:
CityblockDist=Abs(x1-x2) + Abs(y1-y2)

isn't this called "manhatten distance"?

Anyway, what, blitz3D faster? this is incredible.

H. T. U.

(Posted 2008) [#17]

If you want a completely acurate system, Jasu's method is the fastest possible to my knowledge in B3d. It is my prefered method also.

If it doesn't need to be perfect, then skip the square root, it does slow things down.

However, if you REALY want to get your hands dirty, using the computers logic functions(and,nand,or,nor,and ex-or) might be faster, but it gets complicated very fast when you go beyond addition.

ringwraith

(Posted 2008) [#18]

Hey,

Thanks for all the ideas everyone. My problem was that I was in debug mode. With debug enabled taking out the sqr and using Jasu's method seems to be the most efficient. I also used the city block (manhattan) method to narrow down the amount of distance calculations that have to be made which also helps a lot.