Pathfinding for Tower Defense games

From Red Blob Games's Blog

In a Tower Defense game, you have lots of units that all go to the same place. Instead of repeatedly running a pathfinding algorithm like A*, in some games you can run pathfinding once to all locations, and then have all enemies move along those paths.

I wrote an article about using Breadth First Search to solve pathfinding for Tower Defense.

Things I wanted to experiment with, as I explore how to use interactive diagrams on my pages:

• Sharing: At first, I made each diagram separate, but then I found myself annoyed that edits to one map didn't affect the others. I changed it all to share all state, but then I found that when I ran the search animation for the first diagram, I'd miss the other animations, since they're off the page. So I ended up sharing the graph configuration, but not the search process. Does this behavior match what you want?
• Code Correspondence: I wanted to animate the sample code, showing how it affects the graph. However, that was enough work that I decided to postpone it. Instead, I took a simpler step of color coding the key variables in the algorithm and color coding the diagram with the same colors. What do you think?
• Simplex to Complex: I wanted to show the simplest version of the algorithm first, and then work my way up to more complex algorithms. In this article I show Breadth First Search with only a single destination, and only a grid. I then add parent pointers and distances. In future articles I'll add edges weights (which will lead to Dijkstra's Algorithm), heuristics (Greedy Best First Search and A*), and non-grid graphs. Do you prefer the three diagrams of variants of Breadth First Search separated out, or would you rather have them all presented at once?

While working on it, I ended up spending too much time on tangents:

• Non-grid graphs: too many of my pages use grids, but A* and other graph search algorithms work great on other graphs too. I started thinking about other types of graphs and how to incorporate them into my pathfinding pages. I get distracted easily. I ended up writing all these ideas down for later.
• Exterior corner waypoints: I believe the optimal waypoints for grids will all be at exterior corners. I sketched out a simple way to find these and connect them up into a graph, but I don't have a proof, nor an implementation. That's for a future blog post.

I spent longer than I wanted to spend on this article, but I think it gives me a good foundation for a series of articles, which I'll eventually link together into a new guide to pathfinding algorithms.

Here's the article.

Labels: pathfinding