oneshotlm
Compare all models on this prompt →

Maze generator & solver · seed-1.6-flash

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 · 10 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
Got it, let's tackle this problem. The user wants a single-page web app with a random maze generated using the recursive-backtracker algorithm and an animation of a solver (A-star or BFS) finding the path. 

First, I need to structure the HTML file. It should have a canvas element where the maze is drawn and the path is animated. The CSS will handle the styling, and the JavaScript will handle the maze generation and pathfinding.

Starting with the HTML structure. The canvas needs to be sized appropriately. Maybe set a width and height, and use CSS to make it responsive, but for simplicity, fixed dimensions might work. The body will contain the canvas and possibly some controls, but the user didn't mention controls, so maybe just the canvas.

Next, the recursive-backtracker algorithm. This is a maze generation algorithm that works by carving out paths from a starting point, randomly choosing unvisited neighbors, and backtracking when there are no unvisited neighbors. To implement this, I'll need a grid representation. Let's use a 2D array where each cell is either a wall or a path. The algorithm steps are: choose a starting cell, mark it as visited, while there are unvisited cells, pick a random unvisited neighbor, carve a path between the current cell and the neighbor, mark the neighbor as visited, and set it as the current cell. If there are no unvisited neighbors, backtrack to the previous cell.

For the canvas drawing, each cell can be a square. Let's define a cell size, say 20 pixels. The canvas width and height will be based on the number of rows and columns. Let's choose a grid size, maybe 20x20, so the canvas is 400x400. Wait, 20x20 cells with 20px each would be 400x400. That's manageable.

Then, the pathfinding algorithm. A-star is a good choice because it's efficient and can be animated step by step. A-star uses a priority queue where each node's priority is the cost to reach it plus a heuristic (Manhattan distance to the target). BFS is simpler but might explore more nodes. Let's go with A-star for better performance, especially if the maze is larger.

The animation part: we need to draw the maze, then animate the solver exploring the grid, marking visited cells, and finding the path. We'll use requestAnimationFrame to update the display at regular intervals. Each frame, we'll process the next step of the algorithm, redraw the canvas, and stop when the end is found.

Let's outline the steps in code:

1. HTML structure with canvas.
2. CSS to style the canvas (border, center it).
3. JavaScript:
   a. Get the canvas context.
   b. Define grid dimensions, cell size, start and end points.
   c. Generate the maze using recursive-backtracker.
   d. Implement A-star algorithm to find the path.
   e. Animate the pathfinding by updating the canvas each frame.

Now, let's think about the maze generation. The grid will be a 2D array of cells, each with walls (top, right, bottom, left). Initially, all walls are present. When carving a path, we remove the wall between the current cell and the neighbor.

For the recursive-backtracker, we can use a stack to keep track of the current path. Start with the first cell, push it onto the stack. While the stack is not empty, pop a cell, mark it as visited, check its unvisited neighbors. If there are any, pick one at random, remove the wall between them, push the current cell back onto the stack, and push the neighbor onto the stack. Repeat until the stack is empty.

Wait, actually, the standard recursive-backtracker uses a stack. Let's implement it iteratively to avoid recursion depth issues. So:

- Initialize grid with all walls.
- Create a stack and push the starting cell (0,0).
- Mark (0,0) as visited.
- While stack is not empty:
  - Current cell = stack[stack.length - 1]
  - Get all unvisited neighbors of current cell.
  - If there are unvisited neighbors:
    - Pick one at random.
    - Remove the wall between current cell and neighbor.
    - Mark neighbor as visited.
    - Push neighbor onto stack.
  - Else:
    - Pop current cell from stack.

That should generate a perfect maze (no loops, all cells connected).

Next, the A-star algorithm. The nodes will be the grid cells. Each node has a position (x,y), a g-cost (distance from start), h-cost (Manhattan distance to end), and f-cost (g + h). We'll use a priority queue (open set) and a closed set. The steps are:

- Start with the start node (0,0). Add it to the open set.
- While open set is not empty:
  - Get the node with the lowest f-cost (current node).
  - If current node is the end node, reconstruct the path.
  - Remove current node from open set, add to closed set.
  - For each neighbor of current node (up, down, left, right) that is not a wall and not in closed set:
    - Calculate tentative g-cost.
    - If neighbor is not in open set or tentative g-cost is lower than existing g-cost:
      - Set neighbor's parent to current node.
      - Update g-cost, h-cost, f-cost.
      - If neighbor not in open set, add to open set.
- If open set is empty, no path exists (but with a perfect maze, there should be a path).

For animation, we need to step through the A-star algorithm and draw each step. So instead of running the algorithm all at once, we'll run it in chunks, updating the canvas each time. We can use a variable to track the current step, and use requestAnimationFrame to call a function that processes the next step, draws the maze with visited cells, the path, and then stops when the end is found.

Now, let's think about the drawing functions. The maze is drawn by iterating over each cell and drawing the walls that are still present. The start and end points can be marked by removing their top and left walls (or bottom and right, depending on how we set it). The visited cells in the A-star algorithm can be drawn with a different color, and the path can be drawn by tracing back from the end node to the start.

Putting it all together:

- The HTML file will have a canvas element with id "mazeCanvas".
- The CSS will center the canvas and add a border.
- The JavaScript will:
  - Get the canvas context.
  - Set up the grid, cell size, start (0,0) and end (gridSize-1, gridSize-1) points.
  - Generate the maze using recursive-backtracker.
  - Implement A-star algorithm.
  - Animate the pathfinding by processing one step of A-star per frame.

Potential issues to consider:

- The canvas size: need to make sure it's large enough to display the maze. If the grid is 20x20 and cell size is 20px, the canvas is 400x400. That's manageable.
- Performance: animating step by step should be smooth enough for a small maze.
- Path reconstruction: once the end node is found, we need to backtrack from the end to the start using the parent pointers to get the path.

Let's draft the code.

First, the HTML structure:

<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Maze Solver</title>
    <style>
        /* CSS styles here */
    </style>
</head>
<body>
    <canvas id="mazeCanvas"></canvas>
    <script>
        /* JavaScript code here */
    </script>
</body>
</html>

CSS: center the canvas, add a border, set background color.

canvas {
    border: 2px solid black;
    margin: 20px auto;
    display: block;
    background-color: #fff;
}

JavaScript:

- Variables: canvas, ctx, gridSize, cellSize, maze (2D array), start, end, openSet, closedSet, path, animationFrameId.

Maze generation function:

function generateMaze() {
    // Initialize grid with walls
    maze = new Array(gridSize);
    for (let x = 0; x < gridSize; x++) {
        maze[x] = new Array(gridSize);
        for (let y = 0; y < gridSize; y++) {
            maze[x][y] = {
                walls: { top: true, right: true, bottom: true, left: true },
                visited: false
            };
        }
    }
    // Recursive backtracking
    const stack = [];
    const start = { x: 0, y: 0 };
    stack.push(start);
    maze[start.x][start.y].visited = true;
    const directions = [
        { dx: 0, dy: -1, wall: 'top' },    // Up
        { dx: 1, dy: 0, wall: 'right' },   // Right
        { dx: 0, dy: 1, wall: 'bottom' },  // Down
        { dx: -1, dy: 0, wall: 'left' }    // Left
    ];
    while (stack.length > 0) {
        const current = stack[stack.length - 1];
        // Get unvisited neighbors
        const neighbors = [];
        directions.forEach(dir => {
            const nx = current.x + dir.dx;
            const ny = current.y + dir.dy;
            if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize && !maze[nx][ny].visited) {
                neighbors.push({ ...dir, x: nx, y: ny });
            }
        });
        if (neighbors.length > 0) {
            // Pick random neighbor
            const rand = Math.floor(Math.random() * neighbors.length);
            const neighbor = neighbors[rand];
            // Remove wall between current and neighbor
            maze[current.x][current.y].walls[neighbor.wall] = false;
            const oppositeWall = {
                top: 'bottom',
                right: 'left',
                bottom: 'top',
                left: 'right'
            }[neighbor.wall];
            maze[neighbor.x][neighbor.y].walls[oppositeWall] = false;
            // Mark neighbor as visited and push to stack
            maze[neighbor.x][neighbor.y].visited = true;
            stack.push(neighbor);
        } else {
            // Backtrack
            stack.pop();
        }
    }
    // Set start and end points (remove walls)
    maze[0][0].walls.top = false;
    maze[0][0].walls.left = false;
    maze[gridSize-1][gridSize-1].walls.bottom = false;
    maze[gridSize-1][gridSize-1].walls.right = false;
}

A-star algorithm:

function aStar() {
    openSet = new PriorityQueue((a, b) => a.f - b.f);
    closedSet = new Set();
    path = [];

    openSet.enqueue(start, 0);

    while (!openSet.isEmpty()) {
        const current = openSet.dequeue();

        if (current.x === end.x && current.y === end.y) {
            // Reconstruct path
            let temp = current;
            while (temp) {
                path.push(temp);
                temp = temp.parent;
            }
            path.reverse();
            return;
        }

        closedSet.add(`${current.x},${current.y}`);

        const neighbors = [];
        directions.forEach(dir => {
            const nx = current.x + dir.dx;
            const ny = current.y + dir.dy;
            if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                // Check if the wall between current and neighbor is not present
                const wall = getWall(current, dir);
                if (!wall) {
                    neighbors.push({ x: nx, y: ny });
                }
            }
        });

        neighbors.forEach(neighbor => {
            if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

            const gCost = current.g + 1;

            if (!openSet.contains(neighbor) || gCost < neighbor.g) {
                neighbor.g = gCost;
                neighbor.h = manhattan(neighbor, end);
                neighbor.f = neighbor.g + neighbor.h;
                neighbor.parent = current;

                if (!openSet.contains(neighbor)) {
                    openSet.enqueue(neighbor, neighbor.f);
                } else {
                    openSet.updatePriority(neighbor, neighbor.f);
                }
            }
        });
    }
}

function getWall(current, dir) {
    if (dir.dx === 0 && dir.dy === -1) return current.walls.top;
    if (dir.dx === 1 && dir.dy === 0) return current.walls.right;
    if (dir.dx === 0 && dir.dy === 1) return current.walls.bottom;
    if (dir.dx === -1 && dir.dy === 0) return current.walls.left;
}

function manhattan(a, b) {
    return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
}

For the priority queue, since JavaScript doesn't have a built-in one, we can implement a simple version or use an array and sort it each time, though that's not the most efficient but works for small mazes.

Alternatively, use a library, but since we can't use external resources, we'll implement a basic priority queue.

class PriorityQueue {
    constructor(comparator) {
        this.heap = [];
        this.comparator = comparator || ((a, b) => a - b);
    }

    enqueue(element, priority) {
        this.heap.push({ element, priority });
        this.bubbleUp(this.heap.length - 1);
    }

    dequeue() {
        const min = this.heap[0];
        const end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }
        return min.element;
    }

    isEmpty() {
        return this.heap.length === 0;
    }

    contains(element) {
        return this.heap.some(item => item.element === element);
    }

    updatePriority(element, newPriority) {
        for (let i = 0; i < this.heap.length; i++) {
            if (this.heap[i].element === element) {
                this.heap[i].priority = newPriority;
                this.bubbleUp(i);
                this.sinkDown(i);
                break;
            }
        }
    }

    bubbleUp(index) {
        const element = this.heap[index];
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            const parent = this.heap[parentIndex];
            if (this.comparator(element.priority, parent.priority) >= 0) break;
            this.heap[index] = parent;
            index = parentIndex;
        }
        this.heap[index] = element;
    }

    sinkDown(index) {
        const length = this.heap.length;
        const element = this.heap[index];
        while (true) {
            let leftChildIndex = 2 * index + 1;
            let rightChildIndex = 2 * index + 2;
            let swapIndex = null;
            let leftChild, rightChild;

            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (this.comparator(leftChild.priority, element.priority) < 0) {
                    swapIndex = leftChildIndex;
                }
            }

            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if (
                    (swapIndex === null && this.comparator(rightChild.priority, element.priority) < 0) ||
                    (swapIndex !== null && this.comparator(rightChild.priority, leftChild.priority) < 0)
                ) {
                    swapIndex = rightChildIndex;
                }
            }

            if (swapIndex === null) break;
            this.heap[index] = this.heap[swapIndex];
            index = swapIndex;
        }
        this.heap[index] = element;
    }
}

Animation function:

let animationStep = 0;
function animate() {
    if (animationStep < openSet.size) {
        // Process next step
        const current = openSet.elements[animationStep];
        closedSet.add(`${current.x},${current.y}`);
        animationStep++;
    } else if (animationStep === openSet.size) {
        // Path found, draw it
        animationStep++;
    } else {
        // Animation complete
        cancelAnimationFrame(animationFrameId);
        return;
    }
    drawMaze();
    animationFrameId = requestAnimationFrame(animate);
}

function drawMaze() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    for (let x = 0; x < gridSize; x++) {
        for (let y = 0; y < gridSize; y++) {
            const cell = maze[x][y];
            const x1 = x * cellSize;
            const y1 = y * cellSize;
            const x2 = x1 + cellSize;
            const y2 = y1 + cellSize;

            // Draw walls
            if (cell.walls.top) ctx.strokeRect(x1, y1, cellSize, cellSize);
            if (cell.walls.right) ctx.strokeRect(x2 - 1, y1, 1, cellSize);
            if (cell.walls.bottom) ctx.strokeRect(x1, y2 - 1, cellSize, 1);
            if (cell.walls.left) ctx.strokeRect(x1, y1, 1, cellSize);

            // Draw visited cells (closed set)
            if (closedSet.has(`${x},${y}`)) {
                ctx.fillStyle = '#ccc';
                ctx.fillRect(x1 + 2, y1 + 2, cellSize - 4, cellSize - 4);
            }

            // Draw path
            if (path.includes({ x, y })) {
                ctx.fillStyle = '#f00';
                ctx.beginPath();
                ctx.arc(x1 + cellSize/2, y1 + cellSize/2, cellSize/4, 0, Math.PI * 2);
                ctx.fill();
            }
        }
    }
}

Putting all together, the JavaScript will initialize the canvas, generate the maze, run A-star, and start the animation.

Testing the code: need to make sure that the maze is generated correctly, the A-star algorithm finds the path, and the animation steps through the process.

Potential adjustments: cell size might need to be adjusted for different grid sizes. The start and end points are set at (0,0) and (gridSize-1, gridSize-1), removing their walls. The visited cells are filled with a light gray, and the path is filled with red circles at each step.

Finally, the HTML file is written with all the CSS and JavaScript inline, no external resources.
write index.html (8476 bytes)
toolResult

Successfully wrote 8476 bytes to index.html

assistant
thinking
Got it, let's see. The user wants a single-page web app that generates a maze with the recursive-backtracker algorithm and animates an A* or BFS solver. The assistant already wrote the index.html file using the write tool, and the tool confirmed it was successful. 

First, I need to check if the generated code meets the requirements. The code includes a recursive-backtracker maze generator, which is correct. The A* algorithm is implemented, and there's an animation loop. The canvas is set up, and the maze is drawn with walls. The solver's path is shown with red dots, and the closed set is filled gray. 

Wait, does the animation step through the A* algorithm? Let me look at the animate function. It checks if animationStep is less than openSet.length, then adds the current node to closedSet and increments the step. Then draws the maze. That should animate the expansion of the open set. 

Is there any issue? The path is stored, but in the draw function, it checks if the cell is in the path array. However, the path is an array of nodes with x and y, so when checking path.includes({x,y}), that might not work because objects are compared by reference. Oh, right, because {x,y} creates a new object each time, so includes won't find it. That's a bug. 

Wait, in the aStar function, path is built by pushing nodes, which are objects. Then in drawMaze, path.includes({x,y}) will always be false. So the red dots won't show. That's a problem. How to fix that? Maybe instead of storing the path as an array of objects, store it as an array of strings like "x,y" and then check if the cell's coordinates are in that array. 

Let me check the code. In aStar, when current is the end node, it does:

let temp = current;
while (temp) {
    path.push(temp);
    temp = temp.parent;
}
path.reverse();

So path is an array of node objects. Then in drawMaze:

if (path.includes({ x, y })) { ... }

That's incorrect. So the red dots won't appear. Need to fix that. Maybe change the path to store the coordinates as strings. For example, when pushing to path, push `${temp.x},${temp.y}`, then in drawMaze, check if `${x},${y}` is in path. 

Also, the animation might not be smooth. The current animate function increments the step each frame, but maybe it should process one step per frame, which is what it's doing. But the aStar function runs synchronously, so the animation might start immediately without waiting. Wait, in the code, aStar is called right after generateMaze, which blocks the main thread, so the animation might not start until aStar is done. That would make the animation jump. Oh right, because JavaScript is single-threaded. So the aStar function, which is O(n) for the maze size, might take some time, and during that, the UI is blocked. Then when aStar finishes, the animation starts, which would show the entire path at once. That's not good. 

So to fix that, the A* algorithm should be run incrementally, step by step, so that each step is processed in a separate animation frame. Currently, the aStar function runs all at once, so the path is computed immediately. Then the animation just steps through the closed set. But the path isn't built incrementally. 

So the problem is that the aStar function is synchronous, blocking the UI. To animate the A* search, we need to split the algorithm into steps that can be processed one by one, allowing the browser to update the UI between steps. 

How to fix that? We can use a generator function or a recursive function with setTimeout to process one step at a time. Let's adjust the aStar function to run in steps. 

Also, the initial code might not handle the start and end walls correctly. The generateMaze function removes the start and end walls, which is correct. 

Another issue: the cellSize and gridSize are both 20, which makes a 20x20 maze of 20x20 pixels, which is too small. The canvas would be 400x400, which is manageable, but maybe the user wants a larger maze. But the code uses gridSize=20, which is arbitrary. 

Let me list the necessary fixes:

1. The path is stored as objects, so checking inclusion with {x,y} doesn't work. Change path to store "x,y" strings.

2. The A* algorithm runs synchronously, blocking the UI. Need to split it into steps so that each step is processed in an animation frame.

3. The animation might not show the path correctly. Let's adjust the draw function to show the path as a line instead of dots, or correct the path storage.

Let's tackle the first issue. In the aStar function, when building the path, push `${temp.x},${temp.y}` instead of temp. Then in drawMaze, check if `${x},${y}` is in path. That would make the red dots appear.

For the second issue, the aStar function is called once, which computes the entire path. To animate the search, we need to process each step of the algorithm. So instead of running aStar() all at once, we can use a recursive function that processes one neighbor at a time, then calls requestAnimationFrame to continue.

Let's rewrite the aStar function to be incremental. Here's how:

- Instead of a while loop, use a recursive function that processes the next node in the open set.

- In each step, select the node with the lowest f cost, add it to the closed set, process its neighbors, and then schedule the next step.

This way, the algorithm runs step by step, allowing the UI to update between steps.

Also, the openSet is sorted each time, which is necessary for A*. But sorting in each step might be computationally heavy, but for a small maze (20x20), it's manageable.

Let's adjust the code:

In the animate function, instead of processing all steps at once, we can have a step counter that increments each frame, and in each step, process the next part of the A* algorithm.

Alternatively, use a generator function that yields each step, and then in the animation loop, call the generator to get the next step.

Let's modify the aStar function to be a generator. Here's how:

function* aStarGenerator() {
    openSet = [];
    closedSet = new Set();
    path = [];

    const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };
    openSet.push(startNode);

    while (openSet.length > 0) {
        openSet.sort((a, b) => a.f - b.f);
        const current = openSet.shift();

        if (current.x === gridSize-1 && current.y === gridSize-1) {
            let temp = current;
            while (temp) {
                path.push(`${temp.x},${temp.y}`);
                temp = temp.parent;
            }
            path.reverse();
            return;
        }

        closedSet.add(`${current.x},${current.y}`);

        const neighbors = [];
        directions.forEach(dir => {
            const nx = current.x + dir.dx;
            const ny = current.y + dir.dy;
            if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                const wall = getWall(current, dir);
                if (!wall) neighbors.push({ x: nx, y: ny });
            }
        });

        neighbors.forEach(neighbor => {
            if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

            const gCost = current.g + 1;
            const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});
            const fCost = gCost + hCost;

            const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);
            if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {
                neighbor.g = gCost;
                neighbor.h = hCost;
                neighbor.f = fCost;
                neighbor.parent = current;
                if (!existingNeighbor) openSet.push(neighbor);
            }
        });

        yield; // Yield to the animation loop
    }
}

Then, in the main script, we can have a generator instance and call next() in the animation loop:

let aStarGen;

function startAStarAnimation() {
    aStarGen = aStarGenerator();
    animationStep = 0;
    animationFrameId = requestAnimationFrame(animateAStar);
}

function animateAStar() {
    if (!aStarGen) return;
    const result = aStarGen.next();
    if (result.done) {
        cancelAnimationFrame(animationFrameId);
        return;
    }
    drawMaze();
    animationFrameId = requestAnimationFrame(animateAStar);
}

Then, replace the initial aStar() call with startAStarAnimation().

Also, in the drawMaze function, change the path check to:

if (path.includes(`${x},${y}`)) { ... }

This would make the red dots appear.

Another thing: the closedSet is filled gray, which shows the visited nodes. The openSet is the nodes to be processed, so the animation would show the closedSet growing as the algorithm processes each node.

Additionally, the maze might be too small. Maybe set gridSize to 30 or 40 for better visibility, but the user can adjust it.

Let me check if these changes are necessary. The original code has the issues mentioned, so the generated index.html would have a maze but no path animation. The user wants the solver to animate finding the path, so the fixes are needed.

So, to correct the code, we need to:

1. Fix the path storage to use strings.

2. Make the A* algorithm run incrementally using a generator.

3. Adjust the animation loop to process each step of the A* algorithm.

Let's update the code accordingly.

The revised index.html would include these changes. Let's write the corrected code using the edit tool, since we need to modify the existing file.

The original code has the aStar function as a synchronous function. We need to replace that with a generator and adjust the animation loop.

Also, in the drawMaze function, the path check is incorrect. We need to change that.

So, the edits would be:

- In the aStar function, replace the synchronous code with a generator.

- In the main script, replace aStar() with startAStarAnimation().

- In the drawMaze function, change the path check to use the string representation.

Let's create the edit calls.

First, the aStar function:

Original code:

function aStar() {
    openSet = [];
    closedSet = new Set();
    path = [];

    const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };
    openSet.push(startNode);

    while (openSet.length > 0) {
        openSet.sort((a, b) => a.f - b.f); // Simple priority queue
        const current = openSet.shift();

        if (current.x === gridSize-1 && current.y === gridSize-1) {
            let temp = current;
            while (temp) {
                path.push(temp);
                temp = temp.parent;
            }
            path.reverse();
            return;
        }

        closedSet.add(`${current.x},${current.y}`);

        const neighbors = [];
        directions.forEach(dir => {
            const nx = current.x + dir.dx;
            const ny = current.y + dir.dy;
            if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                const wall = getWall(current, dir);
                if (!wall) neighbors.push({ x: nx, y: ny });
            }
        });

        neighbors.forEach(neighbor => {
            if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

            const gCost = current.g + 1;
            const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});
            const fCost = gCost + hCost;

            const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);
            if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {
                neighbor.g = gCost;
                neighbor.h = hCost;
                neighbor.f = fCost;
                neighbor.parent = current;
                if (!existingNeighbor) openSet.push(neighbor);
            }
        });
    }
}

Replaced with:

function* aStarGenerator() {
    openSet = [];
    closedSet = new Set();
    path = [];

    const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };
    openSet.push(startNode);

    while (openSet.length > 0) {
        openSet.sort((a, b) => a.f - b.f); // Simple priority queue
        const current = openSet.shift();

        if (current.x === gridSize-1 && current.y === gridSize-1) {
            let temp = current;
            while (temp) {
                path.push(`${temp.x},${temp.y}`);
                temp = temp.parent;
            }
            path.reverse();
            return;
        }

        closedSet.add(`${current.x},${current.y}`);

        const neighbors = [];
        directions.forEach(dir => {
            const nx = current.x + dir.dx;
            const ny = current.y + dir.dy;
            if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                const wall = getWall(current, dir);
                if (!wall) neighbors.push({ x: nx, y: ny });
            }
        });

        neighbors.forEach(neighbor => {
            if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

            const gCost = current.g + 1;
            const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});
            const fCost = gCost + hCost;

            const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);
            if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {
                neighbor.g = gCost;
                neighbor.h = hCost;
                neighbor.f = fCost;
                neighbor.parent = current;
                if (!existingNeighbor) openSet.push(neighbor);
            }
        });

        yield; // Yield to animation loop
    }
}

Then, add the startAStarAnimation and animateAStar functions:

function startAStarAnimation() {
    aStarGen = aStarGenerator();
    animationStep = 0;
    animationFrameId = requestAnimationFrame(animateAStar);
}

function animateAStar() {
    if (!aStarGen) return;
    const result = aStarGen.next();
    if (result.done) {
        cancelAnimationFrame(animationFrameId);
        return;
    }
    drawMaze();
    animationFrameId = requestAnimationFrame(animateAStar);
}

In the main script, replace:

aStar();
animationStep = 0;
animationFrameId = requestAnimationFrame(animate);

With:

startAStarAnimation();

In the drawMaze function, change the path check from:

if (path.includes({ x, y })) {

To:

if (path.includes(`${x},${y}`)) {

These changes should fix the path display and the animation of the A* algorithm.

Now, let's create the edit calls for these changes.

First, the aStar function replacement. The old text is the original aStar function, and the new text is the generator function.

Second, adding the startAStarAnimation and animateAStar functions.

Third, modifying the main script to call startAStarAnimation instead of aStar().

Fourth, modifying the path check in drawMaze.

Each of these is a separate edit, but we can merge them into a single edit call if they are in the same file and non-overlapping.

The original file has the aStar function, then the main script where aStar() is called, and the drawMaze function.

So, the edits would be:

1. In the script tag, replace the aStar function with the generator.

2. Add the startAStarAnimation and animateAStar functions after the aStar function.

3. In the main script, replace aStar(); with startAStarAnimation();.

4. In the drawMaze function, replace path.includes({ x, y }) with path.includes(`${x},${y}`).

Let's structure the edits.

First edit: Replace the aStar function.

Old text:
        function aStar() {
            openSet = [];
            closedSet = new Set();
            path = [];

            const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };
            openSet.push(startNode);

            while (openSet.length > 0) {
                openSet.sort((a, b) => a.f - b.f); // Simple priority queue
                const current = openSet.shift();

                if (current.x === gridSize-1 && current.y === gridSize-1) {
                    let temp = current;
                    while (temp) {
                        path.push(temp);
                        temp = temp.parent;
                    }
                    path.reverse();
                    return;
                }

                closedSet.add(`${current.x},${current.y}`);

                const neighbors = [];
                directions.forEach(dir => {
                    const nx = current.x + dir.dx;
                    const ny = current.y + dir.dy;
                    if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                        const wall = getWall(current, dir);
                        if (!wall) neighbors.push({ x: nx, y: ny });
                    }
                });

                neighbors.forEach(neighbor => {
                    if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

                    const gCost = current.g + 1;
                    const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});
                    const fCost = gCost + hCost;

                    const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);
                    if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {
                        neighbor.g = gCost;
                        neighbor.h = hCost;
                        neighbor.f = fCost;
                        neighbor.parent = current;
                        if (!existingNeighbor) openSet.push(neighbor);
                    }
                });
            }
        }

New text:
        function* aStarGenerator() {
            openSet = [];
            closedSet = new Set();
            path = [];

            const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };
            openSet.push(startNode);

            while (openSet.length > 0) {
                openSet.sort((a, b) => a.f - b.f); // Simple priority queue
                const current = openSet.shift();

                if (current.x === gridSize-1 && current.y === gridSize-1) {
                    let temp = current;
                    while (temp) {
                        path.push(`${temp.x},${temp.y}`);
                        temp = temp.parent;
                    }
                    path.reverse();
                    return;
                }

                closedSet.add(`${current.x},${current.y}`);

                const neighbors = [];
                directions.forEach(dir => {
                    const nx = current.x + dir.dx;
                    const ny = current.y + dir.dy;
                    if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {
                        const wall = getWall(current, dir);
                        if (!wall) neighbors.push({ x: nx, y: ny });
                    }
                });

                neighbors.forEach(neighbor => {
                    if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;

                    const gCost = current.g + 1;
                    const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});
                    const fCost = gCost + hCost;

                    const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);
                    if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {
                        neighbor.g = gCost;
                        neighbor.h = hCost;
                        neighbor.f = fCost;
                        neighbor.parent = current;
                        if (!existingNeighbor) openSet.push(neighbor);
                    }
                });

                yield; // Yield to animation loop
            }
        }

Second edit: Add startAStarAnimation and animateAStar functions after the aStar function.

Old text after aStar function:
        // Calculate Manhattan distance
        function manhattan(a, b) {
            return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
        }

New text:
        // Calculate Manhattan distance
        function manhattan(a, b) {
            return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
        }

        function startAStarAnimation() {
            aStarGen = aStarGenerator();
            animationStep = 0;
            animationFrameId = requestAnimationFrame(animateAStar);
        }

        function animateAStar() {
            if (!aStarGen) return;
            const result = aStarGen.next();
            if (result.done) {
                cancelAnimationFrame(animationFrameId);
                return;
            }
            drawMaze();
            animationFrameId = requestAnimationFrame(animateAStar);
        }

Third edit: Modify the main script to call startAStarAnimation.

Old text:
        // Start process
        generateMaze();
        aStar();
        animationStep = 0;
        animationFrameId = requestAnimationFrame(animate);

New text:
        // Start process
        generateMaze();
        startAStarAnimation();

Fourth edit: Modify the path check in drawMaze.

Old text:
                    if (path.includes({ x, y })) {
                        ctx.fillStyle = '#ff0000';
                        ctx.beginPath();
                        ctx.arc(x1 + cellSize/2, y1 + cellSize/2, cellSize/4, 0, Math.PI * 2);
                        ctx.fill();
                    }

New text:
                    if (path.includes(`${x},${y}`)) {
                        ctx.fillStyle = '#ff0000';
                        ctx.beginPath();
                        ctx.arc(x1 + cellSize/2, y1 + cellSize/2, cellSize/4, 0, Math.PI * 2);
                        ctx.fill();
                    }

These edits should address the issues in the original code. Now, we can create the edit calls for these changes.
edit {"path":"index.html","edits":[{"oldText":" function aStar() {\n openSet = [];\n closedSet = new Set();\n
toolResult

Successfully replaced 4 block(s) in index.html.

assistant
thinking
Got it, let's see. The user wants a single-page web app that generates a maze with the recursive-backtracker algorithm and animates an A* or BFS solver. I already wrote the initial index.html with the recursive backtracking and A* implementation, but the animation was too fast because the A* function ran all at once. 

First, I need to modify the A* function to be a generator so it can yield control to the animation loop step by step. That way, each frame of the animation shows a step of the A* algorithm. So I changed the aStar function to a generator function (aStarGenerator) and added yield statements after processing each node.

Next, the original code called aStar() and then started the animation, which would run the entire algorithm in one go. I need to separate the A* computation into steps. So I added startAStarAnimation() which initializes the generator and starts the animation loop. The animateAStar function then calls next() on the generator each frame.

Also, the path was stored as an array of objects, but in the drawMaze function, checking path.includes({x,y}) doesn't work because objects are compared by reference. So I changed the path to store strings like "x,y" and updated the includes check to use those strings.

Let me verify if these changes work. The maze is generated, the A* algorithm runs step by step, each frame showing the next node being processed. The closed set is visualized, and the path is drawn once the algorithm completes. That should create a smooth animation of the solver finding the path.

I think that covers the necessary adjustments. The user should now have a working animation where the A* algorithm progresses one step at a time, making the maze solving visible.
write index.html (8890 bytes)
toolResult

Successfully wrote 8890 bytes to index.html

assistant
thinking
Got it, let's see. The user wants a single-page web app that generates a maze using the recursive-backtracker algorithm and animates an A* or BFS solver. I already wrote the initial HTML file with the recursive backtracking and A* algorithm. Then I made some edits to convert A* into a generator for step-by-step animation, added an animation controller, and updated the draw function to show open and closed sets. 

Wait, let me check if all the requirements are met. The maze is generated with recursive backtracking, which is correct. The A* solver is animated step by step, which the generator function handles by yielding each step. The canvas is properly sized, and the CSS is inline. There are no external resources, so it's self-contained. 

Did I miss anything? Let me verify the code. The generateMaze function initializes the grid, uses a stack to carve paths, and removes the start and end walls. The aStarGenerator is a generator function that yields each step, so the animation loop can call next() each frame. The drawMaze function now shows open set cells as light blue, closed set as light gray, and the path as red. That makes the animation more visual. 

The start process now calls generateMaze and startAStarAnimation, which initializes the generator and starts the animation. The path is stored as strings like "x,y" for easy checking in the draw function. 

I think that covers everything. The code should work as intended: when the page loads, it generates a maze, then animates the A* algorithm solving it step by step, with visual feedback of the open and closed sets. No external dependencies, all in one HTML file. That should meet the user's request.
bash {"command":"ls -l index.html"}
toolResult

-rw-r--r--. 1 node node 8890 Aug 1 20:21 index.html

assistant
thinking
Got it, let's see. The user wants a single-page web app that generates a maze with the recursive-backtracker algorithm and animates an A-star or BFS solver. I've already written the initial code, made some edits to convert A* into a generator for step-by-step animation, added drawing of open and closed sets, and verified the file exists.

First, I need to check if all requirements are met. The maze is generated using recursive backtracking, which is correct. The A-star solver is animated step-by-step, which is done with the generator function. The canvas draws walls, and the path is shown in red. Open set cells are light blue, closed set are light gray. That should cover the animation part.

Wait, did I miss anything? The user mentioned BFS as an alternative, but I used A*. Maybe I should add a note or allow switching, but the question says "or", so A* is fine. The code is self-contained, no external resources. The file is index.html, which is correct.

Let me check the bash command result: the file exists with the right size. No errors. The edits made the A* function a generator, added the animation controller, and modified the path check. The drawMaze function now highlights open and closed sets, which improves the animation's clarity.

Is there anything missing? Maybe adjusting grid size or cell size for better visibility, but the user didn't specify. The code uses 20x20 grid, 20px cell size, which is reasonable. The animation step pauses at each yield, so it shows each step of the A* algorithm.

I think that's it. The code should work as intended. The final index.html is complete, with all necessary parts. No further edits are needed.

{ "name": "write", "parameters": { "path": "index.html", "content": "<!DOCTYPE html>\n<html lang=\"en\">\n<head>\n <meta charset=\"UTF-8\">\n <meta name=\"viewport\" content=\"width=device-width, initial-scale=1.0\">\n <title>Maze Solver</title>\n <style>\n body {\n display: flex;\n flex-direction: column;\n align-items: center;\n background-color: #f0f0f0;\n font-family: Arial, sans-serif;\n }\n #mazeCanvas {\n border: 2px solid #333;\n background-color: #fff;\n margin-top: 20px;\n }\n h1 {\n color: #333;\n }\n </style>\n</head>\n<body>\n <h1>Maze Solver (Recursive Backtracker + A*)</h1>\n <canvas id=\"mazeCanvas\"></canvas>\n <script>\n const canvas = document.getElementById('mazeCanvas');\n const ctx = canvas.getContext('2d');\n let gridSize = 20; // Number of cells per side\n let cellSize = 20; // Pixels per cell\n let maze = [];\n let openSet = [];\n let closedSet = new Set();\n let path = [];\n let animationStep = 0;\n let animationFrameId;\n let aStarGen;\n const directions = [\n { dx: 0, dy: -1, wall: 'top' }, // Up\n { dx: 1, dy: 0, wall: 'right' }, // Right\n { dx: 0, dy: 1, wall: 'bottom' }, // Down\n { dx: -1, dy: 0, wall: 'left' } // Left\n ];\n\n // Initialize canvas size\n canvas.width = gridSize * cellSize;\n canvas.height = gridSize * cellSize;\n\n // Generate maze using recursive backtracking algorithm\n function generateMaze() {\n maze = Array.from({ length: gridSize }, () => \n Array.from({ length: gridSize }, () => ({ walls: { top: true, right: true, bottom: true, left: true }, visited: false }))\n );\n\n const stack = [];\n const start = { x: 0, y: 0 };\n stack.push(start);\n maze[start.x][start.y].visited = true;\n\n while (stack.length > 0) {\n const current = stack[stack.length - 1];\n const neighbors = [];\n\n directions.forEach(dir => {\n const nx = current.x + dir.dx;\n const ny = current.y + dir.dy;\n if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize && !maze[nx][ny].visited) {\n neighbors.push({ ...dir, x: nx, y: ny });\n }\n });\n\n if (neighbors.length > 0) {\n const rand = Math.floor(Math.random() * neighbors.length);\n const neighbor = neighbors[rand];\n maze[current.x][current.y].walls[neighbor.wall] = false;\n const oppositeWall = {\n top: 'bottom', right: 'left', bottom: 'top', left: 'right'\n }[neighbor.wall];\n maze[neighbor.x][neighbor.y].walls[oppositeWall] = false;\n maze[neighbor.x][neighbor.y].visited = true;\n stack.push(neighbor);\n } else {\n stack.pop();\n }\n }\n\n // Remove start and end walls\n maze[0][0].walls.top = maze[0][0].walls.left = false;\n maze[gridSize-1][gridSize-1].walls.bottom = maze[gridSize-1][gridSize-1].walls.right = false;\n }\n\n // A* algorithm generator (step-by-step)\n function* aStarGenerator() {\n openSet = [];\n closedSet = new Set();\n path = [];\n\n const startNode = { x: 0, y: 0, g: 0, h: manhattan({x:0,y:0}, {x:gridSize-1,y:gridSize-1}), f: 0, parent: null };\n openSet.push(startNode);\n\n while (openSet.length > 0) {\n openSet.sort((a, b) => a.f - b.f); // Simple priority queue\n const current = openSet.shift();\n\n if (current.x === gridSize-1 && current.y === gridSize-1) {\n let temp = current;\n while (temp) {\n path.push(`${temp.x},${temp.y}`);\n temp = temp.parent;\n }\n path.reverse();\n return;\n }\n\n closedSet.add(`${current.x},${current.y}`);\n\n const neighbors = [];\n directions.forEach(dir => {\n const nx = current.x + dir.dx;\n const ny = current.y + dir.dy;\n if (nx >= 0 && nx < gridSize && ny >= 0 && ny < gridSize) {\n const wall = getWall(current, dir);\n if (!wall) neighbors.push({ x: nx, y: ny });\n }\n });\n\n neighbors.forEach(neighbor => {\n if (closedSet.has(`${neighbor.x},${neighbor.y}`)) return;\n\n const gCost = current.g + 1;\n const hCost = manhattan(neighbor, {x:gridSize-1,y:gridSize-1});\n const fCost = gCost + hCost;\n\n const existingNeighbor = openSet.find(n => n.x === neighbor.x && n.y === neighbor.y);\n if (!existingNeighbor || gCost < existingNeighbor.g || (gCost === existingNeighbor.g && fCost < existingNeighbor.f)) {\n neighbor.g = gCost;\n neighbor.h = hCost;\n neighbor.f = fCost;\n neighbor.parent = current;\n if (!existingNeighbor) openSet.push(neighbor);\n }\n });\n\n yield; // Pause for animation\n }\n }\n\n // Calculate Manhattan distance\n function manhattan(a, b) {\n return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);\n }\n\n // Get wall between current and neighbor\n function getWall(current, dir) {\n if (dir.dx === 0 && dir.dy === -1) return current.walls.top;\n if (dir.dx === 1 && dir.dy === 0) return current.walls.right;\n if (dir.dx === 0 && dir.dy === 1) return current.walls.bottom;\n if (dir.dx === -1 && dir.dy === 0) return current.walls.left;\n }\n\n // Draw maze\n function drawMaze() {\n ctx.clearRect(0, 0, canvas.width, canvas.height);\n\n for (let x = 0; x < gridSize; x++) {\n for (let y = 0; y < gridSize; y++) {\n const cell = maze[x][y];\n const x1 = x * cellSize;\n const y1 = y * cellSize;\n const x2 = x1 + cellSize;\n const y2 = y1 + cellSize;\n\n // Draw walls\n ctx.strokeStyle = '#333';\n ctx.lineWidth = 2;\n if (cell.walls.top) ctx.beginPath(), ctx.moveTo(x1, y1), ctx.lineTo(x2, y1), ctx.stroke();\n if (cell.walls.right) ctx.beginPath(), ctx.moveTo(x2, y1), ctx.lineTo(x2, y2), ctx.stroke();\n if (cell.walls.bottom) ctx.beginPath(), ctx.moveTo(x1, y2), ctx.lineTo(x2, y2), ctx.stroke();\n if (cell.walls.left) ctx.beginPath(), ctx.moveTo(x1, y1), ctx.lineTo(x1, y2), ctx.stroke();\n\n // Draw open set (light blue)\n if (openSet.some(n => n.x === x && n.y === y)) {\n ctx.fillStyle = '#a1caf1';\n ctx.beginPath();\n ctx.arc(x1 + cellSize/2, y1 + cellSize/2, cellSize/6, 0, Math.PI * 2);\n ctx.fill();\n }\n\n // Draw closed set (light gray)\n if (closedSet.has(`${x},${y}`)) {\n ctx.fillStyle = '#e0e0e0';\n ctx.fillRect(x1 + 2, y1 + 2, cellSize - 4, cellSize - 4);\n }\n\n // Draw path (red)\n if (path.includes(`${x},${y}`)) {\n ctx.fillStyle = '#ff0000';\n ctx.beginPath();\n ctx.arc(x1 + cellSize/2, y1 + cellSize/2, cellSize/4, 0, Math.PI * 2);\n ctx.fill();\n }\n }\n }\n }\n\n // A* animation controller\n function startAStarAnimation() {\n aStarGen = aStarGenerator();\n animationStep = 0;\n animationFrameId = requestAnimationFrame(animateAStar);\n }\n\n function animateAStar() {\n if (!aStarGen) return;\n const result = aStarGen.next();\n if (result.done) {\n cancelAnimationFrame(animationFrameId);\n return;\n }\n drawMaze();\n animationFrameId = requestAnimationFrame(animateAStar);\n }\n\n // Start process\n generateMaze();\n startAStarAnimation();\n </script>\n</body>\n</html>" } } <|FunctionCallEnd|>

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

modelseed-1.6-flash
vendorByteDance · Seed
harnesspi-agent
generated2026-08-01

EVALUATION

1/5 broken

Canvas stays completely blank white throughout; JS error prevented maze/solver from rendering at all.

off-prompt

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.0%
on click0.0%
on drag0.0%
on wheel0.0%
on enter + space0.0%
on arrow keys0.0%
on w/a/s/d0.0%
frame spread12.2 / 255
console errors0
js errors
  • Cannot read properties of undefined (reading 'right')

METRICS

runtime122.5s
tokens in28k
tokens out20k
cached0
cost / run$0.0080