Maze generator & solver · gemma-4-26b-a4b-it
Generate a random maze with the recursive-backtracker algorithm on a canvas, then animate an A-star or BFS solver finding the path from start to finish.
This one-shot run produced no runnable artifact.
agent produced no index.html
The transcript below shows what the model did — read it to see why the one shot fell short.
transcript · 2 messages
Generate a random maze with the recursive-backtracker algorithm on a canvas, then animate an A-star or BFS solver finding the path from start to finish.
thinking
The user wants a single-page web app (in `index.html`) that:
1. Generates a random maze using the recursive-backtracker algorithm on a `<canvas>`.
2. Animates an A* or BFS solver finding the path from a start point to an end point.
3. The entire app must be in one file, no external resources, no CDNs.
Plan:
1. **HTML Structure**: A container for the canvas, some controls (Generate, Solve, Speed, etc.), and status information.
2. **CSS**: Styling for the UI and canvas.
3. **JavaScript**:
* `Maze` class/logic:
* Represent the grid (cells and walls).
* `generate()` method using Recursive Backtracker.
* `Solver` logic:
* `bfs()` or `aStar()` algorithm.
* Animation mechanism (using `requestAnimationFrame` or `setTimeout` to show progress).
* `Renderer`: Drawing the maze and the search process on the canvas.
* `Controller`: Handling user interactions.
Let's break down the Recursive Backtracker algorithm:
- Start at a random cell.
- Mark it as visited.
- While there are unvisited cells:
- Pick a random unvisited neighbor.
- If neighbor exists:
- Remove wall between current and neighbor.
- Push current to stack.
- Move to neighbor.
- Mark as visited.
- Else:
- Pop from stack.
Let's break down the A* algorithm:
- `openSet`, `closedSet`.
- `gScore`, `fScore`.
- Heuristic (Manhattan distance).
- Priority queue (or just search the open set for simplicity in a small demo).
Wait, for a maze, the "cells" are the walkable spaces, and "walls" are the boundaries.
In a grid-based maze:
- Each cell can have up to 4 walls (North, East, South, West).
- When generating, we remove walls between cells.
A-star on a maze:
- The nodes are the cells.
- Edges exist between adjacent cells if there is no wall between them.
Let's refine the implementation details:
- Grid: 2D array of Cell objects.
- Cell object: `x, y`, `visited`, `walls: {n, e, s, w}`, `parent`, `g, h, f`.
Visuals:
- Maze: Black walls, white paths (or vice versa).
- Search:
- "Exploring" cells: color them slightly differently (e.g., light blue).
- "Path" found: color it (e.g., yellow).
- "Closed" cells: color them (e.g., light grey).
Let's write the code.
*Self-correction on "No external resources"*: I'll use standard Web APIs. No FontAwesome, no Google Fonts, no jQuery.
*Canvas sizing*: I'll make it responsive or fixed-size with a decent resolution.
*Features to include*:
- Reset/Generate Maze button.
- Start Solver button.
- Slider for speed.
- Visual representation of the "search frontier" and "visited" cells.
*Algorithm details*:
- Maze generation: Recursive Backtracker (DFS).
- Solver: A* (better than BFS for visualization as it looks more "intelligent").
Implementation plan for `index.html`:
1. `<html>`, `<head>`, `<style>`, `<body>`, `<script>`.
2. Styles: Dark theme, nice buttons, centered canvas.
3. Script:
- Constants: `CELL_SIZE`, `COLS`, `ROWS`.
- `Cell` class.
- `Maze` class.
- `Solver` class (to handle the animation state).
- Main loop and event listeners.
Let's start drafting the code.```html <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> <title>Maze Generator & Solver</title> <style> :root { --bg-color: #1a1a1a; --panel-color: #2d2d2d; --text-color: #e0e0e0; --accent-color: #4caf50; --accent-hover: #45a049; --button-secondary: #555; --button-secondary-hover: #666; --path-color: #ffeb3b; --visited-color: rgba(33, 150, 243, 0.3); --frontier-color: rgba(255, 152, 0, 0.5); } body { margin: 0; padding: 0; background-color: var(--bg-color); color: var(--text-color); font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif; display: flex; flex-direction: column; align-items: center; justify-content: center; min-height: 100vh; overflow: hidden; } .container { display: flex; flex-direction: column; align-items: center; gap: 20px; padding: 20px; background: var(--panel-color); border-radius: 12px; box-shadow: 0 10px 30px rgba(0,0,0,0.5); } canvas { background-color: #000; border-radius: 4px; box-shadow: inset 0 0 10px rgba(0,0,0,1); cursor: crosshair; } .controls { display: flex; flex-wrap: wrap; gap: 10px; justify-content: center; align-items: center; } button { padding: 10px 20px; font-size: 14px; font-weight: bold; border: none; border-radius: 4px; cursor: pointer; transition: background 0.2s, transform 0.1s; color: white; } button:active { transform: scale(0.95); } .btn-primary { background-color: var(--accent-color); } .btn-primary:hover { background-color: var(--accent-hover); } .btn-primary:disabled { background-color: #333; cursor: not-allowed; } .btn-secondary { background-color: var(--button-secondary); } .btn-secondary:hover { background-color: var(--button-secondary-hover); } .slider-container { display: flex; flex-direction: column; align-items: center; font-size: 12px; } input[type=range] { width: 120px; margin-top: 5px; } .stats { font-size: 14px; color: #aaa; margin-top: 5px; } h1 { margin: 0; font-size: 24px; letter-spacing: 1px; } </style> </head> <body> <div class="container"> <h1>Maze Explorer</h1> <canvas id="mazeCanvas"></canvas> <div class="controls"> <button id="btnGenerate" class="btn-primary">Generate New Maze</button> <button id="btnSolve" class="btn-primary">Solve (A*)</button> <div class="slider-container"> <label for="speedRange">Speed</label> <input type="range" id="speedRange" min="1" max="100" value="50"> </div> </div> <div class="stats" id="statusText">Ready</div> </div> <script> /** * CONSTANTS & CONFIG */ const CANVAS_SIZE = 600; const GRID_SIZE = 25; // Number of cells (width/height) const CELL_SIZE = CANVAS_SIZE / GRID_SIZE; const canvas = document.getElementById('mazeCanvas'); const ctx = canvas.getContext('2d'); canvas.width = CANVAS_SIZE; canvas.height = CANVAS_SIZE; const btnGenerate = document.getElementById('btnGenerate'); const btnSolve = document.getElementById('btnSolve'); const speedRange = document.getElementById('speedRange'); const statusText = document.getElementById('statusText'); /** * CLASSES */ class Cell { constructor(r, c) { this.r = r; this.c = c; // Walls: top, right, bottom, left this.walls = { t: true, r: true, b: true, l: true }; this.visited = false; // A* properties this.g = Infinity; this.h = 0; this.f = Infinity; this.parent = null; // Visualization state this.state = 'none'; // 'none', 'visited', 'frontier', 'path' } } class Maze { constructor(rows, cols) { this.rows = rows; this.cols = cols; this.grid = []; for (let r = 0; r < rows; r++) { this.grid[r] = []; for (let c = 0; c < cols; c++) { this.grid[r][c] = new Cell(r, c); } } this.startCell = this.grid[0][0]; this.endCell = this.grid[rows - 1][cols - 1]; } getNeighbors(cell) { const neighbors = []; const { r, c } = cell; if (r > 0) neighbors.push(this.grid[r - 1][c]); if (r < this.rows - 1) neighbors.push(this.grid[r + 1][c]); if (c > 0) neighbors.push(this.grid[r][c - 1]); if (c < this.cols - 1) neighbors.push(this.grid[r][c + 1]); return neighbors; } removeWallsBetween(a, b) { const dr = Math.abs(a.r - b.r); const dc = Math.abs(a.c - b.c); if (dr === 1) { // Vertical neighbor if (a.r < b.r) { // a is above b a.walls.b = false; b.walls.t = false; } else { // a is below b a.walls.t = false; b.walls.b = false; } } else if (dc === 1) { // Horizontal neighbor if (a.c < b.c) { // a is left of b a.walls.r = false; b.walls.l = false; } else { // a is right of b a.walls.l = false; b.walls.r = false; } } } /** * Recursive Backtracker Algorithm */ async generate() { const stack = []; const start = this.grid[0][0]; start.visited = true; stack.push(start); while (stack.length > 0) { const current = stack[stack.length - 1]; const neighbors = this.getNeighbors(current).filter(n => !n.visited); if (neighbors.length > 0) { const next = neighbors[Math.floor(Math.random() * neighbors.length)]; next.visited = true; this.removeWallsBetween(current, next); stack.push(next); } else { stack.pop(); } // Optional: Yield to allow rendering if we wanted to animate generation // await new Promise(r => setTimeout(r, 0)); } } resetStates() { for (let r = 0; r < this.rows; r++) { for (let c = 0; c < this.cols; c++) { const cell = this.grid[r][c]; cell.g = Infinity; cell.h = 0; cell.f = Infinity; cell.parent = null; cell.state = 'none'; } } } } /** * ENGINE & RENDERING */ let maze = new Maze(GRID_SIZE, GRID_SIZE); let isSolving = false; let animationId = null; function draw() { ctx.clearRect(0, 0, canvas.width, canvas.height); for (let r = 0; r < maze.rows; r++) { for (let c = 0; c < maze.cols; c++) { const cell = maze.grid[r][c]; const x = c * CELL_SIZE; const y = r * CELL_SIZE; // Draw Cell Background / State if (cell.state === 'visited') { ctx.fillStyle = 'rgba(33, 150, 243, 0.3)'; ctx.fillRect(x, y, CELL_SIZE, CELL_SIZE); } else if (cell.state === 'frontier') { ctx.fillStyle = 'rgba(255, 152, 0, 0.5)'; ctx.fillRect(x, y, CELL_SIZE, CELL_SIZE); } else if (cell.state === 'path') { ctx.fillStyle = '#ffeb3b'; ctx.fillRect(x, y, CELL_SIZE, CELL_SIZE); } // Draw Walls ctx.strokeStyle = 'white'; ctx.lineWidth = 2; ctx.beginPath(); if (cell.walls.t) { ctx.moveTo(x, y); ctx.lineTo(x + CELL_SIZE, y); } if (cell.walls.r) { ctx.moveTo(x + CELL_SIZE, y); ctx.lineTo(x + CELL_SIZE, y + CELL_SIZE); } if (cell.walls.b) { ctx.moveTo(x, y + CELL_SIZE); ctx.lineTo(x + CELL_SIZE, y + CELL_SIZE); } if (cell.walls.l) { ctx.moveTo(x, y); ctx.lineTo(x, y + CELL_SIZE); } ctx.stroke(); } } // Draw Start and End ctx.fillStyle = '#4caf50'; // Green ctx.fillRect(maze.startCell.c * CELL_SIZE + 2, maze.startCell.r * CELL_SIZE + 2, CELL_SIZE - 4, CELL_SIZE - 4); ctx.fillStyle = '#f44336'; // Red ctx.fillRect(maze.endCell.c * CELL_SIZE + 2, maze.endCell.r * CELL_SIZE + 2, CELL_SIZE - 4, CELL_SIZE - 4); } /** * A* SOLVER IMPLEMENTATION */ async function solveAStar() { if (isSolving) return; isSolving = true; btnGenerate.disabled = true; btnSolve.disabled = true; statusText.innerText = "Solving..."; maze.resetStates(); const start = maze.startCell; const end = maze.endCell; start.g = 0; start.h = manhattan(start, end); start.f = start.h; let openSet = [start]; const closedSet = new Set(); while (openSet.length > 0) { // Get node with lowest f score let currentIdx = 0; for (let i = 0; i < openSet.length; i++) { if (openSet[i].f < openSet[currentIdx].f) { currentIdx = i; } } const current = openSet[currentIdx]; // Check if reached goal if (current === end) { await reconstructPath(current); statusText.innerText = "Path Found!"; isSolving = false; btnGenerate.disabled = false; return; } // Move current from open to closed openSet.splice(currentIdx, 1); closedSet.add(current); if (current !== start && current !== end) { current.state = 'visited'; } // Process neighbors const neighbors = getAccessibleNeighbors(current); for (const neighbor of neighbors) { if (closedSet.has(neighbor)) continue; const tentativeG = current.g + 1; if (tentativeG < neighbor.g) { neighbor.parent = current; neighbor.g = tentativeG; neighbor.h = manhattan(neighbor, end); neighbor.f = neighbor.g + neighbor.h; if (!openSet.includes(neighbor)) { openSet.push(neighbor); if (neighbor !== end) neighbor.state = 'frontier'; } } } // Control speed and draw draw(); const delay = Math.max(1, 101 - speedRange.value); await new Promise(r => setTimeout(r, delay)); } statusText.innerText = "No path found."; isSolving = false; btnGenerate.disabled = false; } function manhattan(a, b) { return Math.abs(a.r - b.r) + Math.abs(a.c - b.c); } function getAccessibleNeighbors(cell) { const neighbors = []; const { r, c } = cell; // Check walls to see if we can move if (!cell.walls.t && r > 0) neighbors.push(maze.grid[r - 1][c]); if (!cell.walls.r && c < maze.cols - 1) neighbors.push(maze.grid[r][c + 1]); if (!cell.walls.b && r < maze.rows - 1) neighbors.push(maze.grid[r + 1][c]); if (!cell.walls.l && c > 0) neighbors.push(maze.grid[r][c - 1]); return neighbors; } async function reconstructPath(endCell) { let curr = endCell; while (curr) { curr.state = 'path'; curr = curr.parent; draw(); await new Promise(r => setTimeout(r, 30)); } } /** * EVENT HANDLERS */ async function handleGenerate() { isSolving = false; btnGenerate.disabled = true; btnSolve.disabled = true; statusText.innerText = "Generating..."; maze = new Maze(GRID_SIZE, GRID_SIZE); await maze.generate(); draw(); statusText.innerText = "Maze Generated"; btnGenerate.disabled = false; btnSolve.disabled = false; } btnGenerate.addEventListener('click', handleGenerate); btnSolve.addEventListener('click', solveAStar); // Initial state handleGenerate(); </script> </body> </html> ```
TAKE IT TO CODE
This run produced no artifact — reuse the prompt with a different model or your own pi-agent run.