I've been playing Spore recently. It's an interesting game. One of the criticisms is that the physical characteristics of the things you do in the editor don't make a difference to gameplay. For example, having wide legs or narrow legs or four legs or six legs doesn't affect your speed. Only the +Speed items affect speed. Only in the Cell stage does placement matter. I read some of their reasoning behind this design and I agree with it. In a game where creativity is more important than realism, simplifying that aspect of the game will encourage people to be more creative in their designs. I know that if the number of legs actually mattered for gameplay, I wouldn't have made my creature hop around on one leg.

Although I think they made the right decision for Spore, I was inspired to explore the alternative: something where the way you design your creature matters a great deal. To fit in with the 2d top-down theme I've been using (see the space station miniproject), I'm using spaceships instead of creatures.

The main idea for this miniproject is that you'd design the ship, and then the “AI” would learn how to fly the ship you designed. For example, let's consider the following ship with four thrusters:

Diagram of Test Ship 1 and its thrusters

If you fire either thruster A or B, you'd end up rotating. But if you fire both at once, you would go forwards. Given a set of thrusters (location on the ship, direction they fire, and their maximum power), I can calculate the effect on the ship (acceleration and rotational acceleration). Initially I was calculating the force to be only what was transmitted along the A→O vector, but later I realized that because the ship is rigid, the entire force gets transmitted to the entire ship, and is independent of the location of the thruster. Since thruster A fires in direction (0, +2), the force on the ship is (0, -2). Rotation is slightly trickier, as we need to calculate torque, and take into account the rotational moment of inertia. For now I'm assuming the mass and moment of inertia are constants, but later I'll compute these based on the characteristics of the ship. The torque does take into account the position of the thruster, and we have to compute the cross product of the A→O vector (-2, 4) and the force vector (0, -2).

The forward mapping from thrusters to forces turns out to be a matrix multiplication. Each thruster is a column and each effect on the ship is a row. Doing this for each of the thrusters, we get the thruster matrix M mapping thrusters to force and torque:

M:ABCD
Fx 0 0 -0.5 0.5
Fy-2 -2 0.5 0.5
Tq 10 -10 1.25-1.25

Given a thruster configuration vector T, M∙T gives us the forces acting on the ship.

The real problem though is reversing that mapping. The player presses a key to move forwards, and I need to figure out which combination of thrusters best accelerates the ship forwards. What value of T leads to M*T being close to [ 0 1 0 ]?

The simplest approach is brute force. So I started with that first. I generated lots of random inputs and calculated their outputs. Then when I needed some particular output, I scanned them all and picked the input that most closely generated that output. Over multiple simulation cycles, any errors would be corrected by picking different input/output pairs. I could make this even more stable by iterating within a single simulation cycle, and interpolating among the results.

This approach worked reasonably well!

The ship behavior was interesting. My first test ship (the one I'm using for these examples) moved reasonably well forwards and backwards, and could rotate well, but it couldn't slide left and right quickly.

My second ship is a variant of the first. When moving forwards it can rotate well, but if you're stationary or going backwards the rotation is limited. When you fly it you'll see that if you want to rotate, you need to move forwards at the same time. Here's what it looks like:

Closeup of Test Ship 2

My third ship had reasonable movement, and rather asymmetric: it could rotate and slide left at the same time, or rotate and slide right at the same time, but it was much slower if you rotated left while sliding right or vice versa. It looks a little different from the first two, but right now that makes no difference in the physics:

Closeup of Test Ship 3

My fourth ship is a damaged version of the third ship, to see if having inoperable thrusters would make for interesting gameplay. Going forwards would also make you spin around in circles. It was fun to play with in the prototype but I'm not convinced it'd be fun in a game. You can see why it's unstable:

Closeup of Test Ship 4

My fifth test ship could rotate very quickly but couldn't go backwards at all (at least until I fixed a bug in the physics calculations), so you'd turn around and go forwards in order to stop moving. This might be a ship you can't build until later stages of the game, when you've gained building points or parts or money. Just look at how much power it has:

Closeup of Test Ship 5

At this point the prototype made me think there was something potentially fun for a game. You could design your own ship and make tradeoffs. The game “AI” would learn how to map your keys to thruster movements, and the player would then have to learn best to use the controls for navigation and combat. For example, having to turn a ship around to stop is unusual but you might design a ship that way if you could get lightning-quick rotation in return. You might design different ships for different levels. Or you might learn how to play a ship so well that you don't want to switch to something else with different characteristics.

I knew the ships were all different in their behaviors but I didn't understand what their limits were. So my next step was to try to understand the flight characteristics of the ships. That's for the next post.

Labels: , ,

4 comments:

Bram wrote at January 11, 2009 3:43 PM

I like these ideas.
Before you have AI steer the ship for you,
it may be interesting to have the player
fly it manually first.
After the player buys an expensive ship computer,
the AI would help you fly it.
But ship/thruster design should make some good game-play.

zzzzrrr wrote at May 02, 2009 9:20 PM

Your ship models are awesome. Are you using bitmap or vector graphics? My OpenMelee ships could definitely use some help, although at this point I'm inclined to stick with vector drawing if possible!

Amit wrote at May 02, 2009 11:21 PM

Hi Mason! The ships are vector graphics, with Flash's BitmapFilters (bevel, shadow, glow, blur). You can get one of the above ships in than 15 lines of code; I'm happy to send it to you or anyone else who wants it.

sdfgeoff wrote at May 16, 2021 6:02 AM

After 11 years this is still a very interesting blog post!

But for those who find there way here, there is a solution to the inverse problem other than brute force: This is an inverse kinematics problem and can be solved as such. One of these solutions is to use the jacobian method. Because all the engines are independant, it turns out that ... the matrix 'M' (from the original post) is our jacobian. So we can iteratively apply it with:

thruster_output_guess = zeros()
inv_m = pseudo_inverse(M)
desired_forces = [...]
for i in range(100)
force_error = desired_forces - compute_force(thruster_output_guess)
thruster_output_guess += inv_m * force_error

I implemented the 'thrusters don't thrust backwards' constraint by clamping the 'thruster output_guess' variable. This increases the number of iterations, but didn't affect convergence.

Also, you can solve for both linear and angular forces at tye same time by having 'desired_forces' be a 6-vec of [force, torque]. The matrix 'M' then becomes dimension 6xnum_thrusters etc.

I plan to do a full writeup of this somewhere at some point....