Show code
<think>
Okay, I need to create an HTML file that generates a 30x20 maze using the recursive backtracker algorithm on a canvas. The user wants the maze to be carved one cell at a time, with visual feedback: highlighting the current cell, showing the stack path in another color, and the walls disappearing as they're carved. Also, after the maze is done, it should wait briefly and then restart. Plus, display the number of cells carved and the current stack depth. All using requestAnimationFrame for smooth animation, no user input, and no external libraries. And the HTML file must be self-contained, under 120 lines.
First, I need to structure the HTML. The canvas element will be the main component. The script will handle the maze generation with recursive backtracking. Let me think about the steps:
1. Set up the canvas and its context. The size should accommodate 30 columns and 20 rows. Maybe 600x400 pixels (each cell 20x20 pixels). Wait, 30x20 grid, so 30 cells in x and 20 in y. Let me see: 30 columns mean 600px width (each cell 20px), 20 rows mean 400px height. That seems manageable.
2. The maze generation algorithm. Recursive backtracking works by choosing a starting cell, then randomly visiting neighboring cells, carving paths between them, and using a stack to backtrack. Each step should be drawn on the canvas with animation. But since JavaScript is single-threaded, I need to use requestAnimationFrame to animate each step, without blocking the UI.
3. The maze data structure. Each cell needs to track visited status, walls (north, east, south, west), and maybe neighbors. The stack will hold the path of cells being processed.
4. Visual elements:
- Current cell: highlighted (maybe in red).
- Stack path: the cells in the stack (excluding the current) displayed in another color (like blue).
- Walls: when carved, remove wall lines between cells.
- Counters for cells carved and stack depth.
5. Animation: Each step of the algorithm must be drawn in a frame. Since recursive backtracking is a recursive function, but to make it work with requestAnimationFrame, I'll need to make it iterative or use async/await with promises. However, that might complicate the code. Alternatively, use a loop with a step function that processes one step each animation frame.
Wait, recursive functions can't be easily paused. So maybe implement the recursive backtracker iteratively. Let's think: the standard recursive approach is:
function backtrack(cell):
mark cell as visited
while there are unvisited neighbors:
choose a random neighbor
knock down wall between them
backtrack(neighbor)
But to make this work with animation frames, I can represent this as a stack-based iteration. The stack holds the current path. Instead of recursion, I use a stack array where each entry is the current cell and its unprocessed neighbors. Each animation frame pops a cell, selects a neighbor (if any), processes it, and pushes the next steps.
Hmm, perhaps the iterative approach is better here. Let me structure the algorithm as:
Initialize the stack with the starting cell. Mark it as visited. Then, in each step:
- Current cell = top of stack.
- Check if it has any unvisited neighbors.
- If yes, pick a random one, knock down the wall between, add to stack, and proceed.
- If no, backtrack by popping the stack.
Each step would be one frame, allowing the animation to update.
6. For drawing:
- The canvas needs to redraw the maze each frame. But this might be slow if done naively. Alternatively, perhaps we can just draw the changes (only the current cell and the walls being carved). But maybe for simplicity, redraw everything each frame, but it's manageable with 30x20=600 cells. Let's see.
Each cell can be represented in an array. The maze grid can be a 2D array of objects with walls.
Wait, perhaps the grid can be stored as an array of cells, each with four walls (north, south, east, west). Or maybe it's easier to track walls between cells. Alternatively, for each cell, track which walls are present. For example, each cell has walls north, south, east, west. When moving to a neighbor, we can remove the wall between the current cell and the neighbor.
But to draw the maze, we have to loop through each cell and draw their walls. To optimize, maybe precompute which walls to draw, then draw all in one go.
But with animation, each step only modifies a few walls, but redrawing the entire maze each frame might be acceptable given the size.
Let me outline the steps in code:
First, the HTML structure:
- Doctype, html, head with title, body with canvas and a div for counters.
The script will handle:
- Canvas setup, context, initial variables.
- The maze grid (2D array).
- The stack for backtracking.
- Flags for if the maze is being built, if done, and then restart.
Variables needed:
- mazeWidth = 30, mazeHeight = 20
- cellSize = 20 (so canvas width 30*20, height 20*20)
- grid: 2D array of cells, each cell has visited, walls (as booleans for N, E, S, W?), and maybe neighbors.
Wait, perhaps each cell can be an object with visited, and walls as an array or object. Alternatively, to track visited and the walls, perhaps:
Each cell has:
visited: boolean
walls: array of four elements (N, E, S, W walls present). Or maybe 4 booleans.
Alternatively, for each cell, store the walls as bits, but that's more complicated.
Alternatively, for a cell at (x,y), the walls can be represented as:
northWall (top of the cell, so the same as the south wall of the cell above)
But perhaps it's easier to track each cell's own walls. For example, for a cell (x,y), walls.north is if there is a wall above it, walls.east is to the right, etc.
So, each cell can have an object like:
{
visited: false,
walls: { north: true, east: true, south: true, west: true }
}
Then, when moving from current cell to a neighbor, say right, we can set current cell's east wall to false, and neighbor's west wall to false.
So, to generate the maze:
Initialize all walls as present, then the algorithm proceeds.
The stack will hold the path. The stack could be an array of positions (x,y), or pointers to the cell objects.
Starting point: pick a random cell (or fixed, like 0,0). Let's start at (0,0).
Then, the algorithm steps:
- While stack is not empty:
- currentCell = stack.pop()
- (Wait, no, in iterative approach, maybe use a stack to track path, and check neighbors)
Alternatively, the standard iterative backtracking approach uses a stack where you push the current cell, then pick a neighbor, and when you backtrack, you go back.
Hmm, the iterative approach for recursive backtracking is:
Initialize stack with starting cell. Mark as visited. Then, while stack not empty:
current = stack[-1]
find an unvisited neighbor. If found:
pick one, remove the wall between