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:
- One source, one destination:
- One source, all destinations, or all sources, one destination:
- 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) start.visited = True while not frontier.empty(): current = frontier.get() for next in current.neighbors(): if not next.visited: next.visited = True frontier.put(next)
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.
- 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.
- 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.
- 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. This is two additional lines of code:
frontier = Queue() frontier.put(start) start.visited = True start.came_from = None while not frontier.empty(): current = frontier.get() for next in current.neighbors(): if not next.visited: next.visited = True next.came_from = current frontier.put(next)
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. This is two additional lines of code:
frontier = Queue() frontier.put(start) start.visited = True start.distance = 0 while not frontier.empty(): current = frontier.get() for next in current.neighbors(): if not next.visited: next.visited = True next.distance = current.distance + 1 frontier.put(next)
Let’s see what this looks like:
If you further restrict the nodes you put into the queue to only those that are less than N, you can find all tiles that are walkable in N steps or less.
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. It’s a nice algorithm to know.
- To implement Breadth First Search, don’t use the sample code above without making minor modifications. I describe the implementation here, and give complete programs you can try out.
- If you want paths from a single location instead of to a single location, reverse the
came_frompointers 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.
- Weighted edges: if you need varying movement costs, Breadth First Search becomes Dijkstra’s Algorithm.
- Heuristic: if you add a way to guide the search towards the goal, Breath First Search becomes Best First Search.
- If you start with Breadth First Search and add early exit, weighted edges, and a heuristic, you get A*.