Subject: Re: Sounds and hearing in roguelikes
From:    bear@sonic.net
Date:    Wed, 30 Jul 2003 22:43:32 GMT
Groups:  rec.games.roguelike.development

Joonas Hirvonen wrote:

> 
> Any suggestions on how to implement sounds and hearing?
> 
> If you for example fight, cast a spell or bash a door, beings nearby might
> hear and take a loot at the happening.
> 
> I was thinking of using simple ray tracing and then reducing the sound
> volume if there's obstacles in the way but I'm feeling there's better ways
> for this.
> 
> Btw. what's the fastest way to calculate the distance between two points
> (x1,y1 -> x2,y2)?


Well -- assuming you mean the true euclidean distance, which is ordinarily
written as 

    sqrt(sqr(x1 - x2) + sqr(y1 - y2)),

the problem is the sqrt operation.  It takes twelve to fifteen times 
as long as the rest of the calculation put together.  If you need the 
true euclidean distance, the *fastest* way to calculate it is by 
tabular lookup.  In C you would write 

    distances[abs(x1 - x2)][abs(y1 - y2)]

That gets it down to four additions and two conditional negations 
(which are typically one clock cycle each) plus a pointer indirection
for the array lookup.  You'd need to initialize the array when you 
started up the game. 
-----

If you don't need the true distance, however, there are other 
ways of calculating a distance that won't occupy so much memory 
or incur the pointer lookup.  

In games with orthogonal movement, for example, you could use 
the Manhattan distance: 

   abs(x1 - x2) + abs(y1 - y2)

This incurs three additions, two conditional negations, and no 
pointer indirection, which makes it faster than tabular lookup.
It has the property that distances along any line-of-sight will 
be accurate within a factor of 2/sqrt(2), and distances along 
the same line of sight will compare accurately.  It never 
underestimates the distance. 

-----
If you want to accurately *compare* distances regardless of 
direction, you may want to use the squared euclidean distance: 

   sqr(x1 - x2) + sqr(y1 - y2)

This is three additions and two multiplications, and it gets a 
distance you can compare accurately to other squared euclidean 
distances in any direction.  This is surprisingly robust as 
long as you're not adding or subtracting distances; if you're 
strictly comparing distances (less than line-of-sight?  greater
than spell range?  closer than another monster? etc) it's good. 

-----
Then there's the Chebyshev distance, which is 

   max (abs(x1 - x2), abs(y1 - y2))

This incurs two additions, two conditional negations, and a 
comparison, which makes it about as fast as the manhattan 
distance.  Where the manhattan distance is accurate within 
2/sqrt(2), the Chebyshev distance is accurate within 
sqrt(2)/2.  Typically you want to use the manhattan distance 
when it's important not to underestimate and the Chebyshev 
distance when it's important not to overestimate. 

-----
And finally there's this little thing... 

	xdiff = abs(x1 - x2);
	ydiff = abs(y1 - y2);
	distance = (xdiff + ydiff + max(xdiff, ydiff)) >> 1;

which gets you four additions, two conditional negations, 
a comparison and a bitshift.  That makes it slower 
than either Chebyshev or Manhattan, but the good news is that 
it's still faster than table lookup, way faster than euclidean
distance, it's accurate in eight directions corresponding to 
the compass points and quarters which are typically the 
usable directions in roguelike movement, and the maximum 
error factor is less than half of either. 

				Bear