I'm doing my first RTS game (something like WarCraft 2) in own game engine using Monogame for graphics. I am wondering how can I implement pathfinding for a selected group of units. Movement is tile-based, I don't want to play with navmesh yet.
First of all my map is tiled (up to 256x256) For a single unit I could definitely go for something like simple shortest path algorithm (maybe Dijkstra or A*). Unfortunately, the found path can be blocked by different unit or a building. So, quick maths 256x256x4 = 262k (edges). 262k * log 262k = 5* 10^6 (no log for A*, 20 times less) That's quite a lot. If I'd want my unit to respond to possible obstacle on the path, I'd have to run the algorithm each time it moves, let's say each second. It's definitely a lot... probably too much.
But what about few units? For each of them I have to run this algorithm once again, so for 10 units the complexity would be 5 * 10^7, quite a lot for a second. And even if I somehow reduce it, the units in the selected group would detect each other, which can totally mess up the whole pathfinding.
How can I solve this problem quicker? Maybe different algorithms or... I really have no idea.
EDIT: Well, I'm not going to have different speeds on different terrain, so basically I can go with a simple BFS (still not sure if A* is better than BFS, both have worst case O(|E|), so is it worth to implement A*? BFS is much quicker to write). So right now the complexity is about 200k per second for one unit.
EDIT 2: I'd like to avoid using any pathfinding libraries. I'm doing that game only for learning purposes, so I'd love to do all the stuff by myself.