This function allows the calculation of the distance between two points without squaring the numbers, greatly increasing the max distance before the number overflows.

function calc_dist(x1,y1,x2,y2) local xdif=x1-x2 local ydif=y1-y2 local atan=atan2(xdif,ydif) local xdist=cos(atan)*xdif local ydist=sin(atan)*ydif return xdist+ydist end |

it is also quite fast, doing 5000 calculations per frame (which is way more than you will ever need) uses around 0.63 CPU

If you don't need exact distances, @TetraPengwin, but still want to know how far away one sprite might be to another, this also works.

function calc_dist2(x1,y1,x2,y2) return abs(x1-x2)+abs(y1-y2) end |

Quite a bit faster and smaller.

Oh, BTW, @TetraPengwin. Is there a simple way to use the formula I have above where diagonal distances are not counted double as straight up and down ?

Here for instance is the formula I have in use:

x1=1, y1=1, x2=2, y2=1 - the distance would be 1.

However if x1=1, y1=1, x2=2, y2=2 - the distance would be 2, which is not entirely correct.

@dw817

That depends on what value you'd want to approximate the diagonals as instead. If a diagonal is approximated as a distance of 1, then you can just use `max(abs(x1-2x),abs(y1-y2))`

, since in that case the smaller axis collapses into nothing. If an approximated diagonal is a distance of .7, then you can use

local dx,dy=abs(x1-x2),abs(y1-y2) return min(dx,dy)+.7*(max(dx,dy)-min(dx,dy)) |

That said, you're getting into the territory of grid-based movement, which makes more sense in games resembling board games rather than a continuous in-game space. That's an important distinction, as messing with approximations of diagonals means that you can't reliably use the same formulas for a continuous space.

#### Edit: This is incorrect. I forgot to consider if xdif or ydir equal 0 as pointed out in the comments below.

@TetraPengwin

You can get another (modest) speed boost out of your function if you want. Once you've calculated the angle with `atan2`

you don't need to calculate both the `sin`

and the `cos`

just one or the other.

function calc_dist(x1,y1,x2,y2) local xdif=x1-x2 local ydif=y1-y2 local atan=atan2(xdif,ydif) return xdif / cos(atan) -- or this. both work: -- return ydif / sin(atan) end |

Even ignoring overflow issues, `sqrt`

seems to be a real CPU hog on Pico-8 so it's not a terrible idea to avoid it when possible.

@jasondelaat

won’t work if xdiff or ydiff is zero

in such case, you need to take the max abs value, defeating the purpose

Good solution, @freds72 and @jasondelaat !

@kimiyoribaka, what you have is interesting and more what I am looking for.

Is there a way to count the # of pixels most efficiently reached between two points. Not A*Star, just a straight-line and it counts the pixels without having to write a FOR/END loop.

In this it would always be an integer value.

[8x8] | |

For instance here it would be 7.

@dw817

That's approximating using a diagonal distance of 1. `max(abs(y1-y2),abs(x1-x2))`

should work.

@freds72

I don't see how that'd defeat the purpose. Wouldn't letting the function return early if either is 0 only make the function that much faster in edge cases? Even for the base version, I would think putting

if y1==y2 then return abs(x1-x2) end if x1==x2 then return abs(y1-y2) end |

would have a net benefit.

Um...I'm confused? Why would that only work for integers? If those values aren't equal then the relevant other values won't be 0.

Also why are you concerned about max and abs? Those should be cheap functions. Max is just a simple comparison and in c no less. Abs is likely implemented by just setting some bits in easily predicted ways.

Hi @kimiyoribaka:

Here is your distance formula in use, and yep, that covers exactly what I want.

Thanks !!

Use arrow keys to navigate and ❎ to swap target control.

wow! this is pretty incredible. I spent some time sketching this to try and understand it, and eventually came up with this interactive diagram: https://www.desmos.com/geometry/o5krkiqx7g

But it's not a convincing proof, it just feels magical (the surprising thing is that the point B, where the two gray arcs meet the green line, is one single point instead of two separate points. that's not something I forced to be true, it's just the result of this distance formula being correct. but *why* is it correct? this diagram doesn't really say)

I later figured out a nice proof, but that diagram is still satisfying so I wanted to show it off :)

sketch of the proof:

- given a vector v, what's the dot product of v with its unit vector?
`a dot b = |a|*|b|*cos(ang)`

, so`v dot v_unit = |v|*|v_unit|*cos(0) = |v|*|1|*1 = |v|`

.- but
`v_unit=(cos(ang),sin(ang))`

, and the other dot product formula gives`v dot v_unit = v.x*v_unit.x+v.y*v_unit.y`

, so`|v| = v dot v_unit = x*cos(ang)+y*sin(ang)`

and here's a comparison of some different distance functions:

-- tokens: 15 -- cycles: 9 + 28 = 37 (lua+sys) -- numerical issues: breaks down for differences in the hundreds. can cause big problems function dist_naive(dx,dy) return sqrt(dx*dx+dy*dy) end -- tokens: 39 -- cycles: 23 + 28 = 51 (lua+sys) -- 26 + 28 = 54 (when "if" is hit) -- numerical issues: very slightly inaccurate; (5,12) is off by 0.0002 function dist_fancy(dx,dy) local u,v=abs(dx),abs(dy) if v < u then u,v=v,u end local a=u/v return v*sqrt(a*a+1) end -- tokens: 23 -- cycles: 21 + 0 = 21 (lua+sys) -- numerical issues: very minor -- error in range (0,0)-(127,127): max 0.0017, avg 0.0004 (thanks, sparr!) function dist_trig(dx,dy) local ang=atan2(dx,dy) return dx*cos(ang)+dy*sin(ang) end -- tokens: 33 -- cycles: 26 + 0 = 26 (lua+sys) -- 29 + 0 = 29 (when "if" is hit) -- numerical issues: slightly inaccurate; (5,12) is off by 0.0009 function dist_drakeblue(dx,dy) dx,dy=abs(dx),abs(dy) if dy < dx then dx,dy=dy,dx end return dy/sin(atan2(dx,dy)) end |

cycle counts were tested with `prof(dist_naive,dist_fancy,dist_trig,dist_drakeblue,{locals={13,29}})`

.

bonus: here's some code to show a fun visualization of the different methods:

for name in all(split"dist_naive,dist_fancy,dist_trig,dist_drakeblue") do local fn=_𝘦𝘯𝘷[name] local scale=0.1 for y=0,127 do for x=0,127 do local u=(x-64)/scale local v=(y-64)/scale local d=fn(u,v) pset(x,y,d) end end ?"\#0"..name,0,0,6 repeat until btnp()>0 end |

I used this in PICO Space:

-- distance with trig -- to avoid too large numbers function dist_trig(a,b) local x,y=abs(b.x-a.x),abs(b.y-a.y) if x<y then x,y=y,x end -- accuracy goes down massively if x is much smaller than y return x/sin(atan2(y,x)) end |

The accuracy drop mentioned caused a very strange bug where the ship would spontaneously dive into the top and bottom of the sun. Turns out the game thought it was too close to the edge of the playing area (because of the bad distance value) and pushed it inwards - boom! It took quite some time to get to the bottom of that one.

I did some perf testing at the time and it's reasonably fast and I guess it's fairly "battle tested". I might see if I can find my test code and poke this and some of the other suggestions here some more since I'm thinking about updating that game anyway.

3d version for anyone interested:

-- overflow safe 3d vector length -- faster than sqrt variant (23.5+14 vs. 27.5) function v_len(v) -- {x,y,z} format local x,y,z=v[1],v[2],v[3] -- {x=..,y=..,z=..} format -- local x,y,z=v.x,v.y,v.z -- token stressed version - adds 6 cycles to the mix -- local x,y,z=unpack(v) local ax=atan2(x,y) local d2=x*cos(ax)+y*sin(ax) local az=atan2(d2,z) return d2*cos(az)+z*sin(az) end |

[Please log in to post a comment]