Angband Forums accurate distance
 Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 February 15, 2010, 06:43 #1 PowerDiver Prophet   Join Date: Mar 2008 Posts: 2,712 accurate distance I distinctly remember someone implementing a correct distance function, and thought it made it into the V dev code. I seem to remember being pleased that radius 15 destruction actually destroyed those points within a distance of 15. However, distance() in 3.1.2 is the same hack it used to be. I checked some revs on my machine I haven't deleted, and no diff there either. Did anyone ever release something with a correct distance function? Is there some reason not to use it?
 February 15, 2010, 14:31 #2 RogerN Swordsman     Join Date: Jul 2008 Posts: 308 I don't know the answer to your exact question, but fast integer distance functions are pretty standard fare in all sorts of games: Code: static int isqrt(int num) { if (num == 0) return 0; int n = (num / 2) + 1; int n1 = (n + (num / n)) / 2; while (n1 < n) { n = n1; n1 = (n + (num / n)) / 2; } return n; } static int distance(int x1, int y1, int x2, int y2) { int dx = x2 - x1; int dy = y2 - y1; return isqrt(dx*dx + dy*dy); }
 February 15, 2010, 15:03 #3 ekolis Knight     Join Date: Apr 2007 Location: Cincinnati, OH, USA Age: 39 Posts: 918 But unless there's some magic I'm not aware of going on in the background, it takes 1 move to move straight and 1 move to move diagonally... not 1 to move straight and sqrt(2) to move diagonally, or 2 to move straight and 3 to move diagonally... so why should distance calculations be any different from movement when it comes to detection, archery, spellcasting, and even lighting? __________________ You read the scroll labeled NOBIMUS UPSCOTI... You are surrounded by a stasis field! The tengu tries to teleport, but fails!
 February 15, 2010, 15:42 #4 Pete Mack Prophet   Join Date: Apr 2007 Location: Seattle, WA Posts: 6,706 Donated: \$40 btw, you don't actually have to compute the square root to do distance calculations. x^2 + y^2 <= r^2 is a lot easier than sqrt(x^2 + y^2) <= r
February 15, 2010, 19:40   #5
Magnate
Angband Devteam member

Join Date: May 2007
Location: London, UK
Posts: 5,060
Quote:
 Originally Posted by PowerDiver I distinctly remember someone implementing a correct distance function, and thought it made it into the V dev code. I seem to remember being pleased that radius 15 destruction actually destroyed those points within a distance of 15. However, distance() in 3.1.2 is the same hack it used to be. I checked some revs on my machine I haven't deleted, and no diff there either. Did anyone ever release something with a correct distance function? Is there some reason not to use it?
Have you checked the angband-dev ML archive? ISTR this being offered around the time I started contributing as a dev, so about a year ago, give or take a month or two. I definitely remember it too, it was quite elegant.

 February 15, 2010, 19:40 #6 PowerDiver Prophet   Join Date: Mar 2008 Posts: 2,712 Suppose dx > dy. The distance function in V is currently dx + (dy/2) . I agree with Pete that one should just use distance_squared when possible, which is presumably all of the time. The only time I imagine non-squared distance is needed in *bands is for ball damage effects, but they don't properly work off of distance anyway, and their answer is a small lookup table or perhaps the travesty above. These are computable in constant time, so speed is not relevant.
 February 16, 2010, 15:22 #7 d_m Angband Devteam member     Join Date: Aug 2008 Location: Philadelphia, PA, USA Age: 42 Posts: 1,516 I wrote the patch to do this (modulo community suggestions), but it was before I had commit access and it never made it into V. I will dig it up and see if it still works--it kind of dropped off my radar but I do think it would be nice. __________________ linux->xterm->screen->pmacs
 February 18, 2010, 21:30 #8 PowerDiver Prophet   Join Date: Mar 2008 Posts: 2,712 I think you need to change your distance function to round. Consider radius 1 and radius 2 balls. I think the current implementation is right, although familiarity does cause bias. For a radius 1 ball, distance \sqrt{2} is inside the ball. Also, distance \sqrt{5} is inside a radius 2 ball, but distance \sqrt{8} is not. In these cases rounding works. Of course, I don't think the distance function should be called for inclusion in a ball. Instead there should be a macro inside_ball(dx, dy, r). The only times I know of that distance is important besides ball inclusion is for reduction in ball damage or minuses on ranged attacks. Nevertheless it might be good to be consistent.

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Angband     AAR     Vanilla     Development     ToME     Sil     Variants     Competition The real world     Idle chatter     Oook! Obsolete     v4