Friday, May 3, 2013

User Functions 1: Pathfinding

We have been talking about maps a lot in this blog.  What's the first thing we want to find out from a map?  If I am here, and I want to be there, what route to I follow in my travels?

We have set down a number of rules for travel.  Interestingly enough, none of them say much about the specific capabilities of any ship (at least one that can travel significant distances in space)
  1. You may jump from star A to star B if the mass of B in solar masses divided by the square of the distance from A to B squared is greater than 0.1.
  2. Respect for conservation of momentum and potential energy.
  3. Sufficiently flat space.
  4. Velocity vector at moment of departure pointed directly at target position.
So, if I want to get from A to B, how do I  plot a route.  Well, route planning using graph theory is simply enough a matter of assigning a cost to each edge (clearly directed in this case) and then minimizing the cost to traverse a set of edges from joining A to B - if set a set exists.  The trick is the costing function.

There are static elements to the problem.  Rule 1 is simple enough; the existence of an edge depends on destination mass and that is that.  The detailed cost of rules 2 though 4, however, depend on decisions about technology and choices made on how to use it. 

Why?  Rules 1 and 2 together determine how far we have to go through real space to get to the point to which we can jump to another star, and how far we are out from that star when we arrive.  Rule 4 decides where that point is.  Simple enough, but how much that then costs depends on the delta-V of our ship, and how we want to trade off between time and fuel consumption.  Are there fuel sources en-route?  Do I have to stop to use them, or will they rendezvous with me?   What contingency do I want for emergency? 

How about other consumables?  How do we cost food, water, air - and of course urgency.  It's an interesting set of problems.

Rule 4 has another interesting set of implications.  Lets say I am going from A to B to C.  If A-B-C is very nearly a straight line, I do not have to spend very much fuel in system B to line up my vector to jump to C.  I can (it's a choice) accelerate all I want, or even do mid-flight turnover for the whole flight while passing through B.  But it is a choice.  If on the other hand the angle ABC is highly acute I have to adjust my vector while passing through system B from the A-B direction to the B-C direction.  Not only are there costs to this of itself, my the point at which I mitigate that cost is back in system A when I decide on the magnitude of the AB vector.  Hairy stuff.

In fact, it might be a good idea to come up with a "rule 5" - a correct velocity at which to be traveling when the jump is made.  This at least has the virtue of eliminate a set of optimizations.  Something to think about.

No comments:

Post a Comment