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.

This question already has an answer here:

What do you suggest would be the best algorithm for a tower-defense game? It's a 2D based tile game, where there is walls and towers blocking the way, between spawnpoints and their destination points.

Constantly, as the player places a new tower to block the way, or to help shoot spawning units before they reach their destination, a new path for the affected spawnpoint's path will have to be recalculated, and the units must be re-routed to that new path.

Therefore, I need performance.

I tried the A* algorithm, but everytime the player places a new tower, and path has to be recalculated, the existing units who haven't gone past the tower yet, get lost, and stand still, since they were a part of the old path that has now lost its pathing information.

share|improve this question
7  
Just calculate the path for all units whenever you place a tower? –  bummzack May 28 '11 at 15:34
add comment

marked as duplicate by Anko, bummzack, msell, Trevor Powell, Josh Petrie May 1 '13 at 16:29

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

5 Answers

up vote 3 down vote accepted

A* should be plenty fast enough. Each time a tower is placed you should calculate a new path for each spawn point, and assign that path to each unit that is spawned there. You should also calculate a new path for the units "in the field". Units in the field can have their paths calculated as the shortest path to get back on track, as in a path to the new path. Or the units can have their path calculated from their current position to the destination.

You can likely save calculations by grouping units in the field and calculate a common path for them all. For example if you have a group of units in tile (4,7), they can all use the same path, so you just have to calculate it once.

Additionally (depending on what your rules are) you should consider doing these calculations as a check before the tower is placed. This will disallow the player from placing towers that block all paths. Or as some tower defense games work, if the play blocks all paths, the units just ignore towers when path finding.

share|improve this answer
    
A* is not approprate for Tower defence games. –  Richard Fabian Jun 1 '11 at 11:25
    
Want to elaborate? –  Byte56 Jun 1 '11 at 20:27
    
A* is for path finding from single entities to one or more destinations, tower defence games are about multiple entities routing around a (relatively) static map, in which case, you want Floyd's algorithm, it was mentioned in the duplicate question too, and in both cases the A* question has been chosen as the correct answer yet in both cases, the answer is to not path find "per mob", but "per grid square". –  Richard Fabian Jun 7 '11 at 9:55
1  
I agree, using A* for each mob would be a waste. That's why I said using A* to find a path for a group of units would be better. So, yes A* can still be appropriate, as long as its use is optimized. The reason I answered how I did is because the asker already had A* implemented, so a optimized use of A* would be simple. If they were starting from scratch I'd go with something like this answer. –  Byte56 Jun 7 '11 at 19:23
add comment

Answer:

Rather than calculating a path from one point to another you could calculate the movement direction for each separate tile. Start from the exit, mark each adjacent tile with a pointer to the exit, then from each of these tiles let all adjacent unmarked tiles point to that tile etc.

The maths are really the same as Dijkstra's algorithm (A* without distance optimization), you just don't throw away any data and therefore end up with a many-to-one path.

You should end up with a data-array that looks something like this, generated in linear time:

|---|---|---|---|
|   |   |   |   |
| | | X | ->| e |
| v |   |   |   |
|---|---|---|---|
|   |   | ^ | ^ |
| | | X | | | | |
| v |   |   |   |
|---|---|---|---|
|   |   | ^ | ^ |
| ->| ->| | | | |
|   |   |   |   |
|---|---|---|---|
| ^ | ^ |   | ^ |
| | | | | X | | |
|   |   |   |   |
|---|---|---|---|

Somewhat related random ramblings:

Regarding point-to-point pathfinding it's worth noting that A* lose a lot of it's advantage to the simpler Dijkstra algorithm when operating in a twisted maze. A* will probably still search fewer nodes, but it is also slower per node than Dijkstra.

For the typical tower defence maze, entry and exit points are placed at the edge of the field, this means that Dijkstra won't as otherwise waste time by searching a big field in the wrong direction. In conjunction with the maze this means that Dijkstra and A* will search almost the same number of nodes, thus Dijkstra takes the win in this case for being faster per node.

share|improve this answer
1  
in addition to hist answer I can add,first you just have to change these directions only when a new tower is placed, and second for just a simple game you can use bfs, and if your game is a bit just more complicated (some pathes are prefered to some other due to any tile properties) you can use dijkstra to create that arrows. –  Ali.S May 28 '11 at 19:00
    
I like this idea, I'd say this is totally worth trying. You'd still have to follow it through to ensure that a valid path existed, but it has some good potential. –  Byte56 May 29 '11 at 17:41
    
you don't have to follow it through if you build the costs with Floyd's algorithm, you just check to see if any of the final costs are infinity in the open grid cells. –  Richard Fabian Jun 9 '11 at 11:33
add comment

I actually wrote a game once which did this sort of thing perfectly. And the amount of recalculation was very little compared to A*.

In a grid base map (even if the characters don't move in a grid base way), you have a 2dimensional array, and mark the finish with 0,0.

Add the four adjacent squares to a list.

Then using a for or while loop, iterate through the list, and simply give each square a value of the minimum of the four surrounding squares + 1.

Then add the four surrounding squares to that square to the list (if their value is still not set).

basically, on an empty map, you could receive an effect like this in the array:

  • 3,2,1,2,3,4
  • 2,1,0,1,2,3
  • 3,2,1,2,3,4
  • 4,3,2,3,4,5
  • 5,4,3,4,5,6

However on a map with obstacles...

  • 3,2,1,2,3,4
  • 2,1,0,X,4,5
  • 3,2,1,X,5,6
  • 4,X,2,X,6,X
  • 5,4,3,X,7,8

Now this method has 3 main benefits.

If i place a block on a 4 for example. Then only the squares with a value of 5 or higher need to be updated! I simply have a loop which goes through the values of 5 upwards (make sure you have all the 5's done before you do the 6's, and all the 6's before the 7's, etc.

Or you could do it from an empty array again. It's extremely fast!

The second benefit, is that the grid is exactly the same for all enemies! Every enemy in the map follows this array. If it is on a 7, then it wants to move to a 6! Doesn't matter which 6 it takes, because they all are the same distance (6 squares) away from the end!

Thirdly, if, during your loop to work out the values of this array, if a square doesn't get reached, (if the value stays unset, and there isn't a tower there), then it means that part of the map is cut off from the base. In most tower defenses, this isn't allowed. So if you check this before confirming a towers placement, it means you know whether it is a legal or illegal build.

Hope this helped, Randomman159

share|improve this answer
add comment

You need to compute a new path for each existing unit, and a new one for the newly-spawning units.

share|improve this answer
    
And is A* really the most suitable algorithm for this scenario then? –  Mathias Lykkegaard Lorenzen May 28 '11 at 16:11
1  
@Mathias: Yes, A* is industry-accepted to be the smartest pathfinding algorithm around. –  DeadMG May 28 '11 at 20:10
1  
@Mathias, A* may be industry-accepted to be good enough, and it may be that many people in the industry haven't heard of better pathfinding algorithms, but they do exist. I've had to implement an extension of A* which uses two heaps when A* wasn't good enough for a game I was developing. However, Gajet is correct to point out in a comment to another answer that breadth-first search may be the most suitable algorithm in this particular scenario. –  Peter Taylor May 29 '11 at 7:39
    
I would disagree, read my method. It produces a method which only needs one algorithm for every enemy. Which means when your player starts having loads of enemies on the screen at once, there is much less lag than using the A* algorithm. –  Randomman159 May 29 '11 at 11:44
add comment

It really depends on the type of tower defence you are developing.

Case 1: If your towers can't block your runners (so you can't change the path), you can simply develop a simple region system. It is really easy to implement:

Unit1 enters region1 -> run to region2 Unit1 enters region2 -> go to region3 ...

All you need is to position you regions in way that there is no blocking objects between two linked regions.

Case 2 (Your case): Your towers can block. If its the case you will need to design a A* algorithm system. The system can be harder to implement for beginners but don't worry, there is a lot of A* pathfinding system on the web that you can reuse. You will need to recalculate the path every time something change the actual path. But don't worry, a good A* system can recalculate the path of thousand of units in a blink of an eye!

You can mix the region system and the A* path finding for a faster results! You will only have to calculate the path to the next region and not to the endpoint so you will improve you performance.

share|improve this answer
    
you can use Floyd's algorithm in both cases (in my case, I just added a cost for breaking through the barrier into the heuristic). No need for A* in tower defense games, it adds too much CPU work. –  Richard Fabian Jun 7 '11 at 9:57
add comment

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