Watch BFS, DFS, A*, and Dijkstra explore a randomly generated maze in real time. Compare nodes explored, path length, and computation time to understand each algorithm's trade-offs.
Maze Settings
Algorithm
Animation Speed
Statistics
Legend
Passage (unvisited)
Wall
Frontier (in queue)
Visited
Final Path
Start
Goal
Theory Notes
BFS: f(n) = g(n) — actual cost only
Uses queue. Guarantees shortest path.
DFS: Uses stack. Explores deeply.
May not find shortest path.
A*: f(n) = g(n) + h(n)
h = Manhattan distance (heuristic)
Optimal and efficient.
Dijkstra: Considers all edge costs.
Equivalent to A* with h=0 (uniform grid).
What exactly is the difference between BFS and DFS? They both seem to just search the maze until they find the exit.
🎓
Basically, it's about their strategy. BFS (Breadth-First Search) explores like a wavefront—it checks all immediate neighbors first, guaranteeing the shortest path. DFS (Depth-First Search) is like a determined explorer; it goes down one path as far as possible before backtracking. In practice, try running them side-by-side in the simulator. You'll see BFS's search area spread out, while DFS's search looks like a long, winding tunnel.
🙋
Wait, really? So DFS might not find the shortest path? Why would anyone use it then?
🎓
Exactly! DFS can find a very long, winding path. It's used because it can be more memory efficient in some cases, as it only needs to remember the current branch. A common case is exploring a huge maze where you just need any solution, not the best one. Try increasing the maze "Size" parameter above—on a huge maze, DFS might find a path faster, but look at the "Path Length" to see how inefficient it can be.
🙋
Okay, so A* and Dijkstra are the "smart" ones. What's the secret sauce for A*? It always seems fastest here.
🎓
The secret is a good guess! A* uses a heuristic—an educated guess about the distance to the goal—to prioritize which nodes to explore. It's like having a compass. Dijkstra has no compass; it explores based purely on the distance traveled so far, which is why its search area is more circular. When you change the algorithm in the simulator, watch the "Nodes Explored" counter. A* typically explores far fewer nodes because it's guided toward the target.
Physical Model & Key Equations
The core of these algorithms is managing a "frontier" of cells to explore. For BFS, this is a First-In-First-Out (FIFO) queue. For DFS, it's a Last-In-First-Out (LIFO) stack. This simple data structure choice dictates the entire search pattern.
Queue: First cell added is the first one explored (like a line). Stack: Last cell added is the first one explored (like a stack of plates).
The A* algorithm is defined by a cost function that combines the actual cost from the start with an estimated cost to the goal. This is what makes it "informed."
$$ f(n) = g(n) + h(n) $$
$g(n)$: The actual, known cost from the start node to node $n$ (like distance traveled). $h(n)$: The heuristic—estimated cost from node $n$ to the goal (often the straight-line or "Manhattan" distance).
The algorithm always expands the node with the lowest $f(n)$ value, efficiently steering the search.
Frequently Asked Questions
Yes, you can freely edit the wall placement by clicking or dragging on the grid on the screen. Additionally, you can adjust the number of rows and columns of the maze from the size change menu. There is also a function to randomly generate a maze.
BFS uses a queue to explore evenly from nearby nodes, while DFS uses a stack to prioritize one direction deeply. A* and Dijkstra search based on cost, but A* also takes into account the estimated cost toward the goal, making it more efficient at finding a path.
This is because the number of nodes explored varies depending on the browser load, the shape of the maze, and the start and goal positions. In particular, A* depends on the accuracy of the heuristic function, while Dijkstra expands evenly, so the difference becomes more noticeable when the maze is complex.
This tool assumes a static grid-based maze. In real environments, obstacles may move or movement costs may be uneven, so dynamic planning algorithms such as D* Lite or integration of sensor information are necessary. Please use this tool solely for basic understanding.
Real-World Applications
GPS Navigation & Map Apps: A* and its variants are the backbone of route-finding in apps like Google Maps. The roads form a graph (like our maze), and the algorithm finds the fastest or shortest path between your location and your destination, weighing factors like traffic and road types.
Robotics & Autonomous Vehicles: Robots use these algorithms for path planning in real-time. For instance, a warehouse robot uses A* to navigate around shelves and obstacles to pick up an item, constantly replanning if a new obstacle (like a person) appears.
Video Game AI: Non-player characters (NPCs) use pathfinding to chase the player or navigate complex game worlds. BFS might be used for simple grid-based games, while A* is standard for more complex, dynamic environments where performance is critical.
Network Routing: Data packets traveling across the internet need to find efficient paths through a network of routers. Algorithms like Dijkstra (used in OSPF protocol) calculate the shortest path for data based on link cost, ensuring efficient and reliable communication.
Common Misconceptions and Points to Note
When you start using this simulator, there are a few key points to keep in mind. First, A* is not always the fastest. While it's efficient thanks to the heuristic, in very simple mazes (e.g., a wide-open space with almost no walls), the overhead of heuristic calculation can sometimes make it slower than a simple BFS. You can experience this yourself in the tool by reducing the "size" and setting the "wall density" close to 0%.
Next, the choice of heuristic function significantly impacts the results. For instance, using Euclidean distance in a maze where diagonal movement is not allowed can underestimate the actual cost, potentially causing the search to expand unnecessarily. NovaSolver uses Manhattan distance, which is precisely why it excels in grid-based mazes. When implementing, it's crucial to choose a distance metric suited to your problem's structure.
Finally, be aware of the pitfall that "number of explored nodes" and "computation time" are not proportional. DFS goes deep without visiting many nodes, so it might seem "lightweight" at first glance. However, if backtracking from dead-ends is frequent, it can actually take more processing time. It's interesting to compare the "computation time" display, especially in complex mazes, to see the differences in internal processing weight between algorithms.
Adjust speed slider (1–10x) to control visualization playback rate, then click Generate to create random maze with start/end points
Click Solve to execute pathfinding and observe node exploration sequence, highlighted path, nodes explored count, and computation time in milliseconds
Worked Example
On a 20×20 maze (400 cells), solving with A* heuristic typically explores 45–65 nodes and finds path length of 28 steps in 3–5ms. BFS on same maze explores 120–150 nodes but guarantees shortest path (28 steps, 8–12ms). DFS explores 95–110 nodes, discovers suboptimal path (35 steps, 2–3ms). Dijkstra explores 140–160 nodes, confirms shortest 28-step path in 10–15ms. Larger 40×40 maze increases BFS nodes explored to 300–450 range.
Practical Notes
A* outperforms others on large mazes (30×30+) when Manhattan/Euclidean heuristics are well-calibrated; DFS minimizes memory footprint for embedded systems or real-time robotics with acceptable suboptimal paths
Speed parameter affects only visualization; set to 10x for instant solution then inspect replay at 1x; computation time metric excludes rendering overhead
BFS guarantees optimality in unweighted grids; switch to Dijkstra only if cells have variable traversal costs (e.g., terrain resistance in game pathfinding)