February 15, 2010, 06:43  #1 
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 
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 
Knight

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 
Prophet
Join Date: Apr 2007
Location: Seattle, WA
Posts: 5,383
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  
Angband Devteam member

Quote:


February 15, 2010, 19:40  #6 
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 nonsquared 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 
Angband Devteam member
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 39
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 worksit kind of dropped off my radar but I do think it would be nice. 
February 18, 2010, 21:30  #8 
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  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
More accurate distance algorithm?  d_m  Vanilla  8  June 16, 2009 21:47 