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.

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.)

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

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

@musurca excellent low level alternative
Ported to 0.2.2 and indeed x2 time faster than regular sqrt()

function approx_dist(dx,dy)
 local maskx,masky=dx>>31,dy>>31
 local a0,b0=(dx+maskx)^^maskx,(dy+masky)^^masky
 if a0>b0 then
  return a0*0.9609+b0*0.3984
 end
 return b0*0.9609+a0*0.3984
end

To avoid overflow, I do three things...

1) my function returns whether two points are less than a given distance from each other, rather than calculating the distance
2) I first check the so-called "manhattan" distance. Is the dx or dy less than the distance?
3) Only if it is, do I then check the actual distance, using the square-of-the-hypotenuse check you described above.

E.g.

function are_closer_than(d, x1,y1, x2,y2)
  local dx = abs(x2-x1)
  local dy = abs(y2-y1)
  return dx < d 
     and dy < d 
     and (dx^2 + dy^2) < d^2
end

Here's a "within distance" check that should be pretty accurate, avoids numeric overflow, and doesn't call sqrt:

function isnearer(x,y,d)
 if(abs(x)>=d or abs(y)>=d)return false
 x/=d y/=d
 return x*x+y*y<1
end