Instructions: Click and drag on grid to draw walls/weights. Press W to toggle between drawing walls and drawing weights. Click and drag start/goal to move them. Drawing walls/weights or moving the start/goal after an algorithm has visualized will instantly show the final result as you drag your mouse. Pick an algorithm and enjoy.

BFS was originally meant for traversing/searching a tree or graph data structure. It works by checking whether any one of the origin's neighbors is the destination. If so, the algorithm returns true. If not, then it asks one of its neighbors the same question to all of the neighbor's neighbors. This cycle is repeated either iteratively or recursively. For the purposes of this web tool, the algorithm was slightly modified to use what the algorithm learns on its journey in order backtrack its way from the destination to the origin. See Wikipedia page

DSPF is very similar to BFS in that it asks each of the origin's neighbors the question of whether it's the destination or not, and repeats this iteratively or recursively. The difference, however is that DSPF takes into account so-called "weights", otherwise known as traffic or anything that would slow someone down on the way to their destination. It does this by initializing each node, except the origin, to have a distance of infinity from the origin. The algorithm also uses an array of nodes sorted by each of their distances from the origin, which gets updated and sorted with every iteration. The algorithm checks the neighbors of the node closest to the origin and updates their distances from the origin only if the path to the current neighbor is closer than the array says. This distance is the number of steps it takes to get to the node closest to the origin, added to the number of steps it takes to get to its current neighbor. The second addend will be either 1 or the weight of the weight indicated on the slider. As it turns out, DSPF, or at least a modified version of it, is apparently used by Google Maps. See Wikipedia page

A* is very similar to DSPF in that it keeps track of each node's distance from the origin. The difference, however is that A* takes into account each node's distance from the goal as well. Using both the distance from the origin and distance from the goal, of a particular node, the algorithm can tell which path takes the least steps to get to the goal. Similar to DSPF, A* uses an array of nodes sorted by the nodes' total distance (distance from origin + distance from goal), which gets updated and sorted with every iteration. The algorithm checks the neighbors of the node with the least total distance, and updates their distances from the origin and total distance, only if the distance from the origin to the current neighbor is closer than the array says. Hence, the pattern that shoots towards the goal. Furthermore, thanks to this algorithm's heuristic, it is faster than DSPF. See Wikipedia page

DFS is an algorithm similar to BFS, except instead of checking all current neighbors in order, it checks one neighbor and iteratively or recursively checks its neighbors until the algorithm has checked as deep as possible on a single node, at which point the algorithm backtracks to find another way to go. Hence "depth-first" as opposed to "breadth-first" (where breadth is referring to the breadth of a node, which are all its neighbors). To generate a maze using DFS however, there is a slight variation. It involves starting with a random node (which in this case is the start node) and choosing a single neighbor at random on every function call. Furthermore, it assumes that the grid is filled with walls. Everytime the function is called and there is a valid (wall) node two nodes in a random direction from the current node, then a path between the two nodes gets created, and DFS is invoked on that node that is two nodes away. See Wikipedia page