The greatest challenges in implementation were bug handling related to resetting the state of cells after various modifications to them incurred by adding walls, weights, running algorithms, or maze generation. As such, the Cell object was extremely useful in tracking and updating the relevant instance variables of each cell depending on the use of the program. The instance variables were rather straight forward to control but the difficult and quite buggy parts arose when having to control the animations of each cell. Because we use setTimeout and setInterval to animate components of the visualization, it was necessary to fully reset/clear the reference IDs of each of these called timeouts/intervals in order to mitigate visual and operational bugs. This was rather simple with entire algorithms, for example, upon finding a shortest path, an algorithm will clear its own interval reference ID such that it does not continue to search. However, within the algorithms, we use timeouts on many different cells in order to animate each one according to its state (visited, queued, part of the path, etc). This ended up causing a lot of bugs early on and we weren't sure where they were arising from; particularly, if you were to reset/clear a search before termination, the timeouts called for animation would remain idle and reprompt upon the call to another algorithm. This would make it so algorithms were incorrectly visualized and various ran at the same time; it was a mess. A solution ultimately came through keeping a list of all the reference IDs to timeouts called on various cells, such that upon clearing and resetting all the timeouts could be cleared. This fixed the problem we were facing but boy was it a pain to debug.
Each algorithm in our program is implemented in a "step" manner; by that, rather than iterating until the algorithms termination condition, each algorithm performs only one step of its conventional purpose and is called intermittently. This was done in order to create an animated visualization, as if the algorithms were to compute their final result upon a single call, the visual output would only show that outcome, not each step of the process.
Breadth-First Search is an unweighted search algorithm that starts at the root node and explores all the nodes at the present depth before moving on to the next depth level. By that, at a given node, BFS will explores each of its neighbors before preceeding to the neighbors of neighbors and so on, so forth. It uses a queue to keep track of the nodes to be explored next such that the algorithm processes nodes in a breadth-first manner.
Depth-First Search is an unweighted search algorithm that starts at the root node and explores as far as possible along each branch before backtracking. It uses a stack to keep track of the nodes to be explored next such that the algorithm processes nodes in a depth-first manner. This results in the long, winding paths that DFS takes.
A* search is an informed, weighted search algorithm that uses heuristic estimates to guide the search towards the goal. It combines the advantages of both BFS and DFS by using a priority queue to explore nodes with lower estimated cost first. The estimated cost of each node is the sum of the cost of the path from the start node to the current node and a heuristic estimate of the cost from the current node to the target node. Our A* uses a combination of the euclidian and manhattan distance from the target as its heuristic. Manhattan distance as a heuristic by itself guarantees the shortest path. The addition of euclidian distance greatly increases the speed of A* at the cost of a occasionally finding slightly suboptimal paths.
Uniform Cost Search is an uninformed, weighted search algorithm that uses only the cost of the path from the start node to the current node to guide the search. It also uses a priority queue to explore nodes with lower cost first. It is like Dijkstras algorithm except UCS terminates upon finding the target node, rather than computing shortest distance to every node in the graph.
Our maze generation uses a variation of kruskals algorithm to create a perfect maze (only a single path exists from any given starting point to any given ending point). The algorithm runs on a configuration of the grid where each non-wall is disconnected (every other row and column is fully walls); from here, the algorithm repeatedly selects a random wall to remove. If removing the wall connects two separate regions (the cells on either side of the wall have different groups) of the maze, the wall is removed and the regions are merged. The algorithm runs until all cells are connected (all cells have the same group, with a cells group representing the cells that can be reached from that cell).