Flow Field 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^[1], 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.

To solve this problem we need either a vector field (also called a flow field) or a distance field (also called a Dijkstra Map). Enemies will move in the direction that gets them closer to the player:

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:
   • Greedy Best First Search^[2]
   • A*^[3] - commonly used in games
2. One source, all destinations, or all sources, one destination:
   • Breadth First Search^[4] - unweighted edges
   • Dijkstra’s Algorithm^[5] - adds weights to edges
   • Bellman-Ford^[6] - supports negative weights
3. All sources, all destinations:
   • Floyd-Warshall^[7]
   • Johnson’s Algorithm^[8]

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. This is sometimes called a flow field.

Let’s explore Breadth First Search, which is sometimes called “flood fill” (FIFO variant). Although graph search works on any node-and-edge graph^[9], 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 a list/array of graph nodes (grid tiles) that still need to be analyzed. It starts out containing only a single element, the start node. The reached flag on each node keeps track of whether we’ve seen it yet. Nodes start out as not reached   except the start node starts out as reached  . 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 find current’s neighbors. For each neighbor, if it hasn’t been reached yet, add it to both frontier and reached. Here’s some Python code:

frontier = Queue()
frontier.put(start )
reached = dict()
reached[start] = True

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

Now that you’ve seen the code, try stepping through the animation below. Pay attention to the frontier queue, the current node, and the set of neighbor nodes. At each step, an element of the frontier becomes the current node   →   , unreached neighbors are added to the frontier   →   , and reached neighbors are discarded    → X.

It’s a relatively simple algorithm, and useful for all sorts of things, including game AI^[10]. 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 reached 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 reached table to came_from and use it to keep track of the previous location:

frontier = Queue()
frontier.put(start )
came_from = dict()
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 vector field 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 reached table into distance and use it to keep a counter:

frontier = Queue()
frontier.put(start )
distance = dict()
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 distance field looks like:

You can have both variables if you want to compute both paths and distances. The two are related. The vector field (“flow field”) is the negative gradient^[11] (∇) of the distance field (“Dijkstra Map”), and you can calculate the vector by looking at which direction makes the distance decrease.

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^[12]. For flow field pathfinding, where units aren’t in the center of a grid cell, you can interpolate the flow arrows in each cell. Breadth First Search is 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. I have some examples of this here.
• 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 and also on its own page.
• 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, Breadth 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.