Which pathfinding algorithm should I use for multiple enemies and tower placement?

Question

I am new to game development and I am developing my first "Tower Defense"-type game.

I need a pathfinding algorithm to place my towers and to move enemies.

• For tower placement case: I want the algorithm to run from entry to exit so that if it passes, the user can place tower and if fails user can't.
• For the enemy case: it should help multiple enemies to find their shortest path by running it for each enemy's current position to exit.

Searching about path finding I have found some algorithms like Floyd–Warshall, A*, Breadth First, Dijkstra's and some others. Some answers give priority to Floyd's over it for path finding with multiple enemies. So what do you suggest that I use for my case?

My grid size is 17x23 and my game would have multiple entry and exit points in future. I am using the Unity game engine and scripting in C#.

Answer 1

I recommend using A* for it's simplicity. You have a relatively small grid, and I presume monsters can only move in cardinal (up, down, left, right) directions.

I have an implementation of A* working in Objective-C (C# should translate OK) on my developer's blog here. You can see the monsters currently interacting with a changing landscape on my first post. A* post is lower down...

I'll add some extra comments to your questions on 1) & especially 2).

Don't run a pathfinding algorithm for every monster.

Run the pathfinding algorithm once for each entrance & exit pair, and put each monster on that path. Then, for each monster that is not on that path, run a pathfinding algorithm.

This will greatly improve performance, because it makes some assumptions about the general use case of the path - the monsters will already be following a valid path, whcih has now just changed in one place. Chances are, one new path will suffice.

If it doesn't (say the new object placement brakes the monster group into 2). Then start with the monster that isn't on the new valid path that is farthest away from the exit. That path, should be valid for every monster in the second group (who are not on the first path).

Hope that makes sense. In a very simple grid-style map system where users can place objects only 1-at-a-time, you really don't need to run a path for every monster. Especially if they're not interacting in real-time with anything else. (i.e. field changes in a static manner, you're not pathfinding two groups of monsters against each other).

HTH

Answer 2

I'm actually fixing to implement the same type of thing for an AI semester project. I'm wanting to have a tower defense game that starts out with an open field to the tower. I want to be able to place objects on the field to alter the path of the creeps.

So, a creep will be on a certain path and I'll be able to place something that blocks them in the middle of the path. They will then be able to find a new path.

What I'll be using is Incremental A*. This allow you to re-use parts of the path( tree ) that are the same, so you don't have to re-run the full A* algorithm.

Here's a link. http://books.nips.cc/papers/files/nips14/CN09.pdf