Return to Question

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.

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.

I'm doing my first RTS game (something like WarCraft 2). I am wondering how can I implement pathfinding for a selected group of units.

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.

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.