Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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#.

share|improve this question

2 Answers 2

up vote 5 down vote accepted

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

share|improve this answer
    
+1 For A* and the optimization suggestion. Also, @Syed, check Unity's asset store for Pathfinding projects. There are some free (and not-free) ones that may help take the dirty work out of it for you (unless you want the experience of implementing it). –  chaosTechnician Oct 28 '11 at 16:42
    
@Syed, yes, sorry I can't comment on your actual coding issues with C# & Unity. A super-quick google search yielded this –  Stephen Furlani Oct 28 '11 at 17:06

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.