Maze generator & solver · deepseek-r1
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-page web app that generates a maze using the recursive backtracker algorithm and then animates solving it with A* search.
The entire app will be in one file: index.html.
We'll have:
- A canvas element for drawing the maze and the solution path.
- Buttons to generate a new maze and to solve it.
- The JavaScript will include:
* Maze generation using recursive backtracker (depth-first search).
* A* algorithm for solving the maze.
* Animation of the solution.
Steps:
1. Set up the HTML structure with a canvas and buttons.
2. Write the CSS for basic styling (centering, etc.).
3. Write the JavaScript:
a. Define constants for the maze (rows, columns, cell size).
b. Set up the canvas context.
c. Implement the recursive backtracker algorithm to generate the maze.
d. Draw the maze on the canvas.
e. Implement the A* algorithm to find the path from start to end.
f. Animate the solution path.
Important: We must use a canvas and draw the grid. The maze will be a grid of cells with walls between them.
Implementation details for maze generation:
- We represent the maze as a 2D grid of cells. Each cell has four walls (top, right, bottom, left).
- We use a stack to keep track of the path for backtracking.
- We start at a cell (say top-left: [0,0]), mark it as visited, and push it to the stack.
- While the stack is not empty:
* Pop the current cell from the stack.
* Check for unvisited neighbors (in random order).
* If there is an unvisited neighbor:
- Remove the wall between the current cell and the neighbor.
- Push the current cell back onto the stack.
- Mark the neighbor as visited and push it to the stack.
For solving with A*:
- We represent each cell as a node with a position and cost values (g, h, f).
- We use a priority queue (min-heap) for the open set. But since we are animating, we can step through the algorithm.
- We'll animate by drawing the open and closed sets as the algorithm progresses.
However, note: We are required to write everything in one file (index.html) and use no external resources.
We'll structure the HTML file as:
<!DOCTYPE html>
<html>
<head>
<title>Maze Generator and Solver</title>
<style>
... CSS styles ...
</style>
</head>
<body>
<div class="container">
<canvas id="mazeCanvas" width="800" height="600"></canvas>
<div>
<button id="generateBtn">Generate Maze</button>
<button id="solveBtn">Solve Maze</button>
</div>
</div>
<script>
... JavaScript code ...
</script>
</body>
</html>
Let's plan the JavaScript:
Constants:
const ROWS = 20;
const COLS = 20;
const CELL_SIZE = 30; // pixels
We'll have:
let maze = []; // 2D array for the maze cells
let ctx = canvas.getContext('2d');
Each cell will be an object with properties for walls and visited flag (for generation).
For the maze generation algorithm, we'll create a Cell class or just use a simple object.
Steps for generation:
1. Initialize the grid: create a 2D array of cells, each with all walls initially present and not visited.
2. Start at (0,0) and mark as visited, push to stack.
3. While stack not empty:
current = pop from stack
get unvisited neighbors (up, right, down, left) that are within grid
if any, choose one randomly
remove the wall between current and neighbor
push current back onto stack
push neighbor onto stack and mark as visited
For drawing the maze:
We'll loop through each cell and draw the walls that are present.
For solving with A*:
We'll represent the maze as a graph where each cell is a node and edges exist where there is no wall.
We'll use the A* algorithm with Manhattan distance as heuristic.
We'll have:
let openSet = []; // priority queue (we'll use an array and sort for simplicity, but note: for performance we might use a heap, but our grid is small)
let closedSet = [];
let start = {x:0, y:0};
let end = {x: COLS-1, y: ROWS-1};
We'll create a grid of nodes for A*.
Steps for A*:
openSet.push(start);
while openSet is not empty:
current = node in openSet with lowest f cost (f = g + h)
if current is end, we reconstruct the path.
remove current from openSet and add to closedSet.
for each neighbor of current (that is accessible, i.e., no wall in between) and not in closedSet:
tempG = current.g + 1
if neighbor not in openSet, add it and set its g, h, f and parent.
else if tempG < neighbor.g, update neighbor.
Then we reconstruct the path from end to start.
Animation:
We'll use requestAnimationFrame to animate the solving process. We can draw the openSet and closedSet as we go.
We'll break the solving into steps so we can animate.
Implementation note: We'll create a separate function for drawing the current state of the solver (openSet, closedSet, and the path when found).
We'll have:
function drawMaze() { ... } // draws the entire maze
function solveStep() { ... } // one step of A*, then draw the state, and if not done, requestAnimationFrame
We'll also need to handle button clicks.
Let's write the code step by step inside the <script> tag.
Note: Since we are writing everything in one file, we must be cautious with variable scoping.
We'll wrap the JavaScript in an IIFE to avoid polluting the global scope, or use event listeners.
Alternatively, we can attach event listeners after the DOM is loaded.
We'll do:
window.onload = function() {
// get canvas and buttons
// set up event listeners
// initialize the maze and draw
}
Let's proceed.
Important: We are writing to index.html in the current directory.
We'll write the entire HTML content in one go.
Note: We are not allowed to create separate files.
We'll write the content for index.html as a string and then use the write function to write it.
Since we are in the harness, we'll output the entire HTML string.
However, note the instructions: "End with index.html present". So we must write the file.
We'll use the write function to write the index.html file.
Let's compose the HTML string.
I'll create a self-contained HTML file that generates a maze using recursive backtracking and solves it with A* search animation. 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 { font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif; display: flex; flex-direction: column; align-items: center; background: linear-gradient(135deg, #1a2a6c, #b21f1f, #1a2a6c); color: white; min-height: 100vh; margin: 0; padding: 20px; overflow-x: hidden; } .container { display: flex; flex-direction: column; align-items: center; max-width: 1000px; width: 100%; } h1 { text-align: center; font-size: 2.8rem; margin-bottom: 5px; text-shadow: 0 2px 4px rgba(0,0,0,0.5); } .subtitle { text-align: center; font-size: 1.2rem; margin-bottom: 25px; opacity: 0.9; } .controls { display: flex; gap: 15px; margin-bottom: 20px; flex-wrap: wrap; justify-content: center; } button { background: linear-gradient(to right, #4A00E0, #8E2DE2); color: white; border: none; padding: 12px 25px; font-size: 1rem; border-radius: 30px; cursor: pointer; transition: all 0.3s ease; font-weight: 600; box-shadow: 0 4px 6px rgba(0,0,0,0.2); } button:hover { transform: translateY(-2px); box-shadow: 0 6px 8px rgba(0,0,0,0.3); } button:active { transform: translateY(1px); } button:disabled { background: #555; cursor: not-allowed; transform: none; box-shadow: none; } .canvas-container { position: relative; margin: 10px 0 30px; border-radius: 8px; overflow: hidden; box-shadow: 0 10px 30px rgba(0,0,0,0.4); background: #111; } canvas { display: block; } .stats { display: flex; justify-content: space-around; width: 100%; max-width: 600px; margin-top: 15px; background: rgba(0,0,0,0.3); padding: 15px; border-radius: 10px; font-size: 1.1rem; } .stat-item { text-align: center; } .stat-value { font-weight: bold; font-size: 1.3rem; color: #8E2DE2; } .legend { display: flex; gap: 25px; margin-top: 10px; flex-wrap: wrap; justify-content: center; } .legend-item { display: flex; align-items: center; gap: 8px; } .color-box { width: 20px; height: 20px; border-radius: 4px; } footer { margin-top: 30px; text-align: center; opacity: 0.7; font-size: 0.9rem; } @media (max-width: 600px) { h1 { font-size: 2rem; } .controls { flex-direction: column; align-items: center; } button { width: 100%; max-width: 300px; } .stats { flex-direction: column; gap: 10px; } } </style> </head> <body> <div class="container"> <h1>Maze Generator & Solver</h1> <p class="subtitle">Recursive Backtracking Generation • A* Pathfinding Algorithm</p> <div class="controls"> <button id="generateBtn">Generate New Maze</button> <button id="solveBtn">Solve with A*</button> <button id="resetBtn">Reset Solution</button> </div> <div class="canvas-container"> <canvas id="mazeCanvas" width="800" height="500"></canvas> </div> <div class="stats"> <div class="stat-item"> <div>Maze Size</div> <div id="sizeValue" class="stat-value">25x25</div> </div> <div class="stat-item"> <div>Generation Time</div> <div id="genTimeValue" class="stat-value">0ms</div> </div> <div class="stat-item"> <div>Solution Path</div> <div id="pathLength" class="stat-value">0</div> </div> </div> <div class="legend"> <div class="legend-item"> <div class="color-box" style="background-color: #FF5252;"></div> <span>Start Position</span> </div> <div class="legend-item"> <div class="color-box" style="background-color: #4CAF50;"></div> <span>End Position</span> </div> <div class="legend-item"> <div class="color-box" style="background-color: #2196F3;"></div> <span>Explored Path</span> </div> <div class="legend-item"> <div class="color-box" style="background-color: #FFEB3B;"></div> <span>Final Path</span> </div> </div> </div> <footer> Recursive Backtracking Maze Generation • A* Pathfinding Algorithm • Single HTML File Implementation </footer> <script> // Canvas setup const canvas = document.getElementById('mazeCanvas'); const ctx = canvas.getContext('2d'); const generateBtn = document.getElementById('generateBtn'); const solveBtn = document.getElementById('solveBtn'); const resetBtn = document.getElementById('resetBtn'); // Maze configuration const CELL_SIZE = 20; const MAZE_WIDTH = Math.floor(canvas.width / CELL_SIZE); const MAZE_HEIGHT = Math.floor(canvas.height / CELL_SIZE); const START_X = 0; const START_Y = 0; const END_X = MAZE_WIDTH - 1; const END_Y = MAZE_HEIGHT - 1; // Update stats display document.getElementById('sizeValue').textContent = `${MAZE_WIDTH}x${MAZE_HEIGHT}`; // Maze state let maze = []; let solution = []; let exploredCells = []; let isSolving = false; let animationId = null; // Directions for pathfinding const DIRECTIONS = [ { dx: 0, dy: -1 }, // Up { dx: 1, dy: 0 }, // Right { dx: 0, dy: 1 }, // Down { dx: -1, dy: 0 } // Left ]; // Cell class for maze generation class Cell { constructor(x, y) { this.x = x; this.y = y; this.walls = { top: true, right: true, bottom: true, left: true }; this.visited = false; } draw() { const x = this.x * CELL_SIZE; const y = this.y * CELL_SIZE; ctx.strokeStyle = '#FFFFFF'; ctx.lineWidth = 2; if (this.walls.top) { ctx.beginPath(); ctx.moveTo(x, y); ctx.lineTo(x + CELL_SIZE, y); ctx.stroke(); } if (this.walls.right) { ctx.beginPath(); ctx.moveTo(x + CELL_SIZE, y); ctx.lineTo(x + CELL_SIZE, y + CELL_SIZE); ctx.stroke(); } if (this.walls.bottom) { ctx.beginPath(); ctx.moveTo(x + CELL_SIZE, y + CELL_SIZE); ctx.lineTo(x, y + CELL_SIZE); ctx.stroke(); } if (this.walls.left) { ctx.beginPath(); ctx.moveTo(x, y + CELL_SIZE); ctx.lineTo(x, y); ctx.stroke(); } } } // Initialize maze grid function initializeMaze() { maze = []; for (let y = 0; y < MAZE_HEIGHT; y++) { const row = []; for (let x = 0; x < MAZE_WIDTH; x++) { row.push(new Cell(x, y)); } maze.push(row); } } // Check if coordinates are valid function isValid(x, y) { return x >= 0 && x < MAZE_WIDTH && y >= 0 && y < MAZE_HEIGHT; } // Get unvisited neighbors for maze generation function getUnvisitedNeighbors(cell) { const neighbors = []; const directions = [ { dx: 0, dy: -1, wall: 'top', opposite: 'bottom' }, // Up { dx: 1, dy: 0, wall: 'right', opposite: 'left' }, // Right { dx: 0, dy: 1, wall: 'bottom', opposite: 'top' }, // Down { dx: -1, dy: 0, wall: 'left', opposite: 'right' } // Left ]; for (const dir of directions) { const nx = cell.x + dir.dx; const ny = cell.y + dir.dy; if (isValid(nx, ny) && !maze[ny][nx].visited) { neighbors.push({ cell: maze[ny][nx], direction: dir }); } } return neighbors; } // Remove wall between two cells function removeWall(current, neighbor, direction) { current.walls[direction.wall] = false; neighbor.walls[direction.opposite] = false; } // Generate maze using recursive backtracking function generateMaze() { const startTime = performance.now(); initializeMaze(); // Start generation from top-left corner const startCell = maze[START_Y][START_X]; startCell.visited = true; const stack = [startCell]; while (stack.length > 0) { const current = stack.pop(); const neighbors = getUnvisitedNeighbors(current); if (neighbors.length > 0) { stack.push(current); // Randomly select a neighbor const randomIndex = Math.floor(Math.random() * neighbors.length); const { cell: neighbor, direction } = neighbors[randomIndex]; // Remove wall between current and neighbor removeWall(current, neighbor, direction); neighbor.visited = true; stack.push(neighbor); } } // Reset solution state solution = []; exploredCells = []; isSolving = false; if (animationId) { cancelAnimationFrame(animationId); animationId = null; } // Draw the maze drawMaze(); // Update generation time const genTime = performance.now() - startTime; document.getElementById('genTimeValue').textContent = `${Math.round(genTime)}ms`; document.getElementById('pathLength').textContent = '0'; } // Draw the entire maze function drawMaze() { ctx.clearRect(0, 0, canvas.width, canvas.height); // Draw background ctx.fillStyle = '#222'; ctx.fillRect(0, 0, canvas.width, canvas.height); // Draw all cells for (let y = 0; y < MAZE_HEIGHT; y++) { for (let x = 0; x < MAZE_WIDTH; x++) { maze[y][x].draw(); } } // Draw start and end points drawCell(START_X, START_Y, '#FF5252'); drawCell(END_X, END_Y, '#4CAF50'); // Draw explored cells during solving for (const cell of exploredCells) { drawCell(cell.x, cell.y, '#2196F3'); } // Draw solution path if exists if (solution.length > 0) { for (let i = 0; i < solution.length; i++) { const cell = solution[i]; drawCell(cell.x, cell.y, '#FFEB3B'); } // Draw start and end again on top drawCell(START_X, START_Y, '#FF5252'); drawCell(END_X, END_Y, '#4CAF50'); } } // Draw a filled cell function drawCell(x, y, color) { ctx.fillStyle = color; ctx.fillRect( x * CELL_SIZE + 2, y * CELL_SIZE + 2, CELL_SIZE - 4, CELL_SIZE - 4 ); } // Check if two cells are connected (no wall between them) function isConnected(x1, y1, x2, y2) { const cell = maze[y1][x1]; if (x2 === x1 + 1 && y1 === y2) return !cell.walls.right; // Right if (x2 === x1 - 1 && y1 === y2) return !cell.walls.left; // Left if (y2 === y1 + 1 && x1 === x2) return !cell.walls.bottom; // Down if (y2 === y1 - 1 && x1 === x2) return !cell.walls.top; // Up return false; } // A* pathfinding algorithm function solveMaze() { if (isSolving) return; isSolving = true; solution = []; exploredCells = []; // Reset stats document.getElementById('pathLength').textContent = '0'; // Create nodes for A* const nodes = []; for (let y = 0; y < MAZE_HEIGHT; y++) { const row = []; for (let x = 0; x < MAZE_WIDTH; x++) { row.push({ x, y, f: Infinity, g: Infinity, h: Math.abs(x - END_X) + Math.abs(y - END_Y), // Manhattan distance parent: null, closed: false, visited: false }); } nodes.push(row); } // Start node const startNode = nodes[START_Y][START_X]; startNode.g = 0; startNode.f = startNode.h; const openSet = [startNode]; function solveStep() { if (openSet.length === 0) { // No solution found isSolving = false; return; } // Get node with lowest f score openSet.sort((a, b) => a.f - b.f); const currentNode = openSet.shift(); // Mark as visited currentNode.closed = true; exploredCells.push({ x: currentNode.x, y: currentNode.y }); // Check if we reached the end if (currentNode.x === END_X && currentNode.y === END_Y) { // Reconstruct path let temp = currentNode; while (temp !== null) { solution.unshift({ x: temp.x, y: temp.y }); temp = temp.parent; } // Update path length document.getElementById('pathLength').textContent = solution.length; isSolving = false; drawMaze(); return; } // Explore neighbors for (const dir of DIRECTIONS) { const nx = currentNode.x + dir.dx; const ny = currentNode.y + dir.dy; if (!isValid(nx, ny) || !isConnected(currentNode.x, currentNode.y, nx, ny)) { continue; } const neighbor = nodes[ny][nx]; if (neighbor.closed) { continue; } // Calculate tentative g score const tentativeG = currentNode.g + 1; if (tentativeG < neighbor.g) { neighbor.parent = currentNode; neighbor.g = tentativeG; neighbor.f = neighbor.g + neighbor.h; if (!neighbor.visited) { neighbor.visited = true; openSet.push(neighbor); } } } drawMaze(); // Continue animation if (isSolving) { animationId = requestAnimationFrame(solveStep); } } animationId = requestAnimationFrame(solveStep); } // Reset solution function resetSolution() { solution = []; exploredCells = []; isSolving = false; if (animationId) { cancelAnimationFrame(animationId); animationId = null; } drawMaze(); document.getElementById('pathLength').textContent = '0'; } // Event listeners generateBtn.addEventListener('click', generateMaze); solveBtn.addEventListener('click', solveMaze); resetBtn.addEventListener('click', resetSolution); // Initial maze generation generateMaze(); </script> </body> </html> ``` This implementation features: 1. **Maze Generation**: - Recursive backtracking algorithm creates a perfect maze - Randomized depth-first search approach - Walls removed between cells to form paths 2. **Pathfinding**: - A* search algorithm finds the shortest path - Manhattan distance heuristic for efficient searching - Animated exploration showing the algorithm's progress 3. **Visual Design**: - Responsive layout with gradient background - Clean canvas display with distinct colors for: - Start position (red) - End position (green) - Explored paths (blue) - Final solution (yellow) - Statistics panel showing maze size, generation time, and path length - Legend for color coding 4. **Controls**: - Generate New Maze button - Solve with A* button - Reset Solution button The entire application is self-contained in a single HTML file with no external dependencies, as requested. The maze generation and solving algorithms are implemented from scratch using pure JavaScript and Canvas API.
TAKE IT TO CODE
This run produced no artifact — reuse the prompt with a different model or your own pi-agent run.