ID:195153
 
//Title: Linear Distance Procs
//Credit to: Jtgibson
//Contributed by: Jtgibson


/*
This is a set of distance functions which you can use in BYOND. Each distance
function is quite rapid, save for Euclidean distance.


Euclidean Distance:
Euclidean distance is a formula calculated using the Pythagorean formula for
finding the length of the hypoteneuse given an offset "A" and "B". All
distances can be computed exactly in this fashion, to whatever level of
precision is desired. It is called "Euclidean" distance because it is based
on the infinite plane, which is the foundation of Euclidean geometry
(something that the mathematician Euclid is famous for).

However, the sqrt() function which is used by the Euclidean distance formula
is INCREDIBLY slow. This isn't so bad when working with small computations,
because modern computers are extremely powerful, but you can expect it to lag
considerably if you're calculating the distance thousands of times simul-
taneously (e.g., if you're calculating the distance to every tile within a
huge explosion radius).


Squared Euclidean Distance
When you want to precisely compare distances to determine whether a certain
tile is farther than another tile, you can simply use the squared Euclidean
distance. This eliminates the "sqrt()" function from the computation, vastly
improving the speed, but has the obvious side effect that the number produced
is actually the square of the distance and not an accurate measurement of
distance (as distance increases, the margin of error is exponential).

For example, you could use this function once between one object and another
to produce one value, and then compare the result to the result of using this
function between the first object and a different object. The comparison will
accurately yield whether one is closer, further, or of equal distance if you
compare the results.

This is not very useful for circumstances where you want to yield distance
between two points, but it's faster than Euclidean distance and produces
results which are guaranteed to be true (i.e., if one of the distances is
larger, then that target is guaranteed to be further away).

You cannot add or subtract values to/from the squared Euclidean distance
(unless you square those values first). Squared Euclidean distance cannot be
used to accurately calculate the ACTUAL distance between two points, either,
though you can use sqrt() on the result to yield the Euclidean distance... but
in that case, what's the point of using this function instead of the
euclid_dist() function?


Manhattan Distance
Manhattan distance is a system based on only allowing the four orthogonal
movement directions. It is only accurate within a factor of 2/sqrt(2),
meaning that you can't actually use it to accurately compare two objects'
distances (though, of course, you can use it to roughly compare them).

This function is excellent to use if it is important not to underestimate the
distance. It is also great if your game disallows diagonal movements; in such
a case, the Manhattan distance function will give you the exact number of
orthogonal moves required to get to a certain destination (assuming no
obstacles along the way, of course).


Chebyshev Distance
This function is almost as fast as the Manhattan distance. Matter-of-factly,
it's the fundamental opposite of the Manhattan distance -- it is accurate
within a factor of sqrt(2)/2, and is useful when it's important not to
overestimate the distance.

BYOND's get_dist() function is Chebyshev distance. It's reproduced here in
soft-code so you can see how it works.


Shifted Distance
This is a nifty function which is slightly slower than Manhattan distance or
Chebyshev distance, but which is faster than Euclidian distance or a table
lookup*. It's quite accurate -- less than half the error factor of Manhattan
and Chebyshev distance -- and is especially accurate in the eight major
cardinal directions; give it a shot and see if you like it.

* If you want to see a table lookup, check out my Table-Lookup Distance Proc,
which should be available from the same place you got these procs.
*/



proc/euclid_dist(atom/src, atom/trg) //Euclidean Distance
//Sets the distance to be as defined by the Pythagorean theorem:
// c*c = a*a + b*b -> c = sqrt((a*a) + (b*b)
//E.g. a target is 4 tiles west and 3 tiles north. This proc reports that
// the target's distance is exactly 5.
return sqrt((src.x-trg.x)*(src.x-trg.x) + (src.y-trg.y)*(src.y-trg.y))


proc/compare_dist(atom/src, atom/trg) //Squared Euclidean Distance
//Sets the distance to be sum of the square of the X offset and the square of
// the Y offset.
//E.g.: a target is 3 tiles east and 5 tiles north. This proc reports that
// the target's comparative distance is 34. A second target is 4 tiles
// east and 4 tiles north. This proc will report that the second target's
// comparative distance is 32. Thus, the first target is farther away than
// the second target.
return (src.x-trg.x)*(src.x-trg.x) + (src.y-trg.y)*(src.y-trg.y)


proc/manhattan_dist(atom/src, atom/trg) //Manhattan Distance
//Sets the distance to the sum of the offsets from the source along both
// the X and Y axes.
//E.g.: a target is 15 tiles west and 2 tiles south. This proc reports
// that the target is 17 tiles away.
return abs(src.x - trg.x) + abs(src.y - trg.y)


proc/chebyshev_dist(atom/src, atom/trg) //Chebyshev Distance
//Sets the distance equal to the maximum offset from the source, either
// along the X axis or the Y axis.
//E.g.: a target is 3 tiles east and 5 tiles north. This proc reports
// that the target is 5 tiles away.
return max(abs(src.x - trg.x), abs(src.y - trg.y))


proc/shift_dist(atom/src, atom/trg) //Shifted Distance
var/x_dif = abs(src.x - trg.x)
var/y_dif = abs(src.y - trg.y)
return ((x_dif + y_dif + max(x_dif, y_dif)) >> 1)


//3D VERSIONS
//These functions are necessary if you're calculating distance between mobs who
// are on separate Z-levels. They're only included to show you how another
// dimension affects these procedures (though, of course, you can still use them
// if you need them).

proc/euclid_dist3D(atom/src, atom/trg)
return sqrt((src.x-trg.x)*(src.x-trg.x) + (src.y-trg.y)*(src.y-trg.y) + \
(src.z-trg.z)*(src.z-trg.z))

proc/compare_dist3D(atom/src, atom/trg)
return ((src.x-trg.x)*(src.x-trg.x) + (src.y-trg.y)*(src.y-trg.y) + \
(src.z-trg.z)*(src.z-trg.z))

proc/manhattan_dist3D(atom/src, atom/trg)
return abs(src.x - trg.x) + abs(src.y - trg.y) + abs(src.z - trg.z)

proc/chebyshev_dist3D(atom/src, atom/trg)
return max(abs(src.x - trg.x), abs(src.y - trg.y), abs(src.z - trg.z))

proc/shift_dist3D(atom/src, atom/trg)
var/x_dif = abs(src.x - trg.x)
var/y_dif = abs(src.y - trg.y)
var/z_dif = abs(src.z - trg.z)
return ((x_dif + y_dif + z_dif + max(x_dif, y_dif, z_dif)) / 3)


///*
//Testing code/sample implementation

//I assume that all tiles are 2 metres across (approx 6'6").

mob/var/tmp/rangefinder_mode = 1

atom/verb/get_range()
set src in oview()
usr << "<b>Distance</b>: \..."
switch(usr.rangefinder_mode)
if(1) //EUCLIDEAN
usr << "[euclid_dist(usr,src)*2] m. (Euclidean Mode)"
if(2) //SQUARED EUCLIDEAN
usr << "sqrt([compare_dist(usr,src)*2]) m. (Compare Mode)"
if(3) //MANHATTAN
usr << "approx. [manhattan_dist(usr,src)*2] m. (Manhattan Mode)"
if(4) //CHEBYSHEV
usr << "approx. [chebyshev_dist(usr,src)*2] m. (Chebyshev Mode)"
if(5) //SHIFTED
usr << "approx. [shift_dist(usr,src)*2] m. (Shift Mode)"

mob/verb/configure_rangefinder(mode as null|anything in list(
"Euclidean","Compare","Manhattan","Chebyshev","Shift"))

if(!mode) return

switch(mode)
if("Euclidean")
rangefinder_mode = 1
usr << "You adjust your rangefinder to Euclidean mode."
if("Compare")
rangefinder_mode = 2
usr << "You adjust your rangefinder to Compare mode."
if("Manhattan")
rangefinder_mode = 3
usr << "You adjust your rangefinder to Manhattan mode."
if("Chebyshev")
rangefinder_mode = 4
usr << "You adjust your rangefinder to Chebyshev mode."
if("Shift")
rangefinder_mode = 5
usr << "You adjust your rangefinder to Shift mode."
//*/