Build a Pathfinding Visualizer
Visualize BFS, DFS, and Dijkstra's algorithms on an interactive grid.
Introduction
30 Second Summary
Every time you open a maps app and ask for directions, an algorithm is racing through millions of possible routes to find the best one. The magic behind that instant answer comes down to one choice: which data structure the algorithm uses to decide where to look next.
In this project, you will build an interactive pathfinding visualizer that lets you watch three different algorithms solve a maze in real time. You will see exactly how a queue, a stack, and a priority queue each produce wildly different search behaviors on the same grid.
What You'll Build
An interactive Pygame application where you click to place start/end nodes and draw walls on a grid, then press a key to watch BFS, DFS, or Dijkstra's algorithm find the shortest path with color-coded animation.
By the end of this project, you'll have:
- A working interactive grid where you place start/end nodes and draw walls with mouse clicks.
- Three pathfinding algorithms (BFS, DFS, Dijkstra's) implemented from scratch, each using a different data structure (queue, stack, heap).
- Real-time color-coded visualization showing how each algorithm explores the grid differently.
- Secret Mission: Add A* search with Manhattan distance heuristic and visually compare it to Dijkstra's.
Are there any prerequisites?
You should be comfortable with basic Python (functions, classes, loops). Familiarity with introductory data structures (lists, dictionaries) is helpful but not required. This project teaches you queues, stacks, and heaps hands-on.
Before We Start
To build a pathfinding visualizer, you need a way to draw shapes on screen and update them frame by frame.
In this step, you will install Pygame, a Python library for creating games and visual simulations. You will also create the project file and confirm that a basic window appears on screen.
In this step, get ready to:
- Verify that Python 3.6 or higher is installed.
- Install Pygame and confirm it works.
- Create your project file with a basic game window.
Verify your Python installation
Pygame requires Python 3.6 or higher. Let's confirm your version before installing anything.
- Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
- Type PyCharm and press Enter to open it.
- Open PyCharm's built-in terminal by pressing Alt+F12 (Windows) or Option+F12 (macOS).
- Check your Python version by running this command:
python --versionYou should see a version number printed in the terminal.
✔️ I see version 3.6 or higher
Your Python version is compatible with Pygame. Move on to the next substep.
ⓧ I see a version lower than 3.6
You need Python 3.6 or higher for Pygame to work. Visit the official Python downloads page to install a newer version:
- Go to https://www.python.org/downloads/ and download the latest stable release.
- Run the installer and follow the prompts.
- Restart PyCharm after installing.
- Run python --version again to confirm the new version.
ⓧ Command not found
Python is not available in your terminal path. Download and install Python from the official website:
- Go to https://www.python.org/downloads/ and download the latest stable release.
- During installation on Windows, check the box that says Add Python to PATH.
- Restart PyCharm after installing.
- Run python --version again to confirm it works.
Install Pygame
Pygame is the library that gives you a window, drawing tools, and an event loop for your visualizer. Let's install version 2.6.1 so everyone is on the same page.
- Install Pygame by running this command in PyCharm's terminal:
pip install pygame==2.6.1What does this command do?
The pip install command downloads and installs a Python package from the PyPI registry. The ==2.6.1 part pins the exact version so your setup matches this project.
- Verify Pygame installed correctly by running this command:
python -m pygame.examples.aliensA small game window should appear with a playable aliens game. This confirms Pygame is working.
- Close the aliens game window before continuing.
Game window not appearing?
- Make sure the pip install pygame==2.6.1 command completed without errors. Look for "Successfully installed" in the output.
- If you see a permission error, try running pip install --user pygame==2.6.1 instead.
- help me troubleshoot my Pygame installation
Create your project file
Every Pygame application follows the same basic structure: initialize the library, create a window, run a loop that listens for events, and clean up when done. You will build on this skeleton for the rest of the project.
- In PyCharm's Project panel on the left, right-click your project folder.
- Select New, then Python File.
- Type pathfinder as the file name and press Enter. PyCharm adds the .py extension automatically.
- Copy the following code into pathfinder.py:
import pygame
# Initialize Pygame
pygame.init()
# Create a 600x600 pixel window
surface = pygame.display.set_mode((600, 600))
pygame.display.set_caption("Pathfinding Visualizer")
# Main game loop
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
pygame.display.flip()
# Clean up when the window is closed
pygame.quit()What does this code do?
- pygame.init() starts up all of Pygame's internal modules (display, sound, events).
- pygame.display.set_mode((600, 600)) creates a 600 by 600 pixel window and returns the drawing surface.
- The while running loop keeps the window open. Each iteration checks for events (like clicking the X button) and refreshes the display.
- pygame.display.flip() updates the full screen with whatever has been drawn to the surface.
- pygame.quit() shuts down Pygame cleanly after the loop exits.
- Save pathfinder.py.
- Run the file by right-clicking in the editor and selecting Run 'pathfinder'.
You should see a black 600x600 window with the title "Pathfinding Visualizer" appear. It closes cleanly when you click the X button.
Window not appearing or closing immediately?
- Check that pygame.init() is called before pygame.display.set_mode(). The order matters.
- Make sure pygame.display.flip() is inside the while running loop. Without it, the window never refreshes.
- If the window flashes and disappears, check that your for event loop is indented inside the while loop.
- help me debug my Pygame window not appearing
✔️ Awesome, I've got everything!
Great job. Double check you have saved pathfinder.py and confirmed the black window appears.
ⓧ I'd like to double check the full code
Here is the complete pathfinder.py file at this point:
import pygame
pygame.init()
surface = pygame.display.set_mode((600, 600))
pygame.display.set_caption("Pathfinding Visualizer")
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
pygame.display.flip()
pygame.quit()Your environment is ready and your game window is running. Next up, you will build the grid system and make it interactive with mouse clicks.
Build the Grid and Node System
Your Pygame window is alive. Now you need to fill it with something useful: a grid that represents a graph.
In pathfinding, each cell in a grid is a node, and each node connects to its neighbors. In this step, you will build the grid data structure, draw it to the screen, and add mouse interaction so you can place start points, end points, and walls.
In this step, get ready to:
- Define a Node class that represents each cell on the grid.
- Create helper functions that build and render the grid.
- Add mouse interaction to place start, end, and wall nodes.
Define the Node class and grid constants
Before building any algorithms, you need the data structures that represent the grid. Each cell needs to know its position, its current color (which encodes its state), and which neighbors it connects to.
- In PyCharm, open pathfinder.py.
- Select all the existing code and delete it.
- Replace it with the following imports and constants:
import pygame
import heapq
from collections import deque
# Constants
WIDTH = 600
ROWS = 25
CELL_SIZE = WIDTH // ROWS
# Colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
LIGHT_BLUE = (173, 216, 230)
YELLOW = (255, 255, 0)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)What does this code do?
- WIDTH = 600 sets the window size. ROWS = 25 divides it into a 25x25 grid. CELL_SIZE calculates how many pixels wide each cell is (24px).
- Each color constant is an RGB tuple that encodes a node's state: GREEN for start, RED for end, LIGHT_BLUE for visited cells, and so on.
- The heapq and deque imports will be used in later steps for the algorithm data structures.
Now you need a class to represent each cell. Each node tracks its position, its color (state), and its neighbors on the grid.
- Add the following Node class below the color constants:
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.color = WHITE
self.neighbors = []
def get_pos(self):
return self.row, self.col
def is_wall(self):
return self.color == BLACK
def is_start(self):
return self.color == GREEN
def is_end(self):
return self.color == RED
def reset(self):
self.color = WHITE
def make_start(self):
self.color = GREEN
def make_end(self):
self.color = RED
def make_wall(self):
self.color = BLACK
def make_visited(self):
self.color = LIGHT_BLUE
def make_frontier(self):
self.color = ORANGE
def make_path(self):
self.color = YELLOW
def draw(self, surface):
# Calculate pixel position from grid coordinates
x = self.col * CELL_SIZE
y = self.row * CELL_SIZE
pygame.draw.rect(surface, self.color, (x, y, CELL_SIZE, CELL_SIZE))
def update_neighbors(self, grid):
# Check all 4 adjacent cells and add non-wall neighbors
self.neighbors = []
# Down
if self.row < ROWS - 1 and not grid[self.row + 1][self.col].is_wall():
self.neighbors.append(grid[self.row + 1][self.col])
# Up
if self.row > 0 and not grid[self.row - 1][self.col].is_wall():
self.neighbors.append(grid[self.row - 1][self.col])
# Right
if self.col < ROWS - 1 and not grid[self.row][self.col + 1].is_wall():
self.neighbors.append(grid[self.row][self.col + 1])
# Left
if self.col > 0 and not grid[self.row][self.col - 1].is_wall():
self.neighbors.append(grid[self.row][self.col - 1])What does this class do?
Each Node object is one cell in your grid. Instead of storing a separate "state" field, the node's color IS its state. Changing a node's color to BLACK makes it a wall. Changing it to GREEN makes it the start.
The update_neighbors() method checks all four adjacent cells (up, down, left, right). If a neighbor is not a wall, it gets added to the node's neighbors list. This is how the grid becomes a graph with edges between adjacent cells.
- Save pathfinder.py.
You will not see any visual change yet. The Node class is a data structure that the drawing functions will use next.
Seeing a red underline in PyCharm?
If PyCharm shows warnings about unused imports (heapq and deque), that is expected. Those imports will be used in later steps when you implement the algorithms.
Help me fix errors in my Node class.
Create the grid and drawing functions
You have a Node class, but you need functions to create a 2D grid of nodes and render them to the screen.
- Below the Node class, add the make_grid function:
def make_grid(rows):
# Build a 2D list of Node objects
grid = []
for i in range(rows):
grid.append([])
for j in range(rows):
node = Node(i, j)
grid[i].append(node)
return gridWhat does this function do?
make_grid creates a 25x25 2D list where each element is a Node object. The node at grid[3][7] is the cell at row 3, column 7. This 2D list is your graph's adjacency structure.
- Add the drawing and input utility functions below make_grid:
def draw_grid_lines(surface, rows):
# Draw grey lines to show cell boundaries
for i in range(rows):
pygame.draw.line(surface, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
pygame.draw.line(surface, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))
def draw(surface, grid, rows):
# Clear the screen, draw all nodes, then draw grid lines
surface.fill(WHITE)
for row in grid:
for node in row:
node.draw(surface)
draw_grid_lines(surface, rows)
pygame.display.flip()
def get_clicked_pos(pos):
# Convert mouse pixel position to grid row and column
x, y = pos
row = y // CELL_SIZE
col = x // CELL_SIZE
return row, colWhat do these functions do?
- draw_grid_lines() draws horizontal and vertical grey lines at each cell boundary so the grid is visible.
- draw() is the main rendering function. It clears the screen, redraws every node at its current color, overlays the grid lines, and flips the display buffer.
- get_clicked_pos() translates a mouse click's pixel coordinates into the grid row and column that was clicked.
- Save pathfinder.py.
You still will not see visual output because there is no game loop calling these functions yet. The next substep adds that.
Seeing an IndentationError?
Make sure each function is defined at the module level (no indentation before def). These functions sit outside and below the Node class.
Help me fix an indentation or syntax error in my grid functions.
Add mouse interaction for placing nodes
The grid data structure and rendering functions are ready. Now you need a main() function with a game loop that draws the grid each frame and responds to mouse clicks.
- Add the main() function and the entry point below get_clicked_pos:
def main():
pygame.init()
surface = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("Pathfinding Visualizer")
grid = make_grid(ROWS)
start = None
end = None
running = True
while running:
draw(surface, grid, ROWS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
# Left click: place start, end, or wall
if pygame.mouse.get_pressed()[0]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if not start and node != end:
start = node
start.make_start()
elif not end and node != start:
end = node
end.make_end()
elif node != start and node != end:
node.make_wall()
# Right click: erase a node
elif pygame.mouse.get_pressed()[2]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()
pygame.quit()
if __name__ == "__main__":
main()What does this code do?
- The game loop calls draw() every frame, so the grid always reflects the current state of every node.
- Left-click logic follows a priority: the first click places a green start node, the second click places a red end node, and all subsequent clicks toggle walls (black).
- Right-click erases any node back to white. If you erase the start or end, it sets that variable back to None so you can place a new one.
- The if __name__ == "__main__": guard ensures main() only runs when you execute the file directly.
- Save pathfinder.py.
- Run the file by clicking the green play button in PyCharm, or by right-clicking the file and selecting Run 'pathfinder'.
- Left-click anywhere on the grid. The first click should produce a green cell (start). The second click should produce a red cell (end). Additional clicks produce black cells (walls).
- Right-click a colored cell to erase it back to white.
You should see a white 25x25 grid with visible grey lines. Clicking places colored cells exactly where your mouse is.
Window opens but clicks do nothing?
Check that draw(surface, grid, ROWS) is inside the while running: loop but BEFORE the for event block. If the draw call is missing, the screen never updates to show your changes.
Also confirm that pygame.mouse.get_pressed()[0] uses square brackets (indexing a tuple), not parentheses.
Help me debug why my grid doesn't respond to mouse clicks.
✔️ Awesome, I've got everything!
Great. Double check you have saved your file before moving on.
ⓧ I'd like to double check the full code
Here is the full pathfinder.py as it should look at the end of this step:
import pygame
import heapq
from collections import deque
# Constants
WIDTH = 600
ROWS = 25
CELL_SIZE = WIDTH // ROWS
# Colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
LIGHT_BLUE = (173, 216, 230)
YELLOW = (255, 255, 0)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.color = WHITE
self.neighbors = []
def get_pos(self):
return self.row, self.col
def is_wall(self):
return self.color == BLACK
def is_start(self):
return self.color == GREEN
def is_end(self):
return self.color == RED
def reset(self):
self.color = WHITE
def make_start(self):
self.color = GREEN
def make_end(self):
self.color = RED
def make_wall(self):
self.color = BLACK
def make_visited(self):
self.color = LIGHT_BLUE
def make_frontier(self):
self.color = ORANGE
def make_path(self):
self.color = YELLOW
def draw(self, surface):
x = self.col * CELL_SIZE
y = self.row * CELL_SIZE
pygame.draw.rect(surface, self.color, (x, y, CELL_SIZE, CELL_SIZE))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < ROWS - 1 and not grid[self.row + 1][self.col].is_wall():
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_wall():
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < ROWS - 1 and not grid[self.row][self.col + 1].is_wall():
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_wall():
self.neighbors.append(grid[self.row][self.col - 1])
def make_grid(rows):
grid = []
for i in range(rows):
grid.append([])
for j in range(rows):
node = Node(i, j)
grid[i].append(node)
return grid
def draw_grid_lines(surface, rows):
for i in range(rows):
pygame.draw.line(surface, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
pygame.draw.line(surface, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))
def draw(surface, grid, rows):
surface.fill(WHITE)
for row in grid:
for node in row:
node.draw(surface)
draw_grid_lines(surface, rows)
pygame.display.flip()
def get_clicked_pos(pos):
x, y = pos
row = y // CELL_SIZE
col = x // CELL_SIZE
return row, col
def main():
pygame.init()
surface = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("Pathfinding Visualizer")
grid = make_grid(ROWS)
start = None
end = None
running = True
while running:
draw(surface, grid, ROWS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if pygame.mouse.get_pressed()[0]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if not start and node != end:
start = node
start.make_start()
elif not end and node != start:
end = node
end.make_end()
elif node != start and node != end:
node.make_wall()
elif pygame.mouse.get_pressed()[2]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()
pygame.quit()
if __name__ == "__main__":
main()Your interactive grid is working. You can draw any maze you like. Next up, you will implement BFS (Breadth-First Search) and watch it explore your grid layer by layer using a queue.
Implement BFS
Your grid is interactive, but it does not yet know how to find a path between two points. That is what Breadth-First Search (BFS) is for.
BFS uses a queue to explore nodes layer by layer outward from the start. Because it expands one full layer before moving to the next, it guarantees finding the shortest path on an unweighted grid.
In this step, get ready to:
- Write a path reconstruction function that traces the solution backwards.
- Implement BFS using a deque (double-ended queue) for FIFO processing.
- Wire up keyboard controls so SPACE triggers BFS with real-time animation.
Understand how neighbor computation feeds BFS
BFS needs to know which cells each node can reach. The update_neighbors method you wrote in the previous step handles this by checking all 4 adjacent cells (up, down, left, right) and skipping walls.
Why update neighbors right before running?
Walls can be placed or removed at any time. If you computed neighbors once at startup, they would become stale after the user draws new walls.
By calling update_neighbors on every node right before running BFS, you guarantee the neighbor lists reflect the current maze state. You will wire this call into the keyboard handler in substep 3.
Write the path reconstruction and BFS functions
BFS tracks where each node came from in a dictionary. Once it reaches the end, a separate function walks that dictionary backwards to highlight the shortest path.
- In pathfinder.py, find the get_clicked_pos function near the bottom of your helper functions.
- Add the following reconstruct_path function directly below get_clicked_pos:
def reconstruct_path(came_from, current, draw_func):
# Trace backwards from end to start using the came_from map
while current in came_from:
current = came_from[current]
current.make_path()
draw_func()What does this code do?
This function walks backwards through the came_from dictionary. Each node maps to the node that discovered it. Following these links from end to start reveals the shortest path.
Each step along the way colors the node YELLOW and calls draw_func() so you see the path appear one cell at a time.
You will not see a change yet. The BFS function you write next will call reconstruct_path when it finds the end node.
- Directly below reconstruct_path, add the BFS function by pasting this code:
def bfs(draw_func, grid, start, end):
# Initialize queue with start node (FIFO order)
queue = deque([start])
came_from = {}
visited = {start}
while queue:
# Keep window responsive during algorithm
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
# Dequeue from the front (FIFO)
current = queue.popleft()
# Check if we reached the end
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
# Explore all unvisited neighbors
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
queue.append(neighbor)
neighbor.make_frontier()
# Mark current node as fully explored
if current != start:
current.make_visited()
draw_func()
return FalseWhat does this code do?
- deque([start]) creates the queue with the start node as the first item. A deque provides O(1) pops from the left side, which is essential for FIFO ordering.
- queue.popleft() removes from the front. This is what makes BFS expand in layers. Nodes discovered first are processed first.
- visited is a set that prevents the same node from being added to the queue twice. Without it, the algorithm would loop forever.
- came_from[neighbor] = current records which node discovered this neighbor. This builds the chain that reconstruct_path follows backwards.
- draw_func() is called every iteration. This redraws the entire grid each loop, creating the real-time animation effect as colors change.
Why handle pygame.QUIT inside the algorithm?
BFS takes over the main thread while it runs. Without checking for pygame.QUIT events inside the while loop, clicking the window's close button would do nothing until the algorithm finishes. The event check keeps the window responsive.
You will not see a change yet. The next substep wires BFS to a keyboard shortcut so you can trigger it.
Add keyboard controls and path clearing
You need a way to trigger BFS from the keyboard and a way to reset the visualization colors without losing your walls.
- Add the clear_path function directly below your bfs function:
def clear_path(grid, start, end):
# Reset all non-wall, non-start, non-end nodes to white
for row in grid:
for node in row:
if not node.is_wall() and not node.is_start() and not node.is_end():
node.reset()What does this code do?
clear_path removes the visited (light blue), frontier (orange), and path (yellow) colors while keeping your walls, start, and end intact. This lets you re-run algorithms on the same maze without redrawing everything.
Now you need to update the main() function to handle keyboard events.
- In your main() function, find the right-click handler block that ends with node.reset(). Find this code:
elif pygame.mouse.get_pressed()[2]: # Right click
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()- Add the following keyboard handling code directly below that right-click block, still inside the for event in pygame.event.get(): loop:
if event.type == pygame.KEYDOWN:
if start and end:
# Refresh neighbor lists to account for current walls
for row in grid:
for node in row:
node.update_neighbors(grid)
if event.key == pygame.K_SPACE:
clear_path(grid, start, end)
bfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_c:
clear_path(grid, start, end)
if event.key == pygame.K_r:
start = None
end = None
grid = make_grid(ROWS)What does this code do?
- update_neighbors(grid) is called on every node before running BFS. This ensures the neighbor lists reflect the current wall layout.
- SPACE triggers BFS. The lambda: draw(surface, grid, ROWS) passes your draw function so BFS can animate each frame.
- C clears visited and path colors while keeping walls intact.
- R does a full reset, wiping everything and creating a fresh grid.
- Save pathfinder.py.
- Run the file in PyCharm.
- Left-click to place a green start node, then a red end node, then draw some black walls between them.
- Press SPACE. You should see orange cells (frontier) expanding outward layer by layer from the start, followed by light blue (visited) cells filling in behind. When BFS reaches the red end node, a yellow path appears tracing back to the start.
Nothing happens when you press SPACE?
- Make sure you placed both a green start node and a red end node before pressing SPACE. The algorithm only runs when both exist.
- Check that the keyboard handling block is inside the for event in pygame.event.get(): loop at the same indentation level as the mouse handlers.
- If you see an error about reconstruct_path not being defined, make sure it appears in the file above the bfs function.
Why isn't my BFS algorithm running when I press SPACE?
✔️ Awesome, I've got everything!
Great. Double check you have saved pathfinder.py and that BFS animates correctly when you press SPACE.
ⓧ I'd like to double check the full code
Here is the complete pathfinder.py at this point:
import pygame
import heapq
from collections import deque
# Constants
WIDTH = 600
ROWS = 25
CELL_SIZE = WIDTH // ROWS
# Colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
LIGHT_BLUE = (173, 216, 230)
YELLOW = (255, 255, 0)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.color = WHITE
self.neighbors = []
def get_pos(self):
return self.row, self.col
def is_wall(self):
return self.color == BLACK
def is_start(self):
return self.color == GREEN
def is_end(self):
return self.color == RED
def reset(self):
self.color = WHITE
def make_start(self):
self.color = GREEN
def make_end(self):
self.color = RED
def make_wall(self):
self.color = BLACK
def make_visited(self):
self.color = LIGHT_BLUE
def make_frontier(self):
self.color = ORANGE
def make_path(self):
self.color = YELLOW
def draw(self, surface):
x = self.col * CELL_SIZE
y = self.row * CELL_SIZE
pygame.draw.rect(surface, self.color, (x, y, CELL_SIZE, CELL_SIZE))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < ROWS - 1 and not grid[self.row + 1][self.col].is_wall():
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_wall():
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < ROWS - 1 and not grid[self.row][self.col + 1].is_wall():
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_wall():
self.neighbors.append(grid[self.row][self.col - 1])
def make_grid(rows):
grid = []
for i in range(rows):
grid.append([])
for j in range(rows):
node = Node(i, j)
grid[i].append(node)
return grid
def draw_grid_lines(surface, rows):
for i in range(rows):
pygame.draw.line(surface, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
pygame.draw.line(surface, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))
def draw(surface, grid, rows):
surface.fill(WHITE)
for row in grid:
for node in row:
node.draw(surface)
draw_grid_lines(surface, rows)
pygame.display.flip()
def get_clicked_pos(pos):
x, y = pos
row = y // CELL_SIZE
col = x // CELL_SIZE
return row, col
def reconstruct_path(came_from, current, draw_func):
while current in came_from:
current = came_from[current]
current.make_path()
draw_func()
def bfs(draw_func, grid, start, end):
queue = deque([start])
came_from = {}
visited = {start}
while queue:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current = queue.popleft()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
queue.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def clear_path(grid, start, end):
for row in grid:
for node in row:
if not node.is_wall() and not node.is_start() and not node.is_end():
node.reset()
def main():
pygame.init()
surface = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("Pathfinding Visualizer")
grid = make_grid(ROWS)
start = None
end = None
running = True
while running:
draw(surface, grid, ROWS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if pygame.mouse.get_pressed()[0]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if not start and node != end:
start = node
start.make_start()
elif not end and node != start:
end = node
end.make_end()
elif node != start and node != end:
node.make_wall()
elif pygame.mouse.get_pressed()[2]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()
if event.type == pygame.KEYDOWN:
if start and end:
for row in grid:
for node in row:
node.update_neighbors(grid)
if event.key == pygame.K_SPACE:
clear_path(grid, start, end)
bfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_c:
clear_path(grid, start, end)
if event.key == pygame.K_r:
start = None
end = None
grid = make_grid(ROWS)
pygame.quit()
if __name__ == "__main__":
main()BFS expands in beautiful concentric layers and always finds the shortest path. But what if you swapped the queue for a stack? Next up, you will implement DFS and see how one data structure change completely transforms the exploration pattern.
Implement DFS
Your BFS implementation explores the grid layer by layer, expanding outward like a ripple. Now you will implement a fundamentally different traversal pattern by swapping one data structure.
Depth-First Search uses a stack instead of a queue. That single change makes the algorithm dive deep into one path before backtracking. You will see the difference immediately in the animation.
In this step, get ready to:
- Implement the DFS algorithm using a Python list as a stack.
- Bind the D key to trigger DFS and compare its exploration pattern to BFS.
Implement DFS using a stack
BFS uses a queue (FIFO) and always processes the oldest node first. DFS uses a stack (LIFO) and always processes the most recently added node. This means DFS keeps diving deeper along one path until it hits a dead end, then backtracks.
- In pathfinder.py, find the bfs() function. Add the following dfs() function directly below it (before clear_path):
def dfs(draw_func, grid, start, end):
# Use a Python list as a stack (append to push, pop from end)
stack = [start]
came_from = {}
visited = {start}
while stack:
# Handle window close events during animation
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
# Pop from end of list = LIFO (stack behavior)
current = stack.pop()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
if current not in visited:
visited.add(current)
# Add unvisited neighbors to the stack
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
stack.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return FalseWhat does this code do?
This function mirrors BFS almost exactly. The critical difference is one line: stack.pop() instead of queue.popleft().
- stack.pop() removes the last item added (LIFO). This means the algorithm always processes the most recently discovered neighbor, diving deeper before exploring siblings.
- The came_from dictionary and reconstruct_path() work identically to BFS, tracing the discovered path back from end to start.
- The coloring is the same: ORANGE for nodes in the frontier (on the stack), LIGHT_BLUE for visited nodes, YELLOW for the final path.
Why doesn't DFS guarantee the shortest path?
BFS explores all nodes at distance 1, then distance 2, then distance 3. So the first time it reaches the end node, that path is guaranteed to be the shortest. DFS commits to one direction and goes as far as possible before backtracking.
The first path DFS finds might be a winding route that is much longer than necessary. You will see this clearly in the animation.
- Save pathfinder.py.
Seeing a syntax error?
- Make sure the dfs() function is at the same indentation level as bfs() (a top-level function, not nested inside another function).
- Check that you placed the function after the closing return False of bfs() and before clear_path().
Help me debug a syntax error in my DFS function.
Add the D key binding to trigger DFS
Your visualizer already has the C key to clear visited/path colors and R to fully reset the grid. Now you need a way to trigger DFS from the keyboard.
- In the main() function, find the block that handles the SPACE key:
if event.key == pygame.K_SPACE:
clear_path(grid, start, end)
bfs(lambda: draw(surface, grid, ROWS), grid, start, end)- Add the following block directly below it, at the same indentation level:
if event.key == pygame.K_d:
clear_path(grid, start, end)
dfs(lambda: draw(surface, grid, ROWS), grid, start, end)What does this code do?
When you press D, the visualizer first calls clear_path() to remove any previous algorithm colors (LIGHT_BLUE, ORANGE, YELLOW) while preserving your walls, start, and end. Then it runs DFS with the draw callback for real-time animation.
- Save pathfinder.py.
- Run the program. Place a start node (green), an end node (red), and draw some walls between them.
- Press D to run DFS. You should see the algorithm dive deep along one direction (ORANGE frontier), coloring visited cells LIGHT_BLUE, then backtracking when it hits a dead end.
- Press C to clear the colors, then press SPACE to run BFS on the same maze. Compare how BFS expands in even layers while DFS explored in a winding, depth-first pattern.
Pressing D does nothing?
- Make sure you placed both a start (green) and end (red) node before pressing D. The key binding only fires when both exist.
- Check that the if event.key == pygame.K_d: block is inside the if start and end: check, at the same level as the SPACE key block.
Help me figure out why pressing D isn't triggering DFS.
✔️ Awesome, I've got everything!
Great. Double check you have saved your file before moving on.
ⓧ I'd like to double check the full code
import pygame
import heapq
from collections import deque
# Constants
WIDTH = 600
ROWS = 25
CELL_SIZE = WIDTH // ROWS
# Colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
LIGHT_BLUE = (173, 216, 230)
YELLOW = (255, 255, 0)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.color = WHITE
self.neighbors = []
def get_pos(self):
return self.row, self.col
def is_wall(self):
return self.color == BLACK
def is_start(self):
return self.color == GREEN
def is_end(self):
return self.color == RED
def reset(self):
self.color = WHITE
def make_start(self):
self.color = GREEN
def make_end(self):
self.color = RED
def make_wall(self):
self.color = BLACK
def make_visited(self):
self.color = LIGHT_BLUE
def make_frontier(self):
self.color = ORANGE
def make_path(self):
self.color = YELLOW
def draw(self, surface):
x = self.col * CELL_SIZE
y = self.row * CELL_SIZE
pygame.draw.rect(surface, self.color, (x, y, CELL_SIZE, CELL_SIZE))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < ROWS - 1 and not grid[self.row + 1][self.col].is_wall():
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_wall():
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < ROWS - 1 and not grid[self.row][self.col + 1].is_wall():
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_wall():
self.neighbors.append(grid[self.row][self.col - 1])
def make_grid(rows):
grid = []
for i in range(rows):
grid.append([])
for j in range(rows):
node = Node(i, j)
grid[i].append(node)
return grid
def draw_grid_lines(surface, rows):
for i in range(rows):
pygame.draw.line(surface, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
pygame.draw.line(surface, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))
def draw(surface, grid, rows):
surface.fill(WHITE)
for row in grid:
for node in row:
node.draw(surface)
draw_grid_lines(surface, rows)
pygame.display.flip()
def get_clicked_pos(pos):
x, y = pos
row = y // CELL_SIZE
col = x // CELL_SIZE
return row, col
def reconstruct_path(came_from, current, draw_func):
while current in came_from:
current = came_from[current]
current.make_path()
draw_func()
def bfs(draw_func, grid, start, end):
queue = deque([start])
came_from = {}
visited = {start}
while queue:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current = queue.popleft()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
queue.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def dfs(draw_func, grid, start, end):
stack = [start]
came_from = {}
visited = {start}
while stack:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current = stack.pop()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
if current not in visited:
visited.add(current)
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
stack.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def clear_path(grid, start, end):
for row in grid:
for node in row:
if not node.is_wall() and not node.is_start() and not node.is_end():
node.reset()
def main():
pygame.init()
surface = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("Pathfinding Visualizer")
grid = make_grid(ROWS)
start = None
end = None
running = True
while running:
draw(surface, grid, ROWS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if pygame.mouse.get_pressed()[0]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if not start and node != end:
start = node
start.make_start()
elif not end and node != start:
end = node
end.make_end()
elif node != start and node != end:
node.make_wall()
elif pygame.mouse.get_pressed()[2]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()
if event.type == pygame.KEYDOWN:
if start and end:
for row in grid:
for node in row:
node.update_neighbors(grid)
if event.key == pygame.K_SPACE:
clear_path(grid, start, end)
bfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_d:
clear_path(grid, start, end)
dfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_c:
clear_path(grid, start, end)
if event.key == pygame.K_r:
start = None
end = None
grid = make_grid(ROWS)
pygame.quit()
if __name__ == "__main__":
main()You now have two algorithms side by side that demonstrate how the choice of data structure changes behavior. Next up, you will implement Dijkstra's algorithm using a priority queue to see how weighted shortest-path search works.
Implement Dijkstra's Algorithm
You now have two algorithms that take opposite approaches to exploring a grid. BFS uses a queue to expand layer by layer, guaranteeing the shortest path. DFS uses a stack to dive deep before backtracking, often finding longer paths.
In this step, you will implement Dijkstra's algorithm using a priority queue (heap). On this uniform grid, Dijkstra's finds the same shortest path as BFS. The real power is in the pattern: the priority queue always expands the cheapest node first, which generalizes to weighted graphs where BFS would fail.
In this step, get ready to:
- Understand the weighted edges concept and why Dijkstra's uses a heap.
- Implement Dijkstra's algorithm with a distance dictionary and priority queue.
- Bind the J key and compare all three algorithms on the same maze.
Understand the weighted edges concept
BFS treats every move as equal. It does not care about cost. Dijkstra's algorithm, on the other hand, assigns a cost to every edge and always picks the cheapest option next.
In your grid, every move from one cell to an adjacent cell costs 1. This is a uniform weight. It means Dijkstra's will produce the same shortest path as BFS on this particular grid.
Why implement Dijkstra's on a uniform grid?
The value is in the pattern, not the result. Dijkstra's uses heapq to always expand the node with the lowest cumulative cost. This same code structure works on weighted graphs (where each edge could cost 1, 5, or 100) without any modification to the algorithm logic.
BFS only works correctly when all edges have equal weight. Dijkstra's handles any non-negative edge weight. You are learning the general-purpose tool.
Implement Dijkstra's algorithm
Dijkstra's algorithm maintains a distance dictionary that tracks the cheapest known cost to reach every node. It uses a heap (priority queue) to always process the node with the smallest total distance next.
- In pathfinder.py, find the dfs function. Add the following dijkstra function below it (before the clear_path function):
def dijkstra(draw_func, grid, start, end):
# Counter breaks ties when two nodes have the same distance
count = 0
# Push (distance, tiebreaker, node) onto the heap
heap = [(0, count, start)]
came_from = {}
# Set all distances to infinity, then mark start as 0
dist = {node: float("inf") for row in grid for node in row}
dist[start] = 0
visited = set()
while heap:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
# Always expand the node with the lowest cumulative cost
current_dist, _, current = heapq.heappop(heap)
# Skip nodes we have already finalized
if current in visited:
continue
visited.add(current)
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
# Each move costs 1 (uniform weight)
new_dist = dist[current] + 1
# Only update if we found a cheaper path
if new_dist < dist[neighbor]:
came_from[neighbor] = current
dist[neighbor] = new_dist
count += 1
heapq.heappush(heap, (new_dist, count, neighbor))
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return FalseWhat does this code do?
- dist is a dictionary that maps every node to its cheapest known distance from the start. Everything begins at infinity except the start node (which is 0).
- heapq.heappop(heap) always returns the tuple with the smallest first element. This guarantees you process the cheapest node next.
- The count variable is a tiebreaker. When two nodes have the same distance, Python would try to compare Node objects (which fails). The counter ensures a consistent ordering.
- The visited set prevents re-processing nodes. A node can appear in the heap multiple times (with different distances), but only the first pop matters because it has the lowest cost.
- new_dist = dist[current] + 1 is the relaxation step. If this new path to a neighbor is cheaper than any previously known path, we update the distance and push it onto the heap.
How is this different from BFS?
BFS uses a simple FIFO queue. Dijkstra's uses a min-heap sorted by cumulative cost. On a uniform grid (cost = 1 everywhere), they produce identical results. But if you changed some edges to cost 5 or 10, BFS would give wrong answers while Dijkstra's would still find the true cheapest path.
- Save pathfinder.py.
Seeing a TypeError about comparing Node objects?
This happens if the count tiebreaker is missing from your heap tuples. Make sure every heapq.heappush call uses the format (new_dist, count, neighbor) with three elements, not two.
Help me fix a TypeError in my Dijkstra's heap implementation.
Bind the J key and test all three algorithms
Now you need to connect Dijkstra's to a keyboard shortcut so you can trigger it alongside BFS and DFS.
- In the main() function, find the block that handles the D key for DFS:
if event.key == pygame.K_d:
clear_path(grid, start, end)
dfs(lambda: draw(surface, grid, ROWS), grid, start, end)- Add the following block directly below it to bind the J key to Dijkstra's:
if event.key == pygame.K_j:
clear_path(grid, start, end)
dijkstra(lambda: draw(surface, grid, ROWS), grid, start, end)What does this code do?
This follows the same pattern as your BFS (SPACE) and DFS (D) bindings. It clears any previous path colors first with clear_path, then runs the Dijkstra's function. The lambda passes your draw function so the algorithm can animate in real time.
- Save pathfinder.py and run the program.
- Place a start node, an end node, and draw some walls to create a maze.
- Press J to run Dijkstra's. Watch the orange frontier and light blue visited cells expand.
- Press C to clear the path, then press SPACE for BFS on the same maze.
- Press C again, then press D for DFS on the same maze.
You should see that BFS and Dijkstra's produce the same shortest yellow path. Their exploration patterns are similar but the node processing order differs slightly due to heap tie-breaking. DFS typically finds a longer path because it explores depth-first.
Dijkstra's not finding a path?
Make sure your dijkstra function is placed after dfs and before clear_path in the file. Also confirm the J key binding is inside the if start and end: block so that neighbor updates happen before the algorithm runs.
Help me debug why Dijkstra's is not finding a path in my visualizer.
✔️ Awesome, I've got everything!
Great. Double check you have saved your file before moving on.
ⓧ I'd like to double check the full code
Here is the complete pathfinder.py file as it should look at the end of this step:
import pygame
import heapq
from collections import deque
# Constants
WIDTH = 600
ROWS = 25
CELL_SIZE = WIDTH // ROWS
# Colors
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
GREEN = (0, 255, 0)
RED = (255, 0, 0)
LIGHT_BLUE = (173, 216, 230)
YELLOW = (255, 255, 0)
ORANGE = (255, 165, 0)
GREY = (128, 128, 128)
class Node:
def __init__(self, row, col):
self.row = row
self.col = col
self.color = WHITE
self.neighbors = []
def get_pos(self):
return self.row, self.col
def is_wall(self):
return self.color == BLACK
def is_start(self):
return self.color == GREEN
def is_end(self):
return self.color == RED
def reset(self):
self.color = WHITE
def make_start(self):
self.color = GREEN
def make_end(self):
self.color = RED
def make_wall(self):
self.color = BLACK
def make_visited(self):
self.color = LIGHT_BLUE
def make_frontier(self):
self.color = ORANGE
def make_path(self):
self.color = YELLOW
def draw(self, surface):
x = self.col * CELL_SIZE
y = self.row * CELL_SIZE
pygame.draw.rect(surface, self.color, (x, y, CELL_SIZE, CELL_SIZE))
def update_neighbors(self, grid):
self.neighbors = []
if self.row < ROWS - 1 and not grid[self.row + 1][self.col].is_wall():
self.neighbors.append(grid[self.row + 1][self.col])
if self.row > 0 and not grid[self.row - 1][self.col].is_wall():
self.neighbors.append(grid[self.row - 1][self.col])
if self.col < ROWS - 1 and not grid[self.row][self.col + 1].is_wall():
self.neighbors.append(grid[self.row][self.col + 1])
if self.col > 0 and not grid[self.row][self.col - 1].is_wall():
self.neighbors.append(grid[self.row][self.col - 1])
def make_grid(rows):
grid = []
for i in range(rows):
grid.append([])
for j in range(rows):
node = Node(i, j)
grid[i].append(node)
return grid
def draw_grid_lines(surface, rows):
for i in range(rows):
pygame.draw.line(surface, GREY, (0, i * CELL_SIZE), (WIDTH, i * CELL_SIZE))
pygame.draw.line(surface, GREY, (i * CELL_SIZE, 0), (i * CELL_SIZE, WIDTH))
def draw(surface, grid, rows):
surface.fill(WHITE)
for row in grid:
for node in row:
node.draw(surface)
draw_grid_lines(surface, rows)
pygame.display.flip()
def get_clicked_pos(pos):
x, y = pos
row = y // CELL_SIZE
col = x // CELL_SIZE
return row, col
def reconstruct_path(came_from, current, draw_func):
while current in came_from:
current = came_from[current]
current.make_path()
draw_func()
def bfs(draw_func, grid, start, end):
queue = deque([start])
came_from = {}
visited = {start}
while queue:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current = queue.popleft()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
queue.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def dfs(draw_func, grid, start, end):
stack = [start]
came_from = {}
visited = {start}
while stack:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current = stack.pop()
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
if current not in visited:
visited.add(current)
for neighbor in current.neighbors:
if neighbor not in visited:
visited.add(neighbor)
came_from[neighbor] = current
stack.append(neighbor)
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def dijkstra(draw_func, grid, start, end):
count = 0
heap = [(0, count, start)]
came_from = {}
dist = {node: float("inf") for row in grid for node in row}
dist[start] = 0
visited = set()
while heap:
for event in pygame.event.get():
if event.type == pygame.QUIT:
pygame.quit()
return False
current_dist, _, current = heapq.heappop(heap)
if current in visited:
continue
visited.add(current)
if current == end:
reconstruct_path(came_from, end, draw_func)
end.make_end()
start.make_start()
return True
for neighbor in current.neighbors:
new_dist = dist[current] + 1
if new_dist < dist[neighbor]:
came_from[neighbor] = current
dist[neighbor] = new_dist
count += 1
heapq.heappush(heap, (new_dist, count, neighbor))
neighbor.make_frontier()
if current != start:
current.make_visited()
draw_func()
return False
def clear_path(grid, start, end):
for row in grid:
for node in row:
if not node.is_wall() and not node.is_start() and not node.is_end():
node.reset()
def main():
pygame.init()
surface = pygame.display.set_mode((WIDTH, WIDTH))
pygame.display.set_caption("Pathfinding Visualizer")
grid = make_grid(ROWS)
start = None
end = None
running = True
while running:
draw(surface, grid, ROWS)
for event in pygame.event.get():
if event.type == pygame.QUIT:
running = False
if pygame.mouse.get_pressed()[0]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if not start and node != end:
start = node
start.make_start()
elif not end and node != start:
end = node
end.make_end()
elif node != start and node != end:
node.make_wall()
elif pygame.mouse.get_pressed()[2]:
pos = pygame.mouse.get_pos()
row, col = get_clicked_pos(pos)
if 0 <= row < ROWS and 0 <= col < ROWS:
node = grid[row][col]
if node == start:
start = None
elif node == end:
end = None
node.reset()
if event.type == pygame.KEYDOWN:
if start and end:
for row in grid:
for node in row:
node.update_neighbors(grid)
if event.key == pygame.K_SPACE:
clear_path(grid, start, end)
bfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_d:
clear_path(grid, start, end)
dfs(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_j:
clear_path(grid, start, end)
dijkstra(lambda: draw(surface, grid, ROWS), grid, start, end)
if event.key == pygame.K_c:
clear_path(grid, start, end)
if event.key == pygame.K_r:
start = None
end = None
grid = make_grid(ROWS)
pygame.quit()
if __name__ == "__main__":
main()You now have three algorithms running on the same grid, each demonstrating a fundamentally different data structure. BFS uses a queue, DFS uses a stack, and Dijkstra's uses a heap. The choice of data structure is what makes each algorithm behave differently. Next up, the Secret Mission challenges you to add A* search and see how a heuristic can guide the heap toward the goal even faster.
Secret mission
Add A* Search
Your three algorithms work, but can you make a smarter one? A* combines Dijkstra's cost-so-far with a heuristic estimate of how far the goal is. The result: an algorithm that finds the same optimal path while exploring dramatically fewer nodes.
Clean Up Your Resources
Clean Up Your Resources
This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your resources on your machine, or delete them entirely.
Resources you used:
- pathfinder.py project file (local).
- Pygame library (installed via pip).
Keep everything running
No action needed. Choose this if you want to keep experimenting with the visualizer or add more algorithms.
- Your pathfinder.py file stays in your PyCharm project.
- Pygame remains installed and available for other projects.
Pause - I'll come back to this later
Close PyCharm to free up memory. Your file and Pygame installation will still be there when you come back.
- Close PyCharm.
- Everything is saved locally. Reopen PyCharm and your project whenever you are ready to continue.
Delete - I don't want to use this again
Remove the project file and uninstall Pygame to start fresh.
- In PyCharm, right-click pathfinder.py in the project panel and select Delete.
- Uninstall Pygame by running this command in PyCharm's terminal:
pip uninstall pygame- Type y and press Enter when prompted to confirm the uninstall.
That's a Wrap!
That's a Wrap!
Nice work! You just built a fully interactive pathfinding visualizer from scratch using Pygame.
You've learned how to:
- Built an interactive grid system with mouse-driven node placement and real-time algorithm visualization using Pygame.
- Implemented three pathfinding algorithms from scratch (BFS, DFS, and Dijkstra's), each powered by a different data structure (collections.deque, a list as a stack, and heapq).
- Observed how the choice of data structure (queue vs stack vs heap) fundamentally changes how each algorithm explores the grid and whether it guarantees the shortest path.
- Secret Mission: Added A* search with a Manhattan distance heuristic, demonstrating how heuristics reduce the search space while preserving optimality.
Ready to quiz yourself?