Considering we're in a 3D system of coordinates:
Question: on what vector does our ship need to shoot its bullet, such that the asteroid is hit?
My attempt so far: find a point C such that:
- distance(A,C) / speed_of(bullet) = distance(B,C) / speed_of(asteroid)
- point C is on the asteroid's known vector
And I'm stuck here.
That's a good start, but point 2 can be made a bit more precise. Let's say the asteroid starts at $\mathrm{B}_0$ at time $0$ and has constant velocity $\dot{\mathrm{B}}$. Then its position at time $t$ is $$ \mathbf{B}(t) = \mathbf{B}_0 + t \dot{\mathbf{B}}. \tag{1} $$ Your $\mathbf{C}$ is just some point on this line, which we would know if only we knew $t_\mathrm{hit}$, the time at which the bullet hits the asteriod: $$ \mathbf{C} = \mathbf{B}(t_\mathrm{hit}). \tag{2} $$
But how to find $t_\mathrm{hit}$? Well, we can work form the perspective of the bullet, whose position I'll denote with $\mathbf{A}(t)$ (no need to worry about the ship, since it's not moving). As before, we have $$ \mathbf{A}(t) = \mathbf{A}_0 + t \dot{\mathbf{A}}, \tag{3} $$ except here $\dot{\mathbf{A}}$ is an unknown vector constant. Actually, it's not entirely unknown, since it must satisfy $$ v^2 = \dot{\mathbf{A}} \cdot \dot{\mathbf{A}} = \dot{A}_x^2 + \dot{A}_y^2 + \dot{A}_z^2, \tag{4} $$ where $v$ is the fixed bullet speed. Now again the impact point must occur along the bullet's trajectory, and after the same elapsed time: $$ \mathbf{C} = \mathbf{A}(t_\mathrm{hit}). \tag{5} $$
Equations (1), (2), (3), and (5) combine to form $$ \mathbf{B}_0 + t_\mathrm{hit} \dot{\mathbf{B}} = \mathbf{A}_0 + t_\mathrm{hit} \dot{\mathbf{A}}. \tag{6} $$ Then (4) and (6) form a system of 4 scalar equations in 4 unknowns ($t_\mathrm{hit}$, $\dot{A}_x$, $\dot{A}_y$, and $\dot{A}_z$) and so can be solved uniquely.
(Actually there might be two or zero solutions, depending on the actual values. Zero solutions means your bullet is too slow to ever catch up. Two solutions probably means one corresponds to negative $t_\mathrm{hit}$, as though the bullet went from the asteroid in the past to the ship in the present. Though it might also mean there are two chances to hit the asteroid.)
For a moving ship, your bullet's velocity in these coordinates, $\dot{\mathbf{A}}^\mathrm{bullet}$, is given by the sum of the known ship's velocity when the bullet is fired, say $\dot{\mathbf{A}}^\mathrm{ship}$, and the to-be-found velocity of the bullet with respect to the ship, $\dot{\mathbf{A}}^\mathrm{relative}$. To work with this, just solve for $\dot{\mathbf{A}}^\mathrm{bullet}$ (aka $\dot{\mathbf{A}}$) as above, and then calculate $$ \dot{\mathbf{A}}^\mathrm{relative} = \dot{\mathbf{A}}^\mathrm{bullet} - \dot{\mathbf{A}}^\mathrm{ship}. $$
You have to turn this into a 2D problem. To find 3 unit vectors describing a local 3D coordinate system where the planar problem is along the local $\hat{i}$ and $\hat{j}$ axes, with the plane perpendicular $\hat{k}$. Subscript A denotes the asteroid, and B the bullet, with $\vec{r}$ positions, $\vec{e}$ directions and $v$ speeds. The notation is reverse from the OP because A=asteroid, B=bullet is easier to remember.
Suppose you shoot an infinite number of virtual bullets at some speed $v$ in all possible directions. At some time $t$ in the future, these virtual bullets will lie on the surface of a sphere with radius $vt$. This spherical surface obviously grows with time. Suppose that at time $t$, the moving asteroid crosses this sphere. This intersection tells you where you want to shoot.
The ship is at point $A$ at all times, and the asteroid is at point $B$ initially and moves with some velocity $V$. The displacement vector from the ship to the asteroid is $\vec B - \vec A + \vec V t$. Denoting $\vec B - \vec A$ as $d_0 \hat u$ and $\vec V$ as $V\hat v$, the distance between the ship and the asteroid is given by $d(t)^2 = {d_0}^2 + 2d_0V \hat u \cdot \hat v t + V^2t^2$.
Let $\phi$ be the angle between the initial displacement vector from the spaceship to the asteroid and the asteroid's velocity vector. In terms of the above, $\cos \phi = \hat u \cdot \hat v$. This gives an alternate way to express the distance to the asteroid: $d(t)^2 = {d_0}^2 + 2d_0V \cos(\phi)\,t + V^2t^2$.
We're looking for the point in time where this distance is equal to $v^2t^2$, where $v$ is the speed at which a bullet is shot from the spaceship. This results in the quadratic equation $$(V^2-v^2)t^2 + 2d_0V \cos(\phi)\, t + {d_0}^2 = 0$$ As is the case with all quadratic equations, this has two solutions: $$\begin{aligned} t &= \frac{-d_0V \cos\phi \pm \sqrt{d_0^2V^2 \cos^2\phi - {d_0}^2(V^2-v^2)}}{V^2-v^2} \\ &= \frac{d_0}{V^2-v^2} \left(-V \cos\phi \pm \sqrt{v^2 - V^2 (1-\cos^2\phi)}\right) \end{aligned}$$ There are no real solutions if the radical $v^2 - V^2 (1-\cos^2\phi)$ is negative. The two solutions are identical (a double root) if the radical is zero. There are two distinct real roots if the radical is positive. You can't hit the asteroid if there are no real solutions or if both real solutions are negative. Note that a negative real solution represents the asteroid having shot a bullet at your spacecraft at that time in the past, with that bullet hitting your spacecraft right now.
If there is a positive solution $t$ to the above expression quadratic equation, this tells you where to aim your bullet. Simply aim at the point where the asteroid will be at that time.
The above assumes the asteroid is moving at a constant velocity and the spacecraft is stationary. That represents an asteroid field in empty space, far from any gravitating body. Asteroid fields are a side effect of star formation and the formation of a large planet (e.g. Jupiter) that prevents those asteroids themselves from forming a planet. In other words, asteroids orbit a star and are perturbed by one or more jovian planets. The constant velocity solution described above does not apply. If you can ignore the perturbations by the jovian planets you essentially have Lambert's problem, with additional constraints. This wikipedia article summarizes Lambert's problem. This nice little pdf from the Colorado Center for Astrodynamics Research (CCAR) describes the standard algorithm for solving Lambert's problem.
