fast way to compute distance between two points?

djcouchycouch · Post by **djcouchycouch** » Wed May 23, 2012 1:32 am

Hi,

I'm looking for a fast way to compute the distance between two points. It doesn't need to be very accurate as I want to roughly determine the distance between two sprites. It could even be on a tile position to tile position basis.

Any suggestions?

As usual, I'm using SGDK.

Thanks!
DJCC

neologix · Post by **neologix** » Wed May 23, 2012 5:06 am

don't know abt sgdk, but cartesian distance is generally the following formula:

dx = x2-x1
dy = y2-y1
distance = SQRT(dx*dx+dy*dy)

unless there's some sgdk-specific thing available, you're looking at an addition, 2 multiplies, and a square root at worst. if you're fine w/working w/the distance squared instead, you can ignore the SQRT; otherwise, i personally have no idea how to optimize the formula for computer usage.

Nemesis · Post by **Nemesis** » Wed May 23, 2012 6:04 am

Yeah, I'd suggest the same as what neologix posted. Use the squared distance if you can, but if you absolutely need to get back to a linear value, and you care more about performance than you do ROM space, consider using a pre-computed lookup table with an upper limit to perform the SQRT operation, that way it's just a few instructions. You could store an accurate SQRT lookup table with an 8-bit result that is useful for distances up to 256x256 (input 0x0-0x1FFFF) in 128Kb of ROM space.

ob1 · Post by **ob1** » Wed May 23, 2012 7:03 am

@Nemesis : +1

Chilly Willy · Post by **Chilly Willy** » Wed May 23, 2012 7:07 am

The fastest way is to use the taxi cab distance. TCD is based on a discrete grid that all objects must follow, like the grid of roads a taxi has to follow to go from one point to another. It's really simple - distance = change in X + change in Y. If you draw a grid and plot the two points and then draw a line from one to the other only using spaces in the grid, you'll see the number of points crossed is the change in X + change in Y. Wikipedia has a good picture if you're having trouble visualizing this.

Stef · Post by **Stef** » Wed May 23, 2012 8:43 am

If you really need the linear distance calculation you can enable the MATH_BIG_TABLES define in config.h file so you have access to fix16Sqrt(fix16 value) to calculate sqrt.
The function use a precalculated table so it's fast... but that means your distance have to fit in fix16 type :-/

Chilly Willy>Do your method requires to actually draw the line between the 2 points (using Bresenham or whatever algo) ?? for a long line it will be way slower than calculating Cartesian distance...

Chilly Willy · Post by **Chilly Willy** » Wed May 23, 2012 5:16 pm

I don't think Taxicab Geometry is meant for doing some things, it just makes certain things easier, like distance. In this case, he asked for a simple method of measuring distance that didn't need to be super accurate. The Taxicab Distance has been used in simple games for measuring distance for quite some time. That's where I first learned of it - in an article on collision detection in 8-bit/16-bit games.

http://en.wikipedia.org/wiki/Taxicab_geometry

Stef · Post by **Stef** » Wed May 23, 2012 7:03 pm

Ah ok i see, i was using this method (without knowing the name) in my first programs because i did not known the cartesian formula :p
It's not very accurate, but fast indeed : |(x2-x1)| + |(y2-y1)|

Chilly Willy · Post by **Chilly Willy** » Thu May 24, 2012 12:36 am

Stef wrote:Ah ok i see, i was using this method (without knowing the name) in my first programs because i just didn't known the cartesian formula :p
It's not very accurate, but fast indeed : |(x2-x1)| + |(y2-y1)|

Yeah, I'd never heard of taxicab geometry, either. Funny that something like that actually has a name and serious study behind it. Have you looked at this page?

http://www.taxicabgeometry.net/

There's some serious math there.

Stef · Post by **Stef** » Thu May 24, 2012 8:39 am

Yeah i saw that, sounds very serious for a so simple stuff :
(taken from history section)

The metric (distance formula) underlying what has become known as taxicab geometry was first proposed as a means of creating a non-Euclidean geometry by Herman Minkowski (1864-1909) early in the 20th century. (Minkowski was an early teacher of Albert Einstein.) The metric was one of a whole family of metrics Minkowski proposed to easily create non-Euclidean geometries.

In 1952, Karl Menger created a geometry exhibit at the Museum of Science and Industry in Chicago. For visitors to the exhibit, Menger also created a booklet entitled You Will Like Geometry. It was in this booklet that the term "taxicab geometry" was first used. It has remained associated with the geometry ever since.

By 1975, work to develop a full geometry based on the taxicab metric had still not been done. At this time Eugene Krause commented, "It would seem the time has come to do so." Krause's book published in 1975, Taxicab Geometry: An Adventure in Non-Euclidean Geometry, is still the standard introduction to the geometry.

Modern research in taxicab geometry first began appearing sporadically in the early 1980s. It would not be until about 1997 that continuous, earnest research would start in taxicab geometry. This research began with near simultaneous, independent work on taxicab angles and trigonometry by Kevin Thompson at Oregon State University and also Rüstem Kaya in Turkey. Thompson's research was conducted in graduate school in 1996 with Tevian Dray and published in 2000 with Kaya's research being published in 1997. From 1997 to 2010, Rüstem Kaya has been the most productive researcher in the geometry.

djcouchycouch · Post by **djcouchycouch** » Sun May 27, 2012 3:36 am

I've decided to use a pre-computed table of values for distance and angles between two points. I try to explain in the Goplanes Demo thread:

viewtopic.php?p=15562#15562

TapamN · Post by **TapamN** » Tue May 29, 2012 2:57 am

I guess it's a bit late for this, then, but here is an interesting way of calculating approximate distances when you can't use the squared distance (mention by Nemesis):

http://www.flipcode.com/archives/Fast_A ... ions.shtml

The example code uses 32-bit operations, but if the distance between points isn't that big or you reduce precision, you could get away with 16-bit operations.

Chilly Willy · Post by **Chilly Willy** » Tue May 29, 2012 5:30 am

TapamN wrote:I guess it's a bit late for this, then, but here is an interesting way of calculating approximate distances when you can't use the squared distance (mention by Nemesis):

http://www.flipcode.com/archives/Fast_A ... ions.shtml

The example code uses 32-bit operations, but if the distance between points isn't that big or you reduce precision, you could get away with 16-bit operations.

Wow - that was pretty nifty. The first version using a couple multiplies would be really good and fast on the SH2.

The other version with the shifts would be good for the 68000.

Stef · Post by **Stef** » Tue May 29, 2012 8:03 am

Chilly Willy wrote: Wow - that was pretty nifty. The first version using a couple multiplies would be really good and fast on the SH2.

The other version with the shifts would be good for the 68000.

Indeed i will add the second version in math unit of SGDK