Err, have you played the game? I cant get past 100,000 without the game beginning to slow down. I have a decent computer too.

I was bothered by this problem so I solved it for my own city builder game, Archapolis (still very early development):

https://www.youtube.com/watch?v=7q0l87hwmkI

I can path 200,000 to 300,000+ units simultaneously to random destinations, with a bonus of utilizing all shortest paths between two points.

The paths are all cached for constant time path finding, but I figured out how to do so efficiently (both building and storing tree/graph)

I wrote a non-technical article here:

https://www.yesboxstudios.com/2022/04/27/all-nck-shortest-pa...