Maze generator & solver · deepseek-r1-0528
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
We are going to create a single HTML file (index.html) that contains: 1. CSS styles in a <style> tag. 2. JavaScript code in a <script> tag. 3. A <canvas> element for drawing the maze and the solution path. The application will: - Generate a maze using the recursive backtracker (depth-first) algorithm. - Draw the maze on a canvas. - Use the A* algorithm to find a path from the top-left (start) to the bottom-right (end). - Animate the solving process (showing the exploration and then the path). We'll structure the code as follows: HTML: - A canvas element with an id "mazeCanvas" - Buttons for generating a new maze and solving it. CSS: - Style for the canvas and buttons. JavaScript: - Constants for maze dimensions, cell size, etc. - Maze representation (2D array of cells). - Functions for generating the maze (recursive backtracker). - Functions for drawing the maze (drawing walls and paths). - A* algorithm implementation for solving the maze. - Animation of the solution. We'll break down the JavaScript code into parts: 1. Initialization: - Set up the canvas, context, and initial state. 2. Maze generation (recursive backtracker algorithm): - We'll represent the maze as a grid of cells. Each cell has four walls (top, right, bottom, left). - We'll use a stack to keep track of the path for backtracking. 3. Drawing the maze: - Draw the grid with walls for each cell that has not been broken. 4. Solving the maze with A*: - We'll implement the A* algorithm to find the path from start (0,0) to end (cols-1, rows-1). - We'll use a grid for the gScore (cost from start) and fScore (gScore + heuristic to end). - The heuristic function will be the Manhattan distance. 5. Animation: - We'll draw the explored cells during the solving process with a different color. - Once the path is found, we'll draw the path from start to end. Note: We must avoid external libraries. We'll use pure JavaScript. Let's design the index.html file.
I'll create a self-contained HTML file with a maze generator and solver. The implementation will: 1. Generate a maze using Random DFS (recursive backtracker) 2. Solve it using A* algorithm with Manhattan distance heuristic 3. Animate both maze generation and solving Here's the complete implementation: 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> body { margin: 0; padding: 20px; display: flex; flex-direction: column; align-items: center; background-color: #f0f0f0; font-family: Arial, sans-serif; } .container { text-align: center; } h1 { color: #333; } canvas { border: 1px solid #333; background-color: white; } .controls { margin: 15px 0; } button { padding: 10px 20px; margin: 0 10px; font-size: 16px; background-color: #4CAF50; color: white; border: none; border-radius: 4px; cursor: pointer; } button:hover { background-color: #45a049; } button:disabled { background-color: #cccccc; cursor: not-allowed; } .info { margin: 10px 0; font-size: 14px; color: #666; } </style> </head> <body> <div class="container"> <h1>Maze Generator & Solver</h1> <div class="controls"> <button id="generateBtn">Generate Maze</button> <button id="solveBtn" disabled>Solve Maze</button> <button id="resetBtn">Reset</button> </div> <div class="info"> <span id="stats">Maze: 30x30 cells</span> </div> <canvas id="mazeCanvas" width="601" height="601"></canvas> </div> <script> // Constants and configurations const ROWS = 30; const COLS = 30; const CELL_SIZE = 20; const WALL_SIZE = 2; const BG_COLOR = "#FFFFFF"; const WALL_COLOR = "#000000"; const PATH_COLOR = "#FFFFFF"; const START_COLOR = "#4CAF50"; const END_COLOR = "#F44336"; const EXPLORE_COLOR = "#FFD700"; const SOLUTION_COLOR = "#2196F3"; // Create canvas and context const canvas = document.getElementById("mazeCanvas"); const ctx = canvas.getContext("2d"); // Buttons const generateBtn = document.getElementById("generateBtn"); const solveBtn = document.getElementById("solveBtn"); const resetBtn = document.getElementById("resetBtn"); const stats = document.getElementById("stats"); // Maze data structure let maze = []; let visited = []; let solutionPath = []; let generationComplete = false; let animationId = null; let delay = 0; // Initialize maze with all walls function initMaze() { maze = Array(ROWS).fill().map(() => Array(COLS).fill().map(() => ({ top: true, right: true, bottom: true, left: true, visited: false }))); // Clear solution path solutionPath = []; } // Draw a single cell function drawCell(row, col) { const cell = maze[row][col]; const x = col * CELL_SIZE; const y = row * CELL_SIZE; // Fill cell background if (solutionPath && solutionPath.some(pos => pos.row === row && pos.col === col)) { ctx.fillStyle = SOLUTION_COLOR; } else if (visited && visited[row][col]) { ctx.fillStyle = EXPLORE_COLOR; } else { ctx.fillStyle = PATH_COLOR; } ctx.fillRect(x, y, CELL_SIZE, CELL_SIZE); // Draw walls ctx.fillStyle = WALL_COLOR; if (cell.top) ctx.fillRect(x, y, CELL_SIZE, WALL_SIZE); if (cell.right) ctx.fillRect(x + CELL_SIZE - WALL_SIZE, y, WALL_SIZE, CELL_SIZE); if (cell.bottom) ctx.fillRect(x, y + CELL_SIZE - WALL_SIZE, CELL_SIZE, WALL_SIZE); if (cell.left) ctx.fillRect(x, y, WALL_SIZE, CELL_SIZE); } // Draw start and end markers function drawMarkers() { // Start marker (top-left) ctx.fillStyle = START_COLOR; ctx.beginPath(); ctx.arc(CELL_SIZE/2, CELL_SIZE/2, CELL_SIZE/3, 0, 2 * Math.PI); ctx.fill(); // End marker (bottom-right) ctx.fillStyle = END_COLOR; ctx.beginPath(); ctx.arc( canvas.width - CELL_SIZE/2, canvas.height - CELL_SIZE/2, CELL_SIZE/3, 0, 2 * Math.PI ); ctx.fill(); } // Draw entire maze function drawMaze() { ctx.fillStyle = BG_COLOR; ctx.fillRect(0, 0, canvas.width, canvas.height); for (let row = 0; row < ROWS; row++) { for (let col = 0; col < COLS; col++) { drawCell(row, col); } } drawMarkers(); } // Check if cell is within bounds function isValidCell(row, col) { return row >= 0 && row < ROWS && col >= 0 && col < COLS; } // Get unvisited neighbors function getUnvisitedNeighbors(row, col) { const neighbors = []; const directions = [ {dr: -1, dc: 0, wall: 'top', opposite: 'bottom'}, {dr: 0, dc: 1, wall: 'right', opposite: 'left'}, {dr: 1, dc: 0, wall: 'bottom', opposite: 'top'}, {dr: 0, dc: -1, wall: 'left', opposite: 'right'} ]; for (const {dr, dc, wall, opposite} of directions) { const newRow = row + dr; const newCol = col + dc; if (isValidCell(newRow, newCol) && !maze[newRow][newCol].visited) { neighbors.push({ row: newRow, col: newCol, direction: wall, opposite: opposite }); } } return neighbors; } // Recursive DFS maze generation function generateMaze() { initMaze(); visited = Array(ROWS).fill().map(() => Array(COLS).fill(false)); solutionPath = []; generationComplete = false; drawMaze(); solveBtn.disabled = true; generateBtn.disabled = true; // Start generation from top-left corner const stack = []; const startRow = 0; const startCol = 0; maze[startRow][startCol].visited = true; visited[startRow][startCol] = true; stack.push({ row: startRow, col: startCol }); let step = 0; function stepGeneration() { if (stack.length > 0) { const current = stack[stack.length - 1]; const neighbors = getUnvisitedNeighbors(current.row, current.col); if (neighbors.length > 0) { // Pick random neighbor const next = neighbors[Math.floor(Math.random() * neighbors.length)]; const { row, col, direction, opposite } = next; // Remove walls between current and next cell maze[current.row][current.col][direction] = false; maze[row][col][opposite] = false; // Mark as visited maze[row][col].visited = true; visited[row][col] = true; // Add to stack stack.push({ row, col }); // Add occasional animation delay after many steps step++; if (step % 100 === 0) delay++; drawCell(current.row, current.col); drawCell(row, col); drawMarkers(); } else { // Backtrack stack.pop(); } animationId = setTimeout(stepGeneration, delay); } else { // Mark generation as complete generationComplete = true; solveBtn.disabled = false; generateBtn.disabled = false; } } stepGeneration(); } // Reset animation delay function resetDelay() { delay = 0; if (animationId) { clearTimeout(animationId); animationId = null; } } // A* algorithm for solving maze function solveMaze() { if (!generationComplete) return; // Set up for solving solveBtn.disabled = true; resetDelay(); visited = Array(ROWS).fill().map(() => Array(COLS).fill(false)); solutionPath = []; drawMaze(); // Heuristic function (Manhattan distance) function heuristic(row, col) { return Math.abs(ROWS - 1 - row) + Math.abs(COLS - 1 - col); } // Priority queue implementation class PriorityQueue { constructor() { this.elements = []; } enqueue(item, priority) { this.elements.push({ item, priority }); this.elements.sort((a, b) => a.priority - b.priority); } dequeue() { return this.elements.shift().item; } isEmpty() { return this.elements.length === 0; } } // Data structures for A* const openSet = new PriorityQueue(); const cameFrom = {}; const gScore = Array(ROWS).fill().map(() => Array(COLS).fill(Infinity)); // Start node const start = { row: 0, col: 0, g: 0, h: heuristic(0, 0) }; gScore[0][0] = 0; openSet.enqueue(start, start.g + start.h); // Solve process function stepSolve() { if (!openSet.isEmpty()) { const current = openSet.dequeue(); const { row, col } = current; // Mark as visited visited[row][col] = true; drawCell(row, col); // Check if we reached end if (row === ROWS - 1 && col === COLS - 1) { // Reconstruct path let path = []; let step = `${row},${col}`; while (step in cameFrom) { const [r, c] = step.split(",").map(Number); path.push({ row: r, col: c }); step = cameFrom[step]; } path.push({ row: 0, col: 0 }); solutionPath = path.reverse(); // Draw the path step-by-step drawSolution(0); return; } // Check neighbors const directions = [ {dr: -1, dc: 0, wall: 'top'}, // Up {dr: 0, dc: 1, wall: 'right'}, // Right {dr: 1, dc: 0, wall: 'bottom'}, // Down {dr: 0, dc: -1, wall: 'left'} // Left ]; for (const {dr, dc, wall} of directions) { const newRow = row + dr; const newCol = col + dc; const key = `${newRow},${newCol}`; // Check if we can move in this direction and cell is valid if (isValidCell(newRow, newCol) && !maze[row][col][wall]) { const tentativeGScore = gScore[row][col] + 1; if (tentativeGScore < gScore[newRow][newCol]) { // Record path cameFrom[key] = `${row},${col}`; gScore[newRow][newCol] = tentativeGScore; const fScore = tentativeGScore + heuristic(newRow, newCol); // Add to open set openSet.enqueue({ row: newRow, col: newCol, g: tentativeGScore, h: heuristic(newRow, newCol) }, fScore); } } } animationId = setTimeout(stepSolve, delay); } else { // No solution found stats.textContent = "No solution found!"; generateBtn.disabled = false; } } stepSolve(); } // Draw solution path (step-by-step animation) function drawSolution(index) { if (index < solutionPath.length) { const { row, col } = solutionPath[index]; // Draw this step ctx.fillStyle = SOLUTION_COLOR; ctx.fillRect( col * CELL_SIZE, row * CELL_SIZE, CELL_SIZE, CELL_SIZE ); // Draw walls on top of the filled color const cell = maze[row][col]; const x = col * CELL_SIZE; const y = row * CELL_SIZE; ctx.fillStyle = WALL_COLOR; if (cell.top) ctx.fillRect(x, y, CELL_SIZE, WALL_SIZE); if (cell.right) ctx.fillRect(x + CELL_SIZE - WALL_SIZE, y, WALL_SIZE, CELL_SIZE); if (cell.bottom) ctx.fillRect(x, y + CELL_SIZE - WALL_SIZE, CELL_SIZE, WALL_SIZE); if (cell.left) ctx.fillRect(x, y, WALL_SIZE, CELL_SIZE); // Draw end marker last to keep it on top if (index === solutionPath.length - 1) { drawMarkers(); } // Do next step after short delay animationId = setTimeout(() => drawSolution(index + 1), 15); } else { generationComplete = true; generateBtn.disabled = false; solveBtn.disabled = false; } } // Reset everything function reset() { resetDelay(); initMaze(); visited = Array(ROWS).fill().map(() => Array(COLS).fill(false)); solutionPath = []; generationComplete = false; drawMaze(); solveBtn.disabled = false; generateBtn.disabled = false; stats.textContent = "Maze: 30x30 cells"; } // Event listeners generateBtn.addEventListener("click", generateMaze); solveBtn.addEventListener("click", solveMaze); resetBtn.addEventListener("click", reset); // Initialize page window.onload = () => { initMaze(); drawMaze(); }; </script> </body> </html> This implementation: 1. Generates a 30x30 maze using recursive backtracker algorithm 2. Animates the maze generation process 3. Implements A* algorithm with Manhattan distance heuristic to find the shortest path 4. Provides controls to generate new mazes, solve current mazes, and reset 5. Uses a visually appealing color scheme to distinguish maze elements: - Start cell: Green - End cell: Red - Exploration: Gold - Solution path: Blue The entire solution is contained in a single HTML file with no external dependencies. You can save this as `index.html` and open it in any modern browser to see it work.
TAKE IT TO CODE
This run produced no artifact — reuse the prompt with a different model or your own pi-agent run.