Showcase Target Leading in 2D // unorthodox solution and full source

orionsyndrome · Jun 11, 2023

tl;dr This is a long read intended as a tutorial, so if you're afraid of long text or bored out of your mind, feel free to skip to the next post where you can download the source code.

This is a work in progress, and some screenshots (and a couple of illustrations) are still missing.

Part I - Intro & Motivation
I worked on this problem ages ago. It was at the time when the internet wasn't as developed as it is today, and so the solution turned out radically different from anything I've seen since then.

Somehow I stumbled on this problem of "target leading" or "intercepting a moving target" one day, possibly through some design idea for a game.

I wasn't a game dev at the time, and so I thought to myself 'wow this is quite a challenge' fully aware of the fact that this field is full of such challenges. Back in the early 2000's it certainly looked like it's not going to get any easier than that, so it seemed like a good practice. As much as I like to be challenged mentally, this looked as something way over my head at the time, but I was ready to learn something new or fail trying.

Today some people would tell you "man, just compute where the target is going to be in N seconds from now and that's gonna be your lead shot." And I thought about that and something was off. Can this apply universally?

Well, imagine trying to shoot two ducks with a BB gun (let's ignore ballistics obviously). Ducks fly in parallel from left to right, but one of them is much closer to you than the other. Intuition alone tells you what works for the one close by, shouldn't work for the one further away. This is because your BB also has a velocity and you need to incorporate its traveling time. This moves the impact forward in time by some unknown amount, so the duck moves forward as well. If N was a fixed value for both ducks, BB would have to be magical, and fly faster to hit the duck #2.

<image: ducks_flying_in_parallel>

Computing this amount of time turns out to be hard. Here's why: What you really want is to go in reverse, say >this< is our moment of impact, but to arrive there, both the duck and the BB have to move backward in time, in proportion to their relative velocities, until they end up in their starting positions. This means that the lengths of the flight paths are directly proportional to the respective velocities. I.e. if a BB is 10x faster than the duck, its flight path will be exactly and consistently 10x longer than the duck's (assuming constant velocities), until the two happen to meet somewhere where this remains to be true after N seconds.

This is true for both ducks, but the exact location and time of impact are completely different. Trying to compensate for the traveling time will inevitably move the duck along its timeline, again changing the length of the trajectory, which smells a lot like an iterative approximation.

<image: ducks_metered_paths>

But, as it turns out, when target and bullet velocities are known and the bullet's velocity is greater, there is exactly one* solution to the problem. Great news. So can we solve this deterministically?

Yes.

(* If you already know how to solve this, you'll think there's a problem with this claim, but bear with me.)

Part II - Geometric Solution
Here's what I did. I considered a simple scenario where the velocities of the bullet (Vb) and its target (Vt) are equal. Then I tried to solve this geometrically.

It turned out there was this line of symmetry p and the two paths would always collide somewhere on this line. Well, not always: if the target was moving away from the projectile, suddenly the projectile couldn't catch up with it any more, because equal speeds. This was a geometric proof that if the target's path doesn't intersect with the line of symmetry, there are no valid solutions.

But I was curious about this image and so I tried to draw a series of concentric circles, to get a better understanding of the more general approach. Starting with a 'range circle' seemed like a good idea because, well, the angle of the gun is pretty much unknown. So I embraced this idea of extending the range with each passing second, and checking for intersections.

Then I tried solving the case where Vt : Vb = 3 : 2. In other words, the target is 50% faster than the bullet. I could almost guess the lead point by sight alone, but this wasn't enough. So I tried to fudge the circles in such a way so that their radii end up being in the 3 : 2 ratio. Their intersection showed me the point of impact, but again there was this problem of finding the amount by which I had to scale the circles. The infamous N seconds.

So I decided again to draw a series of range circles, and observe where these bullet and target ranges would intersect. Surprisingly enough, if you connect the points, this wasn't a straight line any more, but some sort of a smooth curve, parabola maybe?

After working this through, it became apparent that this was not a parabola, but another circle p whose parameters were a complete mystery.

Something obviously happened when I changed the ratio of the velocities and this got me thinking if the difference of the radii is somehow influencing the shape of this circle p. As one range circle is clearly bigger than the other, this started to look as if the previous example was maybe special. So to solve this I remembered a simple geometric principle that could help me here: similarity.

When it comes to circles, they're all regular and rotationally ambiguous, and so they can be easily projected to any other circle regardless of its size. This means they're all self-similar, which in turns means that any pair of them must have a homothetic center, a point through which such a projection occurs. Circles are also special due to mirror symmetry, so each pair of them has in fact two such centers, known as internal and external. (See also homothety.)

And so I immediately had to plot these points and see for myself. There is an easy way to construct these geometrically, with 2 pairs of common tangents.

And sure thing, the two homothetic centers coincided with the circle p I arrived at, and so I now knew both its center (the average between the points) as well as its diameter (the distance between the points). But there was something peculiar about this image: the target's path is a secant to circle p -- does this mean there are two valid lead points?

Yes it does! The problem was a quadratic equation in disguise, but most of the time it simply doesn't express itself as such, for reasons I'll get into in the following example.

Finally, I tried solving the case where Vt : Vb = 1 : 2. I.e. the bullet is two times faster than the target. This was a weird case because -- though I was able to find the circle p -- the geometric construction showed two solutions, but it was obvious that only one of them was valid.

What gives? Well, geometry is completely oblivious to any notion of velocity as a vector or the 'arrow of time'. It's not physics, so it considers the points that lie behind the target's path completely atemporally. In the final code, I decided to eliminate such absurd points with a cheap feasibility test. In the hindsight, a more complete ray-circle intersection method would've done the job, but I still decided against it in the incarnation I'm presenting here, mostly to keep the applied techniques as general as possible.

Originally I solved this through analytic geometry alone. I always liked geometry, AG and trigonometry were the only kinds of math I knew how to handle, but polynomial expressions in code don't look good. Nowadays I can do this through a combination of disciplines, mostly linear algebra, and maybe some geometric algebra and analytic and projective geometry. Which makes this a particularly beautiful approach, in my view. However I'm not a mathematician, and you shouldn't feel intimidated. I learned this only because I'm a problem solver, and I guess a true level-up would be to solve this in 3D. Still I went an extra mile, and invested some effort into visualizing the geometry, and writing all of this. All this took me a week, if you count in the original solving.

For a deterministic solver, it is surprisingly light in computation, featuring a very clean high-level code (unlike the hieroglyphic polynomial soups one can readily find on the internet), works well with the hidden infinities, and possesses a couple of square roots at most (maybe even just one, but don't quote me on that).

What else I'm offering here is a plenty of ready-made general geometric solvers (mostly 2D intersectors) and a couple of useful techniques / references / conclusions. If you're a Unity beginner, or even an above-average intermediate programmer, chances are good you'll take home something of value.

Part III - In-Editor Visualizer
So where to start? Well I'm gonna build a learning tool / visualizer.
And in the end I'll show you how to distill this into a general-purpose method, free of any crap.

It's a long article, sure, but the aim of this is to help you follow along, copy paste the code as you encounter it, see if you can work your way through it. This will teach you a lot about how to make tools such as this, and such tools are, in my opinion, invaluable if you want to accelerate your iteration time and prototyping skills, as this will let you experience more in less time. And maybe you can pick up a few tricks along the way.

We want the turret and the target to be Unity objects that are free to be moved and rotated in the 2D scene, so that you can explore the geometry by dragging the objects around. Set your scene view to '2D mode' and add 3 empty objects to your hierarchy: one to accommodate the script, and the other two you can simply rename to 'turret' and 'target' (you can set them as children of the first object, doesn't matter). The latter two have associated velocities that are supposed to be set via inspector. I also like my in-editor prototypes to work smoothly in the editor itself (no need to hit Play), and here's some code to enable all of that.

Code (csharp):

using UnityEngine;

[ExecuteInEditMode]

public class TargetLeading2DVis : MonoBehaviour {

[Header("Objects")]

[SerializeField] private GameObject _turret;

[SerializeField] private GameObject _target;

[Header("Velocities")]

[SerializeField] [Min(1E-2f)] private float _projectileVel = 1f;

[SerializeField] [Min(1E-2f)] private float _targetVel = 1f;

[Header("Visualization")]

[SerializeField] [Range(0f, 5f)] private float _gizmoScale = 1f;

}

This will now run in the editor, but there is nothing to execute at this stage however, so let's begin with some infrastructure code for drawing gizmos.

Here's a simple method that relies on Handles library to draw gizmo lines with varying thickness. This will be our core drawing method. (The rest of these drawers and static helper methods I'll hide under Spoiler buttons, to make this tutorial a bit easier to follow.)

Code (csharp):

void drawSegment(Vector2 a, Vector2 b, Color? color = null, float thickness = 2f) {

if(color.HasValue) Handles.color = color.Value;

Handles.DrawLine(v3_xy(a), v3_xy(b), thickness * _gizmoScale);

}

Code (csharp):

static Vector3 v3_xy(Vector2 v2) => new Vector3(v2.x, v2.y, 0f);

This tiny conversion function simply takes a 2D vector and produces a 3D vector out of it, because DrawLine works in 3D.

You can also cast the Vector2 to Vector3, either explicitly or implicitly, and this will achieve the same thing, but I have a strong opinion against this, because a) it makes the code less readable and meaningful (especially if done implicitly, you may even forget it's there), and b) you inadvertently destroy the opportunity to be in charge of all such conversions taking place.

This way we clearly communicate the intent: "Hey this is doing something to my Vector2 vars and is called v3_something, hmm I wonder what that could be ..."
What's the meaning of this?

The reason why I want this is to let the caller decide whether to change the color before drawing. That way you can chain several commands and still set the color only once. Particularly useful for drawing circles for example, where you draw many small segments, but the color doesn't change.

But then, Color is a value type, and I can only pass in a valid Color struct, and so the question becomes how to pass in a special state of 'none' and not just (0,0,0,0) which would be a fully transparent black color. Well, if I turn this into a nullable value type, now it can also hold the special value of
null
, which is excellent. We can now set a default value of null and make the entire argument optional.
Handles
live in UnityEditor namespace however, so let's make sure that this script works exclusively in the editor (UnityEditor is not available in the build, only in the editor). We can guard everything with
#if UNITY_EDITOR
directive, and if you build a project this code will be skipped entirely. (More on conditional compilation.)

Code (csharp):

using System;

using UnityEngine;

#if UNITY_EDITOR

using UnityEditor;

#endif

[ExecuteInEditMode]

public class TargetLeading2DVis : MonoBehaviour {

[SerializeField] ...

#if UNITY_EDITOR

// colors go here

void OnDrawGizmos() {

// we're building this incrementally, everything else

// should be somewhere below this method

}

void drawSegment( ... )

static Vector3 v3_xy( ... )

#end if

}

That's the boilerplate, now we're going to incrementally build this OnDrawGizmos function, and everything else goes below that method. Let's just quickly add some colors, immediately above
void OnDrawGizmos()
.

Code (csharp):

Color _green = hexColor(0x6cff6f);

Color _orange = hexColor(0xffb36e);

Color _blue = hexColor(0x6e83ff);

Color _rorange = hexColor(0xd39629);

Color _rviolet = hexColor(0x3e2ad1);

This is a random assortment of colors I've used elsewhere, but they're good enough for this exercise. The functions accepts the hexadecimal color values used on the web that you can copy/paste from Photoshop (or a similar application). To get the code (and understand how I implemented this), click the Spoiler button.
I won't explain this in too much detail because it's out of scope for what we're trying to build. But the key premise is that there are two basic color structs in Unity, named
Color
and
Color32
.
Color
contains 4 32-bit floating point values (expecting values in the range 0..1), while
Color32
contains a 32-bit discrete color information, or 8 bits per channel. One byte has exactly 8 bits, so it has 4
byte
values. hexColor function builds this Color32 struct from a full range 32-bit integer which is then implicitly cast to Color.

To do this I use this helper function which can assign 4 values independently through a single function. I call it lambda, because it's supposed to be used with a lambda expression, which is an in-place anonymous function.

Code (csharp):

static Color32 c32lambda(Func<int, byte> lambda)

=> new Color32(lambda(0), lambda(1), lambda(2), lambda(3));

If I was to specify
c32lambda( i => 2 * i );
I would get this
new Color32(0, 2, 4, 6);
. Pretty neat, but not particularly useful.

Instead I use this to butcher the bits from the original hexadecimal value, and rearrange them as necessary. We end up with this.

Code (csharp):

static Color32 hexColor(uint value, byte alpha = byte.MaxValue)

=> c32lambda( i => (i < 3)? (byte)( ( value >> ((2-i)<<3) ) & byte.MaxValue )

: alpha );
Ok, at this point you should drag your 'turret' and 'target' objects to the eponymous fields in the inspector. But even if you don't, this script should work without errors. There is a difference between "not working" and "screaming of errors". So let's start with that.

Code (csharp):

void OnDrawGizmos() {

if(_turret == null || _target == null) return; // these two are mandatory

var turretPos = v2_xy(_turret.transform.position);

var targetPos = v2_xy(_target.transform.position);

var targetDir = v2_xy(_target.transform.rotation * Vector3.right);

drawSegment(turretPos, targetPos, color: _green);

}
Code (csharp):

static Vector2 v2_xy(Vector3 v3) => new Vector2(v3.x, v3.y);

Of course we now need the opposite of
v3_xy
. It's plugging x and y into Vector2 and discarding the z. In this case we receive 3D coordinates from the actual transforms, so we only take a relevant projection on the XY plane.

Another thing to note regarding these conversions is that it becomes very easy to switch everything to another plane, for example. If we had v2_xz which would be a top down projection, it would be

Code (csharp):

static Vector2 v2_xz(Vector3 v3) => new Vector2(v3.x, v3.z);

and likewise, we'd also use

Code (csharp):

static Vector3 v3_xz(Vector2 v2) => new Vector3(v2.x, 0f, v2.y);
<image: screenshot>

Now you can drag the two objects and observe the green line being drawn between them. You can also freely rotate the target on the Z axis. (Don't rotate it on the X or Y axes, though, because we're in 2D and this will only confuse you, because I'm extracting a projection on the XY plane.) Keep in mind that target rotation does nothing for now, but you'll be able to use this to rotate the velocity vector.

We can work on drawing circles, so that we can see the velocity range for both points.

Code (csharp):

void drawCircle(Vector2 c, float r, int segments = 48, Color? color = null, float thickness = 2f) {

if(color.HasValue) Handles.color = color.Value;

var last = Vector2.zero;

var step = TAU / segments;

for(int i = 0; i <= segments; i++) {

var next = c + r * trig(i * step);

if(i > 0) drawSegment(last, next, thickness: thickness);

last = next;

}

}

This shares a lot of similarity with drawSegment, and in fact, uses drawSegment to draw a regular polygon that, given enough points, only resembles a circle. There are two new things here, namely TAU and trig function. So let's add this as well.

Code (csharp):

static readonly float TAU = MathF.PI * 2f;

static Vector2 trig(float radians) => new Vector2(MathF.Cos(radians), MathF.Sin(radians));

To learn more about this technique, check out the article on unit circle which covers the basics of what sine and cosine essentially mean. Here's a crash course on a couple of important identities in 2D

We develop a series of polar coordinates which are then converted back into Euclidean space. The method will produce a series of short segments connecting the point pairs, through incrementing the angle by fixed, linear steps.

Code (csharp):

void OnDrawGizmos() {

if(_turret == null || _target == null) return;

var turretPos = v2_xy(_turret.transform.position);

var targetPos = v2_xy(_target.transform.position);

var targetDir = v2_xy(_target.transform.rotation * Vector3.right);

drawPoint(turretPos, size: 1.5f, color: _blue);

drawPoint(targetPos, size: 1.5f, color: _orange);

drawCircle(turretPos, _projectileVel, color: _blue, thickness: 2f);

drawCircle(targetPos, _targetVel, color: _orange, thickness: 2f);

}

Code (csharp):

void drawPoint(Vector2 p, float size = 1f, Color? color = null)

=> drawCircle(p, .05f * _gizmoScale * size, 6, color, thickness: 4f);

We can repurpose drawCircle to draw small hexagonal "asterisks" in place of points.

<image: screenshot>

Now you can change your velocities and watch the two range circles shrink and grow.
Let's add a bunch of checkboxes to the inspector to allow us to toggle things on/off.

Code (csharp):

...

[Header("Visualization")]

[SerializeField] private bool _showVectors; // turret and target velocity vectors

[SerializeField] private bool _showRanges; // range circles

[SerializeField] private bool _showLeads; // computed lead points

[SerializeField] private bool _showPaths; // projected paths

[SerializeField] [Range(0f, 5f)] private float _gizmoScale = 1f;

[Header("Homothety")]

[SerializeField] private bool _showCenters; // internal/external homothetic centers

[SerializeField] private bool _showTangents; // common tangents

[SerializeField] private bool _showCircle; // constructed from homothetic centers

Now we can conditionally guard against specific parts of the visualization.

Code (csharp):

void OnDrawGizmos() {

if(_turret == null || _target == null) return;

var turretPos = v2_xy(_turret.transform.position);

var targetPos = v2_xy(_target.transform.position);

var targetDir = v2_xy(_target.transform.rotation * Vector3.right);

if(_showVectors) {

drawArrowSegment(targetPos, targetPos + _targetVel * targetDir, _orange, t: 1f, w: .75f, thickness: 2f);

}

if(_showRanges) {

drawCircle(turretPos, _projectileVel, color: _blue, thickness: 2f);

drawCircle(targetPos, _targetVel, color: _orange, thickness: 2f);

}

}

Code (csharp):

void drawArrowSegment(Vector2 a, Vector2 b, Color? color = null, float t = .5f, float w = .333f, float maxSize = 2f, float thickness = 2f) {

drawSegment(a, b, color, thickness);

drawArrow(a, b, t, w, maxSize, thickness);

}

Just a compound method that draws a segment ending with a little arrow. You can configure where exactly to place this arrow along the segment, but also how wide it should be.

Code (csharp):

void drawArrow(Vector2 a, Vector2 b, float t = .5f, float w = .333f, float maxSize = 2f, float thickness = 2f) {

var pl = lerp(a, b, t);

var delta = b - a;

var mag = magOf(delta);

var dir = delta / mag;

var pd = w * perp(dir);

var aa = pl + _gizmoScale * .2f * min(maxSize, mag) * (pd - dir);

var bb = pl - _gizmoScale * .2f * min(maxSize, mag) * (pd + dir);

Handles.DrawLine(v3_xy(pl), v3_xy(aa), thickness * _gizmoScale);

Handles.DrawLine(v3_xy(pl), v3_xy(bb), thickness * _gizmoScale);

}

This one is fairly complicated, and let's not bother with any it for the moment. There are a lot of functions called here, and we'll have to cover them anyway. So that's what I'm going to do instead.

To make this work we suddenly need several helper functions, namely lerp, magOf, perp, and min. These will come in handy in a lot of upcoming code.

Code (csharp):

// returns the lesser of the two values

static float min(float a, float b) => MathF.Min(a, b);

// linear interpolation or 'lerp'; see https://en.wikipedia.org/wiki/Linear_interpolation

static Vector2 lerp(Vector2 a, Vector2 b, float t) => a * (1f - t) + b * t;

// squaring a value

static float sqr(float v) => v * v;

// taking a square root

static float sqrt(float v) => MathF.Sqrt(v);

// returns the squared magnitude of a vector (same as 'sqrMagnitude' property)

static float sqrMagOf(Vector2 v) => v.x * v.x + v.y * v.y;

// returns the magnitude of a vector (same as 'magnitude' property)

static float magOf(Vector2 v) => sqrt(sqrMagOf(v));

// returns a vector that is perpendicular to the given vector

static Vector2 perp(Vector2 v) => new Vector2(-v.y, v.x);

// returns a normalized vector (same as 'normalized' property)

static Vector2 norm(Vector2 v) => v * (1f / magOf(v));

Some basics regarding vectors in general:
Magnitude of a vector is the same thing as its visible length. It's simply "how powerful" the vector appears to be, as if it was a physical force or velocity.

Normalization is a mathematical way of neutralizing this magnitude back to 1. So to normalize a vector means to reduce (or expand if shorter) its length to 1, but it's still oriented exactly the same. A vector of length 1 (also known as a 'unit vector') is useful because you can multiply it with some scalar value and it will have precisely that length.

Magnitude and normalization are a bit expensive operations because they need to take a square root (thanks to Pythagorean theorem). That's why we sometimes avoid computing magnitude and use its squared counterpart instead.

Also, you can see why it's impossible to normalize a vector of magnitude 0, also known as a zero vector.

Good question!
Well I got three very good reasons:

1) for completeness sake, as this is some sort of tutorial,

2) self-containment in general is good when prototyping, because your product, your libraries, and 3rd party software will shift and move -- and you want your prototype to just work at all times,

3) because I've adopted the style of producing self-contained, self-evident code, especially when I'm working with math. This is something that hit me after decades of coding, from observing how complex shaders are developed: you get all of your tools in front of you, instead of reaching for them "from the cloud". In turn you begin to know your tools very intimately and own the toolkit, which is a very good thing in this craft. (And I use the word 'craft' very consciously.)

Here are some of the benefits for having a clear view over the implementation details:

a) you don't build large behaviors on assumptions, and you can micro-test,
b) you get to codify some higher level abstractions (i.e. sqr(n) => n * n),
c) you can customize a function or cherry pick among the varieties,
d) it's harder to mix MathF and Mathf, for example (MathF is faster for trig and sqrt),
e) the call sites themselves are compact and camelCased, which is appropriate for math fns,
f) micro fns are more likely to be inlined by the compiler; can also be manually inlined without errors,
g) functions are completely transferrable to another class or project, and finally
h) you never ever introduce annoying dependencies.

This concludes the first part of the method. Try it!

Part IV - Homothetic Shenanigans
Let's get ready for what's to come by defining a couple of useful constants and functions.

Code (csharp):

static readonly int EXTERNAL = 0;

static readonly Vector2 V2NaN = new Vector2(float.NaN, float.NaN);

static bool isNaN(Vector2 v) => float.IsNaN(v.x) || float.IsNaN(v.y);

To simplify some math (and skip over having to test bools or enums) I've opted for an integer parameter, but it should normally be an enum. So to help with readability, we have this EXTERNAL special value. Thus the argument is either explicitly set to EXTERNAL (zero) or it's not (in which case it's implicitly 'internal').

This is pretty much a C-like coding style and not really in the spirit of C#, however I'm using it strictly for the visualization, not the solution itself.

And the other thing is a Vector2 defined as NaN (a special value), which will be used as a signal for undefined (garbage or infinite) vectors when we're working with geometric solvers. And we have also prepared a detector for such an undefined vector.

So what do we want to achieve at this point? Given two range circles, we want to compute the two homothetic centers (also known as centers of similitude): internal and external. This will yield two points that will move us one step closer to the final solution.

However, it's worth checking out what circular homothetic centers are.

External common tangents
If you imagine a bicycle chain connecting two disks, that's exactly how external common tangents work: they touch the circles from the outside. And if they are tapered (meaning one of the circles is smaller than the other), they will eventually meet exactly in the external homothetic center. But watch out: if they are parallel, which can happen if the circles are of the same size, then they never meet, and thus the external homothetic center becomes undefined.

External common tangents are also useful when you're building a system of pullies with a belt (physical or simulated), and you need to determine how long the belt should be. This becomes a lot simpler when you have the exact points where the belt disconnects, and you can easily compute the lengths of the tangents and the arcs.

--

Internal common tangents
Now imagine a bicycle chain where you take one disk and rotate it 180 degree around the X axis. The tangents get twisted between the disks. These are now internal common tangents, and the point where these cross over is exactly the internal homothetic center. If the circles are of the same size, this point lies right in the middle between them.

--

Unlike the internal common tangents, external ones are well defined even when the two circles partially overlap, but as soon as one circle completely engulfs the other (or if they're congruent), both tangent sets turn undefined.

The centers are fairly simple to compute, and derive directly from analytic geometry. In fact they both use the exact same formula, but the external homothetic center changes the chirality of the 2nd circle (simply put: its radius becomes negative).

I've tried several approaches until I've settled down with a single method to compute them both in one swoop. Less repeating and better performance. It also features an optimization for the special case of having equal radii.

To resolve this we need some more helper functions.
The following methods are important when trying to work with single-precision floating point values, given that they suffer from rounding and precision errors. For example, when testing whether some computed value is zero, even though it might be very close for all practical purposes, it's still not exactly zero. For this reason, instead of doing
v == 0f
it is preferred to instead do

Code (csharp):

static bool isZero(float n) => abs(n) < 0.000001f;

and then query with
isZero(v)
. If a value is sufficiently small, regardless of its sign, it will be registered as zero. This can be written even more flexible, allowing the user to configure this clipping threshold (here called epsilon or eps).

Code (csharp):

static bool isZero(float n, float eps = 1E-6f) => abs(n) < eps;

Abs itself is the absolute value, letting us ignore the negative sign and this comes with the basic C# math library.

Code (csharp):

static float abs(float n) => Math.Abs(n);

Finally we want
isSame
, a function that will tell us if two floating point values are sufficiently close/similar to each other. The easiest and most precise way to achieve this is to just test their difference against the zero.

Code (csharp):

static bool isSame(float n, float m, float eps = 1E-6f) => abs(m - n) < eps;
The actual equation looks like this

Code (csharp):

Vector2 homotheticCenter(Vector2 c1, float r1, Vector2 c2, float r2)

=> new Vector2(c2.x * r1 + c1.x * r2, c2.y * r1 + c1.y * r2) / (r1 + r2);

But considering that we're going to call this frequently, we can make it slightly better.

Code (csharp):

Vector2 homotheticCenter(ref Vector2 c1, float r1, ref Vector2 c2, float r2)

=> (1f / (r1 + r2)) * new Vector2(c2.x * r1 + c1.x * r2, c2.y * r1 + c1.y * r2);

This way we avoid having to copy the vectors around, and we also trade 2 divisions for 1 division and 2 multiplications without loss of generality. This isn't a major boost (if any) because it's in 2D, but I'm also taking the compounding effect into account.

Now we can apply the formulas.

Code (csharp):

// two centers and two radii go in, two points go out

void computeHomotheticCenters(Vector2 c1, float r1, Vector2 c2, float r2, out Vector2 he, out Vector2 hi) {

// special case

if(isSame(r1, r2)) { he = V2NaN; hi = avg(c1, c2); return; }

// regular case

he = homotheticCenter(ref c1, r1, ref c2, -r2);

hi = homotheticCenter(ref c1, r1, ref c2, +r2);

}

Code (csharp):

static Vector2 avg(Vector2 a, Vector2 b) => (a + b) * .5f;

This is the same as lerp(a, b, 0.5) only with slightly less computation. Also known as arithmetic mean, in this context it produces a 2D vector that is exactly mid way between the original two.

We can now go back and add this to our main method.

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

computeHomotheticCenters(turretPos, _projectileVel, targetPos, _targetVel, out var he, out var hi);

if(_showCenters) {

drawPoint(hi, color: Color.white); // while hi is guaranteed, he is not

if(!isNaN(he)) drawPoint(he, color: Color.white); // Unity wouldn't draw a NaN point anyways, but still

}

}

Part V - Common Tangents
Ok, now comes the tricky part: the tangents themselves.
Here's a good guide on what needs to be done. Sure, maybe it's hard to follow, but it's fairly easy, once you get a hang of it.

There is a pair for each of the two types of tangents, 4 tangents in total. Their method of construction is very similar, but each type is computed starting from a slightly different premise. In the end you just need to fiddle with the signs to get it right. I've decided to make a single method that spits one tangent at a time, by computing its start and end points. You order them one by one through selecting the type (external/internal) and index (0/1).

If you pay close attention to that guide above, you can see that it assumes circle-circle intersections to find the point L in the first image, and point H in the second. Circle-circle intersections are basically quadratic equations which return 0, 1, or 2 solutions, depending on whether the circles are too far apart, touch each other, partially overlap, or something else.

At this point we have everything we need for this method (sqrMagOf, abs, sqr, isZero, sqrt, perp, isSame), so let's tackle this first, so that you can begin to appreciate what's what.

You are not supposed to read this like a bedtime story, but observe the way it opens up: definitions of delta, dsqr, rsum, and rdif. These are quite simple and useful values.

Code (csharp):

// returns the number of solutions: 0, 1, 2

int circleCircle(Vector2 c1, float r1, Vector2 c2, float r2, out Vector2 p1, out Vector2 p2) {

const float EPSILON = 1E-6f;

p1 = V2NaN; p2 = V2NaN;

var delta = c1 - c2;

var dsqr = sqrMagOf(delta);

var rsum = r1 + r2;

var rdif = abs(r2 - r1);

// circles too far apart; or one circle contains the other; or centers coincide

if(dsqr > sqr(rsum) || dsqr < sqr(rdif) || isZero(dsqr, EPSILON)) return 0;

var invd = 1f / sqrt(dsqr);

var a = (sqr(r1) - sqr(r2) + dsqr) * (invd * .5f);

var p = c1 - delta * a * invd;

var hd = sqrt(sqr(r1) - sqr(a)) * invd;

var dp = perp(delta);

p1 = p + dp * hd;

p2 = p - dp * hd;

// circles touch each other from the outside or from the inside, respectively

if(isSame(dsqr, sqr(rsum), EPSILON) || isSame(dsqr, sqr(rdif), EPSILON)) return 1;

return 2; // two points of intersection

}

delta is the differential vector between two circle centers, dsqr is the distance squared, rsum is the sum of radii, and rdif is the absolute difference between the two. Now if you look at the first check, here are the crucial conditions to help isolate the cases which yield no solutions. d > rsum means that circles are spaced apart, d < rdif means that one circle contains another without touching, isZero(d) means the circles are concentric. The difference you're seeing is that all of these conditions are written in a quadratic form to avoid taking a square root. A responsible code will take a square root only when it absolutely has to.

Finally the circles touch each other if any of these are true: d ~= rsum (touching from the outside) or d ~= rdif (touching from the inside).

Not so bad right? We're gonna use this again.

Here's what we do:
- We set up a good framework where we evaluate the tangents only when it makes sense.
- Oh, and we employ the same trick where we pass vectors as references (we don't intend to modify them)

Code (csharp):

// no, it's not exploreHomoeroticTendencies ffs

bool exploreHomotheticTangencies(int type, int index, ref Vector2 c1, float r1, ref Vector2 c2, float r2, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c2 - c1); // squared distance between circle centers

var rsum = r1 + r2; // sum of two radii

var rdif = abs(r2 - r1); // difference between radii

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = type == EXTERNAL? dsqr >= sqr(rdif) // circles at least partially overlap

: dsqr > sqr(rsum); // circles are certainly spaced apart

if(hasTangents) {

// the actual work

t1 = ...

t2 = ...

return true;

}

return false;

}

Breakdown of what we're supposed to do with the internal common tangents (type 1):
1. find the 3rd circle in the middle of the two existing ones, passing through c1 and c2
2. pretend that the 2nd radius is r1 + r2
3. find the two circle-circle intersections between the 3rd and the 2nd circle
4. pick one of the two points (according to supplied index), let's call it p
5. find the delta vector between c1 and this point p
6. turn this vector perpendicular to itself and normalize it
7. rescale it by r1 which is the exact magnitude to push the line from c1 as shown in the guide
8. determine the sign of this offset o

Breakdown of what we're supposed to do with the external common tangents (type 0):
2. pretend that the 2nd radius is abs(r1 - r2)
3a. if the two radii were equal, set the two intermediate results to c2 (to prevent numerical imprecisions)
3b. otherwise, find the two circle-circle intersections between the 3rd and the 2nd circle
Everything else is the same.

Full method:

Code (csharp):

// http://jwilson.coe.uga.edu/emt669/Student.Folders/Kertscher.Jeff/Essay.3/Tangents.html

// type => zero: external (belt-like), non-zero: internal (crossed-out)

// index => zero: first tangent, non-zero: second tangent

bool exploreHomotheticTangencies(int type, int index, ref Vector2 c1, float r1, ref Vector2 c2, float r2, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c2 - c1); // squared distance between circle centers

var rsum = r1 + r2; // sum of two radii

var rdif = abs(r2 - r1); // difference between radii

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = type == EXTERNAL? dsqr >= sqr(rdif) // circles at least partially overlap

: dsqr > sqr(rsum); // circles are certainly spaced apart

if(hasTangents) {

var r = type == EXTERNAL? rdif : rsum; // modified radius of the 2nd circle

var tc = avg(c1, c2); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

Vector2 p1, p2;

if(type == EXTERNAL && isZero(rdif)) {

p2 = p1 = c2; // makes sure the external tangents are computed as parallel

} else {

circleCircle(tc, tr, c2, r, out p1, out p2);

}

// pick a point according to index

var p = index == 0? p1 : p2;

// sign of the result is determined by both type and index

var s = (type == EXTERNAL? sgnstep(r2 - r1) : -1) * (index == 0? 1 : -1);

// offset

var o = r1 * norm(perp(c1 - p)) * s;

// final points

t1 = c1 + o;

t2 = p + o;

return true;

}

return false;

}

sgnstep or 'sign step' is a step function very similar to sign function, but lacks zero. It is useful when zero is meaningless or even dangerous, like in increments. Practically it only ever reacts to a negative value, returning a -1 when the value is negative, and 1 otherwise.

In this particular case we just want to flip the sign if r1 is greater than r2, because the tangents tend to be flipped around when this happens.

Code (csharp):

static float sgnstep(float n) => n < 0f? -1f : 1f;

And then, we finish this off.

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

if(_showTangents) {

for(int type = EXTERNAL; type < 2; type++) { // two types

for(int index = 0; index < 2; index++) { // two lines each

if(exploreHomotheticTangencies(type, index, ref turretPos, _projectileVel, ref targetPos, _targetVel, out var t1, out var t2))

drawSegment(t1, t2, color: Color.white, thickness: 1f);

}

}

}

}

Done.

Oh well, there is one more thing. If you experiment enough by moving 'turret' and 'target' objects around, you might notice that the both tangents pairs disappear once the circles touch or overlap each other. This shouldn't be the case. Remember when I said that the external tangents are well-defined even when the circles overlap? And it is obvious just by looking the partially overlapped circles why this is so. This is exactly why there is a separate
hasTangents
condition.

And yet, this particular technique works only when the two helper circles yield two points of intersection. As soon as the circles touch, one of the circles degenerates to zero size, and so we need to come up with a different technique. So let's approach this from another angle, and even if it's costly, it's for the visualization purposes!

We defined the external homothetic center as "the point where the external common tangents meet". This means we can produce our tangents from this point alone, as it is possible to compute both tangent points from a single point and a circle defined by its center and radius. The only constraint is that the point must lie in the circle exterior, which is guaranteed in our case.

We can prepend a small state machine in front of "the actual work" which conditionally takes over. It shouldn't affect the internal common tangents, and it shouldn't take over in the case when radii are equal because 1) the existing code actually worked properly for that case, but also 2) if tangents are parallel, the external homothetic point is undefined anyway.

All that's left to do is to deal with the point-circle tangent solver.

Code (csharp):

// https://answers.unity.com/questions/1617078/finding-a-tangent-vector-from-a-given-point-and-ci.html

bool pointCircleTangency(Vector2 p, Vector2 c, float r, out Vector2 t1, out Vector2 t2) {

t1 = V2NaN; t2 = V2NaN;

p -= c;

var dsqr = sqrMagOf(p);

var rsqr = sqr(r);

// point is inside the circle, no tangents

if(dsqr < rsqr) return false;

var invd = 1f / sqrt(dsqr);

var a = rsqr * invd;

var q = r * sqrt(dsqr - rsqr) * invd;

var pn = p * invd; // normalization

var pnp = perp(pn);

var va = pn * a;

t1 = c + va + pnp * q;

t2 = c + va - pnp * q;

return true; // tangent points found

}

Now we can apply the core equation function to find the external homothetic center, and query the points of tangencies for both circles, and we'll get a pair for each. Sadly, the chief method is transposed, as it requires one point per circle, so we end up throwing some results away, only to re-evaluate them in the 2nd pass. Again, this is only used for the common tangents visualization and I don't care that much.

Code (csharp):

// http://jwilson.coe.uga.edu/emt669/Student.Folders/Kertscher.Jeff/Essay.3/Tangents.html

// type => zero: external (belt-like), non-zero: internal (crossed-out)

// index => zero: first tangent, non-zero: second tangent

bool exploreHomotheticTangencies(int type, Vector2 c1, float r1, Vector2 c2, float r2, int index, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c2 - c1); // squared distance between circle centers

var rsum = r1 + r2; // sum of two radii

var rdif = abs(r2 - r1); // difference between radii

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = type == EXTERNAL? dsqr >= sqr(rdif) // circles at least partially overlap

: dsqr > sqr(rsum); // circles are certainly spaced apart

if(hasTangents) {

// special external case when circles partially overlap

if(type == EXTERNAL && !isZero(rdif)) { // rdif ~= 0 effectively means that r1 ~= r2

if(dsqr <= sqr(rsum)) {

var he = homotheticCenter(ref c1, r1, ref c2, -r2);

pointCircleTangency(he, c1, r1, out var t11, out var t21);

pointCircleTangency(he, c2, r2, out var t12, out var t22);

if(index == 0) {

t1 = t11;

t2 = t12;

return true;

}

t1 = t21;

t2 = t22;

return true;

}

}

// the usual case when circles are spaced apart

var r = type == EXTERNAL? rdif : rsum; // modified radius of the 2nd circle

var tc = avg(c1, c2); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

Vector2 p1, p2;

if(type == EXTERNAL && isZero(rdif)) {

p2 = p1 = c2; // makes sure the external tangents are computed as parallel

} else {

circleCircle(tc, tr, c2, r, out p1, out p2);

}

// pick a point according to index

var p = index == 0? p1 : p2;

// sign of the result is determined by both type and index

var s = (type == EXTERNAL? sgnstep(r2 - r1) : -1) * (index == 0? 1 : -1);

// offset

var o = r1 * norm(perp(c1 - p)) * s;

// final points

t1 = c1 + o;

t2 = p + o;

return true;

}

return false;

}

Homework: Try to think of a way to cut this work in half (i.e. getting a pair of tangents for the cost of one). (I might do this at some point in the future.)

Part VI - Homothetic Circle
With the trickiest part behind us, we can now focus on the heart of the algorithm -- the homothetic circle p.
The actual parameters of this circle are now incredibly trivial.

Code (csharp):

var hc = avg(hi, he); // center (Vector2), the average of two points

var hr = magOf(hc - hi); // radius (float), a distance from internal homothetic center to hc

if(_showCircle) {

drawCircle(hc, hr, color: _rviolet, thickness: 3f);

}

But this turns out to be too-good-to-be-true for a couple of reasons.
First, this circle p can become very large under some circumstances. Second, we must not forget about the special case when the radii are equal, because the circle essentially becomes infinitely big, and it's not very healthy trying to draw something of that size.

So let's think of another way to represent an infinitely big circle -- as a line perhaps? But because this is only a visualization of what's going on mathematically, we can also include a large threshold to avoid having to draw too large circles, as they approach infinity. We know that the circle p must go through the internal homothetic center at all times, so it's very easy to define the line p parametrically.

And another thing: as the circle grows larger, it makes sense to progressively add segments to it, so that it grows in resolution, instead of just scaling up as a rough regular polygon. Because the relationship between radius and circumference is linear, we can produce a simple formula to achieve this. And let's clamp this value between 32 and 256, it seems to be good enough imo.

Code (csharp):

static int clamp(int value, int min, int max)

=> (value < max)? (value > min)? value : min : max;

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

// note that 'he' might possibly be NaN, or contain very large numbers,

// so both of these results can end up containing NaN values

var hc = avg(hi, he);

var hr = magOf(hc - hi);

if(_showCircle) {

// empirical "infinite" radius sensor

if(isNaN(hr) || hr > 3072f || isSame(_projectileVel, _targetVel, .025f)) {

var hl = 3f * perp(turretPos - targetPos);

drawSegment(hi - hl, hi + hl, color: _rviolet, thickness: 3f);

} else {

drawCircle(hc, hr, segments: clamp((int)(TAU * hr), 32, 256), color: _rviolet, thickness: 3f);

}

}

}

The good news is that there isn't much else to do here.

Part VII - Target Leads
Finally, the leading points. The general solution is to just find intersections between the target's path and the homothetic circle p, however there is also the degenerate case when the circle gets infinitely big, where we switch to a line p instead. In this case we want to find the intersection between the target's path and this line. This truly is the heart of the algorithm -- it's either one or the other (depending on the relative velocities), and both of these methods are very CPU efficient.

So let's move forward by solving a 2D line-line intersection.
For this I'm using homogeneous coordinates, for which you can find a sufficient tutorial here. Unlike the classic analytical solution this one offers incredible numerical stability and features no branching and just a single division.

Code (csharp):

bool lineLine(Vector2 a1, Vector2 a2, Vector2 b1, Vector2 b2, out Vector2 p) {

const float EPSILON = 1E-6f;

p = V2NaN;

var cc = cross(cross(v3_xy1(a1), v3_xy1(a2)), cross(v3_xy1(b1), v3_xy1(b2)));

if(isZero(cc.z, EPSILON)) return false; // lines are parallel or congruent

p = ((Vector2)cc) * (1f / cc.z);

return true;

}

This computes a cross product of two vectors in 3D. Identical to Vector3.Cross.

Code (csharp):

static Vector3 cross(Vector3 a, Vector3 b)

=> new Vector3(a.y * b.z - a.z * b.y, a.z * b.x - a.x * b.z, a.x * b.y - a.y * b.x);

Wait, why are we using 3D coordinates here? Well we don't, but we need to provide homogeneous coordinates which take up the extra dimension for this kind of math to work. In the end we use the extraneous z coordinate to flatten things down to where they belong. Also you can't apply a cross product to 2D vectors, it becomes a thing starting from the three dimensions and upward.

We use this to produce the homogeneous coordinates from 2D ones.

Code (csharp):

static Vector3 v3_xy1(Vector2 v2) => new Vector3(v2.x, v2.y, 1f);

(The final source will also contain the lowered version where the 'cross' calls are all baked in, and the execution is reordered slightly for even better performance.)
Next up, line-circle intersections.

Code (csharp):

// https://mathworld.wolfram.com/Circle-LineIntersection.html

// returns the number of solutions

int lineCircle(Vector2 a, Vector2 b, Vector2 c, float r, out Vector2 p1, out Vector2 p2) {

const float EPSILON = 1E-6f;

p1 = V2NaN; p2 = V2NaN;

a -= c; b -= c;

var delta = b - a;

var dsqr = sqrMagOf(delta);

var pdot = a.x * b.y - b.x * a.y;

var discr = sqr(r) * dsqr - sqr(pdot);

if(discr < 0f) return 0; // no intersections

p2 = p1 = new Vector2(pdot * delta.y, -pdot * delta.x);

var invdsqr = 1f / dsqr;

// same as isZero(discr), because we've discarded negative values

if(discr < EPSILON) {

p2 = p1 = c + p1 * invdsqr;

return 1; // line is a tangent: one point of intersection

}

var im = sqrt(discr) * new Vector2(sgnstep(delta.y) * delta.x, abs(delta.y));

p1 = c + (p1 + im) * invdsqr;

p2 = c + (p2 - im) * invdsqr;

return 2; // line is a secant: two points of intersection

}

And we can finish this off like so

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

int leads = 0;

var lead1 = V2NaN;

var lead2 = V2NaN;

if(isSame(_projectileVel, _targetVel)) {

if(lineLine(targetPos, targetPos + targetDir, hi, hi + perp(turretPos - targetPos), out lead1))

leads = 1;

} else {

leads = lineCircle(targetPos, targetPos + targetDir, hc, hr, out lead1, out lead2);

}

if(_showLeads) {

if(leads >= 1) drawPoint(lead1, size: 3f, color: _green);

if(leads == 2) drawPoint(lead2, size: 3f, color: Color.red);

}

}

Although this looks fine, there are a couple of issues with this that really need sorting out. The first is that we don't yet eliminate absurd points (as explained in chapter II) and we ought to. And the second is that it would be nice if we could order the leads in such a way that
lead1
always lines up as the better choice (unless there are no valid leads).

The feasibility test for the lead point is very simple: it is enough to check the dot product between the target's velocity and target->lead vector. If the two are more than 90 degrees apart (dot product turns negative), the lead is considered behind the target, meaning the target will never get there.

Code (csharp):

static bool isPhysLead(Vector2 pos, Vector2 dir, Vector2 lead)

=> dot(dir, lead - pos) >= 0f;

Exactly the same as Vector2.Dot (more info on how we use dot products here).

Code (csharp):

static float dot(Vector2 a, Vector2 b) => a.x * b.x + a.y * b.y;

Now we can incorporate this

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

int leads = 0;

Vector2 lead1 = V2NaN, lead2 = V2NaN;

if(isSame(_projectileVel, _targetVel)) {

if(lineLine(targetPos, targetPos + targetDir, hi, hi + perp(turretPos - targetPos), out lead1))

if(isPhysLead(targetPos, targetDir, lead1))

leads = 1;

} else {

leads = lineCircle(targetPos, targetPos + targetDir, hc, hr, out lead1, out lead2);

var phys1 = isPhysLead(targetPos, targetDir, lead1);

var phys2 = isPhysLead(targetPos, targetDir, lead2);

// validates and reorders leads so that lead1 is always the best option

// (a bit messy but we'll refactor this for the actual implementation)

if(phys1 && !phys2) { leads = 1; }

else if(!phys1 && phys2) { swap(ref lead1, ref lead2); leads = 1; }

else if(!phys1 && !phys2) { leads = 0; }

else { // here we reorder the leads so that the nearest one is lead1

leads = 2;

if(sqrMagOf(lead2 - turretPos) < sqrMagOf(lead1 - turretPos))

swap(ref lead1, ref lead2);

}

}

if(_showLeads) {

if(leads >= 1) drawPoint(lead1, size: 3f, color: _green); // the better one should always be green

if(leads == 2) drawPoint(lead2, size: 3f, color: Color.red); // extra one comes up when target is faster

}

}

Code (csharp):

static void swap(ref Vector2 a, ref Vector2 b) { var t = a; a = b; b = t; }

We can now determine the angle of the turret and visualize the metered trajectories. Each notch represents 1 second (or whatever time unit) of traveling time. The two trajectories will always have the same amount of notches. The whole point of this solver was to pinpoint the exact location where this quality holds true.

Code (csharp):

void OnDrawGizmos() {

// ... whatever we had before ...

var turretDir = leads == 0? V2NaN : norm(lead1 - turretPos);

if(_showVectors && !isNaN(turretDir)) {

drawArrowSegment(turretPos, turretPos + _projectileVel * turretDir, _blue, t: 1f, w: .75f, thickness: 2f);

}

if(_showPaths) {

if(leads == 0) {

drawSegment(targetPos, targetPos + 5f * _targetVel * targetDir, color: _rorange, thickness: 1f);

} else if(leads == 1) {

drawMeteredSegment(turretPos, lead1, _projectileVel, color: _blue, thickness: 1f);

drawMeteredSegment(targetPos, lead1, _targetVel, color: _rorange, thickness: 1f);

} else {

drawMeteredSegment(targetPos, lead2, _targetVel, color: _rorange, thickness: 1f);

drawMeteredSegment(turretPos, lead1, _projectileVel, color: _blue, thickness: 1f);

drawMeteredSegment(turretPos, lead2, _projectileVel, color: _blue, thickness: 1f);

}

}

}

Code (csharp):

void drawMeteredSegment(Vector2 a, Vector2 b, float meter, float w = .333f, Color? color = null, float thickness = 2f) {

drawSegment(a, b, color, thickness);

var delta = b - a;

var mag = magOf(delta);

var dir = delta / mag;

var pd = w * _gizmoScale * perp(dir);

for(var n = 0f; n < mag; n += meter) {

var mc = a + n * dir;

drawSegment(mc - pd, mc + pd, thickness: thickness);

}

}

And that's it. Does it work?

Part VIII - Hacking The Inspector
Though the core features are now complete, I wanted to round up this tool with some more 'quality of life'. For example, showing some more helper geometry (that emerged from chapter V) as well as the 'time of impact' and 'angle of fire'. But I also really didn't want to make a custom inspector, that's an overkill, the default inspector is fine. So is there a middle ground?

Well, yes and no.

For the helper geometry I wanted simply to add another checkbox to the inspector, i.e. 'Show Helpers', but because this checkbox was in the same pipeline as 'Show Tangents,' this presented a UX problem: toggling 'Show Tangents' off would implicitly turn helpers off (even though the checkbox is on), but this isn't communicated clearly. So I wanted to make this dependency visually communicated through the inspector UI. Easier said than done.

So let's add these helpers, then we'll think about the UI. For example, we can indent the label slightly, that's something.

Place this below _showTangents declaration

Code (csharp):

[SerializeField] private bool _showHelpers;

Then we can modify our
exploreHomotheticTangencies
method to internally support another bool argument. It's called from the
OnDrawGizmos
anyway, and that's the whole requirement to let it draw gizmos in the editor.

Code (csharp):

// check the last argument

bool exploreHomotheticTangencies(int type, int index, ref Vector2 c1, float r1, ref Vector2 c2, float r2, out Vector2 t1, out Vector2 t2, bool visualize = false) {

...

var tr = sqrt(dsqr) * .5f; // radius of the third circle

if(visualize) { // the extra circles are worth checking out

drawCircle(tc, tr, color: Color.black, thickness: 1f);

drawCircle(c2, r, color: Color.black, thickness: 1f);

}

...

// pick a point according to index

var p = index == 0? p1 : p2;

if(visualize) drawPoint(p, color: Color.cyan); // we can also show this point p

...

}

In the
OnDrawGizmos
method, just pass in
_showHelpers
as the last argument. Now we can see the intermediate geometry from chapter V.

Change this line accordingly

Code (csharp):

[SerializeField] [Indented] private bool _showHelpers;

Oh if this would only work, right?
Let's do something funky. At the very end of the file (after
}
), add the following code

Code (csharp):

#if UNITY_EDITOR

[AttributeUsage(AttributeTargets.Field)]

public class IndentedAttribute : PropertyAttribute { }

#endif

The attribute now works. Let's make Unity react to it.
Add this code below the attribute. (But keep it all inside the
#
directive block.)

Code (csharp):

[CustomPropertyDrawer(typeof(IndentedAttribute))]

public class IndentedFieldDrawer : PropertyDrawer {

public override void OnGUI(Rect position, SerializedProperty property, GUIContent label) {

var saved = EditorGUI.indentLevel;

EditorGUI.indentLevel++;

EditorGUI.PropertyField(position, property, label);

EditorGUI.indentLevel = saved;

}

}

Next up, we can work around the inspector, without having to recreate all the stuff we already have going on. We can just add stuff to the beginning and append some stuff to the end of it. For example we can add a warning when the two objects aren't set, as well as some new read-only fields to show the 'Time of impact' etc.

Add this code

Code (csharp):

[CustomEditor(typeof(TargetLeading2DVis))]

public class TargetLeading2DVisEditor : Editor {

public override void OnInspectorGUI() {

EditorGUILayout.HelpBox("Drag the objects into corresponding fields", MessageType.Warning, wide: true);

base.OnInspectorGUI(); // this will re-enact the default inspector

}

}

This works, but is completely static. It should show up only when required.
We can add IsReady method to our MonoBehaviour class.

Code (csharp):

public bool IsReady() => !(_turret == null || _target == null);

Now OnDrawGizmos can start with

Code (csharp):

if(!IsReady()) return;

The editor code can interrogate this as well

Code (csharp):

CustomEditor(typeof(TargetLeading2DVis))]

public class TargetLeading2DVisEditor : Editor {

public override void OnInspectorGUI() {

var target = this.target as TargetLeading2DVis;

if(!target.IsReady())

EditorGUILayout.HelpBox("Drag the objects into corresponding fields", MessageType.Warning, wide: true);

base.OnInspectorGUI();

}

}

That's better. Similarly we can attach new text fields that are a) non-serialized, b) behaving as read-only. Here's how.

Code (csharp):

CustomEditor(typeof(TargetLeading2DVis))]

public class TargetLeading2DVisEditor : Editor {

public override void OnInspectorGUI() {

var target = this.target as TargetLeading2DVis;

if(!target.IsReady())

EditorGUILayout.HelpBox("Drag the objects into corresponding fields", MessageType.Warning, wide: true);

base.OnInspectorGUI();

EditorGUILayout.Space();

GUILayout.Label("Impact", EditorStyles.boldLabel);

var saved = GUI.enabled;

GUI.enabled = false;

EditorGUILayout.TextField("Time of Impact", target.GetInfoString1());

EditorGUILayout.TextField("Angle of Fire", target.GetInfoString2());

GUI.enabled = saved;

}

}

Try it by adding GetInfoString1 and GetInfoString2 methods to MonoBehaviour class.

Code (csharp):

public string GetInfoString1() => "15 seconds";

public string GetInfoString2() => "Who wants to know?";

Obviously this is a bit hardcoded and won't change much, so let's fix this by doing.

Code (csharp):

static string _infoString1, _infoString2;

public string GetInfoString1() => _infoString1;

public string GetInfoString2() => _infoString2;

We can now modify these strings somewhere in OnDrawGizmos, and it'll reflect.
Here's what I did

Code (csharp):

if(leads == 0) {

if(_showPaths) {

drawSegment(targetPos, targetPos + 5f * _targetVel * targetDir, color: _rorange, thickness: 1f);

}

_infoString1 = "n/a";

_infoString2 = "n/a";

} else {

if(leads < 2) {

if(_showPaths) {

drawMeteredSegment(turretPos, lead1, _projectileVel, color: _blue, thickness: 1f);

drawMeteredSegment(targetPos, lead1, _targetVel, color: _rorange, thickness: 1f);

}

var d1 = lead1 - turretPos;

_infoString1 = $"{magOf(d1) / _projectileVel:F1} s";

_infoString2 = $"{angleOf(d1) * RAD2DEG:F1}°";

} else {

if(_showPaths) {

drawMeteredSegment(targetPos, lead2, _targetVel, color: _rorange, thickness: 1f);

drawMeteredSegment(turretPos, lead1, _projectileVel, color: _blue, thickness: 1f);

drawMeteredSegment(turretPos, lead2, _projectileVel, color: _blue, thickness: 1f);

}

var d1 = lead1 - turretPos;

var d2 = lead2 - turretPos;

_infoString1 = $"{magOf(d1) / _projectileVel:F1} s / {magOf(d2) / _projectileVel:F1} s";

_infoString2 = $"{angleOf(d1) * RAD2DEG:F1}° / {angleOf(d2) * RAD2DEG:F1}°";

}

}

In 2D this is simply a good ol' arc tan, taking the vector, dividing its components, and spitting out the angle in radians.

Code (csharp):

static float angleOf(Vector2 v) => atan2(v.y, v.x);

static float atan2(float y, float x) => MathF.Atan2(y, x);

To understand this conversion here's the unit circle again

I've wrote this a couple of times before -- the reason why it's called Atan2 is because it's a more advanced version of the regular Atan. It's still 40 years old, don't get me wrong, but the OG, purely mathematical function would take a single value, like Acos or Asin would, and compute back the inverse tangent. However, because the value is usually obtained by dividing y/x (opposite over adjacent, 'member? the zero is on the right), the sign information would get lost (i.e. two negatives would cancel out and so on), and so people would regularly make their own version of Atan that would take the signs into account, which is how we can tell the quadrants apart. Otherwise it would always return an angle between 0 and Pi/2 (90 degrees). So this is what Atan2 does (and does it optimally), and why you need to supply both values independently in the y, x order.

I've seen very intelligent and educated people getting readily confused over this, not understanding the point or appreciating the history behind it, so it's worth reiterating.

Btw, the result is in radians, so we need to convert this to degrees, by multiplying it with DEG2RAD.
This is defined as

Code (csharp):

static readonly float RAD2DEG = 360f / TAU;

Now to test this, make sure to lock the inspector (with a little padlock icon on top of it), or else it'll switch away when you try moving the objects. Once you try moving them, you'll notice that nothing changes. To refresh the fields, you need to move your mouse back over the inspector, which is frankly bo-ring.

Add this to TargetLeading2DVisEditor class

Code (csharp):

public override bool RequiresConstantRepaint() => true;

Voila.
Normally you don't work like this, you really want your MonoBehaviour (MB) and editor code split, each in a separate file. You then place the editor script in a folder called 'Editor' and it will be excluded from the final build. That way you don't need to use
#
directives, among other things, however I 1) already made this MB to work exclusively in the editor, 2) badly wanted to have everything in just one file.
Part IX - Bonus Observation
Finally, let's add an option to pick the particular set of drawn tangents. It's not much and I promise that this will reveal something new.

Instead of having just on/off for
_showTangents
, we can add a drop-down selector with the following options

Code (csharp):

[SerializeField] private SelectedTangents _showTangents;

// somewhere below

enum SelectedTangents {

None = 0,

Internal = 1,

External = 2,

All = 3

}

We have everything else already set in place, but this changes our logic slightly. Namely this counter

Code (csharp):

for(int type = EXTERNAL; type < 2; type++) { ... }

If we change this to

Code (csharp):

for(int type = typeStart; type <= typeEnd; type++) { ... }

We have to analyze this table of three possible outcomes

Code (csharp):

typeStart typeEnd

=Internal (1) 1 1

=External (2) 0 0

=All (3) 0 1

So let's see, when value is 1, typeStart appears to be 1, otherwise it's 0.
And when value is 3, typeEnd appears to be 1, otherwise it's the same as typeStart.

Code (csharp):

if(_showTangents != SelectedTangents.None) {

var typeStart = (int)_showTangents == 1? 1 : 0;

var typeEnd = (int)_showTangents == 3? 1 : typeStart;

for(int type = typeStart; type <= typeEnd; type++) {

for(int index = 0; index < 2; index++) {

if(exploreHomotheticTangencies(type, index, ref turretPos, _projectileVel, ref targetPos, _targetVel, out var t1, out var t2, _showHelpers))

drawSegment(t1, t2, color: Color.white, thickness: 1f);

}

}

}

Inside
exploreHomotheticTangencies
we can now add one more helper drawing, and that's the original segment that we find before we offset it.

Code (csharp):

...

// pick a point according to index

var p = index == 0? p1 : p2;

if(visualize) {

drawSegment(c1, p, color: Color.cyan, thickness: 1f); // this is new

drawPoint(p, color: Color.cyan);

}

If you try this out, and select 'Internal', you'll see that we have already solved point-circle tangencies, only slightly differently.

<image: screenshot>

In fact, we can now strip this method down to its core and introduce our own distilled, high-level version of
pointCircleTangency
. How? Let's go over this step by step.

Code (csharp):

bool exploreHomotheticTangencies(int type, int index, ref Vector2 c1, float r1, ref Vector2 c2, float r2, out Vector2 t1, out Vector2 t2, bool visualize = false) {

var dsqr = sqrMagOf(c2 - c1); // squared distance between circle centers

var rsum = r1 + r2; // sum of two radii

var rdif = abs(r2 - r1); // difference between radii

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = type == EXTERNAL? dsqr >= sqr(rdif) // circles at least partially overlap

: dsqr > sqr(rsum); // circles are certainly spaced apart

if(hasTangents) {

// special external case when circles partially overlap

if(type == EXTERNAL && !isZero(rdif)) {

if(dsqr <= sqr(rsum)) {

var he = homotheticCenter(ref c1, r1, ref c2, -r2);

pointCircleTangency(he, c1, r1, out var t11, out var t21);

pointCircleTangency(he, c2, r2, out var t12, out var t22);

if(index == 0) {

t1 = t11;

t2 = t12;

return true;

}

t1 = t21;

t2 = t22;

return true;

}

}

// the usual case when circles are spaced apart

var r = type == EXTERNAL? rdif : rsum; // modified radius of the 2nd circle

var tc = avg(c1, c2); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

if(visualize) {

drawCircle(tc, tr, color: Color.black, thickness: 1f);

drawCircle(c2, r, color: Color.black, thickness: 1f);

}

Vector2 p1, p2;

if(type == EXTERNAL && isZero(rdif)) {

p2 = p1 = c2; // makes sure the external tangents are computed as parallel

} else {

circleCircle(tc, tr, c2, r, out p1, out p2);

}

// pick a point according to index

var p = index == 0? p1 : p2;

if(visualize) {

drawSegment(c1, p, color: Color.cyan, thickness: 1f);

drawPoint(p, color: Color.cyan);

}

// sign of the result is determined by both type and index

var s = (type == EXTERNAL? sgnstep(r2 - r1) : -1) * (index == 0? 1 : -1);

// offset

var o = r1 * norm(perp(c1 - p)) * s;

// final points

t1 = c1 + o;

t2 = p + o;

return true;

}

return false;

}

1. Remove visualizations and everything that was EXTERNAL-related

Code (csharp):

bool pointCircleTangency(int type, int index, ref Vector2 c1, float r1, ref Vector2 c2, float r2, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c2 - c1); // squared distance between circle centers

var rsum = r1 + r2; // sum of two radii

var rdif = abs(r2 - r1); // difference between radii

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = dsqr > sqr(rsum);

if(hasTangents) {

var r = rsum;

var tc = avg(c1, c2); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

circleCircle(tc, tr, c2, r, out var p1, out var p2);

// pick a point according to index

var p = index == 0? p1 : p2;

// sign of the result

var s = index != 0? 1 : -1;

// offset

var o = r1 * norm(perp(c1 - p)) * s;

// final points

t1 = c1 + o;

t2 = p + o;

return true;

}

return false;

}

2. Imagine if circle 1 had a radius of 0, so it shrunk to a point. Instead of c1 and r1 we now only have p (rename the old p to oldp). c2 and r2 become c and r, respectively, and dsqr becomes a distance between p and c, thus rsum and rdif are both r. Remove type and index from the arguments.

Code (csharp):

bool pointCircleTangency(Vector2 p, Vector2 c, float r2, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c - p);

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = dsqr > sqr(r);

if(hasTangents) {

var tc = avg(p, c); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

circleCircle(tc, tr, c, r, out var p1, out var p2);

// it gets somewhat confusing after this point, so let's leave it for now

// pick a point according to index

var oldp = index == 0? p1 : p2;

// sign of the result

var s = index != 0? 1 : -1;

// offset

var o = r1 * norm(perp(c1 - oldp)) * s;

// final points

t1 = c1 + o;

t2 = oldp + o;

return true;

}

return false;

}

3. The old method was computing the start and end points for each tangent segment, but this method does only the end points (the starting point is p), and it does two of them, which is where the signs have gone. So we don't need to select a point, because we need them both, and likewise we don't need the offset, because our circle 1 has a radius of 0. And then you realize: circleCircle does the job already.

Code (csharp):

bool pointCircleTangency(Vector2 p, Vector2 c, float r2, out Vector2 t1, out Vector2 t2) {

var dsqr = sqrMagOf(c - p);

t1 = V2NaN;

t2 = V2NaN;

var hasTangents = dsqr > sqr(r);

if(hasTangents) {

var tc = avg(p, c); // center of the third circle

var tr = sqrt(dsqr) * .5f; // radius of the third circle

circleCircle(tc, tr, c, r, out var p1, out var p2);

return true;

}

return false;

}

After cleaning this up and rearranging, behold.

Code (csharp):

bool pointCircleTangency(Vector2 p, Vector2 c, float r, out Vector2 t1, out Vector2 t2) {

t1 = V2NaN; t2 = V2NaN;

var dsqr = sqrMagOf(c - p);

if(dsqr <= sqr(r)) return false; // point is contained by the circle

circleCircle(avg(p, c), sqrt(dsqr) * .5f, c, r, out t1, out t2);

return true;

}

Geez, no wonder
pointCircleTangency
and
circleCircle
looked alike

And that's the end of the visualizer and this tutorial.

----
You will find the full guide to a stripped down implementation, as well as the download link for the full source code (visualizer + the actual solution) in the next post.

If you've read this far, consider liking the post. Writing this down took me about four times as much time than the code itself. It's crazy. But I believe this to be the ultimate learning experience, so it's worth it.

Some of my other tutorials / essays / code:
Logical truths cheat sheet and table generator
Library of Vector2/Vector3 distance comparators [source]
How to hook up functions from the inspector
How to build and use a custom enum-like solution that auto-serializes into strings
An essay on orbital body mechanics in 2D
How to implement math for the 2D ellipses with all kinds of geometry involved
How to decompose quaternion rotations and produce an auto-aiming turret in 3D
A short guide to bitmasks, bitwise values, and flags
Intersecting lines in 2D using homogeneous coordinates
Simple Scene View Panel for buttons and readouts
Bare Quaternions #1, #2

orionsyndrome · May 4, 2023

This post is yet to be fleshed out.
In the meantime, you can download the above source code.

TargetLeading2DVis.zip (v1.0) [download]

Bunny83 · May 3, 2023

Wow, what a post Though I think it's kinda hard to follow. You have too many utility methods that are scattered around in your post. I guess you want to add them to your second post in a more condensed code snippet?

Note about ten years ago I posted a general interception course calculator method on UA. It actually has a webGL build of an example application that compares the "trivial lead" against the actual, correct calculation. This has been a UnityWebPlayer build in the past but I recently found the code somewhere on my HDD and "ported" it to WebGL

As long as you don't change the enemy speed after shooting bullets, with the proper calculations you should get a 100% hit rate. The shoot button will deactivate when the calculated hit point is behind the "wrap point" since the enemy will reset / wrap around at this point. If the interceptor / bullet speed is not several magnitudes larger than the target speed, you will see that the simple prediction is quite bad. The correct calculation even works when the bullet speed is slower than the target, but only when you have room for a head start of course^^.

orionsyndrome · May 12, 2023

Bunny83 said: ↑

I guess you want to add them to your second post in a more condensed code snippet?
Click to expand...

Yes they are condensed in the final code, and pretty much non-existent in the distilled production code. I thought it would be better to follow the spine of the story and only introduce them as they appear, hence the spoiler buttons. Otherwise it's easy to get lost in the tangents (pun intended).

edit: I have written this similar to how Jasper (catlike coding) writes his tutorials, tangents are hidden behind spoiler buttons, but always follow the main story.

Bunny83 said: ↑

Note about ten years ago I posted a general interception course calculator method on UA. It actually has a webGL build of an example application that compares the "trivial lead" against the actual, correct calculation. This has been a UnityWebPlayer build in the past but I recently found the code somewhere on my HDD and "ported" it to WebGL

As long as you don't change the enemy speed after shooting bullets, with the proper calculations you should get a 100% hit rate.
Click to expand...

Yess! This is great! Bravo for the comparison.
I especially like the first-person view. I'm a sucker for the old-school machinegun / ballistic shooters where you defend an island and soldiers, ships and planes all try to get you.

orionsyndrome · May 12, 2023

I'm happy to say that I've managed to produce a Burst-compiled version of this in full 3D.

Preliminary tests on my jalopy suggest that for a frame budget of 4 milliseconds (250 FPS) one can compute around 60K turrets each predicting its own target, in every frame, which is an astounding result.

I think I'll merge this solution with my turret behavior from before, it's a match made in heaven. I wanted to add 2nd order dynamics for the turret motion, but now I'm thinking about doing all of this, and making a very robust asset out of it.

I am still to finish the 2nd post for the 2D implementation.

Search Unity

Unity ID

Useful Searches

Showcase Target Leading in 2D // unorthodox solution and full source

orionsyndrome

orionsyndrome

Bunny83

orionsyndrome

orionsyndrome