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
[Please log in to post a comment]