Build a Pathfinding Algorithm Visualizer

Visualize BFS, DFS, and Dijkstra's on an interactive grid in Python.

Introduction

30 Second Summary

Every time you open a maps app and ask for directions, an algorithm is racing through thousands of possible paths to find the best one. The difference between a fast answer and a slow one comes down to which data structure the algorithm uses to decide where to look next.

In this project, you will build an interactive pathfinding visualizer in Python that lets you draw mazes, then watch three different algorithms explore the grid cell by cell in real time.

What You'll Build

You will run a desktop app where you draw walls with your mouse, pick an algorithm, and watch it paint the grid as it searches for a path from start to end.

By the end of this project, you'll have:

  • A clickable grid application where you draw maze walls by dragging your mouse and place start and end points with a right-click.
  • Three algorithms you built from scratch (BFS, DFS, and Dijkstra's), each using a different core data structure, with real-time animation showing exactly which cells get explored and in what order.
  • Visual proof of how a queue vs a stack vs a priority queue produces fundamentally different exploration patterns on the same maze.
  • Secret Mission: Add A* search with a Manhattan distance heuristic and watch it outperform all three algorithms.

Are there any prerequisites?

You should be comfortable with basic Python: functions, classes, lists, and dictionaries. Familiarity with loops and conditionals is all you need to get started.

Before We Start

Before we dive in, let's lock in what you're about to build and why it matters. You're creating an interactive pathfinding visualizer that reveals how choosing a different data structure (queue, stack, or heap) completely changes the way an algorithm explores a graph.

Set Up the Grid Display

Every pathfinding algorithm needs a graph to traverse. For this project, that graph is a 2D grid where each cell is a node and its four neighbors (up, down, left, right) are connected edges.

In this step, you will build the grid display using tkinter's Canvas widget and wire up mouse interactions. By the end, you will have a clickable grid where you can draw walls and place start and end points.

In this step, get ready to:
  • Draw a 25×25 grid of cells on a tkinter Canvas.
  • Add mouse interactions to draw walls and place start/end points.
Define the constants and color map

Before writing any class logic, you need to establish the grid dimensions, cell sizes, and the color palette the visualizer will use throughout the project.

  • In pathfinder.py, add the following imports and constants:
import tkinter as tk
from collections import deque
import heapq

# Constants
ROWS = 25
COLS = 25
CELL_SIZE = 24
ANIMATION_DELAY = 20

# Cell states
EMPTY = 0
WALL = 1
START = 2
END = 3
WEIGHTED = 4

# Colors
COLORS = {
    EMPTY: "white",
    WALL: "black",
    START: "green",
    END: "red",
    WEIGHTED: "#FFD580",
    "visited": "#87CEEB",
    "path": "yellow",
}

What does this code do?

The imports bring in the three data structure modules you will use across the project: tkinter for the GUI, deque for BFS queues, and heapq for Dijkstra's priority queue.

The constants define a 25×25 grid of 24-pixel cells. Each cell state maps to an integer so you can track what is in every position. The COLORS dictionary maps those states (and algorithm stages) to display colors.

  • Save pathfinder.py.
Create the application class and canvas

The PathfinderApp class owns all application state: the grid data, the canvas, and the start/end positions. Its __init__ sets up data structures, then builds the canvas and binds mouse events.

  • Below the COLORS dictionary, add the class definition with __init__ and _build_canvas:
class PathfinderApp:
    def __init__(self, root):
        self.root = root
        self.root.title("Pathfinding Visualizer")

        self.grid_data = [[EMPTY for _ in range(COLS)] for _ in range(ROWS)]
        self.rect_ids = [[None for _ in range(COLS)] for _ in range(ROWS)]
        self.start = None
        self.end = None
        self.running = False

        self._build_canvas()
        self._draw_grid()

    def _build_canvas(self):
        width = COLS * CELL_SIZE
        height = ROWS * CELL_SIZE
        self.canvas = tk.Canvas(self.root, width=width, height=height, bg="white")
        self.canvas.pack(padx=5, pady=5)

        self.canvas.bind("<Button-1>", self._on_left_click)
        self.canvas.bind("<B1-Motion>", self._on_left_drag)
        self.canvas.bind("<Button-3>", self._on_right_click)

What does this code do?

  • grid_data is a 2D list tracking the state (empty, wall, start, end, weighted) of every cell.
  • rect_ids stores the tkinter item ID for each rectangle so you can update its color later with itemconfig.
  • _build_canvas creates the drawing surface and binds three mouse events: left-click, left-drag, and right-click.
  • Save pathfinder.py.
Draw the grid and run the app

The _draw_grid method fills the canvas with 625 rectangles (25×25). The main function at the bottom wires everything together so you can run the file directly.

  • Below _build_canvas, add _draw_grid, _get_cell, and the main function:
    def _draw_grid(self):
        for r in range(ROWS):
            for c in range(COLS):
                x1 = c * CELL_SIZE
                y1 = r * CELL_SIZE
                x2 = x1 + CELL_SIZE
                y2 = y1 + CELL_SIZE
                rect_id = self.canvas.create_rectangle(
                    x1, y1, x2, y2, fill="white", outline="gray"
                )
                self.rect_ids[r][c] = rect_id

    def _get_cell(self, event):
        col = event.x // CELL_SIZE
        row = event.y // CELL_SIZE
        if 0 <= row < ROWS and 0 <= col < COLS:
            return row, col
        return None, None


def main():
    root = tk.Tk()
    app = PathfinderApp(root)
    root.mainloop()


if __name__ == "__main__":
    main()

What does this code do?

  • _draw_grid loops through every row and column, calculates pixel coordinates, and calls create_rectangle to draw each cell. It stores the returned item ID so you can recolor cells later.
  • _get_cell converts a mouse event's pixel coordinates into a (row, col) pair by dividing by CELL_SIZE.
  • main creates the tkinter root window, instantiates the app, and starts the event loop.
  • Save pathfinder.py.

Before you run this, what do you expect to see?

  • Run your visualizer by entering this command in the terminal:
python pathfinder.py

A window titled "Pathfinding Visualizer" appears showing a 25×25 grid of white cells with gray outlines. Clicking does nothing visible yet because the event handler methods do not exist.

Window not appearing?

  • Check for typos in create_rectangle or mainloop. A misspelled method name raises an AttributeError.
  • Make sure self._build_canvas() and self._draw_grid() are called inside __init__, not outside the class.
  • On macOS with Homebrew Python, tkinter may not be bundled. Run brew install python-tk to add it.

Still stuck? Why isn't my tkinter window appearing when I run pathfinder.py?

  • Close the window (click the X or press Ctrl+C in the terminal) before continuing.
Add mouse interaction for walls and endpoints

A static grid is not useful on its own. You need to draw maze walls by clicking and dragging, and place start/end markers with right-click.

  • Above the main function (still inside the class), add the left-click, drag, and wall-toggle methods:
    def _on_left_click(self, event):
        if self.running:
            return
        row, col = self._get_cell(event)
        if row is None:
            return
        self._toggle_wall(row, col)

    def _on_left_drag(self, event):
        if self.running:
            return
        row, col = self._get_cell(event)
        if row is None:
            return
        if self.grid_data[row][col] == EMPTY:
            self.grid_data[row][col] = WALL
            self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[WALL])

    def _toggle_wall(self, row, col):
        if self.grid_data[row][col] == EMPTY:
            self.grid_data[row][col] = WALL
            self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[WALL])
        elif self.grid_data[row][col] == WALL:
            self.grid_data[row][col] = EMPTY
            self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[EMPTY])

What does this code do?

  • _on_left_click toggles a single cell between wall and empty when you click it.
  • _on_left_drag only draws walls (never erases) so dragging across the grid paints a continuous wall.
  • _toggle_wall handles the actual flip: if the cell is empty it becomes a wall (black), if it is a wall it becomes empty (white).
  • The if self.running guard prevents edits while an algorithm is animating (you will add algorithms in later steps).
  • Save pathfinder.py and run it again:
python pathfinder.py
  • Left-click any cell. It turns black (wall). Click it again and it turns back to white.
  • Hold left-click and drag across multiple cells. A continuous black wall appears.

Clicking does nothing?

  • Confirm the method names match exactly: _on_left_click, _on_left_drag, _toggle_wall. The bindings in _build_canvas reference these names.
  • Make sure these methods are indented inside the PathfinderApp class, not at the module level.

Still stuck? Why doesn't clicking change cell colors in my grid?

  • Now add the right-click handler below _on_left_drag (above _toggle_wall):
    def _on_right_click(self, event):
        if self.running:
            return
        row, col = self._get_cell(event)
        if row is None:
            return
        if self.start is None:
            self.start = (row, col)
            self.grid_data[row][col] = START
            self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[START])
        elif self.end is None:
            self.end = (row, col)
            self.grid_data[row][col] = END
            self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[END])

What does this code do?

The first right-click places the start point (green). The second right-click places the end point (red). After both are placed, further right-clicks do nothing. This ensures you always have exactly one start and one end.

  • Save pathfinder.py and run it one more time:
python pathfinder.py

Right-click one cell. It turns green (start). Right-click a different cell. It turns red (end).

Right-click not working on macOS?

macOS trackpads default to a two-finger tap for right-click. If that does not register, hold Control and click instead. This sends the same <Button-3> event to tkinter.

Need more help? How do I right-click on macOS for tkinter Button-3 events?

✔️ Awesome, I've got everything!

Great. Double check you have saved pathfinder.py and the grid, walls, and start/end all work as expected.

ⓧ I'd like to double check the full code

Here is the complete pathfinder.py so far. Compare it with yours:

Your file has these sections, top to bottom:

  • Imports (tkinter, deque, heapq).
  • Constants (ROWS, COLS, CELL_SIZE, ANIMATION_DELAY), cell states, and COLORS dictionary.
  • PathfinderApp class with __init__, _build_canvas, _draw_grid, _get_cell, _on_left_click, _on_left_drag, _on_right_click, and _toggle_wall.
  • main function and if __name__ == "__main__" block at the bottom.

Scroll up and confirm each chunk you pasted matches these sections in order. If anything is missing, add it now and re-run python pathfinder.py to confirm the grid displays correctly.

Your interactive grid is ready. Next up, you will implement BFS and watch it explore the maze cell by cell in real time.

Implement BFS and Watch It Explore

Your grid is drawn and interactive. You can place walls, set a start, and set an end. But the whole point of this visualizer is to watch algorithms explore the grid in real time.

BFS (Breadth-First Search) is the simplest graph traversal algorithm. It uses a FIFO queue to explore outward layer-by-layer, like ripples spreading from a stone dropped in water. In this step, you will implement BFS and watch it paint your grid cell-by-cell.

In this step, get ready to:
  • Add control buttons and utility methods to your grid application.
  • Implement BFS using a FIFO queue with real-time animation.
  • Trace the shortest path once BFS reaches the destination.
Add control buttons and grid utilities

Before any algorithm can run, you need buttons to trigger them and helper methods to manage the grid state.

  • In pathfinder.py, add the following _build_controls method inside the PathfinderApp class, above _build_canvas:
    def _build_controls(self):
        frame = tk.Frame(self.root)
        frame.pack(side=tk.TOP, fill=tk.X, padx=5, pady=5)

        tk.Button(frame, text="BFS", command=self.run_bfs).pack(side=tk.LEFT, padx=2)
        tk.Button(frame, text="DFS", command=self.run_dfs).pack(side=tk.LEFT, padx=2)
        tk.Button(frame, text="Dijkstra", command=self.run_dijkstra).pack(
            side=tk.LEFT, padx=2
        )
        tk.Button(frame, text="Reset", command=self.reset_visited).pack(
            side=tk.LEFT, padx=2
        )
        tk.Button(frame, text="Clear All", command=self.clear_all).pack(
            side=tk.LEFT, padx=2
        )

        self.status_label = tk.Label(frame, text="Draw walls, right-click for start/end")
        self.status_label.pack(side=tk.RIGHT, padx=5)

What does this code do?

This creates a toolbar frame at the top of the window with five buttons. Each button is wired to a method you will define shortly. The status_label on the right side displays messages about what the algorithm is doing.

  • In the __init__ method, find these two lines:
        self._build_canvas()
        self._draw_grid()
  • Add self._build_controls() above them, so the three lines now look like this:
        self._build_controls()
        self._build_canvas()
        self._draw_grid()
  • In the _build_canvas method, find the last binding line:
        self.canvas.bind("<Button-3>", self._on_right_click)
  • Add this line directly below it:
        self.root.bind("w", self._on_weight_key)

Now add the helper methods the buttons rely on. These handle weight toggling, neighbor lookups, and grid resets.

  • Add the following two methods below _on_right_click:
    def _on_weight_key(self, event):
        if self.running:
            return
        x = self.canvas.winfo_pointerx() - self.canvas.winfo_rootx()
        y = self.canvas.winfo_pointery() - self.canvas.winfo_rooty()
        col = x // CELL_SIZE
        row = y // CELL_SIZE
        if 0 <= row < ROWS and 0 <= col < COLS:
            if self.grid_data[row][col] == EMPTY:
                self.grid_data[row][col] = WEIGHTED
                self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[WEIGHTED])
            elif self.grid_data[row][col] == WEIGHTED:
                self.grid_data[row][col] = EMPTY
                self.canvas.itemconfig(self.rect_ids[row][col], fill=COLORS[EMPTY])

    def _get_neighbors(self, row, col):
        # Returns walkable cells adjacent to (row, col)
        neighbors = []
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = row + dr, col + dc
            if 0 <= nr < ROWS and 0 <= nc < COLS and self.grid_data[nr][nc] != WALL:
                neighbors.append((nr, nc))
        return neighbors

What do these methods do?

Pressing w while hovering over a cell toggles it as a weighted cell (used later for Dijkstra's algorithm). The _get_neighbors method returns the four adjacent cells (up, down, left, right) that are not walls. This is how the grid acts as an implicit graph.

  • Add the reset methods and placeholder stubs below _get_neighbors:
    def reset_visited(self):
        self.running = False
        for r in range(ROWS):
            for c in range(COLS):
                if self.grid_data[r][c] in (EMPTY, WEIGHTED):
                    color = COLORS[self.grid_data[r][c]]
                    self.canvas.itemconfig(self.rect_ids[r][c], fill=color)
        self.status_label.config(text="Reset. Draw walls, right-click for start/end")

    def clear_all(self):
        self.running = False
        self.start = None
        self.end = None
        for r in range(ROWS):
            for c in range(COLS):
                self.grid_data[r][c] = EMPTY
                self.canvas.itemconfig(self.rect_ids[r][c], fill="white")
        self.status_label.config(text="Cleared. Draw walls, right-click for start/end")

    def run_bfs(self):
        self.status_label.config(text="BFS not yet implemented")

    def run_dfs(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.status_label.config(text="DFS not yet implemented")

    def run_dijkstra(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.status_label.config(text="Dijkstra not yet implemented")

What does this code do?

The reset_visited method recolors explored cells back to white (or orange for weighted) while keeping walls and start/end intact. The clear_all method wipes everything including walls.

The three algorithm stubs prevent crashes when you click buttons whose logic you have not written yet. You will replace run_bfs next.

  • Save pathfinder.py and run it:
python pathfinder.py

You should see a row of buttons (BFS, DFS, Dijkstra, Reset, Clear All) above your grid. Draw some walls by left-clicking, then click Clear All. All cells return to white.

Seeing an error on startup?

If you get an AttributeError, check that self._build_controls() appears before self._build_canvas() in __init__. The controls must exist before the canvas tries to bind events.

help me fix the AttributeError in my pathfinder app

Implement BFS with a queue

BFS uses a FIFO (first-in, first-out) queue. You add neighbors to the back and pull the next cell to visit from the front. This guarantees layer-by-layer exploration outward from the start.

What is BFS?

Breadth-First Search explores a graph level by level. Imagine dropping a stone in still water. The ripples expand evenly in all directions. BFS does the same thing on a grid: it visits all cells 1 step away, then all cells 2 steps away, and so on. Because it never jumps ahead, the first time it reaches the end cell is guaranteed to be the shortest path.

  • Replace the run_bfs stub with the real implementation. Find the line:
    def run_bfs(self):
        self.status_label.config(text="BFS not yet implemented")
  • Delete those two lines and paste the following _trace_path method and the start of run_bfs in their place:
    def _trace_path(self, came_from, current):
        # Walk backward through came_from to build the path
        path = []
        while current in came_from:
            path.append(current)
            current = came_from[current]
        path.reverse()
        for r, c in path:
            if (r, c) != self.end:
                self.canvas.itemconfig(self.rect_ids[r][c], fill=COLORS["path"])
        return len(path)

    def run_bfs(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.reset_visited()
        self.running = True
        self.status_label.config(text="Running BFS...")

        queue = deque([self.start])
        visited = {self.start}
        came_from = {}
        visited_count = [0]

What are these data structures?

The deque (double-ended queue from collections) gives O(1) popleft() and append(). This is what makes BFS a FIFO queue.

The visited set tracks which cells have been seen. The came_from dictionary maps each cell to the cell it was discovered from. This lets _trace_path walk backward from end to start to draw the shortest path.

  • Directly below the visited_count = [0] line (still inside run_bfs), add the animation function that drives BFS one step at a time:
        def step():
            if not self.running:
                return
            if not queue:
                self.running = False
                self.status_label.config(
                    text=f"BFS: No path found. Visited: {visited_count[0]}"
                )
                return

            current = queue.popleft()
            visited_count[0] += 1

            if current == self.end:
                path_len = self._trace_path(came_from, self.end)
                self.running = False
                self.status_label.config(
                    text=f"BFS: Path length {path_len}, Visited: {visited_count[0]}"
                )
                return

            if current != self.start:
                self.canvas.itemconfig(
                    self.rect_ids[current[0]][current[1]], fill=COLORS["visited"]
                )

            for neighbor in self._get_neighbors(current[0], current[1]):
                if neighbor not in visited:
                    visited.add(neighbor)
                    came_from[neighbor] = current
                    queue.append(neighbor)

            self.root.after(ANIMATION_DELAY, step)

        step()

How does the animation work?

Each call to step() processes exactly one cell. It pops the front of the queue (popleft()), colors it light blue, then adds its unvisited neighbors to the back (append()).

The line self.root.after(ANIMATION_DELAY, step) schedules the next iteration 20ms later. This keeps the window responsive so you can watch the exploration unfold in real time instead of it finishing instantly.

Run BFS and watch it explore
  • Save pathfinder.py.
  • Run your app:
python pathfinder.py
  • Draw a few walls by left-clicking and dragging across the grid.
  • Right-click once to place a green start cell.
  • Right-click again on a different cell to place a red end cell.

Before you click BFS, predict: will the algorithm explore the entire grid, or will it stop as soon as it finds the end?

  • Click the BFS button.

You should see light blue cells spreading outward from the start in even layers. The moment BFS reaches the red end cell, it stops and a yellow path appears tracing back from end to start. The status bar shows the path length and how many cells were visited.

Why does BFS stop early?

Because BFS explores layer by layer, the first time it reaches the end is guaranteed to be via the shortest route. There is no reason to keep searching. This is why BFS is optimal for unweighted graphs.

BFS button does nothing?

Make sure you placed both a start (green) and an end (red) cell using right-click. Without both, the status bar displays a message asking you to set them.

If you see an indentation error, check that the def step(): function is indented inside run_bfs (8 spaces in), and the body of step() is indented 12 spaces in.

help me debug why BFS is not running in my pathfinder app

✔️ Awesome, I've got everything!

Great. Double check you have saved pathfinder.py and your BFS is animating correctly.

ⓧ I'd like to double check the full code

Your pathfinder.py is getting long. Scroll through and confirm you have each of these sections in order:

  • Imports and constants at the top (ROWS, COLS, CELL_SIZE, ANIMATION_DELAY, cell states, colors).
  • The __init__ method calling _build_controls, _build_canvas, _draw_grid in that order.
  • The _build_controls method with 5 buttons and a status label.
  • The _build_canvas method with bindings for <Button-1>, <B1-Motion>, <Button-3>, and w.
  • Grid drawing, cell lookup, click handlers, _on_weight_key, _toggle_wall.
  • The _get_neighbors, reset_visited, clear_all, and _trace_path utility methods.
  • The full run_bfs method with the nested step() function.
  • Stubs for run_dfs and run_dijkstra.
  • The main() function and if __name__ == "__main__": block at the bottom.

You now have a working BFS that visually proves how a FIFO queue produces layer-by-layer exploration. Next, you will implement DFS and see how swapping the queue for a stack transforms the exploration pattern completely.

Add DFS and Compare Exploration Patterns

In the previous step, you built BFS and watched it explore outward in even layers. That layered behavior comes from using a FIFO queue, where the first cell added is the first one explored.

What happens when you switch to a stack? A stack processes the most recently added cell first, which means the algorithm dives deep into one path before backtracking. This is Depth-First Search. In this step, you'll implement DFS and see how this single data structure change transforms the entire exploration pattern.

In this step, get ready to:
  • Implement DFS using a Python list as a stack with the same animation pattern as BFS.
  • Run both algorithms on the same maze to compare exploration patterns and path lengths.
Implement DFS using a stack

BFS used collections.deque with popleft() to process cells in FIFO order. DFS uses a plain Python list with pop() to process cells in LIFO order. That single change is what makes DFS dive deep instead of spreading wide.

  • In pathfinder.py, find the existing run_dfs method (the stub that prints "DFS not yet implemented").
  • Replace the entire run_dfs method with this code:
    def run_dfs(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.reset_visited()
        self.running = True
        self.status_label.config(text="Running DFS...")

        # Use a list as a stack (LIFO) instead of deque (FIFO)
        stack = [self.start]
        visited = {self.start}
        came_from = {}
        visited_count = [0]

        def step():
            if not self.running:
                return
            if not stack:
                self.running = False
                self.status_label.config(
                    text=f"DFS: No path found. Visited: {visited_count[0]}"
                )
                return

            # Pop from the END of the list (LIFO)
            current = stack.pop()
            visited_count[0] += 1

            if current == self.end:
                path_len = self._trace_path(came_from, self.end)
                self.running = False

What does this code do?

This is the first half of your DFS implementation. Notice how similar it is to BFS.

  • stack = [self.start] initializes a plain Python list instead of a deque. This list will behave as a stack.
  • stack.pop() removes the last item added (LIFO). This is the only structural difference from BFS's queue.popleft() (FIFO).
  • The same visited set, came_from dict, and visited_count list track exploration progress identically to BFS.
  • Immediately below the code you just pasted (still inside the run_dfs method), add the rest of the method:
                self.status_label.config(
                    text=f"DFS: Path length {path_len}, Visited: {visited_count[0]}"
                )
                return

            # Color the current cell as visited
            if current != self.start:
                self.canvas.itemconfig(
                    self.rect_ids[current[0]][current[1]], fill=COLORS["visited"]
                )

            # Push unvisited neighbors onto the stack
            for neighbor in self._get_neighbors(current[0], current[1]):
                if neighbor not in visited:
                    visited.add(neighbor)
                    came_from[neighbor] = current
                    stack.append(neighbor)

            self.root.after(ANIMATION_DELAY, step)

        step()

What does this second half do?

  • stack.append(neighbor) pushes new cells onto the top of the stack. On the next iteration, pop() grabs the most recently added neighbor, diving deeper into that direction.
  • root.after(ANIMATION_DELAY, step) schedules the next algorithm step after 20ms, keeping the animation smooth and the UI responsive.
  • The path tracing uses the same _trace_path method as BFS. The algorithm logic changed, but the visualization infrastructure stays the same.
  • Save pathfinder.py.

Seeing an indentation error?

  • The second chunk continues directly inside the step() function. Make sure self.status_label.config at the top of the second chunk is indented at the same level as if current == self.end: from the first chunk.
  • The final step() call (no self.) must be indented at the same level as def step(): above it (inside run_dfs but outside step).
  • Compare your indentation to run_bfs above. The structure should be identical.

Why is my DFS method not working?

Run DFS and compare with BFS

Now for the real payoff. You'll run both algorithms on the same maze to see how the data structure choice changes everything.

  • Run your visualizer by running this command:
python pathfinder.py
  • Draw a few walls by left-clicking and dragging to create a simple maze with corridors.
  • Right-click to place a green start point on the left side of the grid.
  • Right-click again to place a red end point on the right side.
  • Click the BFS button and watch how it explores.
  • Once BFS finishes, note the path length and visited count shown in the status bar.
  • Click Reset to clear the visited cells (your walls stay).

Before you click DFS, what do you think the exploration will look like compared to BFS? Will it spread outward evenly, or behave differently?

  • Click the DFS button and watch the exploration.

DFS snakes through corridors, diving deep in one direction before backtracking. The exploration is long and narrow instead of the even layers BFS produced.

Why does DFS explore differently?

BFS uses a queue (FIFO): it processes cells in the order they were discovered, so it finishes one layer before starting the next. This guarantees the shortest path on unweighted graphs.

DFS uses a stack (LIFO): it always processes the most recently discovered cell, so it keeps going deeper into whichever direction it found last. The path it finds may be longer than BFS's path because it does not explore all directions evenly.

  • Compare the status bar results. BFS shows something like BFS: Path length 20, Visited: 150 and DFS shows DFS: Path length 34, Visited: 95. Your numbers will differ, but notice that DFS's path length is often longer (no shortest path guarantee) while visited count may be lower or higher depending on the maze shape.

Try an open grid with no walls

Click Clear All and set start/end with no walls at all. Run BFS to see a perfect diamond shape expanding outward. Then reset and run DFS to see it snake across the grid in a single direction. The contrast is dramatic when there are no walls constraining the exploration.

✔️ Awesome, I've got everything!

Great. Double check you've saved pathfinder.py and that both BFS and DFS run correctly on the same maze.

ⓧ I'd like to double check the full code

Your pathfinder.py is too long to show in full here. Scroll through your file and confirm these sections are present in order:

  • Imports (tkinter, deque, heapq) and constants at the top.
  • The PathfinderApp class with __init__, _build_controls, _build_canvas, and _draw_grid.
  • Event handlers: _get_cell, _on_left_click, _on_left_drag, _on_right_click, _on_weight_key, _toggle_wall.
  • Helper methods: _get_neighbors, reset_visited, clear_all, _trace_path.
  • The run_bfs method (unchanged from the previous step).
  • Your new run_dfs method using stack.pop() instead of queue.popleft().
  • The run_dijkstra stub (still shows "Dijkstra not yet implemented").
  • The main() function and if __name__ == "__main__": block at the bottom.

You now have visual proof that data structure choice determines algorithm behavior. The exact same logic with a stack instead of a queue produces a completely different exploration pattern. Next up, you'll tackle the case where not all moves cost the same.

Add Weighted Cells and Dijkstra's Algorithm

You now have two working algorithms that treat every move equally. BFS and DFS both assume moving to any neighboring cell costs the same.

But what if some cells are harder to cross than others? In this step, you will place weighted cells on the grid, watch BFS fail to account for them, and then implement Dijkstra's algorithm with a priority queue that finally handles varying costs.

In this step, get ready to:
  • Place weighted cells on the grid and observe that BFS ignores their cost.
  • Implement Dijkstra's algorithm using a min-heap to find the lowest-cost path.
  • Compare BFS and Dijkstra on the same weighted maze to see the difference visually.
Place weighted cells and expose BFS's limitation

Your grid already supports a third cell type: weighted cells. These light orange cells cost 5 to traverse instead of 1 for normal cells.

  • Run your visualizer by running this command:
python pathfinder.py
  • Right-click to place a green start point on the left side of the grid.
  • Right-click to place a red end point on the right side of the grid.
  • Hover your mouse over empty cells between start and end, then press the w key to toggle them to weighted (light orange).
  • Create a thick band of 3-4 rows of orange weighted cells between your start and end, leaving an unweighted path available above or below the band (a longer route that avoids the orange cells).

How do weighted cells work?

Normal (white) cells cost 1 to enter. Weighted (orange) cells cost 5 to enter. A smart algorithm should prefer a longer path through cheap cells over a short path through expensive ones.

Before you click BFS, think about this: will BFS route around the expensive orange cells, or will it cut straight through them?

  • Click the BFS button.

BFS cuts straight through the orange cells. It finds the path with the fewest hops, completely ignoring that those cells cost 5 each. The status bar reports path length but has no concept of total cost.

Why does BFS ignore weights?

BFS uses a FIFO queue. It processes cells in the order they were discovered, layer by layer. Every cell gets explored at equal priority regardless of the cost to enter it.

To respect varying costs, you need a data structure that always hands you the cheapest cell next. That data structure is a min-heap (priority queue), and the algorithm that uses it is Dijkstra's.

  • Close the visualizer window for now.
Implement Dijkstra's algorithm

Dijkstra's algorithm replaces the queue with a min-heap. Instead of processing cells in discovery order, it always processes the cell with the lowest cumulative cost first.

  • In pathfinder.py, find the existing run_dijkstra method. It currently looks like this:
    def run_dijkstra(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.status_label.config(text="Dijkstra not yet implemented")
  • Delete the entire run_dijkstra method and replace it with the following code that sets up the heap and begins the animation loop:
    def run_dijkstra(self):
        if self.start is None or self.end is None or self.running:
            self.status_label.config(text="Set start and end first (right-click)")
            return
        self.reset_visited()
        self.running = True
        self.status_label.config(text="Running Dijkstra...")

        # Min-heap stores (cost, row, col) tuples
        heap = [(0, self.start[0], self.start[1])]
        # Track the cheapest known cost to reach each cell
        cost_so_far = {self.start: 0}
        came_from = {}
        visited = set()
        visited_count = [0]

        def step():
            if not self.running:
                return
            if not heap:
                self.running = False
                self.status_label.config(
                    text=f"Dijkstra: No path found. Visited: {visited_count[0]}"
                )
                return

            # Always pop the cheapest cell from the heap
            cost, row, col = heapq.heappop(heap)
            current = (row, col)

            if current in visited:
                self.root.after(1, step)
                return
            visited.add(current)
            visited_count[0] += 1

What does this code do?

  • heap is a min-heap of (cost, row, col) tuples. Python's heapq always pops the tuple with the smallest first element (lowest cost).
  • cost_so_far tracks the cheapest known cost to reach each cell. If a neighbor can be reached more cheaply, the dictionary gets updated.
  • The visited set prevents re-processing cells that already have their final cost. If a cell was already popped from the heap, we skip it.
  • heapq.heappop(heap) always gives you the cheapest unprocessed cell. This is the key difference from BFS (which uses a queue and pops in FIFO order).
  • Directly below the code you just pasted (still inside the step() function, at the same indentation level as if current in visited:), add the goal check, cell coloring, and neighbor exploration:
            if current == self.end:
                path_len = self._trace_path(came_from, self.end)
                self.running = False
                self.status_label.config(
                    text=f"Dijkstra: Cost {cost}, Path length {path_len}, Visited: {visited_count[0]}"
                )
                return

            if current != self.start:
                self.canvas.itemconfig(
                    self.rect_ids[row][col], fill=COLORS["visited"]
                )

            # Explore neighbors with weighted edge costs
            for nr, nc in self._get_neighbors(row, col):
                neighbor = (nr, nc)
                move_cost = 5 if self.grid_data[nr][nc] == WEIGHTED else 1
                new_cost = cost + move_cost
                if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                    cost_so_far[neighbor] = new_cost
                    came_from[neighbor] = current
                    heapq.heappush(heap, (new_cost, nr, nc))

            self.root.after(ANIMATION_DELAY, step)

        step()

What does this code do?

  • move_cost = 5 if self.grid_data[nr][nc] == WEIGHTED else 1 assigns a cost of 5 to orange cells and 1 to normal cells. This is the weighted edge that BFS cannot see.
  • The if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor] check ensures we only push a neighbor onto the heap if we found a cheaper path to it.
  • heapq.heappush(heap, (new_cost, nr, nc)) adds the neighbor with its cumulative cost. The heap keeps it sorted so the cheapest cell always surfaces first.
  • The status bar now displays the total path cost, not just hop count. This lets you compare costs between algorithms.
  • Save pathfinder.py.
  • Run the visualizer to confirm Dijkstra's works by running:
python pathfinder.py
  • Right-click to set start and end points.
  • Click Dijkstra. You should see cells turn light blue as the algorithm explores, then a yellow path appears when it reaches the end.

Seeing an error or no animation?

  • Check that the step() call at the bottom is at the same indentation level as def step(): (inside run_dijkstra but outside the nested function).
  • Make sure the body of step() is indented 12 spaces (3 levels: class, method, function). Python is strict about indentation.
  • If you see NameError: name 'heapq' is not defined, confirm that import heapq is still at the top of your file.

Why isn't my Dijkstra's algorithm animating?

✔️ Awesome, I've got everything!

Great. Double check you have saved pathfinder.py and that Dijkstra animates correctly with a yellow path appearing at the end.

ⓧ I'd like to double check the full code

The full pathfinder.py file is too long to show in one block. Scroll up and confirm these pieces are in your run_dijkstra method, in order:

  • Guard clause checking self.start and self.end, then self.reset_visited() and self.running = True.
  • Data structures: heap, cost_so_far, came_from, visited, visited_count initialized.
  • Inner step() function with heapq.heappop, visited check, goal check, coloring, and neighbor loop with heapq.heappush.
  • Final step() call at the bottom of run_dijkstra to kick off the animation.
Compare BFS and Dijkstra on weighted cells

Now for the payoff. You will run both algorithms on the same weighted maze and watch how they make different choices.

  • In the running visualizer, click Clear All to start fresh.
  • Right-click to place a start point on the far left and an end point on the far right.
  • Hover over cells and press w to create a wide horizontal band of weighted (orange) cells between start and end. Leave an unweighted corridor above or below the band.
  • Click BFS. Watch the path it finds and note the path length shown in the status bar.
  • Click Reset to clear the visited coloring (walls and weighted cells stay).

Before you click Dijkstra, predict: will Dijkstra find the same path as BFS, or a different one?

  • Click Dijkstra.

Dijkstra routes around the orange cells, taking the longer but cheaper corridor. The status bar shows a lower total cost even though the path length (hop count) is higher than what BFS found.

Why do the paths differ?

BFS minimizes hop count. It found the geometrically shortest path (fewest cells). Dijkstra minimizes total cost. It found the cheapest path by avoiding cells that cost 5 each.

This is exactly why a priority queue matters. A FIFO queue (BFS) has no way to prioritize cheaper cells over expensive ones. A min-heap (Dijkstra) always surfaces the cheapest option first.

You now have three algorithms, each powered by a different data structure: a queue (BFS), a stack (DFS), and a heap (Dijkstra). Next up, you will take on a Secret Mission to add A* search and watch it outperform all three.

Secret mission

Add A* Search

Dijkstra's explores in all directions equally, wasting time on cells far from the goal. Can you add a smarter algorithm that uses a heuristic to focus the search toward the target, exploring far fewer cells while still finding the optimal path?

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally using Python and tkinter. There are no cloud resources, paid APIs, or ongoing costs.

Resources you used:

  • pathfinder.py file (your pathfinding visualizer source code).

Keep everything running

No action needed. Choose this if you want to keep experimenting with your visualizer, adding new algorithms, or tweaking the animation speed.

  • Your pathfinder.py file stays where you saved it.
  • Run it any time with python pathfinder.py in your terminal.

Pause - I'll come back to this later

Since this is a local Python file with no running processes or servers, there is nothing to pause. Your file sits on disk and uses no resources when you are not running it.

  • Close the tkinter window if it is still open.
  • Close the file in VS Code to declutter your workspace.

Delete - I don't want to use this again

Remove your project file entirely to start fresh.

  • Close pathfinder.py in VS Code.
  • Delete the file using your terminal:

macOS

rm ~/Desktop/pathfinder.py

Windows

Remove-Item ~\Desktop\pathfinder.py
  • Confirm the file is gone by checking your Desktop.

That's a Wrap!

That's a Wrap!

Nice work. You just built a fully interactive pathfinding visualizer that brings graph traversal algorithms to life, cell by cell.

You've learned how to:

  • Build an interactive grid application with mouse-driven wall drawing, start/end placement, and real-time algorithm animation using tkinter and root.after().
  • Implement BFS from scratch using collections.deque (FIFO queue) and DFS using a list as a stack (LIFO), visually proving how data structure choice determines exploration pattern and shortest-path guarantees.
  • Implement Dijkstra's algorithm from scratch using heapq (min-heap/priority queue), handling weighted graphs where BFS fails to find the lowest-cost path.
  • Secret Mission: Implemented A* search with Manhattan distance heuristic, demonstrating how informed search outperforms uninformed search by visiting fewer cells while still finding the optimal path.

Ready to quiz yourself?