Search for the way in tower defense games

[Approx. Per.: In the original article there are interactive demos that I duplicated using video. For greater clarity, I recommend to study the examples in the original.]

In the games of the Tower Defense (TD) genre, many enemies strive to get to one point. In many TD games, there is a predetermined path or several paths. In some, including the classic Desktop Tower Defense, you can place towers in arbitrary locations, and they become obstacles that affect the paths of enemies. Launch the demo and click on the map to build or remove walls:



How to implement it?
')
To find the shortest path between two points, search algorithms on graphs are often used, for example, search A *. You can use it for each enemy to find the path to the goal. There are many different search algorithms for graphs that can be used in games of this genre. Here are classic examples:

1. One starting point and one ending point :
   • Search for the first best match
   • A * - widely used in games
2. One starting point and all end points or all starting points, one end point :
   • Search wide - ribs without weights
   • Dijkstra's Algorithm - Adds Weight to Ribs
   • Bellman-Ford algorithm - has support for negative weights
3. All start and end points :
   • Floyd-Warshall Algorithm
   • Johnson's algorithm

In games like Desktop Tower Defense, there are many enemy positions (starting points) and one end point for all of them. Therefore, they are in the category of all starting and one end points . Instead of performing A * for each enemy, you can run the algorithm once, and it will calculate the path for all enemies. Moreover, it will calculate the shortest path from any place, so when enemies bypass each other or new enemies are created their paths will already be calculated.

Let's look at a wider search algorithm, sometimes called a fill (FIFO variation). Although the graph search works for any graph with nodes and edges , in my examples I use a grid of squares. Grids are a special case of graphs. Each cell of the grid is a node of the graph, and the boundaries between the cells of the grid are the edges of the graph . I am looking at graphs without grids in another article .

The search in width starts from one node and goes through all the neighboring ones in sequence. The key concept here is the “frontier” - the boundary between the studied and unexplored areas. The boundary extends outward from the source node until it examines the entire graph.

The frontier queue is the boundary: a list / array of nodes of the graph (grid cells) that need to be analyzed. At the beginning it contains only one element, the start node. The visited flag of each node allows you to track whether we checked it. At the beginning, for every node except start, it is False. Drag the slider to observe the expansion of the border:


How does the algorithm work? At each step, one element from the frontier is taken and called current . It then searches each of its current neighbors, called next . If they have not been visited ( visited ) before, they are added to the frontier queue. Here is a sample 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 

After reviewing the code, try step by step to study the animation above . Notice the frontier queue, the current node, and the many nodes next . At each stage, the border element becomes the current node, neighbors are marked, and all unvisited neighbors are added to the border. Some neighbors have already been visited, so they are not added to the border.

This is a fairly simple algorithm, and it is useful for many applications, including artificial intelligence . I use it in three main ways:

1. Mark all the nodes that can be reached. This is useful if the card is not fully connected, and you want to know which points you can reach. This is what we did above using the visited field.
2. I find paths from one node to all the others, or from all nodes to one. This is the method I used for the animated demo at the beginning of the article.
3. I measure the distance from one node to all the others. This is useful to know what is within the walking distance of the monster.

If you generate paths, then you need to know in which direction to move from each node. When visiting a neighbor, you need to remember where you came from. Let's rename the visited table to came_from and use it to store 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 it looks like:



If you need distances, you can start with a counter whose value is 0 at the start node and increase it each time you visit a neighbor. Let's rename the visited table to distance and use it to store the 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 we did:



You can leave both variables if you need to calculate both paths and distances.

So it was a search wide. In the games of the Tower Defense genre, I used it to find paths from all points to the desired point instead of consistently using A * to search for the path of each enemy separately. I used it to search for all points within the walking distance of the monster. I also used it for procedural map generation. In Minecraft, it is used for clipping the scope . This algorithm is worth knowing.

Next steps:

• I have implementation notes with Python and C ++ code.
• If you need to limit the paths from one point, and not to one point, then turn the came_from pointers as you came_from along the paths.
• If you need paths to one of several points, and not to one point, you can add edges to the graphs from each end point to an additional end node. The additional node will not be visible on the grid, but in the graph it will represent the end point.
• Early exit: if you are looking for a path to / from one point, you can interrupt the search immediately after this point is found. I explain this in an article on A * .
• Ribs with weights: if you need to use different cost of passing points, then the search in width turns into Dijkstra's algorithm. I describe this in an article on A * .
• Heuristic approach: if you add a way to direct the search towards the target, then the wide search turns into a search for the first best match. Read more about this in the article about A * .
• If you start with a wide search and add an early exit, edges with weights and a heuristic approach, you get A * . As you might guess, I describe this algorithm in an article on A * .

Implementation

Internal state

This article uses the external state of the visited / came_from / distance sets and hash tables. You can also use the internal state in which data is stored within the data structure of the nodes of the graph. Why use external, not internal data? Although internal data is slightly faster (the implementation does not use a hash table), external ones are “cleaner” because they do not change the data structure of the graph in the search. In addition, they support multiple simultaneous search operations, either multi-threaded, or implemented through cororutine. Here is an example of a node with the internal flag of the visited :

 class Node: def __init__(self, name): self.visited = False self.name = name self._neighbors = [] def neighbors(self): return self._neighbors 

Here is an example graph:

 A = Node("A") B = Node("B") C = Node("C") D = Node("D") E = Node("E") A._neighbors = [B] B._neighbors = [A, C] C._neighbors = [D] D._neighbors = [E] E._neighbors = [] start = A 

If the internal state is used, then to re-execute the algorithm, the visited flag must be set to False again. We can do this before executing the algorithm:

 ALL_NODES = [A, B, C, D, E] frontier = Queue() frontier.put(start) for node in ALL_NODES: node.visited = False start.visited = True while not frontier.empty(): current = frontier.get() callback(current) for next in current.neighbors(): if not next.visited: next.visited = True frontier.put(next) 

Download the sample program .

Or we can set the value after the execution of the algorithm, keeping a list of all visited nodes:

 frontier = Queue() frontier.put(start) start.visited = True visited_nodes = [start] while not frontier.empty(): current = frontier.get() for next in current.neighbors(): if not next.visited: next.visited = True visited_nodes.append(next) frontier.put(next) for node in visited_nodes: node.visited = False 

Download the sample program .

How to choose one or another approach? In fact, this is not very important, because we visit all the nodes. If all nodes are visited, the first approach is slightly faster. However, if you use the early exit , then all nodes are not visited, and then the second approach will be much faster. The first method each time passes through all nodes. The second method passes only through the nodes that have been visited.

Node identifiers

(Note: in most cases, this optimization is not required.) For the hash table approach to work, the nodes must be hashed. Or you can give each node an integer identifier. After that, you can use a bitmap to store the visited and a regular int array to store the distance and came_from .

If you are writing code in C or C ++, you can leave the distance and came_from uninitialized (potentially this is a great advantage!). You only need to initialize the bitmap, compressing 64 identifiers into one (long) int . The value in the distance or came_from initialized only if the bit is set. You can either put distance / came_from arrays on the stack, if it has enough space, or use statically allocated arrays that are not initialized again after each search. Carefully weigh the costs of initializing the visited bitmap and the costs of using a hash table. If the part of the visited nodes is small during each search, it may be better to use a hash table.