This is a pathfinding visualizer that I made while learning common pathfinding algorithms like Dijkstra's, A*, and Greedy Best First Search. Below you can find some design decisions that went into making this project.
- Supported Algorithms
- Dijkstra: Optimized breadth-first search that prioritizes exploring lower-cost paths.
- (weighted, shortest path guaranteed)
- A*: Optimized Dijkstra for when we know end node location. Uses lat/long distance as heuristic.
- (weighted, shortest path guaranteed)
- Greedy Best-First Search: Faster version of A* that doesn't guarantee shortest path
- (weighted, shortest path not guaranteed)
- Breadth First Search: Explores all nodes equally in all directions, level-by-level
- unweighted, shortest path guaranteed
- Depth First Search: Explores as far as possible along each branch before backtracing
- unweighted, shortest path not guaranteed
- Dijkstra: Optimized breadth-first search that prioritizes exploring lower-cost paths.
- Supported Cities
- San Francisco (37k nodes, 3.9MB)
- Vancouver (24k nodes, 2.5MB)
- New York (177k nodes, 17.7MB)
- Waterloo (22k nodes, 2.0MB)
Table of contents
- Data preparation
- Loading the graph
- Rendering
- Async everything
- Hit testing
- Pathfinding
- Developing locally
Data generated and stored in this repository comes from www.openstreetmap.org (available under the ODbL license).
BBBike was used to extract regional data as an array of nodes. This data was then run through a Python script to turn it into an undirected graph. During this step, BFS was performed to extract the largest possible connected graph from the dataset.
In the output format, each road is an edge and each intersection is a node. An adjacency list keeps track of directly-connected nodes.
{
"7402583179":{
"lat": 49.246429443359375,
"lon": -123.0760498046875,
"adj": [
"630211867",
"343340007"
]
},
}Since the data for cities can be very large (for example, New York is nearly 18 MB), loading the data needed to be done on-demand. Progress callbacks were used to track the status of a download request
const { data: jsonData } = await axios.get(
`https://pathfinding.kelvinzhang.ca/data/${file}`,
{
onDownloadProgress: (progressEvent) => {
const percentage = Math.round(
(progressEvent.loaded * 100) / progressEvent.total
);
onProgress(percentage);
if (percentage >= 100) {
setTimeout(() => {
setLoading(false);
cityData[city].loaded = true;
}, 400);
}
},
}
);To draw the map, React Leaflet was used. I was initially going to use Google Maps, but support for React was limited and it wasn't that extensible. CartoCDN tiles were used in the styling of the map.
To visualize pathfinding progress, visited nodes needed to be drawn on the screen. However, at the same time, we cannot have a separate SVG element for each node when showing 150k+ elements - that would be impossibly slow. One workaround would be to render everything on a canvas, but there was no built-in library for that. Instead, I built my own library to render a canvas layer for markers.
Still, rendering every single node caused a lot of lag and the app would often freeze. For algorithms such as BFS, each layer/iteration introduces exponentially more nodes than the last. Because of this, only some nodes are flagged for rendering.
Running pathfinding on a large dataset of nodes takes a while, especially for unefficient algorithms like DFS and BFS. Because of this, rendering would often freeze and I needed to make everything asyncronous. Passing data within the application would cause a lot of unnecessary re-renders, so I offloaded tasks to WebWorkers.
At this point, we discussed how data is loaded and how it's rendered. But how do we determine which node is being clicked? How can we click somewhere to set the start/end point and have it snap to the nearest node?
A naive solution would be to iterate through all the points and find the nearest point to our click. This would be a decent solution with a thousand points or less, but in our case, with several hundred thousands of points, it would be very slow.
A QuadTree was used to build an index of points. After a QuadTree is created, it can be queries in logarithmic time for the nearest neighbors around any coordinate. It's similar to a binary tree, but with four children instead.
Currently, these pathfinding algorithms are supported
- Dijkstra: Optimized breadth-first search that prioritizes exploring lower-cost paths.
- (weighted, shortest path guaranteed)
- A*: Optimized Dijkstra for when we know end node location. Uses lat/long distance as heuristic.
- (weighted, shortest path guaranteed)
- Greedy Best-First Search: Faster version of A* that doesn't guarantee shortest path
- (weighted, shortest path not guaranteed)
- Breadth First Search: Explores all nodes equally in all directions, level-by-level
- unweighted, shortest path guaranteed
- Depth First Search: Explores as far as possible along each branch before backtracing
- unweighted, shortest path not guaranteed
Weighted vs Unweighted
You'll notice that some of the algorithms listed above are weighted, while others are unweighted.
The weighted algorithms use the Manhattan distance heuristic, which calculates the sum of horizontal and vertical (read: lateral and longitudinal) distances between two nodes. In other words, the shortest path will have the least physical distance between the two nodes.
Unweighted algorithms give all edges the same weight of 1. In other words, the shortest path will have the least amount of nodes.
Calculating performance
Performance was calculated using a pausable timer. To simulate pathfinding speed, delays were added between iterations. This means that the timer only runs during calculations and is paused during rendering delays. For this reason, the total time to find the path is much smaller than what you see on the screen.
If you'd like to play around with the code:
# install dependencies
npm install
# serve with hot reload at localhost
npm start
# building for production
npm run buildThanks for reading this! I hope you enjoyed it as much as I enjoyed working on this project.