Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old February 15, 2010, 06:43   #1
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
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?
PowerDiver is offline   Reply With Quote
Old February 15, 2010, 14:31   #2
RogerN
Swordsman
 
RogerN's Avatar
 
Join Date: Jul 2008
Posts: 308
RogerN is on a distinguished road
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);
}
RogerN is offline   Reply With Quote
Old February 15, 2010, 15:03   #3
ekolis
Knight
 
ekolis's Avatar
 
Join Date: Apr 2007
Location: Cincinnati, OH, USA
Age: 36
Posts: 911
ekolis is on a distinguished road
Send a message via AIM to ekolis Send a message via MSN to ekolis Send a message via Yahoo to ekolis
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!
ekolis is offline   Reply With Quote
Old February 15, 2010, 15:42   #4
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 5,383
Donated: $40
Pete Mack is on a distinguished road
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
Pete Mack is offline   Reply With Quote
Old February 15, 2010, 19:40   #5
Magnate
Angband Devteam member
 
Join Date: May 2007
Location: London, UK
Posts: 5,057
Magnate is on a distinguished road
Send a message via MSN to Magnate Send a message via Yahoo to Magnate
Quote:
Originally Posted by PowerDiver View Post
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.
Magnate is offline   Reply With Quote
Old February 15, 2010, 19:40   #6
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
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.
PowerDiver is offline   Reply With Quote
Old February 16, 2010, 15:22   #7
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 39
Posts: 1,516
d_m is on a distinguished road
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
d_m is offline   Reply With Quote
Old February 18, 2010, 21:30   #8
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
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.
PowerDiver is offline   Reply With Quote
Reply


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

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 Jump

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


All times are GMT +1. The time now is 21:32.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, vBulletin Solutions Inc.