A Short and Direct Walk with Pascal’s Triangle

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 <a href="https://www.jair.org/index.php/jair/article/view/13544" rel="noopener ugc nofollow" target="_blank">recently published</a> 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. <h1>The Ugly Path Problem</h1> 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. <a href="https://towardsdatascience.com/a-short-and-direct-walk-with-pascals-triangle-26a86d76f75f">Visit Now</a>