Pathfinding is way too slow

[ekolis]

Describe the bug Pathfinding bogs down when you start building moderate numbers of ships and/or exploring moderate numbers of star systems. (Not sure what's triggering it.)

To Reproduce Steps to reproduce the behavior:

1. Play the game for a while.
2. Process a turn

Expected behavior Turn should process in a reasonable amount of time.

Actual behavior Turn takes forever due to pathfinding.

Screenshots N/A

Additional context This seems to be caused by finding warp point exits which is calling ability lookup functions over and over again... We can't cache abilities here, can we?

[ekolis]

I made a few optimizations in a local branch which I'll merge once the issue is solved. I think another thing that would help is to add a "shortcut" method for CheckVisibility on space objects for empires that skips some of the more expensive logic such as checking for scanners if we only care if an object is visible or not.

[ekolis]

Would it make sense to only do the first step of each path every time a ship wants to move, rather than the whole path? Or would that lead to errors like ships getting stuck on several damaging asteroids in a row as in SE4?

[ekolis]

If we could somehow reuse the Dijkstra maps... But there is certain data baked into the maps which will need to be separated.

So I'm thinking we need to separate the maps into three parts:

• The basic connectivity graph. This can be global.
• Empire specific data such as unexplored systems (can't navigate through them) and enemies (shouldn't navigate through them unless navigating aggressively or they are your target, but make sure we hide any cloaked enemies unless we have appropriate sensors). This will need to be stored at the empire level.
• Distance metrics (e.g. "this sector is 3 moves away from us"). The will need to be stored at the ship level.

If we can cache some of this data at a more granular level than the ship level, this should speed up pathfinding.

[ekolis]

I think this is going to call for some unit tests...

[ekolis]

Hmm, I wonder if we could use RogueSharp to do our pathfinding? I hear version 5 isn't finished so we'll need to grab the v4.2.0 tag (dood)...

[ekolis]

Looks like RogueSharp doesn't have the concept of warp points, so the pathfinding problem would need to be broken down somehow, or warp points would need to be added...