BSc Computer Science Academic Project
This interactive platform was developed in 2021 as part of a BSc Computer Science Academic Project. Its primary objective is to visually and interactively demonstrate pathfinding search strategies, graph traversal, and core data structures (such as Queues, Stacks, and Priority Queues) in real-time. By bridging the gap between theory and execution, it provides an intuitive learning aid for computer science students.
1. Theoretical Foundations: What is Pathfinding?
At its core, pathfinding is the problem of finding a route between two points. In computer science, this is modeled using Graph Theory:
- Node (or Vertex): A point on the graph representing a location. In our grid, every individual square cell is a node.
- Edge (or Link): The connection between two nodes. In our grid, edges exist implicitly between any adjacent cells (up, down, left, right) that are not blocked by a wall.
- Path: A sequence of contiguous edges connecting a starting node to a destination node.
- Shortest Path: The path with the fewest edges (or lowest total weight) between the start and target.
2. Search Spaces: The "Thinking" Process
To find a path, an algorithm must search the graph systematically. It splits nodes into three categories:
- Unvisited Set: Nodes that the algorithm has not yet detected.
- Frontier (or Open Set): The "waiting room." These are nodes that the algorithm has discovered but has not yet fully examined.
- Explored Set (or Closed Set): Nodes that have already been evaluated. Keeping track of this prevents the algorithm from spinning in infinite loops.
3. Algorithm Breakdown & Data Structure Usage
Each pathfinding algorithm operates based on how it manages its "frontier" (the list of cells waiting to be explored). The data structure choice changes search behavior:
A. Breadth-First Search (BFS)
How it works: Explores the grid layer-by-layer, expanding outwards uniformly like ripples in a pond. It scans every node at distance 1, then distance 2, etc.
Data Structure: Queue (FIFO - First-In, First-Out). Newly discovered cells are added to the Back, and the next cell to evaluate is pulled from the Front. This FIFO order ensures breadth-first expansion.
Shortest Path Guarantee: Yes (on unweighted grids).
B. Depth-First Search (DFS)
How it works: Plunges deep along a single path, following it until it hits a wall or dead end, and only then backtracks to try other paths.
Data Structure: Stack (LIFO - Last-In, First-Out). Newly discovered cells are pushed onto the Top, and the next cell is popped from the Top. LIFO forces the search to continue along the newest path.
Shortest Path Guarantee: No. It returns the first path it finds, which is usually suboptimal.
C. A* Search (Informed Heuristic)
How it works: Uses a cost formula f(n) = g(n) + h(n) to find the target. g(n) is the distance traveled from start, and h(n) is the estimated distance to the target.
Data Structure: Priority Queue. Nodes are sorted so the one with the lowest total cost f(n) is popped first. This "steers" the search directly towards the target.
Shortest Path Guarantee: Yes (if heuristic is admissible).
D. Greedy Best-First Search
How it works: Rushes straight towards the target by prioritizing the cell that appears geometrically closest, ignoring the distance traveled so far.
Data Structure: Priority Queue (Sorted by Heuristic h(n) Only). Popping the lowest h(n) node makes the search very fast, but blind to obstacles.
Shortest Path Guarantee: No. Can be misled by walls and dead ends.
E. Bidirectional BFS
How it works: Runs two concurrent Breadth-First Searches—one starting at the start node moving forward, and one starting at the target node moving backward. The search stops when they meet.
Data Structure: Double Queue (Two FIFO Queues). Alternating expansions between the two queues minimizes the search tree size.
Shortest Path Guarantee: Yes.
4. Heuristics & Distance Math
A* Search uses distance estimations to guide its path:
- Manhattan Distance: Taxicab grid distance |x - tx| + |y - ty|, used when movement is restricted to 4 directions.
- Euclidean Distance: Straight-line distance √((x-tx)2 + (y-ty)2) (as the crow flies).
5. Practical Internals: How the Code Runs
This web application runs the pathfinding simulation in two phases:
- The Solver Phase: When you click Start, the algorithm runs instantly in JavaScript memory and records the order of visits into a
visited_list and the final route into a path_list.
- The Animation Phase: A browser timer (
window.setInterval) reads from the lists step-by-step, updating cell colors to blue/green and feeding the Live Execution Monitor with frontier updates.
Backtracking Path Reconstruction: Every node remembers its "parent" (the cell that discovered it). Once the target node is reached, the visualizer steps backwards through parent nodes until it reaches the start, reversing the sequence to draw the yellow path.
6. Custom Code Sandbox
Choose "Custom Sandbox" in the solving dropdown to reveal the editor. Write custom algorithms in JS and call helpers like:
helpers.getNeighbours(cell): returns adjacent coordinates.helpers.getVal(x, y): returns grid cell values (0: path, -1: wall, -2: bounds).helpers.distance(p1, p2): returns straight-line distance.
