Blobs in Games: pathfinding

From Red Blob Games's Blog

Connected Components #

Occasionally someone will ask me how to implement Connected Components, which is useful for several things, including

• determining whether there's a path between two points; if there isn't, you can skip running pathfinding
• finding the islands/continents on a procedurally generated map

It's actually a clever use of Breadth First Search. Every time the queue is empty, you find an unvisited node and put it into the queue, and then run the loop some more. When you have no more unvisited nodes, you're done.

Labels: pathfinding

Pathfinding diagram improvements, part 2 #

In the last post I described improving the diagrams on my Tower Defense page. Once I finished that, I moved on to my other pathfinding pages, starting with the A* page.

Labels: design , making-of , pathfinding

Pathfinding diagram improvements, part 1 #

Back in April I wrote about some pathfinding diagrams I was unhappy with. Last month I wrote about reimplementing the diagramming code.

I started with the Tower Defense page. It's smaller than the A* page and I wanted to try out some ideas there before adopting them on the more popular page.

Labels: design , making-of , pathfinding

Reimplementing my pathfinding pages #

Back in 2018 I wrote about rewriting my hexagonal grid page. I had said “I'm generally not a fan of rewrites that have no end-user benefits”. I had started that rewrite because the code was making it hard to make diagram improvements that I wanted to make. As a side effect of the rewrite, I also made some performance improvements.

I've been wanting to make some diagram improvements to my A* page. While looking through the code I realized I was in the same situation as with the hex page. It was hard to make the changes I wanted to make because of the abstractions I had chosen. I decided to rewrite the most problematic abstraction, the Diagram class.

As a side effect of rewriting the Diagram class, I've improved page speed:

Labels: canvas , making-of , pathfinding

Tower Defense page: distance fields #

One reason I prefer having web pages instead of videos or academic papers is that they're easy to update over time. I'm still updating pages I wrote over 20 years ago.

Yesterday I was reviewing the Tower Defense page (2014) and decided the gap between the diagram at the top:

Labels: making-of , pathfinding

Updating C++ code on the A* implementation page #

In my articles I have to make a tradeoff between making things approachable and including all the little details you might need in a real project. I tend to err on the side of making things approachable, but that means people can get frustrated when trying to translate these topics into real code.

For my A* pages I have a “theory” page that describes the main concepts but doesn't go into detail with code, and then I have a separate “implementation” page that shows more of the code. I included some C++ code that is abstract and reusable, but I've been unhappy with it. I decided to simplify it a little bit:

• I dropped the template parameter for SimpleGraph because it's only ever used with char.
• Even though Location is a property of the Graph, the templated code for this is verbose and distracting so I made Location a separate template parameter.
• I switched from unordered_set and unordered_map to set and map; in practice you might prefer a hash table or an array, depending on the location type, but it's hard to pick one of these that's best for all cases.
• I dropped some of the reference and const parameters.
• I switched from set.count() to set.find() to test membership.
• I wrote out explicit types instead of using auto.
• I used std::xyz instead of using to omit the std:: namespace.

I have mixed feelings about most of these, and went back and forth a few times before deciding I'm overthinking it and just going with my gut.

Before:

template<typename Graph>
void dijkstra_search
  (const Graph& graph,
   typename Graph::Location start,
   typename Graph::Location goal,
   unordered_map<typename Graph::Location, typename Graph::Location>& came_from,
   unordered_map<typename Graph::Location, double>& cost_so_far)
{
  typedef typename Graph::Location Location;
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;
  
  while (!frontier.empty()) {
    auto current = frontier.get();

    if (current == goal) {
      break;
    }

    for (auto& next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (!cost_so_far.count(next) || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        came_from[next] = current;
        frontier.put(next, new_cost);
      }
    }
  }
}

After:

template<typename Location, typename Graph>
void dijkstra_search
  (Graph graph,
   Location start,
   Location goal,
   /* out */ std::map<Location, Location>& came_from,
   /* out */ std::map<Location, double>& cost_so_far)
{
  PriorityQueue<Location, double> frontier;
  frontier.put(start, 0);

  came_from[start] = start;
  cost_so_far[start] = 0;
  
  while (!frontier.empty()) {
    Location current = frontier.get();

    if (current == goal) {
      break;
    }

    for (Location next : graph.neighbors(current)) {
      double new_cost = cost_so_far[current] + graph.cost(current, next);
      if (cost_so_far.find(next) == cost_so_far.end()
          || new_cost < cost_so_far[next]) {
        cost_so_far[next] = new_cost;
        came_from[next] = current;
        frontier.put(next, new_cost);
      }
    }
  }
}

The code isn't as fast but I hope it's a little easier to read. I added a section at the end with the faster code.

My goal is to show how the algorithms work, and not to write reusable library code. That's not what I'm good at. Whenever I try to show code, I get into these messes. I hope the code I have is a reasonable starting point for anyone who's writing their own instead of using a library.

This year I'm trying to iterate more and publish things more often. Take a look at the updated A* implementation page and let me know what you think. I'll add suggestions to the Trello page.

Labels: pathfinding

Minor A* page improvements #

Labels: making-of , pathfinding

Updating my Introduction to A* #

One of the things that's bothered me about my Introduction to A* page and also my older A* pages is that I use grids everywhere. I fear that some of my readers will think that A* is only for grids or that it's best with grids. In my opinion it's worst when it is given grids, especially grids where every step has the same movement cost.

I decided the simplest thing I could do would be to change the grid map at the top of the page. That's the first impression a reader gets. Instead of showing non-grid maps halfway down the page, I should show a map that's not a grid. That way the reader immediately sees that we're not solving a grid problem. This was the first map on the page:

I took some graph paper and came up with a polygon version of this map. I hand-coded it and got the A* page to show it:

Although making the initial version of this map with pen and graph paper wasn't too bad, iterating was quite a pain. I decided to make a quick & dirty tool to edit the shapes. I wanted to edit the graph connectivity too but didn't want to spend more than an hour writing the tool, so I didn't implement that. I put the connectivity in manually.

The tool helped a lot! I made it output JSON, and then I copied-and-pasted that JSON into my A* page, where I wrote some code to turn that into the diagram. I spent a few hours on that map and also several others. The tool made it so much easier to edit maps that I ended up making more maps for the page.

After I had this new map up, the next step was to add a section to the page that described graphs. Although I have a link to another page that describes graphs, I think the input and output to an algorithm are too important to not explain on the main page.

I had implemented the A* diagrams with layers (see this); I was able to easily add new layers to show graph nodes and graph edges. With this I made a new diagram:

I wanted to demonstrate two things with pathfinding graphs:

Completely different game maps might have similar pathfinding graphs. I drew a game map based on StarRaven's cartography brushes that shared the same pathfinding map as the main example.

The same game map can be represented by different pathfinding graphs. I added two more pathfinding graphs for the same game map:

Comparing these, you can see how A* has to do a lot more work when the pathfinding graph is a grid than when the pathfinding graph is a navmesh or waypoint graph. If you're looking to optimize pathfinding on a grid, the first thing to try is to construct a non-grid pathfinding map.

With all of the new content on the page, I also wanted to simplify some of the other parts of the page. I decided that the contour maps were the least valuable concept, and removed most of the contour map diagrams. I think it's an interesting way of looking at things, but I was never quite happy with them, and they probably belong on an advanced level page, not on this introductory page.

While testing on iPhone and Android, I realized that I had never finished a touch version of the drag-and-drop maps. Until now, it didn't matter, because the diagrams were grid-based, and I had a touch version of the grid code. I had to fill in the non-grid touch event handlers. It doesn't work that well but it's good enough for now.

I'm much happier with the page now, although I still have some work to do on the wording. Take a look! There's still more I want to improve on this page.

Labels: making-of , pathfinding

Optimizing A* for grid maps #

One thing that annoys me about my own A* pages is that they use grids for the examples. A* is not restricted to grids. A* works on any directed graph. A* on uniform grids is often slow, so people have come up with various ways to make the algorithm faster. I feel like the "right" thing to do is not to change the algorithm but to change the data.

Graph search is used when you want to make "global" decisions that involve potentially analyzing large parts of the map. You look ahead all the way to the end before you can decide anything. It's a waste to use it on "local" decisions that you can make without looking far ahead. Suppose you have this game map (from Baldur's Gate):

What's the easiest thing to do? Make each tile into a graph node:

This is a fine solution, but A* will take a while to find the paths. There are a lot of nodes to visit. Some algorithms will make A* faster by using a cheaper way to visit the nodes. However, it's even faster if you skip most nodes altogether. For any path on this map, almost all of steps can be decided locally, by just following a straight line. There's no need to give those nodes to A*. Instead of making every tile into a pathfinding graph node, give a smaller graph to A*:

You'll need to annotate the map with this graph, either manually in a level editor or automatically with a preprocessing algorithm. A* will run much faster on the tiny graph than the dense grid graph. If you're looking to optimize A* on a grid, consider changing the data before you consider changing the algorithm. Navigation meshes, visibility graphs, and hierarchical approaches are all worth a look.

I have a little more written here and here, but one of these days I will update my pages to put less emphasis on grids.

Labels: grids , pathfinding

Pathfinding on isometric grids #

People sometimes ask about pathfinding on isometric grids. This is the wrong way to look at it.

You're finding paths in the game world. Isometric is not part of the game world. Isometric is how you look at the game world. Consider the shortest path from New York to San Francisco. Does the shortest path depend on how you hold the map? No! The person looking at the map does not matter. The shortest path is the same no matter how you are looking at the map.

Labels: grids , pathfinding

New Introduction to A* page #

I've been working on updating my pathfinding articles with interactive diagrams. While doing so, I realized that I don't like the way I've presented information in my pathfinding articles. Instead of just updating them in-place, I'm writing new tutorials and will eventually figure out how to stitch everything together.

A big one I've been working on is the introduction to A*. I started writing these notes in 1997 and have updated them over the years. The past few months I've been working on a replacement for this page. The page compares Breadth First Search, Dijsktra's Algorithm, Greedy Best First Search, and A*. Differences from the old page:

• All the diagrams are interactive (of course)
• I mention non-grids a little more (still not enough)
• I use contour lines to compare the algorithms (not sure if this will make sense to people)
• I show working Python code for each of the algorithms
• I have supplemental material that includes the helper functions and classes needed for the search algorithms
• I give some guidance on which algorithm to use

There are lots of little things (smoother animations, touch screen support, better code highlighting, better contour line visualization) that remain, but I decided to publish it 90% complete instead of delaying it to polish all those little details. Take a look at the new introduction and let me know what you think. Is it understandable? Do the contour lines help? Is it enough to help you implement A* yourself?

Labels: pathfinding

Dijkstra's Algorithm and reprioritizing nodes #

I'm working on a tutorial showing how Breadth First Search, Dijkstra's Algorithm, Greedy Best-First Search, and A* are related. I'm focusing on keeping the code simple and easy to understand. {Note: this blog post is a shorter version of a page on my site}.

While tracking down a bug in my Dijkstra's Algorithm code, I realized I had forgotten to implement the "reprioritize" case. That led me to wonder why my code seemed to work without handling that case. It turns out that case is never triggered by the graphs I'm searching over. Let me explore this …

Labels: pathfinding , programming

Pathfinding algorithms on grids #

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.

Labels: pathfinding

Graph theory for pathfinding #

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: grids , pathfinding

Pathfinding for Tower Defense games #

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

Diagrams on my pathfinding pages #

My A* pages have some diagrams on them that look like this:

Colorful! Pretty! But what do the colors actually mean?

Labels: making-of , pathfinding