Dijkstra, Breadth First or A* for tower defense? [closed]

Question

So I asked a question about optimizing my A* for my tower defense game and got a couple answers saying I should use Dijkstra or Breadth first instead to calculate the shortest distance for the 50+ enemies.

my questions are

Do I use breadth first or Dijkstra? Is dijkstra faster than A*? Is it as accurate as A*? Is there any way I can optimize A* more than binary heap so that I can calculate the path using A* without having to learn dijkstra?

Currently takes around on average .003 sec to calculate a long path on a 30* 30 grid with my A* using binary heap but I don't think that may be fast enough.

Answer 1

DJikstra is a separate case of A* with inert heuristic function. All question then boils down to if you can propose a suitable heuristic function or not. If you can, A* will perform better, no doubt about that.

Answer 2

For a tower defense game, you will typically want to save the shortest path tree for each exit and reuse it for all mobs heading towards that exit. That way, you only need to recalculate it once whenever the connectivity changes (i.e. when towers are built or destroyed).

Since you want to calculate the full shortest path tree anyway, you might as well use plain old Dijkstra's algorithm instead of the more complicated A*.

It is, however, also possible to use "incremental A*" to build up the shortest path tree as needed. Basically, you'd run A* from the goal to the mob, save the state of the algorithm (including the partial shortest path tree built so far) when you reach the target, and then resume it (with a different target and heuristic) when you next need to find a path to that goal from some point not yet covered by the tree. You can even do incremental updates to the tree when towers are added or removed, although that gets a bit more complicated yet.