Best algorithm for path finding in a tower defense

Question

A have read about A* as well as D* and similar, and i'm not able to choose between them. What is the best searching algorithm when it comes with many searches(50 searches every tick) and with many different possibilities?

Answer 1

Between the two, I would pick D*. D* specifically assumes a best path, but if obstacles were encountered then recalculates. This means that each creep can have it's own personal view of the exit path, which is updated as the creep encounters obstacles.

Such assumptions on the best path with adjustments in behavior is slightly more realistic, as if you or I were walking the path, we wouldn't avoid obstacles prior to knowing about them. It also nicely accounts for path recalculation in the event someone (the players) builds a new tower. If you balance expansion of open nodes well, you might even have creeps walking around both sides of a tower centrally placed in the best path.

However, if you want to really make it fun, take a learning based approach on best path finding. Much more interesting than other solutions. To see an example, look to something like antbuster. Perhaps so interesting that it doesn't quite fit into the standard tower defense game genre.

Answer 2

Q-Learning may be a good choice for this. Q-Learning attempts to map out a grid of penatlies/gains that making a local decision would encoure in a finite world.