Spaceship flyer

 from Red Blob Games
8 Nov 2021

Project from 2009[1]

Click to focus

The spaceship is:

Spaceship design

In 2009 I had done a monte-carlo approach where I tried many different thruster configurations \( \begin{bmatrix} t_{1} & t_{2} & t_{3} & t_{4} \end{bmatrix} \) and picked something close. But my gut feeling was that it was a linear programming problem. This time, in 2021, I tried solving it as a linear programming problem but I ran into an issue: I’m looking for something that has the correct angle in output space, and among solutions with that angle, I want to find the one that has the most movement, and secondarily the least fuel. But I’m not sure how to make that a linear programming problem! It might be that I need to convert that angle into a normal vector and then add a constraint that we can’t move off the correct plane. I’m still thinking about that.

I’m visualizing the thruster capabilities like this:

Another option is to treat this as a simpler problem, a linear system of equations that’s underconstrained. However there too I’m not quite sure how to deal with the angle problem.

\[ \begin{bmatrix} u_{1} & u_{2} & u_{3} & u_{4} \\ v_{1} & v_{2} & v_{3} & v_{4} \\ r_{1} & r_{2} & r_{3} & r_{4} \\ \end{bmatrix} \times \begin{bmatrix} t_{1} \\ t_{2} \\ t_{3} \\ t_{4} \end{bmatrix} = \begin{bmatrix} u \\ v \\ r \end{bmatrix} \]

Maybe I can pick a normalized version of the angle as the desired output, and then I can rescale that until I hit a limit with the thrusters. I’m reading this lecture (pdf)[2] to learn how this math works. It looks like given my physics matrix \( P \) and my desired normalized vector \( n \) I have to solve for \( P P^{T} w = n \) and then the thrusters are \( x = P^{T} w \). That sounds… simple? The thrusters are for a normalized vector though, and I can just scale up \( x \) until one of the thrusters is 1.0. But the problem with this math is that there’s nothing ensuring the thruster values are ≥ 0. So I don’t think this that useful for my problem. Linear programming is what gives me that constraint.

Rich G suggested I might try gradient descent, as it’s more general purpose and probably can handle what I’m wanting simply. But what would I actually do here? For each thruster row \( u_{i} v_{i} r_{i} \) I can see if adding ε times that thruster gets me closer to the desired angle, and I can add more of the thrusters that get me closer?

sum_of_weights = 0
weights = [0] * thrusters.length
for t <= thrusters.length:
  weight[t] = max(0, dot(current_vec - thrusters[t], [1, 1, 1]))
  sum_of_weights += weight[t]
  // the [1, 1, 1] could be weighted higher for the parts that should be zero
for t <= thrusters.length:
current_vec += weight[t] / sum_of_weights * step_size * thrusters[t]

Gradient descent seems like overkill here because it’s a linear function! So I think I can take large step sizes. But I also kind of want to minimize fuel consumption. Does that happen automatically? I think it does if I choose one thruster each round, whichever gives me the most improvement for the least amount of fuel. But I think it doesn’t in general because one thruster may cause us to have to compensate with another, while a third thruster might’ve gotten there without needing compensation. Does that make sense? Hm. I think I should just try it and see how it goes.

In any case I think independent of which algorithm I use to choose the thrusters, I also would like to visualize the thruster capabilities, and I think the visualization I used in 2009 is probably the starting point. I need to intersect each pair of thruster configurations with a zero-plane and then I can draw those points:

for conf in configurations
  for t < thrusters.length
    let a = conf with thruster t on
    let b = conf with thruster t off
    for axis in ['au', 'av', 'aθ']
      if a[axis] * b[axis] < 0
        // signs are opposite, so there must be a mix of these where they add to 0
        mix = abs(a[axis] / (b[axis] - a[axis]))
        let newconfig = a * mix + b * (1-mix)
        // verify that newconfig[axis] is 0!!

Email me , or tweet @redblobgames, or comment: