Monday, May 6, 2013

Pathfinding: A step by step approach

Two things about pathfinding

Start with the simplest

It is hard to picture an optimal roue that will not start by minimizing distance through real space.  I will start with that fairly simple cost function, then look at fuel and delta-v profiles.

The problem of scale

Most of the graph problems I have dealt with so far have head a few dozen nodes, and so are susceptible to exhaustive depth first.  With thousands of nodes, rapidly expanding to tens of thousands, that goes out the window.  Not only do we have too many nodes for that, but they live in a database and should not be schlepped into memory without a good reasons.  That means I am going to have to use some very directed heuristic like A* or something that takes more direct advantage of the nature of the map.

This should make for interesting problems in Object Relational Mapping, since convention database problems simply do not work this way.

Starting small in data terms

I think that I would do well to set up a full map for a subset of the data - a 10 or even 5 parsec subsector centered on Sirius.  That would let me test the data model to make sure it will do what I need it to before there is a lot of data processed.

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.

Thursday, May 2, 2013

Swamp Visions

You all know the old saw "When you are up to your ass in alligators, it's hard to remember you are here to drain the swamp."

I've been zooming in on details of star catalog processing for a few weeks now.  I think it is time to re-focus on how I will use this information, and what products will facilitate that use.

So what are the drivers?


My regular hobby, as you will rapidly guess from visiting my other blogs, is wargaming.  I would like to run a campaign game, by  invitation, fora number of my friends.  I would like them to be able to set policies and make plans that will shape my future history, and apply rules to resolve the shared results of the many players' interactions. Practically speaking, it would be great to have a website where players could log in, see what is going on, and issues their orders all at a conveniently high level, with lots of analysis tools.


With retirement starting to at least be visible peeking over the horizon (half a dozen to ten years, almost down to single digits) I need some way to spend my time that does not involve using TV to cause brain damage.  Like most people who like to read, I have a fantasy that I will be able to write and will enjoy doing it.  I owe it to myself to find out.  One of my favorite genres is Science Fiction, and for really great SF a well-though-out world is essential.  In the old days, this would consist of binders of hand written notes.  What I would like to do in this century is leverage the same sort of tool (or exactly the same tool) as I use to run games as a master reference for an SF future history in which I can set my novels.


Huh?  Well, I am in the computer business; I write code for a living, and have for (brings up calculator) nigh 35 years this fall.  Its been a while since I tried to keep at the "bleeding edge" of development work, but I do depend on support work to pay the mortgage.

If we look at the systems written in the last five years, and project forward to the "legacy applications"  of tomorrow the key technology is Java in a web context using frameworks such as Struts or Spring.  Java Server Faces has solid purchase as a "front end" technology and Hibernate has a big chunk of the persistence space.  Note that I am not trying to predict the prime hot development environments of tomorrow; I need experience with technologies where, if I get solid skills now to complement my existing expertise, I will be well positioned to support those applications that corporations really have to keep going for at least another decade.  That's right, kids, Java is the COBOL of tomorrow.  Eventually it will be obsolete, but there is a solid mass of code its owners can't afford to turn off any time soon.

The obvious thing to do with the tool described above is to code and deploy it using a cross section of those technologies.  It will cost a bit and take some time, but since dev tools these days are free, and web hosting is just a couple of hundred a year, I should be able to put out a  muti-user product that will let me develop and showcase my skills while entertaining me, my friends, and hopefully my readers.

In future posts, I will get more into details.  Right now, I am prepping for a trip up the Danube, and I need to practice my useful Magyar phrases.