Slow path-finding code

[nickshanks]

Is there an existing issue for this?

• I have searched the existing issues

Describe the bug

The path-finding code is very slow. I think it is iterating through every StellarObject in every system once per ship for every ship in the fleet, 60 times a second.
This is most noticable when your escort fleet is 'trapped' on the other side of a Jump Drive gap without a Jump Drive.

Steps to Reproduce

1. Load provided game
2. Leave planet

press 'h' to prevent pathing and get your CPU back.

Expected Behavior

CPU usage would be 10%, not 450%

Screenshots

No response

Link to save file

Nicholas Shanks~250% CPU.txt
Nicholas Shanks~350% CPU.txt
Nicholas Shanks~450% when jumping.txt
Nicholas Shanks~also 250% CPU.txt

Operating System

MacOS X

Game Source

Built from source

Game Version

nickhanks/endless-sky/tree/master with unpushed changes

Additional Information

Commenting out code to find the cause, I traced it here:

AI::Step() {
	if(parent->GetSystem() != it->GetSystem())
		MoveEscort(*it, command);
}

AI::MoveEscort() {
	SelectRoute(ship, parent.GetSystem());
}

AI::SelectRoute() {
	const DistanceMap route();
}

DistanceMap::DistanceMap(const Ship &, const System *, const PlayerInfo *) {
	while(!edges.empty()) {...}
}

Now I am no mathmetician and I don't understand Graph Theory, so I am not best placed to solve this, but I believe we don't need to re-route every escort 60 times a second. An already-found path should suffice until the graph of known systems changes, or the Orders change, or the player or escort moves to a new system (is that the same as 'graph changes'?)
I think caching whether a system has a wormhole would be helpful too.

[TheGiraffe3]

#9587. Not exactly the same, but pretty close.

[eebop]

I've got a planned fix and will pr it sometime soon - a major improvement via caching (I am away from my computer for the next couple days)

[tibetiroka]

Related: #6940