I wouldn't expect performance to take forever (> 1 hr) for 1000x1000 in python. I know I have made not optimized path-finding that can solve 100x100 instantly (< 1 sec), and because the time complexity scales with # of vertices for planar networks that should mean that it would only take ~100 sec to solve 1000x1000.
I was being hyperbolic, run time was more in the two minute range. Thank you for the numbers it seems my idea of thousands of units pathfinding over long distances isn't feasible in this way.
My next idea is to "prerender" a series of interconnected waypoints across the map at the start and then pathfind to the nearest one before moving long distances using small bursts of pathfinding to move around obstacles and stay on track.
