Sunday, January 2, 2011

Starship Builder - Idea & Thruster Algorithm

I have an idea for a game that I've been wanting to make ever since I was a kid. I've actually tried to make it several times as a pen & paper tabletop game, but it's just too complex of an idea for pen & paper. It's only recently that I've become a good enough programmer to tackle the idea as a computer game, and so I've been thinking more about it lately.

The core idea of the game is that the player designs and builds a space ship on a 2D grid. Think SimCity, but instead of placing buildings and roads onto a grid, you're placing corridors, weapons, engines, crew's quarters, and other ship systems onto the grid. Unlike many games, which only let you place systems onto pre-assigned "hardpoints" of the ship's hull, my game will allow the player to completely customize the ship's size, shape, and the location of internal systems.

Where you place engines, weapons, and other systems on your ship will really matter. Engine physics will be accurate, so that you have to actually think about exactly where the best place to put that thruster will be. Weapon damage will be localized, so that weapon fire from an enemy ship will strike a particular part of a ship and damage whatever systems are there. You'll have to think about what systems you want to put near the outside of your ship, and what systems you'll want to protect deeper inside.

Inside the ship will be dozens, possibly hundreds of crew members scurrying about from one system to another, keeping everything operational. You'll have to think about the corridor layout inside your ship so that your crew can easily travel from one system to another.

The key to this idea is that the player has complete flexibility and customization when designing ships. The only game I know of that even barely resembles this is Captain Forever. But Captain Forever is a fairly simple arcade game, whereas my game, if I ever make it, will be much more of a tactical strategy and simulation game.

I actually just threw together a very rough prototype to prove to myself that I could solve what I think will be the hardest programming problem to solve: that is, how to make a ship realistically fly to a desired location no matter where the player places the ship's engines and no matter how many and what size they are. Future Walt laughs at his past-self's naiveté. This was far from the hardest problem to solve. You can try out this prototype right here.


The algorithm I came up with actually seems to work pretty well. Sure, it could use a lot of tweaking and some higher-level intelligence, but basically I think it proves that I can make it work within a larger game.

The basic algorithm works like this, assuming you have a number of thrusters that each can be "activated" from between 0.0 and 1.0:
  1. Calculate a desired force to exert on the ship (X, Y, Rotational) based on the desired location and/or velocity.
  2. Build a list of all the thrusters on the ship and sort it by how much more closely a change in the thruster's activation can bring the ship's current force to its desired force.
  3. Iterate through each thruster in that sorted list, setting its activation to the value that brings the ship's current force as close as possible to the desired force.
  4. Repeat steps 2-3 at least a few times so that the thrusters can "approach" and eventually "settle in" to a near-optimal set of activation levels.
This whole algorithm is run once every frame to constantly adjust the thruster's activation levels.