7
\$\begingroup\$

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.

\$\endgroup\$
1
  • 7
    \$\begingroup\$ Just calculate the path for all units whenever you place a tower? \$\endgroup\$
    – bummzack
    May 28, 2011 at 15:34

5 Answers 5

3
\$\begingroup\$

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.

\$\endgroup\$
4
  • 1
    \$\begingroup\$ A* is not approprate for Tower defence games. \$\endgroup\$ Jun 1, 2011 at 11:25
  • \$\begingroup\$ Want to elaborate? \$\endgroup\$
    – House
    Jun 1, 2011 at 20:27
  • \$\begingroup\$ 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". \$\endgroup\$ Jun 7, 2011 at 9:55
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – House
    Jun 7, 2011 at 19:23
11
\$\begingroup\$

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.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ 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. \$\endgroup\$
    – Ali1S232
    May 28, 2011 at 19:00
  • \$\begingroup\$ 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. \$\endgroup\$
    – House
    May 29, 2011 at 17:41
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 9, 2011 at 11:33
3
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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

\$\endgroup\$
4
  • \$\begingroup\$ And is A* really the most suitable algorithm for this scenario then? \$\endgroup\$ May 28, 2011 at 16:11
  • 1
    \$\begingroup\$ @Mathias: Yes, A* is industry-accepted to be the smartest pathfinding algorithm around. \$\endgroup\$
    – DeadMG
    May 28, 2011 at 20:10
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ May 29, 2011 at 7:39
  • \$\begingroup\$ 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. \$\endgroup\$
    – Joel
    May 29, 2011 at 11:44
0
\$\begingroup\$

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.

\$\endgroup\$
1
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 7, 2011 at 9:57

Not the answer you're looking for? Browse other questions tagged .