A Short and Direct Walk with Pascal’s Triangle | by Rhys Goldstein | Nov, 2022
How pathfinding algorithms can be improved by counting paths
Classic pathfinding algorithms like Dijkstra’s Algorithm and A* are used to generate travel routes in applications such as video games, mobile robotics, and architectural design. Despite the popularity of these algorithms, the paths they produce rarely go straight. In this article, you’ll learn how to compute highly direct paths using a counting technique inspired by Pascal’s Triangle. It’s an idea my colleagues and I developed and recently published in the Journal of Artificial Intelligence Research [1]. With the simple step of counting paths, you can overcome a long-standing problem with traditional pathfinding.
The need to compute short and direct paths arises in a variety of disciplines. Building designers use pathfinding tools to analyze how far people will have to walk to get to the nearest emergency exit. Some architects go a step further and simulate crowds of people evacuating a building, which requires escape routes to be generated for every building occupant. Video game developers rely on pathfinding algorithms to determine how AI-controlled agents should travel from one location to another on a map.
One of the simplest and most popular ways of implementing pathfinding is to represent a map as a grid, then apply a classic search method like Dijkstra’s Algorithm or A* to find a grid path with the shortest possible length. The animation below shows an example of a shortest grid path from a starting location A to a destination B. The shaded grid cells represent walls or other obstacles that must be avoided. We’ll assume for the time being that each move along a grid path is a step in one of 4 directions: north, south, east, or west.
The path above is one of 400 shortest grid paths from A to B. It’s also a highly indirect path. It fails to make use of obvious straight-line shortcuts. It deviates significantly from the direct route a person would take in real life if they were not obligated to walk according to the grid. In the Red Blob Games tutorial on implementing A*, Amit Patel points out that these “ugly paths” are a widely encountered problem.
The most common question I get when people run pathfinding on a grid is why don’t my paths look straight?
The ugly path problem can be tackled in a brute force manner by testing up to hundreds of thousands of possible straight-line shortcuts during an A* path search. An algorithm called Theta*, which was published in 2010, uses this approach [2]. In order to avoid all these line-of-sight tests, our strategy is to select a shortest grid path that happens to approximate a direct route. Of the 400 shortest grid paths in our example, the path below is the one we would select.
This central grid path isn’t actually shorter than the indirect grid path we saw previously. Both paths require 15 grid moves, and each move is one grid spacing in length. However, the central path is a better approximation of the smooth path a person would take in real life. One way to solve the ugly path problem is to find a simple and efficient method for producing central grid paths. Enter Pascal’s Triangle.
In 1655, the French mathematician Blaise Pascal published Traité du Triangle Arithmétique, a treatise on the number pattern that later became known as Pascal’s Triangle.
Pascal’s analysis of the triangle inspired Newton’s contributions to the binomial theorem as well as Leibniz’s work on infinitesimal calculus. Nevertheless, we should acknowledge that Pascal was not the first to come up with the pattern. It had been discovered roughly 1000 years ago in both Persia and China, and possibly more than 2000 years ago in India [3].
Pascal’s Triangle is formed by placing a 1 at the apex and along the two diverging sides. Every other number is generated by adding two preceding numbers. The animation below shows the procedure in action for the first 5 rows.
Pascal’s Triangle is famous for its many fascinating properties. One such property is that every number in Pascal’s Triangle can be interpreted as a path count: the number of shortest grid paths from the apex of the triangle to that number’s location. For example, the hexagonal grid cell at the bottom center of the animation has the number 6, and there are exactly 6 shortest grid paths from the top cell of the triangle to that bottom middle cell. The animation shows a hexagonal grid, but the property also holds when Pascal’s Triangle is drawn on a square grid as in the previous diagram by Blaise Pascal.
A number of online articles and videos explain how to use Pascal’s Triangle to count the number of paths on a grid. It turns out we can go a step further. Pascal’s Triangle shows us not only how to count all possible paths, but also how to select one of the most direct of these paths.
The new pathfinding approach works by counting the number of shortest grid paths that traverse each grid cell, and then selecting the grid cells with the highest counts.
The first step is to count paths in the forward direction. As illustrated below, we begin by assigning the number 1 to the starting location A. Whenever a grid cell is assigned a number, that number is copied forward to the next cell along any shortest grid path. When multiple paths converge, the numbers are added. Similar to Pascal’s Triangle, the result is that every grid cell contains the number of shortest grid paths from A to that cell. For example, there are 12 shortest grid paths between A and the cell labelled 12 in the animation. Notice that there are 400 shortest grid paths between A and B.
Next, we repeat the procedure in the backward direction. So now B is assigned the number 1, and we copy and add numbers until we get to A. In the end, every grid cell contains the number of shortest grid paths from B to that cell. Notice that even though we reversed the direction, there are still 400 shortest grid paths between the two endpoints.
The next step is to take these two sets of path counts, and multiply them to produce a single set of traversal counts. To understand this concept, look at the animations above and find the unique grid cell that has a path count of 12 from A and 20 from B. The 12 paths on one side and the 20 paths on the other can be joined in 12 times 20 different combinations, meaning that there are 240 paths that traverse this grid cell en route from A to B. You’ll see below that the traversal count for this cell is 240. The animation shows the traversal count being calculated for every grid cell.
The final step is to start at A, then repeatedly select the next grid cell that leads towards B and has the highest traversal count. The animation below displays the traversal counts and shows how the path is generated.
The output of the approach is a central grid path, a highly direct shortest grid path that approximates the route a person would likely walk.
To see the difference path counting makes, below is an arbitrary or “ugly” shortest grid path produced by a typical implementation of A*. The map is from the Dragon Age: Origins benchmark dataset [4]. The grid path exhibits large, unnecessary zig-zags, and even the smoothed version of the path has obvious defects. Click on the image to take a closer look.
When A* is extended with path counting, the resulting central grid path adheres closely to sightlines as it crosses empty regions of the map. As shown below, the zig-zags are now as small as possible, and are easily removed by smoothing. On average, it takes about 40% longer to compute a central grid path than an arbitrary grid path. By contrast, switching from A* to Theta* will likely triple the computation time. As you can see, the added step of counting paths significantly improves the quality of the results.
You may notice that the central path above appears to approximate a taut path, the kind of path you’d end up with if you laid down a string and pulled it taut. This observation is in line with a theoretical property of central grid paths. Imagine we were to repeatedly compute a central path between the same endpoints, but at finer and finer grid resolutions. The central limit theorem suggests that this central path will eventually be rerouted to make use of any straight-line shortcuts, and that it will also converge on a taut path. In other words, central grid paths are perfectly direct in the limit.
The new approach can be referred to as central grid path planning, central grid-based pathfinding, or just pathfinding by counting. If you are interested in implementing the technique, below are some practical considerations to keep in mind. More detailed guidance can be found in the open access journal paper “Path Counting for Grid-Based Navigation” [1].
- Use Dijkstra or A* first, then count paths. The animated example in this article is a special case where every reachable grid cell is part of a shortest grid path. In general, it is a good idea to use Dijkstra’s Algorithm or A* to construct a Directed Acyclic Graph (DAG) of shortest grid paths. Once this is done, the path counting operations are performed on the DAG instead of the original map. Details can be found in Sections 3.1 and 3.2 of the paper. The bottom line is that pathfinding by counting is not an alternative to Dijkstra or A*, but rather a way of improving these classic pathfinding methods.
- Use logarithms to compute large path counts. Path counts grow exponentially with the size of the grid. So while there are a total of 400 shortest grid paths in our animated example, there could be more than 10 to the power of 400 paths in a real-world application. This means that even a 64-bit floating-point number could overflow if used to represent path counts directly. Fortunately, it is possible to work with path counts indirectly using logarithms. Section 3.2 of the paper describes this small but extremely important refinement of the approach.
- Allow diagonal moves if possible. In the animated example, grid moves are restricted to the 4 cardinal moves: north, south, east, and west. For higher quality results, it is best to also allow the 4 diagonal moves: northeast, northwest, southeast, and southwest. In that case, we must remember that diagonal moves are roughly 40% longer than cardinal moves. We must also be mindful of rounding errors, which may make equally short paths seem different in length. The examples in the journal paper assume both cardinal and diagonal moves are permitted.
- Smooth the final path if desired. It is common practice to smooth a grid path in a post-processing step, removing unwanted zig-zags and shortening the path. It turns out that path counting and path smoothing work well in combination. Section 3.3 of the paper demonstrates that smoothing central grid paths produces shorter travel routes than smoothing arbitrary shortest grid paths.
- Compare results with an existing implementation. There is at least one available central grid-based pathfinding tool at the time of writing, an architectural design tool my colleagues and I developed called SpaceAnalysis. Other implementations will hopefully appear as more people learn about the technique.
Path counting is a well-known procedure at the heart of Pascal’s Triangle. It’s also a practical way to obtain straighter and more direct travel routes from classic pathfinding algorithms. If you need a simple navigation method for a video game, an analysis tool, or perhaps even a mobile robot, check out the paper and start counting paths!
[1] R. Goldstein, K. Walmsley, J. Bibliowicz, A. Tessier, S. Breslav, A. Khan, Path Counting for Grid-Based Navigation (2022), Journal of Artificial Intelligence Research, vol. 74, pp. 917–955
[2] K. Daniel, A. Nash, S. Koenig, A. Felner, Theta*: Any-Angle Path Planning on Grids (2010). Journal of Artificial Intelligence Research, vol. 39, pp. 553–579
[3] C. Cobeli, A. Zaharescu, Promenade around Pascal Triangle — Number Motives (2013) [PDF], Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, vol. 56, no. 104, pp. 73–98
[4] N. R. Sturtevant, Benchmarks for Grid-Based Pathfinding (2012) [PDF], Transactions on Computational Intelligence and AI in Games, vol. 4, no. 2, pp. 144–148
How pathfinding algorithms can be improved by counting paths
Classic pathfinding algorithms like Dijkstra’s Algorithm and A* are used to generate travel routes in applications such as video games, mobile robotics, and architectural design. Despite the popularity of these algorithms, the paths they produce rarely go straight. In this article, you’ll learn how to compute highly direct paths using a counting technique inspired by Pascal’s Triangle. It’s an idea my colleagues and I developed and recently published in the Journal of Artificial Intelligence Research [1]. With the simple step of counting paths, you can overcome a long-standing problem with traditional pathfinding.
The need to compute short and direct paths arises in a variety of disciplines. Building designers use pathfinding tools to analyze how far people will have to walk to get to the nearest emergency exit. Some architects go a step further and simulate crowds of people evacuating a building, which requires escape routes to be generated for every building occupant. Video game developers rely on pathfinding algorithms to determine how AI-controlled agents should travel from one location to another on a map.
One of the simplest and most popular ways of implementing pathfinding is to represent a map as a grid, then apply a classic search method like Dijkstra’s Algorithm or A* to find a grid path with the shortest possible length. The animation below shows an example of a shortest grid path from a starting location A to a destination B. The shaded grid cells represent walls or other obstacles that must be avoided. We’ll assume for the time being that each move along a grid path is a step in one of 4 directions: north, south, east, or west.
The path above is one of 400 shortest grid paths from A to B. It’s also a highly indirect path. It fails to make use of obvious straight-line shortcuts. It deviates significantly from the direct route a person would take in real life if they were not obligated to walk according to the grid. In the Red Blob Games tutorial on implementing A*, Amit Patel points out that these “ugly paths” are a widely encountered problem.
The most common question I get when people run pathfinding on a grid is why don’t my paths look straight?
The ugly path problem can be tackled in a brute force manner by testing up to hundreds of thousands of possible straight-line shortcuts during an A* path search. An algorithm called Theta*, which was published in 2010, uses this approach [2]. In order to avoid all these line-of-sight tests, our strategy is to select a shortest grid path that happens to approximate a direct route. Of the 400 shortest grid paths in our example, the path below is the one we would select.
This central grid path isn’t actually shorter than the indirect grid path we saw previously. Both paths require 15 grid moves, and each move is one grid spacing in length. However, the central path is a better approximation of the smooth path a person would take in real life. One way to solve the ugly path problem is to find a simple and efficient method for producing central grid paths. Enter Pascal’s Triangle.
In 1655, the French mathematician Blaise Pascal published Traité du Triangle Arithmétique, a treatise on the number pattern that later became known as Pascal’s Triangle.
Pascal’s analysis of the triangle inspired Newton’s contributions to the binomial theorem as well as Leibniz’s work on infinitesimal calculus. Nevertheless, we should acknowledge that Pascal was not the first to come up with the pattern. It had been discovered roughly 1000 years ago in both Persia and China, and possibly more than 2000 years ago in India [3].
Pascal’s Triangle is formed by placing a 1 at the apex and along the two diverging sides. Every other number is generated by adding two preceding numbers. The animation below shows the procedure in action for the first 5 rows.
Pascal’s Triangle is famous for its many fascinating properties. One such property is that every number in Pascal’s Triangle can be interpreted as a path count: the number of shortest grid paths from the apex of the triangle to that number’s location. For example, the hexagonal grid cell at the bottom center of the animation has the number 6, and there are exactly 6 shortest grid paths from the top cell of the triangle to that bottom middle cell. The animation shows a hexagonal grid, but the property also holds when Pascal’s Triangle is drawn on a square grid as in the previous diagram by Blaise Pascal.
A number of online articles and videos explain how to use Pascal’s Triangle to count the number of paths on a grid. It turns out we can go a step further. Pascal’s Triangle shows us not only how to count all possible paths, but also how to select one of the most direct of these paths.
The new pathfinding approach works by counting the number of shortest grid paths that traverse each grid cell, and then selecting the grid cells with the highest counts.
The first step is to count paths in the forward direction. As illustrated below, we begin by assigning the number 1 to the starting location A. Whenever a grid cell is assigned a number, that number is copied forward to the next cell along any shortest grid path. When multiple paths converge, the numbers are added. Similar to Pascal’s Triangle, the result is that every grid cell contains the number of shortest grid paths from A to that cell. For example, there are 12 shortest grid paths between A and the cell labelled 12 in the animation. Notice that there are 400 shortest grid paths between A and B.
Next, we repeat the procedure in the backward direction. So now B is assigned the number 1, and we copy and add numbers until we get to A. In the end, every grid cell contains the number of shortest grid paths from B to that cell. Notice that even though we reversed the direction, there are still 400 shortest grid paths between the two endpoints.
The next step is to take these two sets of path counts, and multiply them to produce a single set of traversal counts. To understand this concept, look at the animations above and find the unique grid cell that has a path count of 12 from A and 20 from B. The 12 paths on one side and the 20 paths on the other can be joined in 12 times 20 different combinations, meaning that there are 240 paths that traverse this grid cell en route from A to B. You’ll see below that the traversal count for this cell is 240. The animation shows the traversal count being calculated for every grid cell.
The final step is to start at A, then repeatedly select the next grid cell that leads towards B and has the highest traversal count. The animation below displays the traversal counts and shows how the path is generated.
The output of the approach is a central grid path, a highly direct shortest grid path that approximates the route a person would likely walk.
To see the difference path counting makes, below is an arbitrary or “ugly” shortest grid path produced by a typical implementation of A*. The map is from the Dragon Age: Origins benchmark dataset [4]. The grid path exhibits large, unnecessary zig-zags, and even the smoothed version of the path has obvious defects. Click on the image to take a closer look.
When A* is extended with path counting, the resulting central grid path adheres closely to sightlines as it crosses empty regions of the map. As shown below, the zig-zags are now as small as possible, and are easily removed by smoothing. On average, it takes about 40% longer to compute a central grid path than an arbitrary grid path. By contrast, switching from A* to Theta* will likely triple the computation time. As you can see, the added step of counting paths significantly improves the quality of the results.
You may notice that the central path above appears to approximate a taut path, the kind of path you’d end up with if you laid down a string and pulled it taut. This observation is in line with a theoretical property of central grid paths. Imagine we were to repeatedly compute a central path between the same endpoints, but at finer and finer grid resolutions. The central limit theorem suggests that this central path will eventually be rerouted to make use of any straight-line shortcuts, and that it will also converge on a taut path. In other words, central grid paths are perfectly direct in the limit.
The new approach can be referred to as central grid path planning, central grid-based pathfinding, or just pathfinding by counting. If you are interested in implementing the technique, below are some practical considerations to keep in mind. More detailed guidance can be found in the open access journal paper “Path Counting for Grid-Based Navigation” [1].
- Use Dijkstra or A* first, then count paths. The animated example in this article is a special case where every reachable grid cell is part of a shortest grid path. In general, it is a good idea to use Dijkstra’s Algorithm or A* to construct a Directed Acyclic Graph (DAG) of shortest grid paths. Once this is done, the path counting operations are performed on the DAG instead of the original map. Details can be found in Sections 3.1 and 3.2 of the paper. The bottom line is that pathfinding by counting is not an alternative to Dijkstra or A*, but rather a way of improving these classic pathfinding methods.
- Use logarithms to compute large path counts. Path counts grow exponentially with the size of the grid. So while there are a total of 400 shortest grid paths in our animated example, there could be more than 10 to the power of 400 paths in a real-world application. This means that even a 64-bit floating-point number could overflow if used to represent path counts directly. Fortunately, it is possible to work with path counts indirectly using logarithms. Section 3.2 of the paper describes this small but extremely important refinement of the approach.
- Allow diagonal moves if possible. In the animated example, grid moves are restricted to the 4 cardinal moves: north, south, east, and west. For higher quality results, it is best to also allow the 4 diagonal moves: northeast, northwest, southeast, and southwest. In that case, we must remember that diagonal moves are roughly 40% longer than cardinal moves. We must also be mindful of rounding errors, which may make equally short paths seem different in length. The examples in the journal paper assume both cardinal and diagonal moves are permitted.
- Smooth the final path if desired. It is common practice to smooth a grid path in a post-processing step, removing unwanted zig-zags and shortening the path. It turns out that path counting and path smoothing work well in combination. Section 3.3 of the paper demonstrates that smoothing central grid paths produces shorter travel routes than smoothing arbitrary shortest grid paths.
- Compare results with an existing implementation. There is at least one available central grid-based pathfinding tool at the time of writing, an architectural design tool my colleagues and I developed called SpaceAnalysis. Other implementations will hopefully appear as more people learn about the technique.
Path counting is a well-known procedure at the heart of Pascal’s Triangle. It’s also a practical way to obtain straighter and more direct travel routes from classic pathfinding algorithms. If you need a simple navigation method for a video game, an analysis tool, or perhaps even a mobile robot, check out the paper and start counting paths!
[1] R. Goldstein, K. Walmsley, J. Bibliowicz, A. Tessier, S. Breslav, A. Khan, Path Counting for Grid-Based Navigation (2022), Journal of Artificial Intelligence Research, vol. 74, pp. 917–955
[2] K. Daniel, A. Nash, S. Koenig, A. Felner, Theta*: Any-Angle Path Planning on Grids (2010). Journal of Artificial Intelligence Research, vol. 39, pp. 553–579
[3] C. Cobeli, A. Zaharescu, Promenade around Pascal Triangle — Number Motives (2013) [PDF], Bulletin mathématique de la Société des Sciences Mathématiques de Roumanie, vol. 56, no. 104, pp. 73–98
[4] N. R. Sturtevant, Benchmarks for Grid-Based Pathfinding (2012) [PDF], Transactions on Computational Intelligence and AI in Games, vol. 4, no. 2, pp. 144–148
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.