GrabDuck

Pathfinding for Tower Defense

:

In a Tower Defense game, there are many enemies that are all headed to the same place. In many Tower Defense games, there is a predetermined path, or a small number of paths. In some, such as the classic Desktop Tower Defense, you can place towers anywhere, and they act as obstacles that affect the paths taken by enemies. Try it out, and click on the map to toggle walls:

How would we implement this?

Graph search algorithms like A* are often used to find the shortest path from one point to another point. You can use this for each enemy to find a path to the goal. There are lots of different graph search algorithms we could use in this type of game. These are the classics:

  1. One source, one destination:
  2. One source, all destinations, or all sources, one destination:
  3. All sources, all destinations:

A game like Desktop Tower Defense has lots of enemy positions (sources) and one destination for all of them. This puts it into the all sources, one destination category. Instead of running A* once per enemy, we can run an algorithm once, and it will calculate the path for all enemies. Even better, it will calculate the shortest path from every location, so as enemies get jostled around or new enemies created, their paths have already been computed.

Let’s explore Breadth First Search, which is sometimes called “flood fill” (FIFO variant). Although graph search works on any node-and-edge graph, I’m using a square grid for these examples. Grids are a special case of graphs. Each grid tile is a graph node, and the borders between grid tiles are the graph edges. I’ll explore non-grid graphs in another article.

Breadth First Search starts with one node and repeatedly visits neighbors. The key concept is a “frontier”, the boundary between the explored and unexplored areas. The frontier expands outwards from the original node until it has explored the entire graph.

The frontier queue is the frontier: a list/array of graph nodes (grid tiles) that need to be analyzed. It starts out containing only a single element, the start node. The visited flag on each node keeps track of whether we’ve seen it yet. It starts out as False everywhere except at the start node. Use the slider to see how the frontier expands:

How does the algorithm work? At every step, take a single element out of frontier and call it current. Then look for each of current’s neighbors, next. Add them to the frontier queue if they haven’t been visited before. Here’s some Python code:

frontier = Queue()
frontier.put(start)
visited = {}
visited[start] = True

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in visited:
         frontier.put(next)
         visited[next] = True

Now that you’ve seen the code, try stepping through the animation above. Pay attention to the frontier queue, the current node, and the set of next nodes. At each step, an element of the frontier becomes the current node, the neighbors are marked, and any unvisited neighbors get added to the frontier. Some neighbors will have been visited already so they don’t need to be added into the frontier.

It’s a relatively simple algorithm, and useful for all sorts of things, including AI. There are three main ways I use it:

  1. Mark all reachable nodes. This is useful if your map isn’t completely connected, and you want to know what’s reachable. That’s what we did above, with the visited field.
  2. Find paths from one node to all other nodes, or from all nodes to one node. This is what I used for the animated demo at the top of the page.
  3. Measure distances from one node to all other nodes. This is useful to know what’s in a given walking distance of a monster.

If you are generating paths, you will want to know which direction to move from every node. When you visit a neighbor, remember where you came from. Let’s rename the visited table to came_from and use it to keep track of the previous location:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

Let’s see what this looks like:

If you need distances, you can start with a counter set to 0 at the start node, and increment it each time you visit a neighbor. Let rename the visited table into distance and use it to keep a counter:

frontier = Queue()
frontier.put(start)
distance = {}
distance[start] = 0

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in distance:
         frontier.put(next)
         distance[next] = 1 + distance[current]

Let’s see what this looks like:

You can have both variables if you want to compute both paths and distances.

So that’s Breadth First Search. For Tower Defense style games, I’ve used it to find paths from all locations to a given location, instead of using A* repeatedly to separately find a path for enemy. I’ve used it to to find all locations within a certain walking distance of a monster. I’ve also used it for procedural map generation. Minecraft uses it for visibility culling. It’s a nice algorithm to know.

Next steps:

  • I have implementation notes with Python and C++ code.
  • If you want paths from a single location instead of to a single location, reverse the came_from pointers when following paths.
  • If you want paths to one of several locations instead of a single location, you can add edges to your graphs from each of your destinations to an extra destination node. The extra node won’t show up on the grid, but in the graph it will represent the destination.
  • Early exit: if you’re looking for a path to/from a single location, you can stop searching as soon as you find that location. I describe this in the A* article.
  • Weighted edges: if you need varying movement costs, Breadth First Search becomes Dijkstra’s Algorithm. I describe this in the A* article.
  • Heuristic: if you add a way to guide the search towards the goal, Breath First Search becomes Best First Search. I describe this in the A* article.
  • If you start with Breadth First Search and add early exit, weighted edges, and a heuristic, you get A*. As you might guess, I describe this in the A* article.