Euclidean Distance Subroutine

Tuesday, 15th October 2019

I found another interesting text-based game from the 1960s or 1970s called Snark. This is one of a trio of games that run on a 10x10 grid, the others being Hurkle and Mugwump. Information for Snark is more elusive than for the other two games, but I found a listing in the Treasure Trove of Games that I posted about previously.

In Snark, your guess consists of a set of coordinates and a radius. The radius defines a circle around those coordinates, and the game will tell you whether the Snark is inside the circle, outside the circle or on the circle. Calculating such a thing sounds like it would need floating point arithmetic and trigonometry functions, which TinyBASIC lacks. But let's look a bit closer.

You can forget about calculating circles as such. All we need to know for Snark is the distance between the two points. Taxicab distance is easy to calculate; it's just the X and Y distances added together, and TinyBASIC's Mugwump sample game uses that method. But I think Snark needs something more refined than that, even if we can't do floating point precision.

There's another method that measures a path that travels towards the destination point at a 45 degree angle, turning to the horizontal or vertical once the diagonal path reaches the same X or Y axis as the destination. A precise formula to calculate that is

d = 0.414n + m

where d is the distance, n is the shorter of the X/Y distances and m is the longer. Since we can't multiply by 0.414 in TinyBASIC, we have to approximate further by dividing n by 2 instead. That's probably as close as we can get to a Euclidean distance, and it is calculated by the subroutine below.

200 LET Z=X-V
    IF Z<0 THEN LET Z=-Z
    LET U=Y-W
    IF U<0 THEN LET U=-U
    IF Z>=U THEN LET Z=Z+U/2
    IF Z<U THEN LET Z=U+Z/2
    RETURN

In this subroutine we use (x,y) and (v,w) as the coordinate pairs. u is a temporary variable to hold the vertical distance, and z is used temporarily to hold the horizontal distance until it's repurposed to hold the return value. Note the careful ordering of the two calculations at the end which repurpose z; if z≥u then the resulting calculation will not change the fact.