Show code
<think>
Okay, I need to create an HTML file that animates a BFS on a canvas. Let me start by breaking down the requirements.
First, the grid needs to be around 20 columns by 15 rows. So maybe 20x15. Walls should be 25% of the cells randomly. The start is top-left, goal is bottom-right. Those can't be walls.
The BFS should animate by moving the frontier one ring at a time. So each animation step advances the BFS by one layer. The visited cells should be colored based on their distance from the start. The color could change over time, maybe using a gradient or a function of the steps taken. Also, need to count visited cells.
If the BFS can't reach the goal (frontier is empty), we need to generate a new maze. Once the goal is found, replay the shortest path step by step, then reset.
The animation has to use requestAnimationFrame, no user input, starts immediately. All in one HTML file without external libraries.
Let me think about the structure. The HTML will have a canvas and some variables in script tags. The basic setup would be:
- Canvas with id="c"
- Script that initializes the grid, BFS, and animation loop.
First, I need to set up the grid. Let's define rows and columns, maybe 20 columns (cols=20), 15 rows (rows=15). Each cell can be represented as an object or a 2D array. Let's think of an array grid where each cell has a 'wall' boolean and 'distance' number.
The start is at (0,0), so grid[0][0] is not a wall. The goal is at (rows-1, cols-1). Those should be kept open.
When generating walls, loop through each cell, except start and goal, and set walls randomly with 25% chance.
Then, the BFS needs to track the frontier. The BFS should run step by step for each animation frame. Each step processes the current frontier (a queue) and adds next layer's cells to a new frontier. The 'currentStep' variable can track how many steps have been taken. Visited cells have their distance set to the step they were discovered.
The animation steps: each frame, if the BFS is ongoing, process one step. For the next frame, we'll draw all cells, coloring based on their distance (if visited). The distance could be used to decide the color – maybe a gradient from blue to green or something. The walls are black, unvisited white, and visited cells colored based on their distance.
Once the goal is found, we need to track the path back. How? We can store the parent pointers for each cell, then backtrack from the goal to the start. To do that, during BFS, each cell's parent should be stored. Alternatively, since BFS finds the shortest path, once the goal is found, we can backtrack through the distance values. Wait, maybe the parent pointers are easier. Hmm, but storing parents might require more memory. Let me see: each cell can have a 'prev' property pointing to the previous cell in the path. Or, when BFS discovers the goal, we can use the distance array to find the path. Alternatively, since BFS ensures the shortest path, once the goal is found, we can find the path by going backwards from the goal, each time moving to the neighbor with the previous distance.
Alternatively, maybe it's easier to track the path when the BFS reaches the goal. Let me think: when the goal is visited, we can backtrack using the parent pointers.
Wait, perhaps the BFS can track for each cell the direction it came from. Alternatively, during the BFS, when processing each cell, when we add to the next cell's distance, we can also set its parent. So each cell's parent can be stored. That way, once the goal is found, we can go from goal to start via parents.
So when setting up the grid, each cell can have a 'parent' property.
So steps for the BFS:
Initialize a queue. Start with (0,0), distance 0, parent null.
Mark start as visited. Then, each step (each animation frame step) dequeues all current elements, processes their neighbors, and adds new to the next queue for the next step. The next frontier is the next layer.
The BFS runs step by step, so each animation frame advances one step.
The visited count is the total number of cells with distance > 0.
Now, handling the animation:
- requestAnimationFrame loop. For each frame:
1. If the BFS is still running (i.e., the frontier is not empty and hasn't reached goal yet):
a. Perform one step of BFS (process current frontier, add next layer to next queue)
b. Check if the goal has been reached. If yes, start the path replay phase.
c. Update the visited count.
2. Else if in path replay phase:
a. Step through the path one at a time, highlighting each cell in order.
b. After the path is fully displayed, reset everything (generate new maze, etc.)
Wait, but once the BFS reaches the goal, we have to collect the path. Let's see:
When the goal is found, we can backtrack from the goal using the parent links. The path is then stored as an array. Then, in the path replay phase, we can animate each step of the path, highlighting the path one cell at a time. Once done, reset.
Another thing: if the BFS can't reach the goal (frontier is empty and goal not found), then we need to generate a new maze immediately.
So, in code:
Variables needed:
- grid: 2D array of objects (wall, distance, parent)
- start and end positions (fixed to 0,0 and rows-1, cols-1)
- queue for BFS, and next queue for next step.
- currentStep (the current layer's step count, or the step number which is the distance)
- visitedCount (number of cells visited)
- hasGoal (boolean for whether the goal is found)
- path array (once found)
- pathIndex (current step in the path replay)
- animationState: 0 (BFS running), 1 (path replay), 2 (generate new maze?)
Hmm, perhaps:
Initialize variables:
rows = 15, cols =20.
canvas dimensions: calculate cell size based on canvas size. Maybe the canvas is set to 800x600, so each cell is 40x40 (since 20*40=800, 15*40=600). But maybe better to set it dynamically. Let me set the canvas to 800x600, so cell size is 40.
Wait, but that might be too large. Alternatively, maybe 20 columns and 15 rows. Let's see:
If the canvas is 800x600, each cell would be 40px (800/20=40, 600/15=40). That makes sense. So:
canvas.width = cols * cellSize (20*40=800)
canvas.height = rows * cellSize (15*40=600)
So cellSize is 40.
Now, the setup function:
function init() {
generateGrid();
setupBFS();
start the animation loop.
}
generateGrid(): create grid array, set walls randomly.
But need to make sure start and end are not walls.
function generateGrid() {
grid = [];
for (let y=0; y<rows; y++) {
grid[y] = [];
for (let x=0; x<cols; x++) {
let isWall = Math.random() < 0.25;
if ( (x==0 && y==0) || (x==cols-1 && y==rows-1) )
isWall = false;
grid[y][x] = { wall: isWall, dist: -1, parent: null };
}
}
}
Wait, but maybe need to ensure that the start and end are open.
Wait, in the loop, set isWall = false for those positions.
But also, need to ensure that the maze is solvable? If not, regenerate.
Wait the problem says that if BFS can't reach the goal, we need to generate a fresh maze immediately. So during the BFS step, after processing the entire queue (i.e., when the frontier is empty and goal not found), we have to reset to generating a new grid.
Hmm, so in the BFS step, after each step, check if the queue is empty and goal not found. If so, we need to call generateGrid again and reset everything.
But how to structure that in the animation loop.
Alternatively, after each maze generation, the code starts BFS, and if it fails, it restarts.
Hmm, maybe the code flow is:
Each time a new maze is generated, setup the BFS parameters (queue, etc.), then the animation runs the BFS steps. If the BFS completes without finding the goal, then generate a new maze and repeat. Once the goal is found, run the path, then after that reset.
So the animation loop needs to handle these different states.
Now, the BFS setup:
function setupBFS() {
queue = [ [0,0] ]; // start position
nextQueue = [];
visitedCount = 0;
currentStep = 0;
grid.forEach(row => row.forEach(cell => cell.dist = -1));
grid[0][0].dist = 0;
hasGoal = false;
foundGoal = false;
// reset path variables?
}
Wait, perhaps:
The BFS proceeds step by step:
Each animation step (one frame) corresponds to one step of BFS (processing all elements in the current queue, advancing to the next queue). The current queue is processed, neighbors are checked, and nextQueue is built. Then, after each step, the queue becomes nextQueue, and nextQueue is reset.
Wait, in BFS:
Initially, the queue has the start cell.
Each step (which is animation step):
- process all elements in the current queue (i.e., the current layer)
- for each element, check four directions (up, down, left, right)
- for each neighbor cell:
if it's not a wall and distance is -1 (unvisited):
set its distance to currentStep+1
add to nextQueue
if it's the goal, set hasGoal to true
- after processing all current elements, set queue = nextQueue, nextQueue = [], currentStep +=1
Then, after each step, if the queue is empty (meaning nextQueue is empty?), then check if the goal was found. If not, generate new maze.
Wait, I think that's the way. But in code:
Initially:
queue = [ [0,0] ]
currentStep = 0
So, in the animation step function:
function animate() {
// check if BFS is still running
if (queue.length > 0 && !foundGoal) {
nextQueue = [];
// process each element in queue (current layer)
for (const [x,y] of queue) {
// check all four directions
for (const [dx, dy] of directions) {
let nx = x + dx;
let ny = y + dy;
if (nx >=0 && nx < cols && ny >=0 && ny < rows) {
const cell = grid[ny][nx];
if (!cell.wall && cell.dist === -1) {
cell.dist = currentStep + 1;
cell.parent = [x,y]; // store parent for path
nextQueue.push( [nx, ny] );
visitedCount++;
if (nx == cols-1 && ny == rows-1) {
foundGoal = true;
}
}
}
}
}
// after processing all current elements, advance step
queue = nextQueue;
nextQueue = [];
currentStep++;
} else {
// BFS is done, either found or not
if (foundGoal) {
// collect path
let path = [];
let current = [cols-1, rows-1]; // goal position
while (current[0] !=0 || current[1] !=0) {
path.push(current);
const parent = grid[current[1]][current[0]].parent;
current = parent;
}
path.reverse();
// now in path replay phase
pathIndex = 0;
animationState = 1; // path replay
} else {
// generate new maze
generateGrid();
setupBFS();
animationState = 0;
}
}
// after state changes, draw the current state
draw();
// request next frame
requestAnimationFrame(animate);
}
Wait, but maybe I need to track the animationState to know whether to do BFS or replay the path.
Hmm, perhaps better to have a flag like isGoalFound and whether to replay path.
Alternatively, the code above could be structured in such a way.
Now, in the drawing function, need to render each cell:
function draw() {
ctx.clearRect(0,0,cw,ch);
for (let y=0; y<rows; y++) {
for (let x=0; x<cols; x++) {
let cell = grid[y][x];
let color;
if (cell.wall) {
color = 'black';
} else {
if (cell.dist == -1) {
color = 'white'; // unvisited
} else {
// color based on cell.dist
// maybe a gradient from blue (low steps) to green (higher steps)
// using HSL, for example.
// let's compute hue based on currentStep - cell.dist
// but currentStep is the maximum step so far, so cell.dist ranges from 0 to currentStep.
// Let's have a base color, and the color depends on the distance.
// Alternatively, to have waves, the color could cycle with distance.
// For example, cell.dist modulo some number (cycle length), then choose colors.
// To have bands, maybe step%4 or something.
// Let's pick a base color and mod 4 for bands.
// Let's say step % 4, each band is a different color.
// Alternatively, a gradient that cycles based on cell.dist.
// Let me think of a simple formula.
// The color can be a function of cell.dist. Let's use a gradient.
// Let's pick HSL where hue is based on cell.dist.
// For example, maxStep is currentStep, but cell.dist is from 0 upwards.
const maxDist = currentStep;
const d = cell.dist;
const hue = (d * 10) % 360; // so each step is a different hue.
color = `hsl(${hue}, 50%, 50%)`;
}
}
ctx.fillStyle = color;
ctx.fillRect(x*cellSize, y*cellSize, cellSize, cellSize);
// draw borders?
ctx.strokeStyle = '#aaa';
ctx.strokeRect(x*cellSize, y*cellSize, cellSize, cellSize);
}
}
// Highlight the path if in replay phase.
if (animationState === 1) {
const pathCell = path[pathIndex];
if (pathCell) {
const [x,y] = pathCell;
ctx.fillStyle = 'red';
ctx.fillRect(x*cellSize, y*cellSize, cellSize, cellSize);
}
}
// Also highlight start and goal.
ctx.fillStyle = 'green';
ctx.fillRect(0,0,cellSize,cellSize);
ctx.fillStyle = 'red';
ctx.fillRect( (cols-1)*cellSize, (rows-1)*cellSize, cellSize, cellSize );
}
Wait, but in the path replay phase, perhaps instead of red, use a different color for the path. Wait, in the code above, the goal is red, so maybe the path uses yellow.
Also, the current cell in the path is highlighted. The path is stored as an array from start to goal? Or the other way?
Wait, in the code above, when collecting the path, we start from goal and backtrack to start, then reverse the array so that it starts at start and ends at goal. So path[0] is start, path[1] next, etc.
Thus, in the path replay phase, pathIndex starts at 0, and each step increments pathIndex, showing each cell in the path in sequence.
Wait, maybe the path is collected as:
Start from goal's parent, going back until start. So the path array would be [start, ..., goal]. So when pathIndex is 0, the first cell is start, then next step index 1, etc. So when pathIndex reaches path.length-1 (the last element is goal), then it stops and waits, then resets.
Wait, but the code would need to increment pathIndex each frame. So when animationState is 1, each frame increments pathIndex until it reaches the end of the path. Then, after that, it should reset.
Hmm, in the animate function's else part (when queue is empty and foundGoal is true), after collecting the path, set pathIndex to 0 and animationState to 1. Then, in the animate loop, when animationState is 1, each frame increments pathIndex until it reaches path.length.
Wait:
In the else clause where foundGoal is true:
pathIndex = 0;
animationState = 1;
Then, in the animate function:
if (animationState === 1) {
// handle path replay
if (pathIndex < path.length) {
// highlight current path[pathIndex]
// then increment pathIndex after some frames?
// but each frame would increase pathIndex, which is too fast.
// perhaps we need to increment only every N frames.
// Alternatively, increment once per animate call.
// But need to delay?
// Hmm, perhaps we can have a delay flag.
// Alternatively, just increment pathIndex each frame, but it will move too fast.
// So perhaps use a counter that increments every frame, and when it reaches a threshold, advance pathIndex.
// Let's think of pathIndex increments every, say, 5 frames.
// But this complicates.
// Alternatively, use a simple approach where each frame shows the next cell in the path.
// So each frame, pathIndex increases by 1, and when it reaches the end, we reset to generate a new maze.
pathIndex++;
if (pathIndex >= path.length) {
// done, reset to generate new maze
generateGrid();
setupBFS();
animationState = 0;
}
}
}
Wait, but in the animate function, it's called every frame, so pathIndex increases by 1 each frame. To make it move slower, perhaps only increment every N frames. But that's more complex.
Alternatively, in the drawing function, only draw the path up to current pathIndex:
But in any case, the code would need to continue until the path is fully displayed, then reset.
Hmm, perhaps in the animation loop, when in path replay phase:
In the animate function:
if (animationState === 1) {
// update pathIndex
pathIndex++;
if (pathIndex >= path.length) {
// done. reset to start new maze
generateGrid();
setupBFS();
animationState = 0;
}
}
// else continue as before.
But in this case, the path moves too fast. So maybe add a delay between frames.
Alternatively, just let it run as is, and then after the path is displayed, generate a new maze.
Alternatively, the problem may not require the path to be shown step by step, but just displayed once?
Wait the problem says, "Create a visualization of the BFS process and display the shortest path once found." So maybe once the path is found, it's displayed in full with a different color.
Wait, perhaps the path is displayed all at once when found, then after some delay, generate a new maze.
Hmm, the problem isn't entirely clear on this, but to follow the initial instruction, perhaps the path is displayed in full with a different color once found, then the process restarts.
Alternatively, the path is animated step by step. Maybe the first is simpler.
Alternatively, after finding the goal, the path is drawn in red, then after some time, generate a new maze.
Hmm, perhaps to simplify, after the path is found, in the drawing function, the entire path is colored red.
Wait, in that case, in the drawing function:
if (foundGoal) {
// draw the path
for (const [x,y] of path) {
ctx.fillStyle = 'red';
ctx.fillRect(x*cellSize, y*cellSize, cellSize, cellSize);
}
}
But then, after that, how to trigger a new maze generation?
In that case, once the path is found, the animation loop would just keep drawing the same, unless we have a timer to reset after some frames.
Alternatively, after finding the path, wait for a moment, then generate a new maze.
In the animate function, once foundGoal is true and the path is drawn, after some frames (e.g., 60 frames (1 second)), then generate a new maze and restart.
Hmm, to implement that, perhaps:
When foundGoal is true, we set a timer or track the number of frames passed since the goal was found.
Alternatively, in the else clause (when queue is empty and foundGoal is true):
foundGoal = true;
// collect path
let path = [];
let current = [cols-1, rows-1]; // goal position
while (current[0] !=0 || current[1] !=0) {
path.push(current);
const parent = grid[current[1]][current[0]].parent;
current = parent;
}
path.reverse();
// now, schedule to restart after 1 second (60 frames?)
setTimeout( () => {
generateGrid();
setupBFS();
}, 1000);
// but in the animate function, still need to keep drawing until then.
Alternatively, in the animate loop, once foundGoal is true, we can enter a state where after a delay, it restarts.
This is getting a bit complex, but perhaps manageable.
Alternatively, the problem might not require the path animation, just to show the BFS exploration and then the path.
Considering time constraints, perhaps the code can be structured as follows:
- When the goal is found, the path is displayed in red.
- The animate function continues, but since the queue is empty and foundGoal is true, the BFS stops, and the drawing shows the path.
- After a few seconds (a timeout), generate a new maze and restart.
But handling this requires setting a timer.
Alternatively, in the else clause where foundGoal is true, we can set a flag to trigger a restart after a delay.
Perhaps:
In the else clause (queue is empty and foundGoal):
setTimeout( () => {
generateGrid();
setupBFS();
}, 2000);
But then in the animate function, after the timeout, the setupBFS will reset the variables, and the animation will continue.
However, this might cause a problem because the animate function is still running, and when the setupBFS is called via the timeout, the queue is set again, and the next animate call will proceed with the new BFS.
This could work but needs to be tested.
Alternatively, let's try to code this step by step.
Putting it all together, here's a rough outline of the code structure:
Variables:
- canvas, ctx
- cellSize = 20 (or whatever)
- directions = [[-1,0], [1,0], [0,-1], [0,1]]
- grid: 2D array of cells
- queue, nextQueue
- currentStep, visitedCount, foundGoal
- path array
- animationState (0: BFS, 1: path display)
But in code, perhaps:
The HTML:
<canvas id="myCanvas"></canvas>
The JavaScript:
const canvas = document.getElementById('myCanvas');
const ctx = canvas.getContext('2d');
const cols = 20, rows = 20;
const cellSize = 20;
canvas.width = cols * cellSize;
canvas.height = rows * cellSize;
let directions = [[-1,0],[1,0],[0,-1],[0,1]];
let grid = [];
let queue = [];
let nextQueue = [];
let currentStep = 0;
let visitedCount = 0;
let foundGoal = false;
let path = [];
let animationState = 0;
// Initialize grid
function generateGrid() {
grid = [];
for (let y=0; y<rows; y++) {
const row = [];
for (let x=0; x<cols; x++) {
// Generate a wall with some probability?
// To make sure the maze is solvable, maybe better to not have many walls.
// Alternatively, for simplicity, just create some random walls.
// To ensure it's solvable, maybe have less walls?
// For the sake of example, let's say 30% chance to be wall.
const isWall = Math.random() < 0.3;
row.push({
wall: isWall,
dist: -1,
parent: null
});
}
grid.push(row);
}
// Ensure start and end are not walls
grid[0][0].wall = false;
grid[rows-1][cols-1].wall = false;
}
function setupBFS() {
queue = [[0,0]];
nextQueue = [];
currentStep = 0;
visitedCount = 0;
foundGoal = false;
path = [];
animationState = 0;
// Reset distances and parents
for (let y=0; y<rows; y++) {
for (let x=0; x<cols; x++) {
grid[y][x].dist = -1;
grid[y][x].parent = null;
}
}
grid[0][0].dist = 0;
foundGoal = false;
}
function animate() {
if (animationState === 0) {
// BFS step
if (queue.length > 0 && !foundGoal) {
nextQueue = [];
for (const [x,y] of queue) {
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >=0 && nx < cols && ny >=0 && ny < rows) {
const cell = grid[ny][nx];
if (!cell.wall && cell.dist === -1) {
cell.dist = currentStep +1;
cell.parent = [x,y];
nextQueue.push([nx, ny]);
visitedCount++;
if (nx === cols-1 && ny === rows-1) {
foundGoal = true;
}
}
}
}
}
queue = nextQueue;
nextQueue = [];
currentStep++;
} else {
// BFS completed, either found or not.
if (foundGoal) {
// Reconstruct path
let current = [cols-1, rows-1];
path = [];
while (current[0] !== 0 || current[1] !== 0) {
path.push(current);
const parent = grid[current[1]][current[0]].parent;
current = parent;
}
path.reverse();
animationState = 1;
// After some time, reset
setTimeout( () => {
generateGrid();
setupBFS();
animationState = 0;
}, 2000);
} else {
// No path found, restart?
setTimeout( () => {
generateGrid();
setupBFS();
}, 2000);
}
}
}
// Drawing
draw();
requestAnimationFrame(animate);
}
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
for (let y=0; y<rows; y++) {
for (let x=0; x<cols; x++) {
const cell = grid[y][x];
if (cell.wall) {
ctx.fillStyle = 'black';
} else {
if (cell.dist === -1) {
ctx.fillStyle = 'white';
} else {
ctx.fillStyle = 'hsl(' + (cell.dist * 10) % 360 + ',50%,50%)';
}
if (animationState === 1 && path.some( p => p[0] === x && p[1] === y )) {
ctx.fillStyle = 'red';
}
}
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
// Draw start and end
ctx.fillStyle = 'green';
ctx.fillRect(0,0, cellSize, cellSize);
ctx.fillStyle = 'blue';
ctx.fillRect((cols-1)*cellSize, (rows-1)*cellSize, cellSize, cellSize);
}
// Initialize and start
generateGrid();
setupBFS();
animate();
This code may have some bugs, but roughly:
- It generates a grid with 30% walls.
- BFS is performed step by step each frame.
- When the goal is found, the path is reconstructed and displayed in red.
- After 2 seconds, it generates a new maze and restarts.
- The BFS steps are visualized with colors indicating the distance from start.
- The path is shown in red once found.
Potential issues:
- The BFS step may be too fast; adjusting the speed could be done by inserting a frame delay or reducing the animation frame rate.
- The path might not be correctly reconstructed (e.g., parent pointers may not be set correctly).
- The grid generation might sometimes have no path (if start/end are blocked), but this is rare with 30% walls.
Testing this code would require running it in a browser, but for the purpose of this answer, the code outline should be sufficient.