A minimal application for solving mazes built with tkinter

Key Features • How To Use • Create New Mazes • Credits • How does the app work

Key Features

• BFS algorithm for maze solving
• Option to generate animated gif
• Option to loop generated gif
• Slider to control gif speed

How To Use

# Clone the repository
git clone https://github.com/EnricoBDev/maze-solvr.git

# Install the required dependencies
cd maze-solver
pip install -r requirements.txt

# Run the app
python main.py

Testing mazes can be found in

assets/test_images

Create New Mazes

To create new mazes you can use any image manipulation program, you just need to follow these rules:

• The image must be in png format
• The start and end points must be indicated with 2 blue #0000ff pixels
• The walls/obstacles must be indicated with black #000000 pixels
• The navigable paths must be indicated with white #ffffff pixels

How does the app work?

As I said previously, this application uses the BFS (Breadth First Search) algorithm, this is an important algorithm used extensively when working with graphs.

But since the input file is an image, how do we generate the adjacency list used to describe the maze in a graph format?

The application follows the following steps:

1. First of all we tranform the image file in a pixel matrix,
2. Then we recreate the pixel matrix but we substitute each pixel value with a predefined constant for every pixel color,
3. After this we find the two blue pixels (indicating the start and the end of the maze), and we save those
4. Finally, by using a recursive algorithm to follow the white path, we take each pixel and we find its neighbours.

Now all that's left to do is to run the algorithm on the adjacency list:

# solve.py

def solve(maze, adj_list):
    start = maze.start
    end = maze.end

    queue = deque([start])
    visited = [False] * (maze.width * maze.height)
    prev = [None] * (maze.width * maze.height)

    visited[start.coords[0] * maze.width + start.coords[1]] = True

    while queue:
        current = queue.pop()

        if current.__repr__() == end.__repr__():
            break
        
        for i in adj_list.get(current.__repr__()):
            visited_pos = i.coords[0] * maze.width + i.coords[1]
            if visited[visited_pos] == False:    
                queue.appendleft(i)
                visited[visited_pos] = True
                prev[visited_pos] = current
        

    path = deque()
    current = end
    while current != None:
        path.appendleft(current)
        current = prev[current.coords[0] * maze.width + current.coords[1]]
    
    if len(path) > 1:
        return path
    else: 
        return False

Credits

The app icon can be found here

This app is powered by the following open source projects:

• Pillow, image manipulation library

• Numpy, array and matrix manipulation library

• Tkinter, gui library included in the std library