June 16, 2009, 06:18  #1 
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 Code:
ceil(sqrt(dy ** 2 + dx ** 2)) 1. adding more floatingpoint 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 
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 nonstandard distance metric. 
June 16, 2009, 09:24  #3  
Prophet
Join Date: Mar 2008
Posts: 2,712

Quote:


June 16, 2009, 17:28  #4  
Angband Devteam member
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516

Quote:
Like Eddie, I have definitely had some points where I suspected the distances were wrong, which is why I looked into this. On a sidenote, there are a few other uses of floats in HEAD. Should be refactored to use integers? 

June 16, 2009, 17:53  #5  
Veteran
Join Date: Apr 2007
Posts: 1,950
Donated: $40

Quote:
__________________
takkaria whispers something about options. more 

June 16, 2009, 17:55  #6  
Angband Devteam member
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516

Quote:
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 integersqrt algorithm. 

June 16, 2009, 17:58  #7 
Veteran
Join Date: Apr 2007
Posts: 1,950
Donated: $40

Yeah, I'm happy to have a better distance() algorithm iff it's integerbased.
__________________
takkaria whispers something about options. more 
June 16, 2009, 18:13  #8 
Angband Devteam member
Join Date: Aug 2008
Location: Philadelphia, PA, USA
Age: 42
Posts: 1,516


June 16, 2009, 21:47  #9  
Prophet
Join Date: Apr 2007
Location: Seattle, WA
Posts: 6,706
Donated: $40

Quote:
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  


Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
FA algorithm for that cool level  konijn_  Variants  5  August 27, 2007 16:33 