[PATCH] System Graph Update & Effects Execution

[cami]

[was: Jump distance matrix generation]

On the client, a significant portion of the remaining turn update time is spent on computing the jump distance between each and every vertex. Besides effects execution, which is quite hard to parallalize and impossible to improve otherwise, and condition evaluation, which is already quite fast even for large galaxies (~40s for 3000 systems on my machine) this is the last O(n²) (or worse) part of turn updates. It is rather easy to improve:

1. Replace johnsons_shortest_paths by repeated BFS (if jump lengths are planned, could use dijkstra instead).
We will never have negative weights and this step saves the whole Bellman-Ford preprocessing.
2. Run the BFS (or dijkstra) instances in parallel.
3. Stop BFS / dijkstra at MAX_JUMPS, and choose this value reasonably low.

I think I could take this up before returning to the project you drew me away from I'm curious about a good value for step 3. It is quite important for large galaxies, as makes the algorithm linear in #nodes when the number of stars within the MAX_JUMPS neighborhood of a node is bounded, which at least approximately is the case for us.

Edit: might have to do something similar for euclidean distances, didnt notice those in the profile data as they are not calculated in a separate function. Maybe they're even cheap enough for any reasonable game size despite the O(n²) algorithm.
Edit2: I noticed the starlane and wormhole lengths are computed but never used. Why is that so?

[Geoff the Medio]

...repeated BFS...

Breadth-first search for what, and why repeated? Traversing the tree to find the shortest path to each other node from each node, and caching the results, or doing that each time a distance is requested if not already in the cache?

...if jump lengths are planned...

What does "jump lengths" mean?

Stop BFS / dijkstra at MAX_JUMPS, and choose this value reasonably low.

Does that mean pathfinding would break for objects further apart than that limit? Imposing such a limit doesn't seem like a good idea if it is just to turn an O(N^2) algorithm into an O(N*M) where M is soft-capped at less than N...

Or do I not understand your suggestion?

[cami]

jump lengths = starlane lengths for starlanes, 0.1 for wormholes
they are computed but the result doesnt seem to get ever used.

Yes path search will fail for large jump distances if capped. Is there any need to cross the galaxy? Its graph diameter can be hundreds of systems. This step is kind of optional, but can be quite effective.

Edit: wait, why do we precompute and store euclidean distances? Does that even save anything? I somehow suspect it hurts more than it helps.

[Geoff the Medio]

jump lengths = starlane lengths for starlanes, 0.1 for wormholes
they are computed but the result doesnt seem to get ever used.

Do you mean the computed cached data about the length of the shortest pathes between each pair of systems? Those values, if stored, may or may no be used, but presumably are gotten free when finding the paths themselves.

Or do you mean the distances between systems, which are the edge weights passed into the shortest paths algorithm? Those are used in that algorithm... It only computes them for lanes, not all system pairs.

[cami]

I see the lane lengths are stored in the graph, I guess they are used for pathfinding. The lane lengths are NOT used in johnson_all_pairs_shortest_paths. There, each lane has weight 1 :

Code: Select all

     m_system_jumps.resize(system_ids.size(), system_ids.size());
     constant_property<EdgeDescriptor, short> jump_weight = { 1 };
     boost::johnson_all_pairs_shortest_paths(m_graph_impl->system_graph, m_system_jumps, boost::weight_map(jump_weight));

Would be no problem to use the actual lane length instead of a constant 1 here, if that is wrong, but I guess using 1 is actually what is needed here. What I question is this code:

Code: Select all

        // define the straight-line system distances for this system
        for (int j = 0; j < i; ++j) {
            int system2_id = system_ids[j];
            TemporaryPtr<const UniverseObject> system2 = GetUniverseObject(system2_id);
            double x_dist = system2->X() - system1->X();
            double y_dist = system2->Y() - system1->Y();
            m_system_distances[i][j] = std::sqrt(x_dist*x_dist + y_dist*y_dist);
        }

In effect, it stores the straight-line (=Euclidean) distance between every pair of systems. That doesn't seem a good idea to me. Recomputing this is not much more expensive than looking it up, and has the advantage of only computing the pairs that are actually needed, which might be much less.

[Geoff the Medio]

I see the lane lengths are stored in the graph, I guess they are used for pathfinding. The lane lengths are NOT used in johnson_all_pairs_shortest_paths.

That's possibly a bug... possibly the m_system_distances should be used? Otherwise paths are always the least jumps, rather than the shortest distance, I think...

Edit: Just substituting m_system_distances in place of m_system_jumps leads to compile errors. /Edit

In effect, it stores the straight-line (=Euclidean) distance between every pair of systems. That doesn't seem a good idea to me. Recomputing this is not much more expensive than looking it up, and has the advantage of only computing the pairs that are actually needed, which might be much less.

I suppose you could reimplement class Universe::distance_matrix to calculate the inter-system distances (and cache as each is determined) as needed instead of pre-caching all of the values.

[cami]

m_system_distances and m_system_jumps have different types, hence the compile errors.

m_system_jumps is used by WithinStarlaneJumps and possibly also LeastJumpsPath. Thus, weight "1" would be correct I think. I dont think it is used for pathfinding, that will probably use dijkstra in conjunction with the edge weights.

I think I would just implement a custom JumpsDistance class/struct instead of specializing the distance_matrix template if possible.

[Geoff the Medio]

Hmm, looks like Universe::LinearDistance is the only place that m_system_distances is used. That could easily be replaced with a calculate-as-needed-with-caching scheme instead of full precomputation used now.

Also, it looks like the ShortestPath code just uses distances between systems that's stored in the system graph, which is initialized in the aptly named Universe::InitializeSystemGraph. That code directly computes the distances between pairs of systems as needed, rather than looking it up with Universe::LinearDistance... The block of code that fills in m_system_distances is immediately after the block that redundantly calculates it all when filling in the system graph edge weights. At the least, that could be rearranged and make use of the stored distances information when filling in the edge weights.

I think I would just implement a custom JumpsDistance class/struct instead of specializing the distance_matrix template if possible.

distance_matrix is a custom class.

[cami]

I know, but it doesnt look like it can be generalized to both being used as a storage for jump distances on the one hand and as a "container" that computes linear distance on the other hand without verbose template magic.
I think I'll just leave distance_matrix alone, add a mutex to universe and populate m_system_distances on-the-fly as you described, while holding a lock on the mutex.

[Geoff the Medio]

I tried moving the population of m_system_distances earlier and then calling LinearDistance when adding edges to the system graph, but something broke in the process...

[cami]

Did you mix up ids and indices, possibly? LinearDistance wants ids, while edge_weight_map and m_system_distances want indices. Try this:

Code: Select all

edge_weight_map[add_edge_result.first] = LinearDistance(system1_id, lane_dest_id);

[Geoff the Medio]

I don't think index vs. id is an issue. The caching loop stores in m_system_distances by index, not id, and LinearDistance calls are used to do the lookup by passing ids that are converted to indices before retreiving from m_system_distances. I think I just was clearing the contents of the array at the wrong time...

[cami]

Well, anyway, I tried it too, and it worked. I just decided to drop the cache entirely now, however. It's pointless. It's two std::map lookups either way (either for the id->index mappings or for the id->object mappings), and those outweigh the X(), Y() and std::sqrt() calls by far anyway.

[Geoff the Medio]

It's two std::map lookups either way ... and those outweigh the X(), Y() and std::sqrt() calls by far anyway.

Hmm... good point. I suppose I'll just remove the DistanceMatrix typedef, m_system_distances, and modify LinearDistance to just do the calculation and return.

[cami]

I already did that, so you can skip it if you want and let me prepare a patch.
For JumpDistance, I guess I need to use a std::vector instead of boost::ublas::symmetric_matrix as storage so I can ensure concurrent writes to items are safe.