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.

No comments:

Post a Comment