Open Problems of A* for Any Angle Pathfinding

In this article I will explore any-angle pathfinding using A* algorithm. A classic game development problem that also happens to have direct applications in robotics (after all robots need to plan paths like game characters do) and has nice mathematical models. It is also known as Euclidean shortest path problem.

So what is it all about? Given some Euclidean space (let's say a 2D game map) and two points in that space (where characters is and where we want it to be), we want to find the shortest path between those two points. Why can't we go in a straight line? Usually there are obstacles in the way and we want to avoid them without making the path longer than necessary.

How did I end up here?

The whole exploration was inspired by a GDC 2011 talk where James Anhalt described how the pathfinding in StarCraft 2 works. I got very curious and wanted to recreate it myself.

The main takeaways from the talk are:

• They build a dynamic navmesh calculating constrained Delaunay triangulation. They first calculate and cache it for the map in its initial state (static obstacles) and then re-run from there any time a building is added or destroyed.
• They run a classic A* on the navmesh and then smooth the path using the funnel algorithm.
• Units are not taken into account when building the navmesh. Walking around moving entities is handled by steering model based on Boids by Craig Reynolds.

StarCraft 2 map editor showing debug view of the pathfinding mesh. Source.

Initial thoughts

What is generally important about designing pathfinding, and it applies especially to games, is that it's not just about finding the shortest path. It's first of all about finding a path that seems the most reasonable to the player. The player is essentially handing off the task of moving unit(s) from A to B to the game's AI and will only feel comfortable using it if it takes decisions that the player either would take themselves or at least finds reasonable.

RTS games, conveniently, are inherently 2D games with 3D view. Everything tends to happen on one plane (sometimes 2, when flying units are involved but it doesn't complicate much). Which means that for a 3D RTS we are essentially solving the same problem as for a 2D non-grid game.

Context

Before we dive deeper, here are some random relevant links:

• A* (1968) – absolute classic of pathfinding algorithms. Can be seen as an extension of Dijkstra's algorithm with added heuristic function that helps to guide the search towards the goal. What people working with A* often confuse about it is that it's in its core a graph traversal algorithm and absolutely is not limited to grids. If you see anyone claim so – run!
• Fixing pathfinding Once and For All (2008) – a (now) classic article that discusses many important points about pathfinding.
• Theta* (2010) – based on A*. The neighbor nodes are not just the ones directly adjacent to the current node, but also the ones that are visible from the current node.
• Simple Stupid Funnel Algorithm (2010) – an absolute classic, widely quoted and recommended. Algorithm takes an array of points, called portals, which form a corridor that encloses the path. The points are in order: start x2, left, right, left, ..., end x2. Another name for this algorithm is string pulling and this describes best what it does – it acts as if we are pulling a string to tighten it around corners of the corridor.
• Boids (1986) – a simple but genius mathematical model describing behavior of flocking animals, like birds. Used by hundreds of games to simulate group behavior.

Short introduction to A*

If you are here there are some chances you are already familiar with A*. If not, the good news is that there are a lot of great source to learn about A* out there. My favorite one that I have been going back to over the past decade is Red Blob Games.

But fortunately, A* implementation can be made relatively short and I can fit the whole source code here (apart form a PriorityQueue implementation but that one has even more sources available):

export function findRoute(start: Node, goal: Node) {
  const frontier = new PriorityQueue<Node>();

  if (start === goal) {
    return [start, goal];
  }

  frontier.enqueue(start, 0);

  const cameFrom = new Map<Node, Node>();
  const costSoFar = new Map<Node, number>();

  costSoFar.set(start, 0);

  while (frontier.getSize() > 0) {
    const current = frontier.dequeue()!;

    if (current === goal) {
      break;
    }

    for (const n of current.neighbors) {
      const newCost =
        costSoFar.get(current)! + current.position.distance(n.position);

      if (!costSoFar.has(n) || newCost < costSoFar.get(n)!) {
        costSoFar.set(n, newCost);
        const priority = newCost + heuristic(n.position, goal.position);
        frontier.enqueue(n, priority);
        cameFrom.set(n, current);
      }
    }
  }

  return reconstructPath(cameFrom, goal);
}

function heuristic(a: Vec2, b: Vec2): number {
  return a.distance(b);
}

function reconstructPath(cameFrom: Map<Polygon, Polygon>, start: Polygon) {
  let current = start;
  const totalPath: Array<Polygon> = [current];

  while (cameFrom.has(current)) {
    const parent = cameFrom.get(current)!;
    totalPath.push(parent);
    current = parent;
  }

  return totalPath.reverse();
}

The effectiveness of the algorithm comes from prioritizing nodes that appear closer to the goal.

Approaches to pathfinding

Almost all pathfinding algorithms operate on graphs. But there are many ways to represent a map as a graph. A lot depends on the problem and the algorithm used. Most but not all try to minimize the number of nodes and edges in the graph.

Here are some popular approaches:

The goal of the graph representation is to limit size of the search space (less nodes, less edges) and provide as good as possible representation of the map. The graph should essentially be only as detailed as needed for the pathfinding to not lose any quality.

Grid

The map is divided into a grid of cells and each cell is a node in the graph. The neighbors of each cell are the cells that are directly adjacent to it.

Rules for travelling diagonally can vary. Here I forbid cutting corners over obstacles.

As we can clearly see, the grid is very simple but also very ineffective and redudant structure in this case. We can see how many tiles are not needed and don't introduce anything important to the search. They are absolutely reasonable for grid-based games, where characters will end up stepping through each of the cells. It's just that they are not well suited for any-angle pathfinding.

Triangles

The map is divided into triangles (often result of triangulation; see my previous blogpost to learn how to do that: Constrained Delaunay Triangulation from a Paper). There are several ways to represent the graph with triangles:

• nodes can be the centers of the triangles
• midpoints of the edges
• the vertices of the triangles or a combination of those.

In the triangle representation (and any other polygon one), postprocessing becomes an important step. The path will almost always look unnatural and contain weird zigzags. But it's not their goal. As long as the final result matches expectations – they are perfectly fine as an intermediary step. The funnel algorithm is a great and quite standard way to make the path smoother.

Convex Polygons

In this method the map is divided into polygons. Most often additional constraint is set: they have to be convex. What it achieves is that within each polygon we can draw a straight line between any two points, meaning that there are no turns within them that we would have to consider. Which means we don't need to make our navigation graph any more detailed to be able to easily avoid generating paths going through obstacles.

Funnel algorithm can also be used here. For it to work, we need two lists of points that define a corridor which the path goes through. It is a bit more tricky than with triangles: we need to find the starting point in the first polygon. Then going counter-clockwise we find the left side and clockwise the right side. The moment both sides start overlapping with the next polygon – we can append our sides so far to the final corridor and move onto the next polygon.

Visibility Graph

Instead of subdividing the map, for each vertex of constrained edges we find other vertices that are visible (i.e. a straight line does not cross any other edge) and connect them into a graph.

This can at times be very effective. As we can see it doesn't even need a postprocessing step since the path is already smooth. But preparation of the visibility graph is quite computationaly expensive – we need good spatial data structures for storing the edges but still it's often hard to avoid $O(n)$ operation as two points on opposite sides of the map will likely cross quite many other edges. Same goes for adding or removing edges – potentially many new lines of sight are opened or closed.

Playground

Now back to the initial problem: recreating the StarCraft 2 pathfinding. Recently I wrote an article about about Constrained Delaunay Triangulation from a Paper and as with many of my blog posts, it was meant to help here.

I implemented the three triangle-based methods described above. You can play with them in the demo. You can drag the start and end points to see different generated paths. You can switch between different graph interpretations of the triangulated map.

Especially interesting cases are:

• paths that are supposed to go through the obstacle cluster in the bottom-left part.
• paths starting or ending in the triangles neighboring the edges.
• paths ending in different parts of the same large triangle (see how for some methods it makes a huge difference).

There is something that you will probably quickly notice: each of the methods can be broken. And they can be broken in a way that is not easy to fix. Let's go through the problems I have noticed.

Variant with edges naturally tends to 'hug' walls. Together with the need to travel to the nearest vertex in the beginning and the end, sometimes resulting path goes around a set of obstacles which after smoothing the path gives clearly suboptimal result. And since many obstacles are squares, from the path point of view it doesn't matter along which edge we go around them, but for smoothing it is critical.

Centroid method is prone to zigzags. When there are a lot of wide triangles between the start and the goal, the path in the navigation graph will be very zigzaggy, making the A* search see it as vey long even when the smoothed path is actually the shortest.

Midpoint method works well to avoid the zigzag problem as it jumps between centers of the edges, which deals perfectly with strips of triangles having centers on opposing sides. However, the paths can still be suboptimal when the ideal path involves walking through a giant triangle – then going to the center of the edge takes farther from the goal.

Tricks I tried that did not work

• I tried subdividing the other edges so that triangulation does not have skinny long triangles. This does help with the edges but ultimately it's not possible to avoid huge triangles in the middle of the map, which means that this helps only partially.
• I tried to snap start and end points to the centers of their triangles. Since sometimes middle of a large triangle is far from centers of its edges, maybe making it a little bit more abstract would help? Well, this solves some edge cases where start or the goal are in a corner of a triangle, but also it introduces other problems – sometimes connecting two corners more directly is a feature not a bug.

Observations

It seems like there's no perfect method to make simple A* work in all cases. I discard grid entirely as it's just not suited for any-angle pathfinding. The visibility graph offers high quality paths but involves a ton of edge-edge intersection calculations which are hard to optimize and come at a big memory cost.

Polygons in my earlier experiments seemed to solve the zizzag problem but involved a ton of postprocessing and preparing for funnel path smoothing turned out to be a very involved computation so I abandoned that path.

This generally leaves the variations of the triangulation methods. And as we can see in the demo – none of them is perfect. Ultimately the problem in every case comes from the fact that the found paths are only an approximation of the real final path (after smoothing). And each method happens to run into cases where the shortest approximated path is not the shortest one post-smoothing.

Conclusions

The conclusion is: simply taking a triangulated map and running A* on some straightfoward navigation graph is not enough to find shortest paths. Using fixed points for nodes of the graph always has edge cases where the shortest real path is not the shortest one according to that graph.

A potentially correct solution would require taking into account the actual path of so far explored nodes, but in my attempts it always led to infinite loops due to instability of the graph.

As of today, there exist a possibly better suited algorithm for the task, Polyanya (2017), which solves exactly this problem – any angle pathfinding.

But what's puzzling here is that creators of StarCraft 2 figured it out in 2010, using a very similar method. But in their case it worked.

Problem remains unsolved for me. If you have worked on pathfinding in the past and have some insights, I would love to hear them. Reach out to me on Twitter or Reddit.