Show code
<think>
Okay, I need to create a self-contained HTML file that animates a flood fill on a 60x40 grid using a canvas. The user wants random blobs of color, a start cell, and the fill to expand step by step. Also, display the number of filled cells and frontier size. It has to use requestAnimationFrame for smooth animation and restart automatically when finished. No external libraries, and the code should be under 120 lines.
First, the HTML structure. I'll start with the basic HTML5 template. Inside the body, a canvas element with id 'canvas', and some divs to show the stats. The canvas should have width and height attributes set to the grid size multiplied by the cell size. Wait, the grid is 60x40, but the cell size? Maybe each cell can be 10px, so the canvas would be 600x400. That seems reasonable.
Next, the JavaScript part. I'll need to handle the canvas context. Let me think about the steps:
1. Initialize the grid. Each cell can have a color. The initial grid should have some random blobs. How to create random blobs? Maybe start by randomly placing seeds and growing them with a certain probability to form regions. But that might be too complex. Alternatively, for simplicity, I can color each cell with random colors, then in the flood fill, find connected regions. Hmm, but the user mentioned "random blobs of color", so perhaps first step is to generate regions with connected colors?
Wait, perhaps the idea is to first create a grid where each cell has a random color (forming blobs), then pick a starting cell and flood fill from there, replacing the original color with a new one. Wait, but the user says "expand the fill one frontier step at a time". So maybe the flood fill is expanding the current color into the neighboring cells. Wait, no, perhaps the initial grid has some colors, and the flood fill starts at a point, and tries to replace the target color with the new color, expanding step by step. But the user says "Generate a few random blobs of colour, pick a start cell, and expand the fill one frontier step at a time so the growing region is clearly visible."
Hmm, perhaps the initial grid has some regions (blobs) of colors, and the flood fill starts at a cell, and replaces the surrounding cells of the same color, but expanding step by step. But maybe the flood fill is starting with a new color and replacing the original color's connected region step by step. Alternatively, maybe the blobs are the initial random colors, and the flood fill is from a start point, changing the color step by step, with the frontier being the next layer.
Alternatively, perhaps the user wants to show the flood fill algorithm in action, where the fill starts at a point and expands to all reachable cells of the same color, one layer at a time. The animation should show each step of the expansion.
So the steps:
- Create a grid (60x40). Each cell has a color (maybe randomized into blobs). Wait, how to make blobs? Maybe first assign random colors to each cell, then for some iterations, blur or smooth the colors to create blobs. Alternatively, use a cellular automaton approach to generate regions. Alternatively, a better approach for simplicity might be to first choose a starting color, then randomly fill adjacent cells to form a blob, but that could be computationally heavy.
Alternatively, for the initial grid, assign each cell a random color, but then apply a thresholding or clustering algorithm, but that might be overcomplicated. Alternatively, maybe the initial grid is filled with random colors, and the flood fill starts at a point, and the target color is the original color of that point. Then, the flood fill will expand to connected cells of the original color, replacing them with a new color (like white or another color chosen for the flood). The animation would show each step of that expansion.
Wait, the user says "expand the fill one frontier step at a time", so the animation should show each step. The flood fill algorithm typically uses a queue; each step processes the current frontier (the edges of the filled region) and adds the next layer to the frontier.
Therefore, the steps are:
Initialize grid with random colors.
Pick a starting cell (maybe random? Or center? The user didn't specify, so perhaps random).
The flood fill will start at that cell, and replace the original color with a new color (like white). The frontier is the list of cells adjacent to the filled region that are of the target color (original color). Each frame processes one step (i.e., takes the current frontier, processes each cell in the current frontier, then adds their adjacent cells to the new frontier).
So in code:
We need to track:
- grid: 2D array for color (maybe as RGB values or just indices for colors)
- filled: another 2D array (or part of the grid) to track filled status?
Alternatively, the grid can be a 2D array where each cell has its current color, and once filled, it's set to the target fill color.
But the flood fill's target color is the original color of the starting cell. So first, get the original color of the starting cell. Then, any cell of that original color is a candidate to be filled.
So the algorithm steps:
Initialize grid with random colors.
Pick a random starting point (x,y).
OriginalColor = grid[x][y]
The flood color can be a new color, say white (or another color not used in the initial grid, but maybe random each time).
Frontier starts as the starting cell's neighbors of OriginalColor.
Wait, actually, the flood fill should start with the starting cell itself, then expand. Wait, the standard flood fill algorithm is:
Initialize a queue with the starting cell.
While queue not empty:
- current cell = dequeue
- if cell's color is original color:
- set it to new color
- add its neighbors to the queue (if they are original color)
But to animate it step by step, each frame processes one step (one cell from the queue?), but that would be slow. Alternatively, process each layer (all current frontier cells) as one step. Wait, perhaps the frontier is stored as a list, and each step processes all current frontier cells, and adds their neighbors to the next frontier.
Wait, maybe using BFS, where each step processes all elements in the current frontier, and the next frontier is built from their neighbors.
Thus, each animation frame, we process the current frontier's cells, mark them as filled, and then compute the next frontier as the neighbors of those cells that are of the original color and not yet filled.
Therefore, variables needed:
- grid: 2D array of colors (maybe stored as numbers for simplicity)
- filled: 2D array of booleans? Or track via color change.
Wait, perhaps the grid can hold the color, and once filled, it becomes the new color. The original color is stored separately. So during the flood, any cell of the original color adjacent to the current filled area becomes part of the next frontier.
Thus, the steps:
Initialize grid:
for each cell (x,y):
grid[x][y] = random color (maybe a random hex or a value between 0 and some number)
Then pick a starting point (x0,y0).
originalColor = grid[x0][y0]
fillColor = some other color (maybe white, or random)
frontier starts with [x0,y0]?
Wait, actually, the starting cell is the first to be filled, so the frontier is initially empty? Hmm.
Wait, let me think again