distance formulas
BlitzMax Forums/BlitzMax Programming/distance formulas
| ||
| ok i have been trying for awhile now to get the distance between 2 points and have gotten no luck. i remember reading in a trig book the formula for this but i no longer have the book this is for AI and range testing for weapons, so can anyone help |
| ||
| (DeltaX^2+DeltaY^2)^.5 |
| ||
| how is that going to help me calculate distance between 2 points? |
| ||
| That's the formula from the book you no longer have. |
| ||
You won't get faster than this when approximating :distance# = (dx# * 0.41) + (dy# * 0.941246) http://en.wikipedia.org/wiki/Euclidean_distance#2D_approximations_for_computer_applications |
| ||
| Indie - that's interesting. First time I've seen a decent speed up approximation that works faster (than Sqr) for modern hardware. Is there a 3d version? Problem with it is that it doesn't work for negative values, so you sometimes have to use this version: distance# = (Abs(dx#) * 0.41) + (Abs(dy#) * 0.941246) ..which is not as fast. |
| ||
Link1426 - try this:Function Distance2D#(x0#,y0#,x1#,y1#) Local dx# = x0-x1 Local dy# = y0-y1 Return Sqr(dx*dx + dy*dy) End Function |
| ||
| Beaker, approximated distance is . (If dy < dx, swap these values.) from the wiki entry.It's followed by... Three-dimensional distance |
| ||
| Try using Phitagoras(did I spell ok?) formula. If you don't know that one then there is no point continuing on(its learned on school in the 4th or 5th grade) |
| ||
| tonyg - I see. Shame, as soon as you do that there is no longer a speed increase (as usual). Oh well. The 3D distance thing isn't an approximation, and I use it already. |
| ||
| beaker, your function works very well i just made a program to test it in 7-10 minutes and everything worked fine |
| ||
| http://en.wikipedia.org/wiki/Pythagorean_theorem the code from Beaker is correct, you can found the function in code archive with the z parameter. |
| ||
Question: After speed meassuring i find blitz sqr is just as fast or slow as the euclidean formula. am i doing something wrong here?SuperStrict Graphics 640,480,0,200 Local dist1:Float, dist2:Float Local test:Int=0 Local time:Int Repeat time=MilliSecs() For Local l:Int=0 To 200000 If test=0 Then dist1=approxdist(GraphicsWidth()/2,GraphicsHeight()/2,MouseX(),MouseY()) Else dist1=realdist(GraphicsWidth()/2,GraphicsHeight()/2,MouseX(),MouseY()) End If Next DrawText MilliSecs()-time,0,0 DrawText "test:"+test,0,20 DrawText dist1,0,40 If KeyHit(key_1) Then test=0 If KeyHit(key_2) Then test=1 Flip False Cls Until KeyDown(key_escape) Function RealDist:Float(x1:Float, y1:Float, x2:Float,y2:Float) Local dx:Float=x1-x2 Local dy:Float=y1-y2 Return Sqr( dx*dx + dy*dy) End Function Function ApproxDist:Float(x1:Float, y1:Float, x2:Float,y2:Float) Local dx:Float=Abs(x1-x2) Local dy:Float=Abs(y1-y2) If dy>dx Then Return (dx*0.41 + dy*0.941246) Else Return (dy*0.41 + dx*0.941246) End If End Function |
| ||
| Try putting a Delay(2000) after the GFX command and then see what happens. |
| ||
| i tried and it showed no difference for me. |
| ||
| You people are crazy just give the poor guy the simple STANDARD formula! :-) Distance# = Sqr((X2#-X1#)^2 + (Y2#-Y1#)^2) Or for a 3D point: Distance# = Sqr((X2#-X1#)^2 + (Y2#-Y1#)^2 + (Z2#-Z1#)^2) |
| ||
| other than the fact you have written the methods on single lines..its no different from beakers.. 2D & 3D pythagoras..is that spelling correct? :/ :p anyway..its also been pointed out in other posts, that using n*n is quicker than n^2... something id overlooked in the past with b3d & bmax... making the dumb assumption that this would be replaced by the compiler.. |
| ||
| Yes, it is faster. But in 99% of cases it doesn't matter because it takes so little time there's no reason to optimize it. And Beaker's writing it out the long was is silly. :-) Twice as much code and it probably is slower to execute to boot. Not that that matters though, as I pointed out, but in this case you're just doing extra code for nothing. :-) |
| ||
Try this:'iParXD = (iParX1 - iParX2) 'iParYD = (iParY1 - iParY2) Function ApproxDistance:Int(iParXD:Int, iParYD:Int) Local iMin:Int Local iMax:Int If iParXD < 0 Then iParXD = -iParXD If iParYD < 0 Then iParYD = -iParYD If iParXD < iParYD Then iMin = iParXD iMax = iParYD Else iMin = iParYD iMax = iParXD EndIf Return (((iMax Shl 8) + (iMax Shl 3) - (iMax Shl 4) - (iMax Shl 1) + (iMin Shl 7) - (iMin Shl 5) + (iMin Shl 3) - (iMin Shl 1)) Shr 8) End Function Function Distance:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0) Return Sqr((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2)) End Function Function DistanceQuad:Float(fParX1:Float, fParY1:Float, fParX2:Float = 0, fParY2:Float = 0) Return ((fParX1 - fParX2) * (fParX1 - fParX2) + (fParY1 - fParY2) * (fParY1 - fParY2)) End Function Function IntDistance:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0) Return Sqr((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2)) End Function Function IntDistanceQuad:Int(iParX1:Int, iParY1:Int, iParX2:Int = 0, iParY2:Int = 0) Return ((iParX1 - iParX2) * (iParX1 - iParX2) + (iParY1 - iParY2) * (iParY1 - iParY2)) End Function The Int-Functions are a little faster than the Float-Ones, also the Quad-Ones are really fast compared to the Non-Quad-ones. But, keep in Mind: If you use the Int-Version, it'll give you an overflow if the quad of the distance is higher than Int can handle. The fastest Distance-Approximation I've seen so far is the ApproxDistance-Function above. Really really fast. |
| ||
| sswift - gimme a break. I was just making it simple for someone who needed a little more help than a formula. Not only is it fast enough, but its also easy to interpret and read. He already said it worked, so anything posted after that point is purely academic, and possibly even more confusing. I use that function in my own code when the speed isn't critical, cos it reads better (and is easier to type). |
| ||
| Fetze - in my tests your ApproxDistance function is still slower than Sqr(). I tested it in Blitz3D. [EDIT: of course I realise that it may be faster on very old hardware, and definitely on simpler devices (PDAs etc).] |
| ||
| Beaker: Okay I'm giving you a break. THIS time! Don't let it happen again! :-) |
| ||
| SHL / SHR approx is a little pointless in BlitzMax at least it seem so. I've tried most you can find on the net and the result is that GCC is just too over optimized to have any use for this "old old school tricks" or internally already applies them all and even more :-) This after all is a good thing, unless you are one of those approx gurus that wanted to use all its own formulas ^^ |
| ||
| hm.. thats strange... didn't test it again but when I tested it last time... it was much faster than any other Distance-Formula oO is it relly SLOWER than the other formulas? |
| ||
| how is that going to help me calculate distance between 2 points? You say you have forgotten the formular, but you seem to have foggoten even what the formular looks like. Oh Well. As a peice of advice, looksee on the net for the simplest Trig functions explinations you can find, it obviosly will not teach you Trig, but often just looking at the equations a few times, and then programming each one in helps you to remember them. And Beaker's writing it out the long was is silly What? Mine was more concise than yours. But having said that Link didnt understand mine, so yours was probably better. But again Beakers was probably more applicable distance# = (dx# * 0.41) + (dy# * 0.941246) This Must by quicker than Distance# = Sqr((Dx#*Dx#) + (Dy#*Dy#)) anyone who says it isnt quicker either ment to say, its not sufficantly quicker to be worth it, or was simply Wrong.X^2 is slower than X*X. But X^2 reads better. (Well to me anyway) However I would probably change it to X*X in intensive calculations. |
| ||
| In Debug yes, then Beakers is faster. In release yours is faster. ' 10000000 calls each Time Fetze: 267 Time Beaker: 1190 But the main reason here is that yours is Int only. If you use the Distance Approx that base on Float with their bitshift approximations, they will be slower than simply using SQR. |
| ||
| dream AFloat * AFloat + Afloat * Afloat take a certain amount of time Yes? And then after that you need to sqr in one method, yet the other methed HAS FINISHED. distance# = (dx# * 0.41) + (dy# * 0.941246) Is quicker than Distance# = Sqr((Dx#*Dx#) + (Dy#*Dy#)) By whatever speed sqr is. Edit: Dream Excuse this post. At first, (before your edit), I thought your post above was @ me. Please ignore this one. |
| ||
| EDITED: didn't see your edit H&K when I posted. PS: yes it is faster. But an approx should be within a given percentage range of the true result, not just plain wrong if no specific case is present. Otherwise you could simply do: distance = 1 ^^ |
| ||
| 1) there not mine, I was just picking them from the Thread. 2) I think you mean as it appraches 0, not = 0 3) Did you miss my apology? |
| ||
| woot!!! another nerd fest over something as trivial as 2D distance calculation i am optimizing as much in my code, like using bytes or shorts where ints are not need and such that i can afford the Sqr slowdown(even if for 200+ enemies at once, which is unlikely that even 40 enemies will be active at any given moment) i think i will make an AI module now, just something to do and you guys will get credit for this help. i may just release it as source for free |
| ||
| something as trivial as 2D distance calculation If its so trivial, I bet you feel really stupid for not being able to do it. Oh and Bytes are often 1) the same size as an Int (in real memory tearms, less you have four of them in one type), 2) Slower than an int. Also any good AI you would want the enemies to know how far they are from each other. So for 40 enimes (and you) thats 800 or so calculations |
| ||
| yes i did, i haven't used it in so long that i completely forgot it. that and i have been out of school for awhile and i tend to forget a lot of stuff from school after a month of summer |
| ||
| Oh snap! Read a book! Ohhh! I went there! |
| ||
| H&K: Not needfully. An intelligent AI would keep track of "surounding" which normally ends with vornoi and similar approaches to only know of the next neightbours and building some graph and similar basing on that. There is no reason to know of everything, at least if it is an animate (autonom operating) based AI. |
| ||
| right now i am making a grid system for collision detection and AI i will test the AI part by making a maze map with distenation point and seeing how well the NPC navigates it |
| ||
| H&K: "What? Mine was more concise than yours." Yes, but your equation was incomplete; you only wrote out the right half. It might be obvious to you what to do with it, but for all you know you're talking to a kid with zero math skills who'll have no idea what to do with those numbers. (I know, cause that kid used to be me!) Also, you put ^0.5 in your equation, which I know is a square root, but again, if you're talking to someone with a grade 10 understanding of algebra, they might not realise that is the same thing as a square root. Plus, you expect him to recognize the formula as being the same one in the book, but neither ^0.5 or Sqr() would be how it would be written in a book. They'd use the square root symbol. And finally, you're expecting someone who doesn't know the distance formula to know that "DeltaX" means X2-X1. That's just crazy talk right there. :-) _I_ wouldn't even have known what you meant if I didn't already know how the distance formula was supposed to be written. That might be common knowledge to people who know Calculus, but I'm not one of those people. :-) |
| ||
| As for this: distance# = (dx# * 0.41) + (dy# * 0.941246) How can that possibly work with any degree of accuracy at all? You're setting the distance to be like, mostly the Y difference, and a bit of the X difference. Shouldn't those two numbers the differences are being multiplied be the same? I guess I'll have to test it to be sure, but it seems like it couldn't possibly work... well! edit: Ah, I see the link tot he wikipedia article and reading that the above equation is incomplete. You have to do ABS on the differences, and you have to swap the values each difference is multiplied by if one is greater than the other. |
| ||
| Hey Link, do you really need the distance between the two points, or do you just need to know if point A is farther from point B than some distance, or farther than point C is from point B? Becuase in that case you don't even have to use square root. |
| ||
| i do need the distance values for my AI functions but i may also need to see which is farther at the same time. |
| ||
| Well in the cases where you only need to see which is farther, you can calculate distance like so: D = X2-X1^2 + Y2-Y1^2 And compare those "squared distance" values. |
| ||
| As long as the objects can't be too far away. Otherwise it will end with value wrapping. (or you have to define D as long) |
| ||
| the objects won't be too far from each other, the enemy is set in an inactive mode when too far off screen |
| ||
| @sswift, ha you missed the point. I wasnt saying mine was the better one, I was saying Beakers one was. For all the reasons that make yours better than mine ;) I was telling you off for your critism of beakers. |
   |