During my week lying down I returned to a math problem I had been working on some time ago. Despite making some progress I still haven't solved it, so this entry will be a report on work in progress. Some background is in order, though.
Triplanetary board game
Triplanetary was a 1973 boardgame about flying and fighting in the inner solar system. I stumbled onto it on Board Game Geek's Elegant Simulations GeekList, and then again over at the wonderful Project Rho website (the centerpiece is Atomic Rockets). The chief attraction is its elegant Newtonian-ish movement system. It's actually pretty similar to a graph-paper race car game I played a bit as a kid, but on a hex grid instead of a rectangular one. Without acceleration, rockets continue on the same course each turn. Acceleration can come from burning fuel, or from flying near a planet, and (for simplicity) is made in whole-hex increments. A cute side effect of the rules is that there is a one-hex-radius orbit around each planet which, once entered, can be maintained indefinitely without expending fuel.
I haven't ever played one of these Newtonian space games; I don't know how fun they'd be live. I suspect you might need more turns than is typical for a board game session in order for the movement system to play out in interesting ways. As a result, you'd want to trim the turn time down to an absolute minimum. Nigel Hodge's Vector V5 game has a two-marker system that I think would probably work pretty well for tracking spacecrafts' present and future positions. Unfortunately, these sorts of games tend to pile on lots of weapon and defense systems that I'd expect would tend to lengthen turns considerably. Also, with “realism” once you're in for a penny there's a tendency to go in for a pound, and some games like Attack Vector: Tactical have added the third dimension to the fray, which I would expect to slow things down even more. Again, I haven't actually played any of these, though, so I can't really criticize.
Newtonian-movement games seem ideally suited to computer form, though; the computer takes care of all the bookwork so turns can fly by as fast as you can bang the keys. I started thinking about writing an AI for playing Triplanetary, so I could see for myself (and by myself) what's fun and what's not.
Here's the Triplanetary map, as represented in my test program. The squiggles in the middle are Asteroids; you take damage if you pass through them with a speed greater than one hex per turn. I don't usually run it with the name labels up. Currently they are placed with no regard to what they might be covering; Jupiter is under Callisto's label. Map labeling is an algorithm for another day...
Path planning in space
A key problem is creating a suitable path planning algorithm. How does a rocket get from one place to another? This has proved to be an interesting challenge and is behind the math problem I've been working on.
Essentially, this sort of thing is done all the time in typical computer games. The world can be thought of as a graph. Each node in the graph represents a state of the game; for simplicity, it usually represents just the essential state of one vehicle, and ignores the others. The edges connecting nodes represent legal moves that the vehicle can make. Creating a path involves finding a sequence of edges (moves) that goes from the current state to the desired state. Usually, you want a “best” path. Short length usually makes for a better path, and there may be other factors as well. These factors can be expressed with costs on the edges, and designing the search to find a sequence of edges with minimum total cost. The standard search algorithm for doing this is called A*, and is well-covered on the Internet.
There are some key differences that make the Triplanetary problem harder than the average game:
- State is more complicated. Most games assume the vehicle moves at low speed and can turn on a dime, so they don't count velocity as part of the state. For Triplanetary, both position and velocity are part of the state, and fuel needs to be as well. (Ships carry limited fuel, so if there are two paths that go the same place in the same amount of time, but one uses less fuel, it's better.) Because state is more complicated, the state space is correspondingly much larger. There isn't just one node in the graph per location on the map; there's a node for each combination of position, velocity, and fuel level. Since there's no upper limit on velocity, there are an infinite number of nodes per map location!
- The graph connectivity can be large. Disregarding the “overload” maneuver for the time being, there are seven legal moves a spacecraft can make: it can coast, or it can change its velocity by one hex per turn in any of the six directions. This compares favorably with a typical grid-based game, where each node connects to its eight neighbors. However, overload allows a ship to make one two-hex acceleration between repairs. This adds an additional twelve edges leaving each node, and a flag at each node indicating whether overload is available.
- It's much harder to come up with a good search heuristic. A* relies on being able to estimate for any given state how expensive it will be to reach the target state. When velocity is not part of the state, a simple distance measurement is a reasonable estimate; the idea is that the cost goes up more-or-less linearly with the distance to be traveled.
Finding a Search Heuristic
An ideal search heuristic keeps the search from examining any nodes that aren't on a best path. Of course, if you've got an ideal heuristic there is no need to search; it will infallibly tell you which way to go is best at each step. Because Triplanetary's state space and connectivity are relatively large, though, it is important to try to get as close as possible to the ideal.
To simplify the initial problem, I'm ignoring a few things:
- Fuel consumption. In theory this should be straightforward to add. It will have the effect of cutting off transitions later in the search, once the spaceship has run out of fuel and can only coast.
- Overload. Overload has the effect of greatly increasing the number of edges that must be examined at each node, so it may slow down the search and increase its memory usage. Again, though, it doesn't add anything conceptually difficult to the search.
- Obstacles. This is a usual omission from heuristics. The search space is considered to be wide-open and regular. For Triplanetary this is not a bad assumption. The asteroids will eventually cause real paths to be more expensive than the estimates, but that will not be a problem (other than causing the search to look at more nodes as it tries to get around them).
- Gravity. Gravity only affects the hexes adjacent to planets, which is a tiny fraction of the game map. This omission is a little worrying because it will make my naïve heuristic overestimate the cost when gravitational “slingshot” maneuvers are possible, but I will worry about that later. With gravity out of the picture, the only force operating on the vehicle is its own acceleration.
With these simplifications, the cost estimate will simply be the number of turns it's likely to take to get from one state to another.
I'm just about out of time so I will have to continue next week, hopefully bringing out the charts and diagrams. I'll leave you with a couple of hints as to where I'm going.
It's instructive to consider the one-dimensional problem first: given an initial position and velocity, and a desired final position and velocity, how quickly can you get there, given that your acceleration can't exceed 1? This problem turns out to have an exact, closed-form solution.
Once you've solved the one-dimensional case, it turns out you can do path planning for the race car game I mentioned earlier! It's played on square graph paper, and the X and Y accelerations are independent. (Thus, you can accelerate 40% more diagonally than you can horizontally or vertically.) This reduces the problem to two independent one-dimensional problems; whichever one takes the longest is a good estimate of how long it will take to reach the destination.
It also simplifies things to consider the continuous rather than the discrete version of the problem. The discrete version has some interesting features that complicate things. For instance, let's say your initial and final velocities are zero. You might expect that the logical thing to do is to accelerate toward the target until you hit the halfway mark, then turn around and decelerate until you arrive. For the continuous case this is true. However, the discrete case introduces some quantization because it evaluates things in whole turns. In some cases it's possible to coast a bit (thus saving fuel) while still reaching the destination in the same number of turns as if you'd accelerated the whole way.
An example is traveling ten units (with zero velocity at the endpoints). This takes seven turns. The “greedy” acceleration method moves these amounts on each turn: 1 2 3 2 1 1 0. It's more fuel-efficient to do these moves instead: 1 2 2 2 2 1 0.
That's all for today. Next week I'll go into the math for the one-dimensional case, then talk about the continuous two-dimensional case. See you then!
No comments:
Post a Comment