The usual pathfinding algorithms I use — Breadth First Search, Dijsktra's Algorithm, A* — run on graphs. In my previous post I described how grids can be viewed as graphs. Most of the time, pathfinding on grids is fine. However, if you need more performance, grids contain additional structure that standard graph algorithms don't take advantage of. I wrote up some notes about this, either transforming your grid into a smaller graph, or modifying the pathfinding algorithm to harness the structure of grids. It's not something I've had to do in my own projects so if you have additional references or words of advice, I'd love to hear how I can improve that page.

While updating my pathfinding pages, I realized that although I cover graph-based pathfinding algorithms, I don't actually explain what graphs are or why we use them. So I wrote a short tutorial on graphs and grids.

Labels: ,

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.

Popular Posts