FreeOrion

I've noticed that FO looks up shortest starlane paths using Boost graph algorithms and linear distances using precalculated distance matrix. Shouldn't that be the OTHER WAY AROUND?

Linear distance calculation is constant-time operation just like looking up a value in std::vector. Not much time saved there. On the other hand, looking up graph distance using Dijkstra's algorithm takes N log N to N^2 log N cycles (N being the number of vertexes in graph/stars on universe map). For those who don't understand, it's still rather fast but doing it over and over is a huge waste of time. There're also functions which calculate distances up to N times (like Condition::WithinStarlaneJumps::Eval).

Distance matrix could be improved to keep all kinds of distances and shortest path chains for all empires available in constant time (linear time for shortest path chains) and be updated using Floyd-Warshall algorithm on the fly (recalculating the matrix when new vertex is added is at most quadratic-time operation, for those who don't understand, that's a little slower but it happens once in a very long time).

I don't want to waste time going through code which isn't important for this so could you give me a few tips and write a few words about how the code works before I start coding the new distance matrix?

Or should I code the redesigned production system first?

Filling the linear distance matrix is/was fairly easy to do, and quite useful as various other algorithms use these numbers. The point probably isn't to decrease the computational complexity, but to speed up other algorithms that use these values in their inner loops by avoiding extra square root calculations.

Shortest paths aren't as generally useful as the linear distances though, as not nearly as many other algorithms would use the info, so filling the whole graph might be a lot of wasted computation in practice. As well, the matrix of starlanes is fairly sparse, so the shortest path calculations aren't generally as bad as a worst-case graph traversal estimate might suggest.

That said, recalculating a shortest path more than once a turn is probably wasteful, and might become a problem if we start having lots of conditions using shortest path tests. However, it's not really an issue right now, so might be a premature optimization, though not an unjustifiable one if you're keen.


Could you be more specific about what code you want to know about? You've already described the algorithms used and the presence of a lookup table for linear distances, so I'm not sure what you're asking...


I have no preference, though it might be worth considering for yourself that adding a hidden lookup table behind the public Universe::ShortestPath(...) function(s) likely won't have any complicated interactions with other code, whereas redoing the production system might require changing a lot more within the production system and other systems...

Pretty much anything useful about the code above it. Especially some tips about which pieces of code might be more fragile than others and how should I design classes to fit them better in the existing code.

I'm not sure what you mean by "the code above it", but it probably doesn't matter. I might be able to help if you have a specific question, but there's too much code and I know too little about what you're planning to do to give any useful advice now...

I'm thinking about 3 classes, probably derived from abstract base class:
- LinearDistanceMatrix
- JumpDistanceMatrix
- ShortestDistanceMatrix

They all should have a method to add a vertex (and update the matrix), get distance between two vertexes and get shortest path between two vertexes (always empty for LinearDistanceMatrix).

Abstract base class will clean up and shorten the code a bit because it'll do Floyd-Warshall algorithm on whatever the derived classes give it and there'll be no need for multiple shortest-path universe methods, you'll just call a method of the right distance matrix. For example, that std::min() std::max() stuff in Universe::LinearDistance is what the distance matrix itself is supposed to do deep inside. Empire starlane visibility filter might also become partially obsolete.

I need to know how much should these classes know about system graph and whether empire distance matrix should belong in the empire or in the universe.

You need to be able to remove vertices as well, and the interface should have a way to set all the vertices in one go, rather than requiring the user to add one vertex at at time.

Each empire will have a separate set of known and accessible systems... But also consider that there might arise many other cases in which paths would need to be found that varies even for objects owned by the same empire. One ship might not be able to travel to certain types of stars, or might have a max allowed starlane length it can go along, or similar. So, it should be possible to calculate a the shortest path (by various definitions) or the existence of any path of a certain range of lengths (not necessarily the shortest, as long as its within the given length range) between systems for an arbitrarily different set of vertices, not just the whole set known to an empire.

I don't see why you really need three separate classes to do the different types of distance calculations. It would seem simpler to the user to just have a single multi-function distance matrix class, or namespace of functions that are called by the already-existing Universe path-related functions. You'd set the vertices for the condition in which you want to path check, and then call ShortestPath(), LeastJumpsPath(), LinearDistance() or whether the systems are connected. Internally, you can store separate information for each, as necessarily.


It would probably be useful to be able to pass a UniverseObject* or Ship* or Fleet* to a function in your class that would set the functions to return paths for the passed object. This is somewhat future proof in that for now you could just check the owner empire of the object and react accordingly, but in future we could set up some way to do per-object graph adjustments. It'd probably be necessary to add an "AccessibleSystems" function to class UniverseObject for this purpose.

Alternatively, you could have a function that takes a Graph parameter (similar to the current Graph parameters to ShortestPathImpl and such) that specifies the allowed graph nodes that can be traversed and edge weights for subsequent calls to the path functions. You could assume undirected graphs, but we might want directed in future, if it's not too much extra work.


The distances between systems is a property of the Universe, not of the empires, so a distance matrix doesn't really belong in the Empire class.

Trivial.


Can be done in linear time rather than in N log N through Dijkstra.


If you have one object which has FastestPath(), LeastJumpsPath() and LinearDistance() methods, all algorithms which use it must know which method to call. If you have 3 different objects each with different ShortestPath() method, you can make one algorithm do three different things without changing a single line of code just by giving it the right object.


Trivial, the worst thing that can happen is having to temporarily "inject" a new origin vertex "inside" an edge.


Distance matrix is not supposed to know anything about empires. All it needs to know is basic vertex/edge info and vertex/edge accessibility map (IsVertexAccessible() and IsEdgePassable() or something like that).


Trivial.


Distance between systems is property of the universe defined by universe graph and system visibility is property of the empire. Distance map is a combination of these properties. Empire distance map actually doesn't make sense outside the scope of the empire and the empire might be the only entity which should be able to modify its own distance map.

Least jumps path already uses breadth first search.


Why is passing the appropriate object better than calling the appropriate function? The latter is probably easier to use as a public interface. If you wanted to do something funky with passing objects, or perhaps just function pointers, just internally, then I suppose that's fine... but having to create or get pathfinding objects and pass them into a common GetPath function is the sort of complexity that should be hidden in the implimentation.


As long as you start with a full universe graph, I don't think there will be any cases where you need to add additional vertices or edges. Any restrictions imposed on where an object can travel to make its path will take the form of limits on the available edges that can be travelled.

Could you initialize some path storage with a set of Djikstra paths for the full graph, and then use this information to set up initial heuristic guesses for A* that's trying to find a path within a subset graph? The idea is that by removing edges, you can never made the path any shorter, so the full graph's distances between two nodes is a lower bound on the distance in the subset graph.


It's more than that. Each individual object has its own distance map, since different objects owned by the same empire might have different additional restrictions on the edges along which they can travel. There is not, in general (or rather, should be) a single distance map that applies to all objects in / owned by an empire.

There's no reason why choose only one of these options.


I was talking about calculating paths for a fleet which is halfway through a starlane but not in any system. In this case, the simplest solution is to inject virtual origin vertex connected to the end points of the starlane.

And why should empire distance maps start from full universe graph? Even if all unexplored systems are not in the distance map, all you need to know to calculate shortest path is the list of starlanes connecting it to any explored system.


The point of using heuristics is to get reasonable results when the best correct algorithm has insane time complexity. Fleet movement orders are made in UI and there's a lot of time to calculate point to point distances from scratch if needed. Guessing could actually make things much worse.

The only other option is to have distance maps for all possible subgraphs and there's not enough memory for that. 2^E (E = edge count) is way too big number.


The point of improved distance maps is to speed up algorithms which use those calculations in loops (often evaluated conditions etc.). Dijkstra is more than fast enough to calculate shortest paths just for fleet movement.