Log In  

Hey, everyone! So I am NOT good at math. It's something that I usually figure out once through trial and error and try not to touch ever again. So I'm turning to the more mathematically capable among us to help me decide on something: should I use a new method of determining the distance between two x/y coordinates?

Here's what I've been using up to this point:

function dist(x,y,x2,y2)
 --gets the distance between
 --two points. faster than
 --the previous version.
 local dx, dy = x - x2, y - y2
 local res=(dx * dx + dy * dy)
 if res<0 then
  res=32767
 end
 return res
end

This is the best I could figure out, and I'm sure it can be improved. It overflows, despite my best efforts to prevent it, but it was passable as long as I worked within its limitations.

Here's what I'm thinking might work better:

function xdist(x,x2)
 --gets the distance between
 --two coordinates.
 return abs(x-x2)
end

In theory, this has no complicated math, and could be used to build another function with the same purpose as the original, even though this only works with two. But here's my question: is it faster? Is the math right?

I appreciate any advice and help given! This forum has been invaluable to me.

P#70392 2019-11-30 05:42 ( Edited 2019-11-30 05:43)

Hey-- first, I should point out that your initial dist function is actually returning the squared Euclidean distance. The Pythagorean theorem is c^2 = a^2 + b^2, c=sqrt(a^2 + b^2)—so you should return sqrt(res).

But even so, overflow is a big issue with distance functions within the limited range of numbers in Pico-8. To avoid it, I use an approximation of the Euclidean distance as described here by Rafael Baptista:

function approx_magnitude(a,b)
 local a0,b0=abs(a),abs(b)
 return max(a0,b0)*0.9609+min(a0,b0)*0.3984
end

(I learned about it here on the forum, but can't recall where it was posted before.)

P#70393 2019-11-30 06:58 ( Edited 2019-11-30 07:38)

there is 2 questions really;

  • fast determination of close objects
  • distance functions

For the former, use crude division of the game space.
Simplest way is to split the world into 16x16 chunks and have entities be dynamically/removed from these chunks.
To check proximity, just take entities in the current chunk (flr(x/16)) and all 9 neighbors.

For collision checks, the sqrt is not needed - the fastest option is to compare square radius (musurca option is good but abs() is still costly)

Keywords for more are: aabox, spatial partionning

Note: if it gets too complicated, just do a game with less entities :]

P#70396 2019-11-30 07:54 ( Edited 2019-11-30 07:56)

If you have the tokens to burn, you miiight get a tiny speed improvement by replacing the calls to abs() with bitwise ops (although I haven't profiled this to compare, so ???):

function approx_dist(dx,dy)
 local maskx,masky=shr(dx,31),shr(dy,31)
 local a0,b0=bxor(dx+maskx,maskx),bxor(dy+masky,masky)
 return max(a0,b0)*0.9609+min(a0,b0)*0.3984
end

But ya, I completely agree— if you're trying to optimize proximity comparisons, it's better to think about how you could rearrange your data to reduce the search space.

EDIT: also worth noting that if you use the squared dist metric and don't need fractional precision (e.g. if you're just comparing integer x-y positions), you can avoid the possibility of overflow by bitshifting:

--always returns a distance in range [0,32767] -- will not overflow
function squaredist(dx,dy)
 local sdx,sdy=shr(dx,8),shr(dy,8)
 return shl(min(0x0.7fff,sdx*sdx+sdy*sdy),16)
end
P#70397 2019-11-30 08:44 ( Edited 2019-11-30 09:41)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2019-12-11 00:26 | 0.010s | 2097k | Q:15