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: