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

 June 16, 2009, 06:18 #1 d_m Angband Devteam member     Join Date: Aug 2008 Location: Philadelphia, PA, USA Age: 42 Posts: 1,516 More accurate distance algorithm? The current distance calculation in HEAD uses: Code: `max(dx, dy) + min(dx, dy) / 2` As the comments say, it tends to over-estimate distance by about 1 grid for every 15 grids of actual distance. Is there any good reason not to use a better distance function, for instance: Code: `ceil(sqrt(dy ** 2 + dx ** 2))` I have an implementation together. It only requires some minor tweaks to cave.c to work. I'm going to try to do some profiling and see how much slower it is. The only problems I can imagine are: 1. adding more floating-point math to angband 2. signficantly slower calculation 3. people will hate the drastic increase in ranges Anway, what do you all think?
 June 16, 2009, 06:27 #2 Pete Mack Prophet   Join Date: Apr 2007 Location: Seattle, WA Posts: 6,706 Donated: \$40 Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots. It's not a bad idea, but I mostly don't even notice the non-standard distance metric.
June 16, 2009, 09:24   #3
PowerDiver
Prophet

Join Date: Mar 2008
Posts: 2,712
Quote:
 Originally Posted by Pete Mack Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots. It's not a bad idea, but I mostly don't even notice the non-standard distance metric.
Every so often I try to plan a destruction radius, and I when the radius isn't what I thought it would be I wonder about my ability to do arithmetic. It's nice to see my problem is that the effect is not really a radius.

June 16, 2009, 17:28   #4
d_m
Angband Devteam member

Join Date: Aug 2008
Age: 42
Posts: 1,516
Quote:
 Originally Posted by Pete Mack Angband runs on mobile devices, which mostly don't have FP. However, there's an easy workaround: What you are interested in is dx^2 + dy^2 <= 20^2. No need for floating point, or square roots.
So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written.

Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this.

On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?

June 16, 2009, 17:53   #5
takkaria
Veteran

Join Date: Apr 2007
Posts: 1,950
Donated: \$40
Quote:
 Originally Posted by d_m So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written. Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this. On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?
Where? I can only see it being used in frontends and in wiz-stats.c, where it's fine.
__________________
takkaria whispers something about options. -more-

June 16, 2009, 17:55   #6
d_m
Angband Devteam member

Join Date: Aug 2008
Age: 42
Posts: 1,516
Quote:
 Originally Posted by takkaria Where? I can only see it being used in frontends and in wiz-stats.c, where it's fine.
Ooops! I guess I was just looking at wiz-stats.c.

As long as you're here, how would you feel about an improved distance algorithm? Especially if distances over 20 aren't important, it should be easy to implement a fast integer-sqrt algorithm.

June 16, 2009, 17:58   #7
takkaria
Veteran

Join Date: Apr 2007
Posts: 1,950
Donated: \$40
Quote:
 Originally Posted by d_m Ooops! I guess I was just looking at wiz-stats.c. As long as you're here, how would you feel about an improved distance algorithm? Especially if distances over 20 aren't important, it should be easy to implement a fast integer-sqrt algorithm.
Yeah, I'm happy to have a better distance() algorithm iff it's integer-based.
__________________
takkaria whispers something about options. -more-

June 16, 2009, 18:13   #8
d_m
Angband Devteam member

Join Date: Aug 2008
Age: 42
Posts: 1,516
Quote:
 Originally Posted by takkaria Yeah, I'm happy to have a better distance() algorithm iff it's integer-based.
Great. I just tested an integer-based sqrt algorithm between 0 and 10,000; I will be sending a patch to dev shortly. Thanks.

June 16, 2009, 21:47   #9
Pete Mack
Prophet

Join Date: Apr 2007
Location: Seattle, WA
Posts: 6,706
Donated: \$40
Quote:
 Originally Posted by d_m So the distance() function doesn't need to distinguish between distances greater than 20? If so then like you say it'll be easy to get something integer-based written. Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this. On a side-note, there are a few other uses of floats in HEAD. Should be refactored to use integers?
That's not what I meant, sorry

dx^2 + dy^2 <= r^2

gives the same results as

sqrt(dx^2 + dy^2) <= r

but it doesn't require taking a root. (There's already code like this for stealth computation.)

 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