Py.Cafe

import dash
import dash_bootstrap_components as dbc
import dash_core_components as dcc
import dash_html_components as html
from dash.dependencies import Input, Output, State
import plotly.graph_objs as go
import numpy as np
import heapq

# Initialize the app
app = dash.Dash(__name__, external_stylesheets=[dbc.themes.BOOTSTRAP])

# 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
def astar(maze, start, goal):
    height, width = maze.shape
    frontier = [(0, start)]
    heapq.heapify(frontier)
    came_from = {start: None}
    cost_so_far = {start: 0}
    
    while frontier:
        current_priority, current = heapq.heappop(frontier)
        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)
                        heapq.heappush(frontier, (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

# Define the layout
app.layout = dbc.Container(
    [
        dbc.Row(
            dbc.Col(html.H1("Maze Generator and Solver"), className="text-center")
        ),
        dbc.Row(
            dbc.Col(
                dcc.Graph(id='maze-graph', style={"height": "600px"}),
                width=12,
            )
        ),
        dbc.Row(
            [
                dbc.Col(html.Label("Width:"), width=2),
                dbc.Col(dcc.Input(id='width-input', type='number', value=50), width=2),
                dbc.Col(html.Label("Height:"), width=2),
                dbc.Col(dcc.Input(id='height-input', type='number', value=50), width=2),
                dbc.Col(dbc.Button("Generate Maze", id='generate-button', color="primary"), width=2),
            ],
            className="text-center",
        ),
    ],
    fluid=True,
)

@app.callback(
    Output('maze-graph', 'figure'),
    [Input('generate-button', 'n_clicks')],
    [State('width-input', 'value'), State('height-input', 'value')]
)
def update_maze_graph(n_clicks, width, height):
    if n_clicks is None:
        return go.Figure()

    # Generate maze
    maze = generate_maze(width, height)
    x_lines, y_lines = maze_to_lines(maze)

    # Solve maze
    path = astar(maze, (0, 0), (width - 1, height - 1))
    if path:
        x_path, y_path = zip(*path)
        x_path = [x + 0.5 for x in x_path]  # Center the path within cells
        y_path = [y + 0.5 for y in y_path]
    else:
        x_path, y_path = [], []

    line_trace = go.Scatter(
        x=x_lines,
        y=y_lines,
        mode='lines',
        line=dict(color='black', width=2),
        hoverinfo='none'
    )

    path_trace = go.Scatter(
        x=x_path,
        y=y_path,
        mode='lines+markers',
        line=dict(color='blue', width=2),
        marker=dict(color='blue', size=6),
        hoverinfo='none'
    )

    layout = go.Layout(
        xaxis=dict(showgrid=False, zeroline=False, showticklabels=False),
        yaxis=dict(showgrid=False, zeroline=False, showticklabels=False, scaleanchor="x", scaleratio=1),
        margin=dict(l=0, r=0, b=0, t=0),
        plot_bgcolor='white'
    )

    return go.Figure(data=[line_trace, path_trace], layout=layout)

# Run the app
if __name__ == "__main__":
    app.run_server(debug=True)