path finding - RTS pathfinding

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.

Answer

With RTS pathfinding, your requirements are:

1. You have to compute paths for all selected units fast.


2. The pathfinding must take into account that a path may not be found (blocked)


3. The pathfinding must take into account, units of varying size.


4. The pathfinding must take into account that the path may become blocked by other allied units/buildings before the path has been completely walked.

So lets address each point in order, using starcraft as an example:

1. Starcraft uses subdivision of cells to reduce top level path finding, and then performs a lower level of pathfinding to trace a path from one cell to the next. This makes it very cheap and thus, fast, to perform.


2. A-Star (used by 90+% of games) is ideal for this, as the algorithm handles blocked paths fine.


3. By using the aforementioned sub-division of cells, you can have units which occupy N subcells. by updating subcell maps frequently, you can allow the algorithm to path small fast units around large slow units.


4. As with 3: You will want to periodically recompute each moving units' path, as a path that was previously open, may become blocked over time. Update the sub-cell maps and recompute, as in 1.

So, to summarise:

Use A-Star, subdivide subcells for performance and accuracy. Maintain a temporary subcell map of obstacles and units for pathing around blockages, or waiting for blocks to clear, and, as I have discovered through experience:

Do not recompute paths for every unit, every frame. Instead, do some sort of queuing system, and do a portion of it each frame, or every other frame, which leaves computational time for other game tasks.