Ever use a map app? Well, map apps use a type of pathfinding algorithm in order to route you from your origin to your destination. PathFinder is simply a tool that visualizes how these types of pathfinding algorithms work. With PathFinder,
you can visualize how the Breadth First Search, Depth First Search, and A* pathfinding algorithms operate upon your own custom drawn graphs. Intended for use by computer science students. Available on iOS, ipadOS, and macOS.
On a more personal note, it always makes my day when I receive messages from students who have used PathFinder to study for their exams, or from non-technical folks who have just enjoyed playing around with the app.
PathFinder is also a winning submission of Apple's Worldwide Swift Student Challenge [WWDC20].
See PathFinder in action and learn more about it here.
A slightly modified version of PathFinder was lucky enough to win Apple's Worldwide Swift Student Challenge at WWDC2020.
"When the Apple 2020 Worldwide Developers Conference kicks off on June 22 in a new virtual format, a global community of 23 million developers will have the opportunity to join from around the world for free through the Apple Developer app and the Apple Developer website. Now in its 31st year, WWDC20 will bring together the largest group of innovators and entrepreneurs ever assembled to connect, share, and create.
Among them will be 350 Swift Student Challenge winners from 41 different countries and regions. The students were chosen based on their original Swift playground submission, part of Apple’s annual WWDC student challenge, which recognizes and celebrates the next generation of coders and creators." [Apple]
Learn more about Apple's Worldwide Swift Student Challenge here and here.
View the source code for the modified project below.
"A* (pronounced "A-star") is a graph traversal and path search algorithm, which is often used in many fields of computer science due to its completeness, optimality, and optimal efficiency.
One major practical drawback is its O(b^d) space complexity, as it stores all generated nodes in memory. Thus, in practical travel-routing systems, it is generally outperformed by algorithms which can pre-process the graph to attain better performance, as well as memory-bounded approaches; however, A* is still the best solution in many cases.
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Edsger Dijkstra's 1959 algorithm.
A* achieves better performance by using heuristics to guide its search."
"Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures.
The algorithm starts at the root node (selecting some arbitrary node as the root node in the case of a graph) and explores as far as possible along each branch before backtracking.
A version of depth-first search was investigated in the 19th century by French mathematician Charles Pierre Trémaux as a strategy for solving mazes."
"Breadth-first search (BFS) is an algorithm for traversing or searching tree or graph data structures.
It starts at the tree root (or some arbitrary node of a graph, sometimes referred to as a 'search key'), and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level.
It uses the opposite strategy of depth-first search, which instead explores the node branch as far as possible before being forced to backtrack and expand other nodes.
BFS and its application in finding connected components of graphs were invented in 1945 by Konrad Zuse, in his (rejected) Ph.D. thesis on the Plankalkül programming language, but this was not published until 1972. It was reinvented in 1959 by Edward F. Moore, who used it to find the shortest path out of a maze, and later developed by C. Y. Lee into a wire routing algorithm (published 1961)."
With PathFinder, you get a blank canvas. Just boot up the app, and draw any graph you'd like to see traversed, using the wall, space, start, and end draw tools.
Select any of the three supported solve algorithms to see them in action.
Set your solve speed using the slider.
Once the algorithm is done finding a path, you can select any other solve algorithm to visualize how the same graph might get solved differently using a different algorithm. No need to re-draw the graph.
Use the "Find Path" button to begin the solve process and use the "Reset" button to reset the canvas.