Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Vanilla

Reply
 
Thread Tools Display Modes
Old June 16, 2009, 06:18   #1
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516
d_m is on a distinguished road
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?
d_m is offline   Reply With Quote
Old June 16, 2009, 06:27   #2
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 6,706
Donated: $40
Pete Mack is on a distinguished road
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.
Pete Mack is offline   Reply With Quote
Old June 16, 2009, 09:24   #3
PowerDiver
Prophet
 
Join Date: Mar 2008
Posts: 2,712
PowerDiver is on a distinguished road
Quote:
Originally Posted by Pete Mack View Post
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.
PowerDiver is offline   Reply With Quote
Old June 16, 2009, 17:28   #4
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516
d_m is on a distinguished road
Quote:
Originally Posted by Pete Mack View Post
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?
d_m is offline   Reply With Quote
Old June 16, 2009, 17:53   #5
takkaria
Veteran
 
takkaria's Avatar
 
Join Date: Apr 2007
Posts: 1,950
Donated: $40
takkaria is on a distinguished road
Quote:
Originally Posted by d_m View Post
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-
takkaria is offline   Reply With Quote
Old June 16, 2009, 17:55   #6
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516
d_m is on a distinguished road
Quote:
Originally Posted by takkaria View Post
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.
d_m is offline   Reply With Quote
Old June 16, 2009, 17:58   #7
takkaria
Veteran
 
takkaria's Avatar
 
Join Date: Apr 2007
Posts: 1,950
Donated: $40
takkaria is on a distinguished road
Quote:
Originally Posted by d_m View Post
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-
takkaria is offline   Reply With Quote
Old June 16, 2009, 18:13   #8
d_m
Angband Devteam member
 
d_m's Avatar
 
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516
d_m is on a distinguished road
Quote:
Originally Posted by takkaria View Post
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.
d_m is offline   Reply With Quote
Old June 16, 2009, 21:47   #9
Pete Mack
Prophet
 
Join Date: Apr 2007
Location: Seattle, WA
Posts: 6,706
Donated: $40
Pete Mack is on a distinguished road
Quote:
Originally Posted by d_m View Post
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.)
Pete Mack 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
FA algorithm for that cool level konijn_ Variants 5 August 27, 2007 16:33


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


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