PyCafe - Streamlit - Maze Generator and Solver

app.py
requirements.txt
app.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
import streamlit as st
import numpy as np
from PIL import Image, ImageDraw

# Maze generation using Depth-First Search algorithm with guaranteed entrance and exit
def generate_maze(width, height):
    maze = np.zeros((height, width), dtype=int)
    stack = [(0, 0)]
    visited = set((0, 0))
    
    while stack:
        current = stack[-1]
        x, y = current
        
        directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        np.random.shuffle(directions)
        
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height and (nx, ny) not in visited:
                visited.add((nx, ny))
                stack.append((nx, ny))
                maze[y, x] |= (1 << directions.index((dx, dy)))
                maze[ny, nx] |= (1 << directions.index((-dx, -dy)))
                break
        else:
            stack.pop()

    # Ensure entrance and exit
    maze[0, 0] |= 1  # Open path to the right
    maze[height-1, width-1] |= 2  # Open path to the left
    return maze

def maze_to_lines(maze):
    height, width = maze.shape
    x_lines = []
    y_lines = []

    for y in range(height):
        for x in range(width):
            if not (maze[y, x] & 1):  # Right
                x_lines.extend([x + 1, x + 1, None])
                y_lines.extend([y, y + 1, None])
            if not (maze[y, x] & 2):  # Down
                x_lines.extend([x, x + 1, None])
                y_lines.extend([y + 1, y + 1, None])
            if y == 0 and not (maze[y, x] & 8):  # Top
                x_lines.extend([x, x + 1, None])
                y_lines.extend([y, y, None])
            if x == 0 and not (maze[y, x] & 4):  # Left
                x_lines.extend([x, x, None])
                y_lines.extend([y, y + 1, None])

    return x_lines, y_lines

# A* pathfinding algorithm without using heapq
def astar(maze, start, goal):
    height, width = maze.shape
    frontier = [(0, start)]
    came_from = {start: None}
    cost_so_far = {start: 0}
    
    while frontier:
        # Get the node with the lowest priority
        frontier.sort()
        current_priority, current = frontier.pop(0)
        
        if current == goal:
            break
        
        x, y = current
        for dx, dy, direction in [(-1, 0, 4), (1, 0, 2), (0, -1, 8), (0, 1, 1)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < width and 0 <= ny < height:
                new_cost = cost_so_far[current] + 1
                if (nx, ny) not in cost_so_far or new_cost < cost_so_far[(nx, ny)]:
                    if maze[y, x] & direction:
                        cost_so_far[(nx, ny)] = new_cost
                        priority = new_cost + abs(goal[0] - nx) + abs(goal[1] - ny)
                        frontier.append((priority, (nx, ny)))
                        came_from[(nx, ny)] = current
    
    path = []
    if current == goal:
        while current is not None:
            path.append(current)
            current = came_from[current]
        path.reverse()
    
    return path

def draw_maze(maze, path=None):
    height, width = maze.shape
    scale = 10
    img = Image.new("RGB", (width * scale, height * scale), (255, 255, 255))
    draw = ImageDraw.Draw(img)

    for y in range(height):
        for x in range(width):
            if not (maze[y, x] & 1):  # Right
                draw.line([((x + 1) * scale, y * scale), ((x + 1) * scale, (y + 1) * scale)], fill=(0, 0, 0))
            if not (maze[y, x] & 2):  # Down
                draw.line([(x * scale, (y + 1) * scale), ((x + 1) * scale, (y + 1) * scale)], fill=(0, 0, 0))
            if y == 0 and not (maze[y, x] & 8):  # Top
                draw.line([(x * scale, y * scale), ((x + 1) * scale, y * scale)], fill=(0, 0, 0))
            if x == 0 and not (maze[y, x] & 4):  # Left
                draw.line([(x * scale, y * scale), (x * scale, (y + 1) * scale)], fill=(0, 0, 0))

    if path:
        for (x, y) in path:
            draw.rectangle([x * scale + 2, y * scale + 2, (x + 1) * scale - 2, (y + 1) * scale - 2], fill=(255, 0, 0))

    return img

st.title("Maze Generator and Solver")

width = st.slider("Maze Width", 10, 100, 50)
height = st.slider("Maze Height", 10, 100, 50)

if st.button("Generate Maze"):
    maze = generate_maze(width, height)
    st.image(draw_maze(maze), caption="Generated Maze")
    solution = astar(maze, (0, 0), (width - 1, height - 1))

    if solution:
        st.image(draw_maze(maze, solution), caption="Solved Maze")
    else:
        st.warning("Generated maze has no solution, please generate again.")
Py.Cafe

streamlit-maze-solver

Maze Generator and Solver
