Depth-First Search(DFS) with Pygame

Today I would like to show how can we use Pygame for making animations to display how the depth-first search(DFS) algorithm works.

This roadmap can be used in other search and path-finding algorithms. We will forward step by step. I have already created a repo that you can find all code in this link.

GitHub — egemengulpinar/DFS-with-Pygame: Recursive DFS Backtracking Algorithm with visualization

Now, Let’s start!

First, we need to create a DFS script for specific cases. I have already a problem that solving with the DFS algorithm. You can find this question in detail below.

You are given an m × n integer array grid where grid [i][j] could be:

1 representing the starting square. There is exactly one starting square.

2 representing the ending square. There is exactly one ending square.

0 representing empty squares we can walk over.

-1 representing obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.

First, we create a class that includes variables and functions for given inputs.

class Solution:
    def __init__(self):
        self.res = 0
        self.grid_history = []

    def uniquePathsIII(self, grid):
        m, n, empty = len(grid), len(grid[0]), 1
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    x, y = (i, j)
                elif grid[i][j] == 2:
                    end = (i, j)
                elif grid[i][j] == 0:
                    empty += 1
        self.dfs(grid, x, y, end, empty)
        if self.res == 0:
            self.animate_solution(blank=True)
        return self.res

We have created 2variables that they have default values.

self.res using for saving all possible ways to reach the “end” path.

self.grid_history using for keeping all tried ways that we use next for Pygame animation.

Next, we have created def uniquePaths(self, grid) that recognize that the given 2D matrix inputs and parsing to (x,y) values.

1 — starting path

2 — end path

0 — empty path

def dfs(self, grid, x, y, end, empty):
        if not (0 <= x < len(grid)) or not (0 <= y < len(grid[0])) or grid[x][y] < 0:
            return 
        if (x, y) == end:
            if empty == 0:
                self.res += 1
                response = self.animate_solution(blank=False)
            return 

        # Save the current state of the grid for animation
        self.grid_history.append([row[:] for row in grid])
        grid[x][y] = -2
        self.dfs(grid, x + 1, y, end, empty - 1)
        self.dfs(grid, x - 1, y, end, empty - 1)
        self.dfs(grid, x, y + 1, end, empty - 1)
        self.dfs(grid, x, y - 1, end, empty - 1)
        grid[x][y] = 0

Then we create the DFS algorithm path, in this part we need to check every recursive iteration

checking in each iteration “x” and “y” values are in the range of the grid(our input matrix).

Also, their values can not be less than 0. Because

-1 = “blocked path”

-2 = “passed”

We also set the previous path to “-2” value that represents “this block has been passed”.

grid[x][y] = -2

Let’s discuss our main recursive part below.

self.dfs(grid, x + 1, y, end, empty - 1)
self.dfs(grid, x - 1, y, end, empty - 1)
self.dfs(grid, x, y + 1, end, empty - 1)
self.dfs(grid, x, y - 1, end, empty - 1)

That part actually represents 4 directions(left, right, up, down). We are trying to walk every block to get to the “end” block. It is kind of like the below image.

After we save all the overpassed blocks coordinate to self.grid_history, we will use it for making pygame animation.

self.grid_history.append([row[:] for row in grid])

Below that part, we create and configure pygame options.

def animate_solution(self,blank):
        # Define constants
        TILE_SIZE = 40
        TILE_MARGIN = 5
        LEGEND_SIZE = 20
        LEGEND_MARGIN = 3
        TILES_X = len(self.grid_history[0][0])
        TILES_Y = len(self.grid_history[0])
        LEGEND_WIDTH = 250
        WINDOW_WIDTH = TILES_X * (TILE_SIZE + TILE_MARGIN) + LEGEND_WIDTH
        WINDOW_HEIGHT = TILES_Y * (TILE_SIZE + TILE_MARGIN)

        # Define colors
        COLORS = {
            1: (0, 255, 0),  # Green for the start tile
            0: (255, 255, 255),  # White for empty tiles
            2: (255, 0, 0),  # Red for the end tile
            -1: (72, 72, 72),  # Black for blocked tiles
            -2: (0, 0, 255)  # Blue for visited tiles
        }

        # Color descriptions
        DESCRIPTIONS = {
            1: "Start Tile",
            0: "Empty Tiles",
            2: "End Tile",
            -1: "Blocked Tiles",
            -2: "Visited Tiles"
        }

        # Initialize pygame and the window
        pygame.init()
        window = pygame.display.set_mode((WINDOW_WIDTH, WINDOW_HEIGHT))
        font = pygame.font.Font(None, 36)

Then, we use “pygame.Rect()” for draw rectangle for each block. That includes also legend info for representing colours explanation.

# Function to draw the grid
def draw_grid(grid):
    for y, row in enumerate(grid):
        for x, tile in enumerate(row):
            rect = pygame.Rect(x*(TILE_SIZE+TILE_MARGIN), y*(TILE_SIZE+TILE_MARGIN), TILE_SIZE, TILE_SIZE)
            pygame.draw.rect(window, COLORS[tile], rect)

# Function to draw the legend
def draw_legend():
    for i, color in enumerate(COLORS):
        rect = pygame.Rect(WINDOW_WIDTH - LEGEND_WIDTH + 50, i*(LEGEND_SIZE+LEGEND_MARGIN) + 10, LEGEND_SIZE, LEGEND_SIZE)
        pygame.draw.rect(window, COLORS[color], rect)

        text = font.render(DESCRIPTIONS[color], True, (255, 255, 255))
        window.blit(text, (WINDOW_WIDTH - LEGEND_WIDTH + 50 + LEGEND_SIZE + 10, i*(LEGEND_SIZE+LEGEND_MARGIN) + 10))

Now we update the window with the function below.

# Function to update the window
        def update_window(grid):
            window.fill((0, 0, 0))  # Fill the window with black
            draw_grid(grid)  # Draw the grid
            draw_legend()  # Draw the legend
            pygame.display.flip()  # Update the display
        if blank:
            text = font.render("PATH NOT FOUND : {}".format(self.res), True, (255, 0, 0))
            window.blit(text, (WINDOW_WIDTH / 2 - text.get_width() / 2, WINDOW_HEIGHT / 2 - text.get_height() / 2))
            pygame.display.flip()
            time.sleep(5)
            return False

If we found way(s), we display a text message first, then show the box animation from the last 15 movements in self.grid_history variable.

# Display "FOUND" message and show the solution path
        text = font.render("FOUND : {}".format(self.res), True, (255, 0, 0))
        window.blit(text, (WINDOW_WIDTH / 2 - text.get_width() / 2, WINDOW_HEIGHT / 2 - text.get_height() / 2))
        pygame.display.flip()
        time.sleep(3)
        for grid_state in self.grid_history[-15::1]:
            for event in pygame.event.get():
                if event.type == pygame.QUIT:  # Quit the game
                    return
            update_window(grid_state)  # Update the window
            time.sleep(0.5)  # Delay to make the animation visible
        return True

And that’s it! now you can test with your own matrix and display using with Pygame animation. Meanwhile, you can also contribute that repo and make it possible to show the animation in the browser. (using with Web Assembly)