I'm working on something for fun in Java at the moment that uses a set of abstract classes I've created for storing a network of nodes, basically, each node instance holds a collection of links to other node instances as a NodeLink class, I rather like the class because you can drop in a seperate NodeMap as a node on the current map, so the pathfinding only has to either find its way to a local point via the node-links, or if it cannot, go to a map link and move to the map 'above' and check to see if any of those Nodemaps contain the searched for link. kind of like going through layers of maps.
The theory behind this is that it would allow me to have a Spanning-Tree style pathfinding for the Nodes, which should allow very fast pathfinding, but it has two drop-backs:
1) Each node has to have a table of every other local node, the next node in the path to that note, and the number of links between it and the destination, whilst dividing up into layers does much to reduce this, there's still going to be quite a lot of ArrayLists being stored.
2) The pathfinding is somewhat rigid, you couldn't, for example, find a path and ignore points that meet certain conditions without completely recomputing the Spanning Tree for that Nodemap, adding some kind of distance 'weight' to undesired points.
3) Computing the Tree seems to be somewhat thirsty, though, I am using a saturation technique (each time a node changes its table, it transmits the table to connected nodes, which compare/update details and repeat the process until a node receives an update that doesn't change its internal table, this does work on paper, but is a highly iterative process.
Basically, I'm wondering if there is an easier way to go about this, I've heard about things like Djikstras algorithm, but that strikes me as being difficult to employ over several sub-maps, but much better at coping with path weighting.
I suppose it boils down to where I want the speed, if I want the pathfinding to be fast, then I guess I have to sacrifice the memory of Routing tables, but if I'm willing to take a small hit on the pathfinding, then Djikstra's is probably the better way to go?
