Build Your Own Pathfinder in Angular
I began what I hope will become a tradition last year around the holidays. My goal is to simply give something away just for the sake of giving it away. Last year’s gift was a variable-width freehand stroke that rendered into a Canvas. This facilitated dynamic drawing in Angular applications through its implementation in a structural directive.
This year’s gift is a Typescript library for 2D pathfinding, namely the A* algorithm for waypoints. If you have ever navigated anywhere using Google Maps or Waze, then you have direct experience with a very sophisticated implementation of the A* algorithm.
A* is a modification of the infamous Dijkstra shortest-path algorithm. This approach uses heuristics to aid in the search process, although in its ‘textbook’ form, the algorithm can suffer from memory problems. The underlying data structures also need to be optimized for use with very sparse graphs.
The A* algorithm has a very efficient implementation for game tiles, where a character can move in one of four or eight directions at a time across a surface divided into square tiles. If you are interested, I have an implementation on GitHub.
Waypoints and Costs
Waypoints are specified across a plane to define the possible collection of paths that connect a specified start and end point. On a network of roads, waypoints are intersections, turn-ins to apartments and shopping centers, and destinations such as a post office.
A graph is constructed by assigning lists of ‘from’ and ‘to’ waypoints along with the cost of travel. When driving a car, for example, most drivers elect to minimize travel time. So, the cost from one waypoint to the next is based on travel time.
Once the optimal path is computed, it is possible that real-time traffic conditions alter the cost between waypoints on the route. A sophisticated algorithm can take advantage of such information and recompute the optimal path en-route.
Of course, the graph representing the complete network of all possible paths can quickly grow to an unmanageable size. For example, if you desire to travel from your home to a doctor’s office less than ten miles away, is it necessary to build a graph of all possible waypoints across the entire city?
Pruning is an important part of any pre-optimization setup. I once worked on an application for the Toronto Airport as a sub-contractor. The mobile app was designed to route people efficiently anywhere inside the airport. A robust waypoint collection was defined, and all path segments were in a straight line. So, Euclidean distance was used as a cost estimate in the pathfinding algorithm.
It was almost never necessary to build a graph of all possible paths throughout the entire airport. The majority of requested routes were from gate to baggage claim and then to ground transportation. Almost all requested routes were inside a single terminal.
I divided waypoints into grids inside each terminal and devised a simple scheme to fetch waypoints inside a grid and inside a terminal. Based on origin and destination point, only waypoints from a selected number of grids (calculated by a custom heuristic) were included in the waypoint list. Each waypoint contained an optimized list of waypoint ids that defined outgoing edges. Cost of an edge was the Euclidean distance between waypoints. This made it quite easy to build a compact graph to serve as input to the pathfinder.
This is just one practical example of A* pathfinding and it was trivial next to the implementation in your favorite map navigation app.
The Code
Here is the GitHub repo.
Usage
Usage of the library is fairly simple. Specs in the __tests__ folder serve as a general usage reference.
Low-level usage requires constructing a graph by adding waypoint data. This is easily accomplished with the createWaypoint function,
import { AStarGraph } from "../src/astar-graph";
import { AStarWaypoint } from "../src/astar-waypoint";
import { AStar } from "../src/astar";
import { createWaypoint } from "../src/astar-waypoint";
.
.
.const graph: AStarGraph = new AStarGraph();
const w: AStarWaypoint = createWaypoint('1', 1, 4, true, 3);graph.addNode(w);.
.
.
const wn: AStarWaypoint = createWaypoint(n, 2, 6, true, 4);
graph.addNode(w2);
The graph is passed to the AStar class find() method to compute the optimal path.
const waypoints: Array<AStarWaypoint> = astar.find(graph, beginId, endId);Larger problems most likely have waypoint data available from a back end service or other data provider. Use the fromObject method to automatically build the graph from the supplied data.
graph.fromObject(graphDataFromServer);
const waypoints: Array<AStarWaypoint> = astar.find(graph, beginId, endId);Summary
This code is best suited for those wishing to learn more about the A* algorithm and pathfinding by studying a code base rather than starting from a mathematical foundation. The code is fairly ‘textbook’ and should not be used for large-scale, production applications. The best way to learn is to jump into the debugger or place console logs in various places throughout the code. Work through one or two tests at a time and see how the algorithm behaves. Then, work through the mathematical foundations to the level you feel comfortable.
My personal recommendation is to spend time on the cost function. Work over the code so that you can use cost estimates that are different from the Euclidean distance between waypoints. You could also implement a reactive ‘wrapper’ (i.e. BehaviorSubject) inside an application. When information about an edge changes, that information can be passed to the find() method. The optimal route could be updated based on new information.
You may also wish to experiment with pruning methods for building the initial graph that is searched by the A* algorithm.
Would that put you on par with Google Maps and Waze? No, but it’s a good first step. I hope your holidays are enjoyable and that you receive some benefit from this code.
Keep using it … I’ll give away more :)
Now that you’ve read this article and learned a thing or two (or ten!), let’s kick things up another notch!
Take your skills to a whole new level by joining us in person for the world’s first MAJOR Angular conference in over 2 years! Not only will You be hearing from some of the industry’s foremost experts in Angular (including the Angular team themselves!), but you’ll also get access to:
- Expert panels and Q&A sessions with the speakers
- A friendly Hallway Track where you can network with 1,500 of your fellow Angular developers, sponsors, and speakers alike.
- Hands-on workshops
- Games, prizes, live entertainment, and be able to engage with them and a party you’ll never forget
We’ll see you there this August 29th-Sept 2nd, 2022. Online-only tickets are available as well.
