Pathfinding at scale is pretty much a solved problem. Spring. Recoil. SupCom. Starcraft. You can do that, for 10.000 units before you run into problems.

https://www.youtube.com/watch?v=2wxwIxz4PaY

Why is it so bad on sandboxes like Minecraft? Modded Minecraft has struggled with pathfinding for years.