Compare all models on this prompt →
Maze generator & solver · deepseek-v4-pro
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.
⛨ sandboxed Open in new tab ↗
transcript · 6 messages
user
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.
assistant
thinking
The user wants me to create a single-page web app (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 start to finish
Let me build this step by step:
1. Recursive-backtracker maze generation:
- Start with a grid where all cells have all walls
- Pick a starting cell, mark it as visited
- While there are unvisited neighbors:
- Pick a random unvisited neighbor
- Remove the wall between current and chosen neighbor
- Move to that neighbor, mark as visited, push to stack
- Backtrack when stuck (pop from stack)
2. A* solver:
- Use Manhattan distance as heuristic
- Maintain open set (priority queue based on f = g + h)
- Animate the exploration and final path
3. BFS solver:
- Queue-based exploration
- Animate exploration and final path
Let me create a comprehensive implementation with:
- Canvas rendering
- Maze generation animation (or instant generation then solve animation)
- A* solver animation
- Controls (generate, solve with A*, solve with BFS)
- Visual distinction between:
- Walls
- Paths
- Explored cells
- Solution path
- Start and end
Let me think about the maze structure:
- A grid of cells, each with 4 walls (top, right, bottom, left)
- Canvas-based rendering
For the animation, I'll use requestAnimationFrame or setInterval to step through the solver's exploration.
Let me design the UI:
- Canvas for maze
- Buttons: Generate Maze, Solve A*, Solve BFS
- Maybe a speed control
I'll use a cell size that works well. Let's say the maze is 25x25 or so (odd numbers work well for mazes).
Actually, let me think about the recursive backtracker algorithm more carefully:
Grid: rows x cols cells
Each cell has walls: top, right, bottom, left (all present initially)
Algorithm:
1. Start at cell (0,0)
2. Mark as visited
3. Get unvisited neighbors
4. If there are unvisited neighbors:
- Pick random unvisited neighbor
- Remove wall between current and chosen
- Recursively visit that neighbor (or use stack)
5. Otherwise backtrack (pop from stack)
For A*:
- Open set: priority queue of {row, col, f, g, h}
- Closed set: visited cells
- f = g + h where g is distance from start, h is Manhattan distance to goal
- Animate: show cells being explored (light blue) and final path (green)
Let me build this now. I'll make it visually appealing with nice colors.
Let me plan the canvas size. With a 400x400 canvas and 25 columns, each cell is 16px. That should work.
Actually, let me make the maze parameters configurable or use a reasonable default. Let me use 21x21 with cell size of 20px = 420px canvas. Or maybe adjustable.
Let me go with a responsive approach - calculate cell size based on canvas dimensions and maze dimensions.
Let me code this up:
```html
<!DOCTYPE html>
<html>
...
```
Let me think about the animation loop. For the solver:
- Run one step of A*/BFS at a time
- Use setInterval or requestAnimationFrame with a delay
- Show explored cells gradually
- When solution is found, highlight the path
I'll implement both A* and BFS. The user can choose.
Let me also animate the maze generation slightly, or just generate it instantly and then show it.
Actually, for a nicer experience, let me:
1. Generate the maze instantly (it's fast)
2. Then animate the solving
But I could also animate the maze generation if the user wants. Let me keep it simple - generate maze, then animate solver.
Now let me code this thoroughly.
Maze representation:
- 2D array of cells: maze[row][col] = { top: true, right: true, bottom: true, left: true, visited: false }
- During generation, all walls are true initially
Let me write the full implementation.
For the priority queue in A*, I'll use a simple binary heap or just sort the array each time (for small mazes it's fine).
Actually, for cleaner code, I'll implement a simple priority queue using an array that I sort.
Let me now write the complete code.
For the solving animation, I'll use:
- `visitedCells`: array of cells that were explored (in order)
- `solutionPath`: array of cells from start to finish
During animation:
- Draw the maze
- Highlight visited cells in order
- When done, draw solution path
I'll use a step counter that increments with each animation frame.
Actually, let me think about how to animate both the exploration and the final path.
Option 1: Animate all visited cells, then show the path
Option 2: Show the path being built as we explore
I'll go with option 1: show exploration spreading, then show the final path.
For BFS, I'll record the order cells are visited, and also keep track of parent pointers for reconstructing the path.
For A*, same thing.
Let me structure the code:
```javascript
// Maze class
class Maze {
constructor(rows, cols) { ... }
generate() { ... } // recursive backtracker
draw(ctx) { ... }
}
// Solver
function solveAStar(maze) { ... } // returns {visited, path}
function solveBFS(maze) { ... } // returns {visited, path}
// Animation
function animateSolve(result) { ... }
```
Now let me write the complete code.
For the maze generation, I'll use a stack-based iterative approach (equivalent to recursive backtracker):
```
stack = [(0,0)]
visited[0][0] = true
while stack not empty:
current = stack[stack.length-1]
neighbors = unvisited neighbors of current
if neighbors.length > 0:
next = random neighbor
remove wall between current and next
visited[next] = true
stack.push(next)
else:
stack.pop()
```
This is correct. The unvisited neighbors are adjacent cells (not diagonal) that haven't been visited.
Alright, let me write the full code now. I want it to look good too.
Let me think about colors:
- Background/walls: dark (#1a1a2e)
- Path cells: white/cream
- Start: green
- End: red
- Explored (during solve): light blue gradient
- Solution path: gold/yellow
- Current frontier (currently exploring): brighter blue
For the canvas, I'll draw:
1. Fill background with wall color
2. For each cell that's a passage, fill it with path color
3. Draw walls as lines between cells
Actually, a typical maze rendering approach:
- Fill the entire canvas with the wall color (dark)
- For each cell, fill the interior with the path color (white)
- Draw walls as needed
Wait, let me think of a cleaner approach. Each cell is a square. I'll:
1. Fill each cell's interior with the passage color
2. Draw walls as thick lines
Here's my approach:
- Cell at row r, col c has its top-left corner at (c * cellSize, r * cellSize)
- Draw the interior of each cell (path color)
- Draw walls: if top wall exists, draw line at top edge; if right wall exists, draw line at right edge; etc.
This is clean. The border walls are already there.
Let me also add some CSS for a nice dark-themed UI.
For the animation speed, I'll use a slider or just a set speed. Let me add a speed slider.
Let me also add stats: cells visited, path length.
OK let me write this now. I'll aim for a polished implementation.
Let me also consider: should I animate maze generation? It could be cool. Let me add it as an option - generate and show instantly, or animate generation.
For simplicity, I'll:
- Generate instantly when "Generate" is clicked (or on load)
- Animate solving with A* or BFS when those buttons are clicked
Actually, let me also animate the maze generation! It's quite satisfying to watch. I'll use the same animation loop pattern.
Let me track the generation steps:
- During generation, record each step (which wall was removed between which cells)
- Then animate by replaying those steps
Or more simply, during generation, at each step:
- The current cell being processed
- The walls that have been removed so far
For animation, I can show the maze being built step by step. At each step, we remove a wall and advance the current position.
Let me implement this. I'll store generation history:
- steps: [{row, col, wall, direction}] - each step removes a wall and moves to a new cell
Or more simply, I'll just record the state after each wall removal.
Actually, the simplest approach for animation:
- Generate the maze step by step in the animation loop
- At each frame, do one iteration of the backtracker
- Draw the current state
This way we don't need to store history; we just run the algorithm step by step.
Let me design the animation loop:
```
animationState = {
type: 'generating' | 'solving' | 'idle',
// for generating:
stack: [...],
visited: [...],
current: {row, col},
// for solving:
visitedCells: [...],
solutionPath: [...],
currentStep: number,
// common:
speed: number (ms per step),
lastTime: timestamp
}
```
Actually, let me use requestAnimationFrame and track time for speed control. Each frame, I check if enough time has passed since the last step. If so, I advance one step.
This gives smooth animation that can be sped up or slowed down.
OK, I think I have enough design. Let me write the code.
Let me make the maze 25x25 with cell size calculated to fit in about 500px. That's 20px per cell = 500px. Let me make it 25x25.
Actually, let me make a responsive-ish canvas. Let me use a fixed canvas of 500x500 with cellSize calculated based on maze dimensions. For a 25x25 maze: cellSize = 20px, canvas = 500x500.
Let me finalize and write the code.
One more thing: for the maze generation animation to look good, I want to highlight the "current" cell (the top of the stack) and show walls being carved. The dark cells are unexplored, the white cells are explored. Initially all cells are unexplored (walls everywhere), and as we carve, cells become explored and walls between them are removed.
For the initial state before generation, I can show all walls (which looks like a solid block of wall color). As generation proceeds, cells become passages.
Actually, let me just draw the maze based on the current state of the cell data. Initially all cells have all walls and are unvisited - they'll be drawn as wall-colored. As they get visited, they become passage-colored with appropriate walls removed.
Wait, this might look weird because initially all cells have all 4 walls, so they look like solid blocks. Let me adjust: draw passage cells as light/white and draw only the walls that exist. For unvisited cells, draw them as dark (wall color). This way, as the maze is generated, you see passages carving through the dark area.
Let me implement this. The draw function will:
1. For each cell, fill its interior with either wall color (unvisited) or passage color (visited)
2. For visited cells, draw existing walls as lines
This will look great during animation.
OK now I'm actually going to write the code. Let me be thorough.
Here's my plan for the complete HTML file:
```
Structure:
- <style>: Dark theme, centered layout, buttons, slider
- <canvas>: Maze display
- <div>: Controls (Generate, Solve A*, Solve BFS, Speed slider)
- <script>: All logic
```
Let me write it all out now.
For the maze drawing during generation animation, I need to keep the maze data (which cells are visited and which walls exist) and update it step by step, redrawing each frame.
Let me also add a "Reset" button that clears the solution visualization but keeps the maze.
States:
- IDLE: Maze generated, no solving in progress
- GENERATING: Maze generation in progress
- SOLVING: Solver in progress
- SOLVED: Solution shown
Buttons behavior:
- "Generate New Maze" - starts generation animation (or generates instantly)
- "Solve with A*" - starts A* animation
- "Solve with BFS" - starts BFS animation
- "Reset Solution" - clears solution, shows plain maze
I'll disable buttons during animations.
Let me code this now. I'll be comprehensive.
Actually, for the canvas size, let me make it a bit more flexible. I'll use a CellSize that's calculated to fit. For 25 rows/cols and a 500px canvas, that's 20px per cell.
Let me set:
- Maze: 21 rows x 21 cols (odd numbers are traditional but even works too with recursive backtracker)
- Canvas: 504px x 504px (21 * 24 = 504)
Hmm, let me just use cellSize = 20 and calculate canvas size = rows * cellSize. With 25 rows: 500px.
Let me go with 25x25, cellSize 20, canvas 500x500.
Now, the maze generation might be a bit slow to animate at 25x25 (625 cells). But with a reasonable speed it should be fine. Let me set default speed so it completes in a few seconds.
At 10ms per step (100 steps/sec), 625 steps would take ~6 seconds. That's reasonable.
But the number of steps in recursive backtracker equals the number of cells (each cell is visited once and a wall is removed when moving to it). So 624 steps for 25x25 (since first cell doesn't need a wall removed to enter it).
OK, at a speed of about 5ms per step, that's about 3 seconds total for generation. That feels good.
For solving, A* and BFS will explore many cells. In the worst case they might explore most cells. Let me animate at maybe 10-20ms per step for exploring, and then show the path.
Alright, let me finalize and write the code!
I'll structure the JS as follows:
```javascript
// Constants
const ROWS = 25;
const COLS = 25;
const CELL_SIZE = 20;
const CANVAS_SIZE = COLS * CELL_SIZE; // 500
// Colors
const WALL_COLOR = '#1a1a2e';
const PASSAGE_COLOR = '#e0e0e0';
const START_COLOR = '#4ade80';
const END_COLOR = '#ef4444';
const EXPLORED_COLOR = '#93c5fd';
const SOLUTION_COLOR = '#fbbf24';
const CURRENT_COLOR = '#60a5fa'; // current cell during generation
// State
let maze = []; // maze[row][col] = { top, right, bottom, left, visited }
let animationState = 'idle'; // idle | generating | solving
let animationId = null;
let solveResult = null; // { visited: [], path: [] }
let solveStepIndex = 0;
let genStack = [];
let genCurrent = null;
let speed = 5; // ms per step
// Initialize
function initMaze() {
maze = [];
for (let r = 0; r < ROWS; r++) {
maze[r] = [];
for (let c = 0; c < COLS; c++) {
maze[r][c] = {
top: true,
right: true,
bottom: true,
left: true,
visited: false
};
}
}
}
// Recursive backtracker - one step
function generationStep() {
// Returns true if generation is complete
...
}
// A* solver
function solveAStar() {
...
}
// BFS solver
function solveBFS() {
...
}
// Drawing
function draw() {
const canvas = document.getElementById('mazeCanvas');
const ctx = canvas.getContext('2d');
// Clear
ctx.fillStyle = WALL_COLOR;
ctx.fillRect(0, 0, CANVAS_SIZE, CANVAS_SIZE);
// Draw cells
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
const cell = maze[r][c];
const x = c * CELL_SIZE;
const y = r * CELL_SIZE;
if (cell.visited) {
// Fill passage
ctx.fillStyle = PASSAGE_COLOR;
ctx.fillRect(x, y, CELL_SIZE, CELL_SIZE);
// Draw walls
ctx.strokeStyle = WALL_COLOR;
ctx.lineWidth = 2;
if (cell.top) {
ctx.beginPath();
ctx.moveTo(x, y);
ctx.lineTo(x + CELL_SIZE, y);
ctx.stroke();
}
if (cell.right) {
ctx.beginPath();
ctx.moveTo(x + CELL_SIZE, y);
ctx.lineTo(x + CELL_SIZE, y + CELL_SIZE);
ctx.stroke();
}
if (cell.bottom) {
ctx.beginPath();
ctx.moveTo(x, y + CELL_SIZE);
ctx.lineTo(x + CELL_SIZE, y + CELL_SIZE);
ctx.stroke();
}
if (cell.left) {
ctx.beginPath();
ctx.moveTo(x, y);
ctx.lineTo(x, y + CELL_SIZE);
ctx.stroke();
}
}
}
}
// During generation, highlight current cell
if (animationState === 'generating' && genCurrent) {
ctx.fillStyle = CURRENT_COLOR;
ctx.fillRect(genCurrent.c * CELL_SIZE + 2, genCurrent.r * CELL_SIZE + 2, CELL_SIZE - 4, CELL_SIZE - 4);
}
// During/after solving, highlight explored and solution
if (solveResult && animationState === 'solving') {
// Draw explored cells up to solveStepIndex
for (let i = 0; i < Math.min(solveStepIndex, solveResult.visited.length); i++) {
const [r, c] = solveResult.visited[i];
ctx.fillStyle = EXPLORED_COLOR;
ctx.fillRect(c * CELL_SIZE + 1, r * CELL_SIZE + 1, CELL_SIZE - 2, CELL_SIZE - 2);
}
}
if (solveResult && animationState === 'solved') {
// Draw all explored cells lightly
for (const [r, c] of solveResult.visited) {
ctx.fillStyle = EXPLORED_COLOR;
ctx.fillRect(c * CELL_SIZE + 1, r * CELL_SIZE + 1, CELL_SIZE - 2, CELL_SIZE - 2);
}
// Draw solution path
for (const [r, c] of solveResult.path) {
ctx.fillStyle = SOLUTION_COLOR;
ctx.fillRect(c * CELL_SIZE + 1, r * CELL_SIZE + 1, CELL_SIZE - 2, CELL_SIZE - 2);
}
}
// Draw start and end
ctx.fillStyle = START_COLOR;
ctx.fillRect(0 + 2, 0 + 2, CELL_SIZE - 4, CELL_SIZE - 4);
ctx.fillStyle = END_COLOR;
ctx.fillRect((COLS-1) * CELL_SIZE + 2, (ROWS-1) * CELL_SIZE + 2, CELL_SIZE - 4, CELL_SIZE - 4);
}
```
Wait, I need to think about the start and end. Start is top-left (0,0), end is bottom-right (ROWS-1, COLS-1). During generation, these will be part of the maze. After generation, they'll be marked as start/end.
OK, let me finalize the design and write the complete code. I want to handle all edge cases properly.
Let me also add a label/status showing what's happening.
For the solveResult, I need to store:
- visited: array of [row, col] in order visited
- path: array of [row, col] from start to end
For BFS: visited is BFS order, path is reconstructed from parent pointers
For A*: visited is order cells are popped from open set (or added to closed set), path is reconstructed from parent pointers
Now let me think about the animation more carefully.
During solving animation:
- Step through visited array
- Each step shows one more cell as explored
- When all visited cells are shown, show the solution path
I'll structure it as:
- Phase 1: Show explored cells one by one (solveStepIndex increases)
- Phase 2: When all explored cells are shown, show solution path (set animationState to 'solved')
For the generation animation:
- Step through the backtracker algorithm
- Each step: either move to a new cell (removing a wall) or backtrack
- When stack is empty, generation is complete
Let me now write the complete code. I'll be careful with the animation loop and timing.
Actually, for the generation animation, I need to be careful. The recursive backtracker uses a stack. At each step:
1. Look at the top of the stack (current cell)
2. Find an unvisited neighbor
3. If found: remove wall, mark neighbor visited, push neighbor onto stack
4. If not found: pop from stack (backtrack)
So each step either advances (carves) or backtracks. To make the animation look good, I should probably only show the advancing steps and skip the backtracking steps (or show them quickly).
Actually, showing backtracking is fine - the current cell highlight moves back. It gives a sense of the algorithm. But it might make the animation longer. Let me keep it and just adjust the speed.
For the speed control, I'll use a range input. Default maybe 10ms per step for generation, 5ms per step for solving.
Let me use a single speed slider that controls both.
OK, I think I've designed enough. Let me write the full code now, in one shot.
Actually, I realize I should also handle the case where the user clicks "Generate" during an animation - cancel the current animation and start the new one.
Let me use `cancelAnimationFrame` to stop the current animation.
OK, writing the code now!
Let me think about one more thing: the canvas size. 500x500 might be too big for some screens. Let me make it responsive or use a smaller size. 400x400 with 20 cells at 20px each = 20x20 maze. Or I could make the canvas take up a reasonable portion of the screen.
Let me go with:
- Canvas: 500x500
- Maze: 25x25
- Cell size: 20px
This looks good on most screens.
If I want to be fancy, I could use devicePixelRatio for crisp rendering on retina displays, but that adds complexity. Let me keep it simple.
One more thing: for the maze walls, I should make sure the outer border walls are drawn. Since all cells start with all walls, the outer edges of the maze will naturally have walls. But when I fill the canvas with wall color and then fill passage cells with passage color, the outer walls will be the wall color showing through. That should work.
Let me finalize the draw logic:
1. Fill entire canvas with WALL_COLOR (dark background)
2. For each visited cell, fill its interior with PASSAGE_COLOR
3. For each visited cell, draw its existing walls as WALL_COLOR lines
4. Overlay: start cell (green), end cell (red)
5. Overlay: explored cells during solve (blue)
6. Overlay: solution path (yellow/gold)
This should produce a clean maze.
Now writing the complete code:
One issue: when drawing the walls for visited cells, I need to be careful at the edges. For the outer border, the cell's outer wall (e.g., top wall of row 0, left wall of col 0) should remain. These walls won't be removed during generation (since we never try to go out of bounds). So they'll naturally stay, and the wall-colored background showing through will form the border.
Wait, but if I fill the canvas with wall color and then fill visited cells with passage color, the outer walls are automatically visible because we don't fill beyond the cell interior. So that works.
Actually, if I fill with wall color and then fill each visited cell with passage color, the thin gaps between cells (if any) would show the wall color. For the internal walls that have been removed, this would cause spurious lines. So I should draw the walls explicitly.
Let me reconsider. Better approach:
1. Fill canvas with wall color
2. For each visited cell, fill with passage color (slightly smaller than cellSize to leave gaps?)
- No, fill exactly cellSize x cellSize
3. For each visited cell, draw existing walls as thick lines in wall color
- This covers up the passage color at the edges where walls exist
This should work well. The wall lines will be thick (maybe 2-3px) so they're visible.
Actually wait, there's a subtlety. If two adjacent visited cells share a wall that has been removed, I shouldn't draw a wall line there. My approach handles this: I only draw walls if `cell.top`, `cell.right`, etc. are true. Each cell draws its own walls. If the wall between cell A and cell B is removed, cell A's right wall is false and cell B's left wall is false, so neither draws the wall. Good.
But there's double-drawing: the wall between two cells is drawn twice (once by each cell's wall line). That's fine since they overlap.
For the outer border, each cell on the edge has its outer wall set to true (never removed during generation since we never go out of bounds). So these walls are drawn, and they cover the edge of the passage-colored fill, creating a clean border. Good.
Now let me think about the wall drawing parameters. If I draw walls as 2px lines centered on the cell boundary, they'll extend 1px into each cell. This looks good. Let me use lineWidth = 2.
Alright, I'm confident in the approach. Let me write the code!
One more consideration: the animation loop. I'll use requestAnimationFrame and track elapsed time:
```javascript
let lastStepTime = 0;
function animationLoop(timestamp) {
if (timestamp - lastStepTime >= speed) {
lastStepTime = timestamp;
// do one step
if (animationState === 'generating') {
if (generationStep()) {
// generation complete
animationState = 'idle';
return;
}
} else if (animationState === 'solving') {
if (solvingStep()) {
// solving complete
animationState = 'solved';
return;
}
}
}
draw();
if (animationState !== 'idle' && animationState !== 'solved') {
animationId = requestAnimationFrame(animationLoop);
}
}
```
This way, the animation runs at approximately `speed` ms per step.
But for 'solved' state, I might want one final draw and then stop. Let me handle that.
OK, actually let me simplify. The animation loop always runs requestAnimationFrame. The state machine determines what happens:
States: 'idle', 'generating', 'solving', 'solved'
- 'idle': draw maze, no animation
- 'generating': step through generation, draw each frame
- 'solving': step through solver visited cells, draw each frame
- 'solved': draw final state with solution path
For 'solved', we don't need continuous animation, just one draw. So when we transition to 'solved', we draw once and stop the animation loop.
Let me finalize and write. I've been overthinking this.
Actually, let me also add a subtle animation for the "solved" state where the solution path animates in (draws progressively), and then stays visible. Or just show it all at once.
Let me do: after all visited cells are shown, transition to 'solved' and show the path all at once. This is clean.
One more thing: for the speed slider, I'll invert the value so higher = faster (shorter delay between steps). Range: 1 to 50 ms. Default: 10ms (100 steps/sec for solving).
For generation, I want it faster since there are only 625 steps and the user wants to see the maze appear. Let me use the same speed for both.
Alright, NOW I'm writing the code. No more deliberation!
Let me think about what functions I need:
1. `initMaze()` - create fresh maze data (all walls, not visited)
2. `startGeneration()` - initialize generation, start animation
3. `generationStep()` - one step of recursive backtracker, returns true if done
4. `startSolving(algorithm)` - initialize solver, start animation
5. `solvingStep()` - one step of solver animation, returns true if done
6. `draw()` - render everything
7. `animationLoop(timestamp)` - main loop
8. `stopAnimation()` - cancel animation frame
9. Event handlers for buttons
Helper functions:
- `getUnvisitedNeighbors(r, c)` - for generation
- `getPassableNeighbors(r, c)` - for solving (checks walls)
- `reconstructPath(parents, end)` - for solving
OK here we go!
Let me also make sure the start and end are clearly marked. Start = (0,0) green, End = (ROWS-1, COLS-1) red.
For BFS, I need to track parents:
```
parents = {}; // key: "r,c" -> "pr,pc"
queue = [[0, 0]];
parents["0,0"] = null;
while queue:
[r, c] = queue.shift();
if r == ROWS-1 && c == COLS-1: break;
for each passable neighbor [nr, nc]:
if "nr,nc" not in parents:
parents["nr,nc"] = [r, c];
queue.push([nr, nc]);
```
For A*, similar but with priority queue:
```
openSet = [{r: 0, c: 0, g: 0, f: heuristic(0,0)}];
parents = {"0,0": null};
closedSet = new Set();
while openSet:
sort openSet by f;
current = openSet.shift();
if current.r == ROWS-1 && current.c == COLS-1: break;
closedSet.add("r,c");
for each passable neighbor [nr, nc]:
if "nr,nc" in closedSet: continue;
g = current.g + 1;
if "nr,nc" not in parents or g < gValues["nr,nc"]:
parents["nr,nc"] = [r, c];
gValues["nr,nc"] = g;
openSet.push({r: nr, c: nc, g, f: g + heuristic(nr, nc)});
```
For Manhattan heuristic: `heuristic(r, c) = (ROWS-1 - r) + (COLS-1 - c)`
Now, for recording visited order:
- BFS: each cell when it's first discovered (when added to queue and parents)
- A*: each cell when it's popped from open set (added to closed set)
This is the "explored" set. I'll record these in order.
Actually for A*, the "visited" order that looks best for animation is the order cells are added to the closed set (popped from open set). This shows how A* explores.
For BFS, it's the order cells are dequeued.
Let me finalize the implementation now!
I also want to make the wall drawing look nice. For the maze walls, I'll use:
- Wall lines: 2px wide, COLOR_WALL
- Cell fills: COLOR_PASSAGE
The walls should look like they separate the passages. With a dark background and light passages, it'll be a classic maze look.
Now, here's one thing: for the canvas size, let me use a fixed size. With 25 cells and 20px per cell, the canvas is 500px. Let me adjust to maybe 21 cells at 24px for a 504px canvas. Or just 25 cells at 20px = 500px. Let me go with 25 at 20px.
Actually wait, I'm going to round the canvas size to be CELL_SIZE * COLS. So 25 * 20 = 500. That's nice and clean.
Let me now write the entire file. I'll be thorough and handle all the edge cases.
For the maze data structure:
```
maze[r][c] = {
top: bool,
right: bool,
bottom: bool,
left: bool,
visited: bool // visited during generation
}
```
Directions for getting neighbors (used in both generation and solving):
```
const DIRS = [
{dr: -1, dc: 0, wall: 'top', oppositeWall: 'bottom'}, // up
{dr: 0, dc: 1, wall: 'right', oppositeWall: 'left'}, // right
{dr: 1, dc: 0, wall: 'bottom', oppositeWall: 'top'}, // down
{dr: 0, dc: -1, wall: 'left', oppositeWall: 'right'} // left
];
```
For generation: check if neighbor is in bounds and not visited.
For solving: check if neighbor is in bounds and there's no wall between current and neighbor.
Alright, I'll write the code now. I'll focus on making it clean, well-commented, and visually appealing.
For the overall UI layout:
- Title at top
- Canvas centered
- Controls below (buttons + speed slider)
- Status text
Color scheme (dark theme):
- Background: #0f0f1a
- Cards/panels: #1a1a2e
- Text: #e0e0e0
- Accent buttons: various
Maze colors:
- Walls: #1a1a2e (same as panel bg)
- Passages: #e8e8f0
- Start: #22c55e (green)
- End: #ef4444 (red)
- Explored: #60a5fa (blue, semi-transparent feel)
- Solution path: #f59e0b (amber/gold)
- Current generation cell: #a78bfa (purple)
Let me write it all now. I'll include proper comments.
For the canvas, I want to handle the case where the maze is fully walled (before generation starts or after init). The canvas should show as a solid block of wall color.
In `draw()`:
1. Fill canvas with wall color
2. For each visited cell:
a. Fill with passage color
b. Draw existing walls
3. Draw start/end markers
4. If solving/solved: draw explored and path overlays
5. If generating: highlight current cell
Now let me write the complete code. It's going to be significant but everything in one file.
Let me also consider: for the "Solve with A*" and "Solve with BFS" buttons, they should be disabled while an animation is running. Let me add button state management.
And for the speed slider, I'll use ms delay. Range: 1-50ms. Default: 10ms. Label: "Speed: Fast ... Slow" or just "Animation Speed".
The slider value represents delay between steps. Lower = faster animation. I'll map slider min to 1ms (fastest) and max to 50ms (slowest). Default at 5ms or 10ms.
OK here's the complete code. I'm going to write it all now.
I realize this is going to be quite long. Let me structure it well.
One thing about the generation animation: `generationStep()` should return `true` when generation is complete. The step function:
1. If stack is empty, return true (done)
2. Peek at top of stack
3. Get unvisited neighbors of current cell
4. If any:
a. Pick random neighbor
b. Remove walls between current and neighbor
c. Mark neighbor as visited
d. Push neighbor onto stack
e. Update genCurrent to neighbor
5. If none:
a. Pop from stack
b. If stack not empty, update genCurrent to new top
The function returns true only when the stack is empty and nothing more can be done.
Wait, the recursive backtracker terminates when the stack is empty. The first cell is pushed at the beginning. We pop when backtracking. When we backtrack all the way and pop the first cell, the stack is empty and we're done. All cells have been visited.
So the step function:
```
function generationStep() {
if (genStack.length === 0) return true; // done
const current = genStack[genStack.length - 1];
genCurrent = current;
const neighbors = getUnvisitedNeighbors(current.r, current.c);
if (neighbors.length > 0) {
const next = neighbors[Math.floor(Math.random() * neighbors.length)];
// Remove walls
maze[current.r][current.c][next.wall] = false;
maze[next.r][next.c][next.oppositeWall] = false;
// Mark visited
maze[next.r][next.c].visited = true;
// Push
genStack.push({r: next.r, c: next.c});
genCurrent = {r: next.r, c: next.c};
} else {
genStack.pop();
if (genStack.length > 0) {
const top = genStack[genStack.length - 1];
genCurrent = {r: top.r, c: top.c};
}
}
return false; // not done yet
}
```
This looks right.
For the solving animation, I need to step through the visited array:
```
function solvingStep() {
if (solveStepIndex >= solveResult.visited.length) {
animationState = 'solved';
return true; // done
}
solveStepIndex++;
return false;
}
```
And when transitioning to 'solved', the draw function will show all visited cells and the solution path.
Let me now finalize and write the complete HTML file. I'll aim for a polished, well-commented implementation.
One more consideration: the `initMaze` function should clear any existing solve result and reset the state. Let me handle this properly.
OK here we go for real:
I think I'll also add some nice CSS transitions and hover effects for the buttons.
Let me also add a small "Stats" display showing:
- Cells visited during solve
- Path length
- Algorithm used
This gives the user some interesting information.
Alright, I'm going to write the complete code now. No more planning!
For the canvas, I realize I should also consider high-DPI displays. But for simplicity, I'll skip that. The canvas will be 500x500 CSS pixels.
Let me also make the maze slightly smaller to fit better on smaller screens. Maybe 21x21 at 20px = 420px. Or 25x25 at 18px = 450px. Let me go with 25x25 at 20px = 500px but make it fit in a container that can scroll if needed.
Actually, 500px should be fine for most screens. Desktop is typically 1200px+ wide. Mobile might need scrolling but that's OK for this demo.
Let me finalize with:
- 25 rows, 25 columns
- 20px cell size
- 500x500 canvas
- Dark theme
- Recursive backtracker generation (animated)
- A* and BFS solvers (animated)
- Speed control
- Stats display
Here's the complete code:
Actually, let me also add the recursive backtracker animation as optional. By default, let me generate the maze instantly (which is faster), and then focus the animation on the solving. But the user might enjoy the generation animation too.
For the best UX, let me:
1. On page load: generate a maze instantly and display it
2. "Generate New Maze" button: animate the generation
3. "Solve A*" / "Solve BFS": animate the solving
Actually, for the initial load, let me also animate the generation. It's a nice intro. But maybe faster.
Hmm, let me just make generation always animated. The speed slider controls all animation speed. Default speed is pretty fast so generation completes quickly.
Or, I'll add a checkbox "Animate Generation" that defaults to checked. Unchecking it generates instantly.
For simplicity, let me just always animate both generation and solving. The speed control adjusts how fast the animation runs. Default speed is fairly fast.
OK WRITING THE CODE NOW.
Let me also think about how the "solving" animation transitions to "solved":
During solving:
- `solveStepIndex` increments each step
- Draw visited cells up to `solveStepIndex`
- When `solveStepIndex >= solveResult.visited.length`, transition to 'solved'
In 'solved' state:
- Draw all visited cells
- Draw solution path
- Show stats
The user can then click "Reset" to clear the solution and go back to just the maze. Or "Generate" to create a new maze.
For "Reset Solution", I'll clear the solve result and set state to 'idle'.
Here's my button layout:
- [Generate New Maze] [Solve A*] [Solve BFS] [Reset Solution]
- Speed: [====slider====]
- Stats: ...
Let me write it now. For real this time. No more planning.
I think the implementation will be around 400-500 lines. Let me write it cleanly.
Alright, here we go. Writing the complete index.html:→ write
/workspace/index.html (16375 bytes)toolResult
Successfully wrote 16375 bytes to /workspace/index.html
assistant
thinking
The file was written successfully. Let me verify it by checking a few things: 1. The file is complete and syntactically valid 2. All features are present Let me also check if there are any issues I should fix. Let me re-read the key parts to ensure correctness. Actually, let me just verify the file exists and looks correct with a quick check.
→ bash
{"command":"wc -l /workspace/index.html && head -5 /workspace/index.html && tail -5 /workspace/index.html"}toolResult
562 /workspace/index.html <!DOCTYPE html> <html lang="en"> <head> <meta charset="UTF-8"> <meta name="viewport" content="width=device-width, initial-scale=1.0"> updateButtons(); startGeneration(); // auto-generate first maze on load </script> </body> </html>
assistant
thinking
The file is 562 lines and looks complete. Let me verify the HTML structure is correct by checking that the script section closes properly and everything is well-formed. The file looks good.
Let me also do a quick sanity check - I should ensure the maze generation and solving work correctly. Let me re-read some key parts of the code to make sure there are no bugs.
Actually, let me just verify the file parses correctly by checking for common issues. I'll look at a few key sections.
One concern: in the `startSolve` function, I run the solver synchronously before starting the animation. The solver computes `solveVisited` and `solvePath` arrays, then the animation steps through `solveVisited`. This should work fine.
Another concern: when the user clicks "Generate" during an animation, I stop the animation and start a new one. The `updateButtons` function disables buttons during animation, so this shouldn't be an issue unless the user clicks very fast. But I also call `stopAnimation()` at the start of `startGeneration()` and `startSolve()`, which handles this gracefully.
Let me also verify that the maze generation animation doesn't have any issues. The `generationStep` function should work correctly:
1. Pop the stack when no unvisited neighbors
2. Push when there are unvisited neighbors
3. Return true when stack is empty
This is the standard iterative recursive-backtracker algorithm. It should work.
One potential issue: when the generation is complete and the stack is empty, `genCurrent` is set to `null`. In the `draw` function, I check `if (animState === 'generating' && genCurrent)` before drawing the current cell highlight. This is correct.
Another thing: the passableNeighbors function checks `!maze[r][c][d.wall]`. This correctly checks if there's NO wall between current and neighbor. During generation, when we remove a wall, we set it to false. So passableNeighbors returns cells where the wall has been removed.
Alright, everything looks correct. Let me also verify the A* algorithm:
1. Open set with start node
2. While open set not empty:
a. Sort by f (lowest first), tiebreak by g (highest first)
b. Pop best node
c. If goal, done
d. Add to closed set
e. For each passable neighbor:
- If in closed, skip
- Compute tentative g
- If not in gScore or tentative g is better, update and add to open set
This is correct A*.
For BFS:
1. Queue with start
2. While queue not empty:
a. Dequeue
b. If goal, done
c. For each passable neighbor:
- If not visited, mark and enqueue
This is correct BFS.
The only concern I have is that for the animation, the entire solver runs first (computing all visited cells and the path), and then the animation replays the visited cells one by one. This means there's a brief pause when clicking "Solve" before the animation starts (the solver runs synchronously). For a 25x25 maze, A* and BFS should complete in a few milliseconds, so this pause should be imperceptible.
Everything looks good. The file is complete and should work correctly.
Actually, wait - I want to make sure the `Reset` button works correctly. Let me trace through:
1. User solves with A* → animState = 'solved'
2. User clicks Reset → `resetSolution()` is called
3. It checks `if (animState === 'generating' || animState === 'solving') return;` - 'solved' passes this check
4. Stops animation, sets state to 'idle', clears solve data, redraws
This should work correctly. The maze data is preserved, only the solution visualization is cleared.
One edge case: what if the user clicks Reset while the maze is partially generated? The check `animState === 'generating'` would prevent reset, which is correct.
What about clicking Generate while a solver animation is running? The button is disabled during animation, so this shouldn't happen. But even if it did somehow, `startGeneration()` calls `stopAnimation()` first, which is clean.
I'm satisfied the implementation is correct. Let me tell the user what was built.The file is complete — 562 lines, fully self-contained `index.html`. Here's what was built: **Maze Generation** - **Recursive backtracker** algorithm (iterative stack-based), animated step by step so you can watch the maze carve itself - Purple highlight follows the "carving head" as it advances and backtracks - First maze auto-generates on load **Solvers (both animated)** - **A\*** — priority-queue guided by Manhattan-distance heuristic; tie-breaks on deeper `g` scores to bias toward the goal - **BFS** — classic breadth-first search **Animation** - Both solvers paint explored cells in blue one-by-one, then draw the final solution path in amber - Speed slider (1–60 ms/step) controls all animations — generation and solving — in real time **Visual design** - Dark theme with subtle glows on buttons - Start cell (green + **S**) top-left, end cell (red + **E**) bottom-right - Stats row shows algorithm name, cells explored, and path length after solving - Reset clears only the solution overlay, keeping the maze intact
TAKE IT TO CODE
A single self-contained HTML file — copy it and open in any browser, or reuse the prompt with your own pi-agent run.
RUN
modeldeepseek-v4-pro
vendorDeepSeek
harnesspi-agent
generated2026-07-10
EVALUATION
★★★★★ 3/5 working
Maze generates and animates via recursive backtracker; no solving path/explored cells visible in any panel, only carving.
Vision grade · anthropic/claude-sonnet-5
MEASUREMENTS
Raw readings from the capture, not a verdict — the grade above is the only judgement. Percentages are how much of the screen changed; the measure under-reports sparse motion on a dark background.
idle motion0.4%
on click5.2%
on drag10.7%
on wheel3.5%
on enter + space16.6%
on arrow keys16.2%
on w/a/s/d0.0%
frame spread85.9 / 255
console errors0
js errors none
METRICS
runtime348.2s
tokens in16k
tokens out16k
cached17k
cost / run$0.0208