Show code
<think>
Okay, I need to create an HTML file that animates a Voronoi diagram using a multi-source BFS flood fill. Let me think through the steps.
First, the Voronoi diagram is made by having seed points that expand outward, and each cell is assigned to the nearest seed. To animate this, I can use a grid where each cell is filled by the first seed that reaches it. The animation should use requestAnimationFrame for smoothness.
The user wants the animation to start immediately, loop continuously, and restart when done. The seed points should be scattered randomly each time. Also, I have to display the number of cells claimed, which I guess means the number of seeds, but maybe it's the total cells? Wait, the user says "show the number of cells claimed"—maybe each seed's area is a cell, so the number of seeds would be the count. Hmm, but maybe it counts all cells? Probably the seeds count as cells. Wait, the problem says "show the number of cells claimed" so perhaps it's the total number of cells in the grid? No, that might not make sense. Maybe each seed's area is a cell, so the number of seeds is the number of cells. The problem says "scatter a handful of seed points", so each seed is a cell center. So the number is the number of seeds. But maybe the user wants to show the progress as the animation runs. Like, how many cells have been claimed so far? Or when it's done, show the total. Hmm, the problem says "show the number of cells claimed", so probably when the animation finishes, it should display how many cells (seeds) there were. Wait, but the user says "Restart with freshly scattered seeds when finished." So maybe after each animation completes, they show the count before restarting.
Alright, the steps are:
1. Set up a canvas.
2. Randomly place seed points each time.
3. Use BFS to simulate the expansion of each seed's influence.
4. The animation should show the grid filling cell by cell, with each cell taking the color of the first seed to reach it.
5. The animation should run as smooth as possible with rAF.
6. After completion, reset with new seeds.
Now, structuring the HTML:
The HTML will have a canvas element and a div to display the count. The script will handle everything.
Let me think about the grid. Maybe use a 2D array for the grid, where each cell records the closest seed's color or index. The BFS needs to process each layer of cells for each seed simultaneously. Since we need to grow all seeds at the same time, each step expands all current frontiers one step outward.
To implement this, maybe the grid is represented as an array of arrays. Each cell can have a color (assigned when claimed) and a distance from the seed. Alternatively, we can track for each cell which seed's wave reached it first.
The BFS approach could be:
- Initialize the grid with all cells unclaimed (color 0 or null).
- Place the seeds randomly on the grid. Each seed has a starting position and a unique color.
- The BFS queues would hold all current frontier cells of each seed.
- Each animation frame, process the next layer: for each seed's current frontier, expand to adjacent cells. For any unclaimed cell, assign the seed's color and add it to the seed's next frontier. If a cell is already claimed, skip it.
- Continue until no cells are left to process.
But how to animate this step by step? Each frame, we can process one step of expansion for all seeds. So each frame, we process the current frontiers and move to the next.
Wait, but in an animation loop, each frame is a single step. So each frame, we do one expansion step for all active seeds.
So steps in code:
- Initialize grid (array) and seeds array.
- seeds array contains objects with x, y, color, and a queue for their BFS frontiers.
- The initial queue for each seed is their position. The next queue is built by expanding each current front cell to its neighbors, checking if unclaimed.
- The animation loop runs each frame:
- if there are remaining cells to process, process the next step:
- for each seed, process its current queue, and expand to neighbors.
- build the next queues for each seed.
- update the grid and check if any cells were claimed this step.
- redraw the canvas (draw grid cells and seeds)
- if all cells are claimed, reset everything.
But how do we represent the grid and queues?
Maybe the grid can be an array of rows, each row is an array of cells. Each cell has a color and a distance (though distance might not be necessary if we process in order of BFS steps). But since each seed's expansion is done in BFS steps, the distance from the seed is the step number. So, when expanding, a cell will choose the closest (earliest step) seed.
Alternatively, since each step processes all seeds' current frontiers, the order of expansion is handled automatically.
Wait, the problem says "grow all of them outward one ring at a time simultaneously". So each step, all frontiers of all seeds advance one cell outward.
The key is that each step, for all seeds, their current front (queue) is expanded to adjacent cells, and any unclaimed cell is taken by the first seed to reach it. Since it's simultaneous, if two seeds reach a cell in the same step, it would be assigned to both? No, but in BFS, if two cells are equidistant from two seeds, that cell is part of the edge between them, but in Voronoi diagrams, those points have no cell (they form the edges). But in our case, maybe we just assign it to one of them arbitrarily, but to make it Voronoi, it's better to have the first seed to reach it. However, since all seeds are progressing at the same rate, when two frontiers meet, the cell is claimed by the first one that reaches it.
Hmm, perhaps the way to handle this is that when expanding a cell's neighbors, if the neighbor is unclaimed, it takes the current seed's color. If it's already claimed, we do nothing.
So in each step, each seed's current frontier is the cells that can expand to their neighbors. Each seed's queue (frontier) is processed, and their neighbors are checked. The first seed to reach an unclaimed cell will claim it. Since we process each seed's queue in sequence, the order might matter, but since the BFS steps are simultaneous, maybe we need to process all seeds' queues in parallel, so that all expansions are considered before any cell is claimed.
Alternatively, process all seeds' queues in the same step, and for each cell's neighbors, if unclaimed, they are assigned to the first encountered seed's expansion in that step? Or perhaps the order of processing seeds' queues determines which seed claims it. To make it Voronoi, the distance must be equal, so when two seeds reach a cell at the same step, it's equidistant, so the cell is between them. But for the purpose of animation, maybe it's okay to have it assigned to whichever seed's queue is processed first in that step. Since the order is random, but the seeds' positions are fixed, maybe the result is correct.
Alternatively, perhaps for each cell, we track the minimal distance from any seed, but this might complicate the animation step.
Hmm, given the time constraints, perhaps the simplest way is to process all current front queues for each seed, and for each neighbor cell, if unclaimed, mark it with the seed's color and add it to the seed's next queue. This way, the first seed to reach the cell (in terms of BFS steps) will claim it, so the Voronoi is correctly formed.
Now, implementing this:
The grid is an array of rows and columns. Let's say the canvas is divided into cells of 1x1 pixels? Or perhaps a grid with cells of size (e.g., 5x5) so that the animation is visible. But for simplicity, maybe use a grid that's the same as the canvas width and height. So each pixel is a cell. But for a 500x500 canvas, that's 250,000 cells. That might be too much for an animation. Alternatively, use a grid that's a smaller grid (e.g., 100x100 cells), each cell is a pixel, but then the canvas needs to have that size. Wait, but if we use a grid with each cell as a pixel, then for a 500x500 grid, that's manageable? Maybe, but in animation loops with rAF, it might be a bit slow. Alternatively, using a grid of size like 100x100 where each cell is a pixel. Let's think of the canvas width and height as being, say, 500 each, so 500x500 grid. But even that might be a lot. Alternatively, use cells that are 2x2 pixels to have a manageable number.
Alternatively, perhaps use a grid where the cells are spaced out so that the animation is visible but manageable. Let's think of using a 100x100 grid (so 10,000 cells). Then, the canvas size could be 500x500, so each cell is 5x5 pixels. That's manageable.
So in the setup:
- canvas width and height set to 500.
- grid size is 100x100 (so each cell is 5x5 pixels).
The grid array can be a 2D array of rows and cols. The seeds are placed randomly within the grid coordinates (0-99, 0-99).
The BFS queues for each seed:
- Each seed has a queue of positions (x,y) that are the current frontier.
- Initially, each seed has their own position in their queue.
The animation loop:
Each frame:
- If there are still cells to be claimed (i.e., any seed's queue is not empty):
- For each seed, process their current queue, expanding to adjacent cells (up, down, left, right? Or all 8 directions? The problem says "grid", so maybe orthogonal directions only).
Wait, in a grid, each cell has four neighbors (up, down, left, right). So to expand, each current cell in the frontier can expand to all four directions.
For each seed's current queue:
For each cell in the current queue:
Check all four neighbors.
For each neighbor (nx, ny):
if the cell is unclaimed (color is default, maybe 0 or undefined):
Assign the seed's color to it.
Add (nx, ny) to the seed's next queue.
Then, after processing all seeds' current queues, replace each seed's current queue with their next queue, and clear the next queue for the next step.
Also, we can track the number of cells claimed by incrementing a counter each time a cell is assigned? Or just count the number of cells in the grid that are assigned, but that might be slower.
Alternatively, the total cells is gridWidth * gridHeight, so when all cells are claimed (all colors set), then it's finished.
So in the animation step, each frame:
For each seed:
nextQueue is empty.
For each cell in seed's current queue:
check all four neighbors.
for each neighbor:
if grid[ny][nx] is 0 (unclaimed):
grid[ny][nx] = seed.color
add (nx, ny) to nextQueue.
seed.currentQueue becomes nextQueue.
Then, after all seeds are processed, if any seed has a non-empty next queue, then the process continues.
Wait, but in this approach, the next queue for each seed is built by processing their current queue's cells, and expanding into neighbors that are unclaimed.
But this way, the expansion is done in parallel for all seeds, so the first seed to reach a cell in that step will claim it, since when we process the neighbor, if it's unclaimed, the first seed to check it will set it to their color, and other seeds' expansions will see it's already claimed.
Therefore, this should work correctly for the Voronoi.
Now, putting this into code.
The steps in code:
1. Setup canvas and grid size.
var canvas = document.getElementById('c');
var ctx = canvas.getContext('2d');
const gridWidth = 100; // 100 cells
const gridHeight = 100;
var cellSize = 5; // 5x5 pixels per cell
canvas.width = gridWidth * cellSize;
canvas.height = gridHeight * cellSize;
But in the HTML, we can set the canvas dimensions via attributes.
Wait, in the HTML, the canvas element will have width and height attributes. So perhaps gridWidth = 100, cellSize = 5 → canvas width is gridWidth * cellSize.
2. The grid is a 2D array, initialized to 0 (unclaimed). Each cell's value is the color (seed's color) or 0.
var grid = new Array(gridHeight);
for (var y = 0; y < gridHeight; y++) {
grid[y] = new Array(gridWidth).fill(0);
}
3. The seeds array holds objects with x, y, color, and queue.
var seeds = [];
var seedCount; // number of seeds to scatter each time. Maybe 5 to 10.
When starting, we need to scatter the seeds. Let's choose a random number between 3 and 10 seeds each time.
function reset() {
// clear grid
for (var y = 0; y < gridHeight; y++) {
for (var x = 0; x < gridWidth; x++) {
grid[y][x] = 0;
}
}
// clear seeds
seeds.length = 0;
// generate seeds count between 3-10
seedCount = 3 + Math.floor(Math.random() * 8);
var added = 0;
while (added < seedCount) {
var x = Math.floor(Math.random() * gridWidth);
var y = Math.floor(Math.random() * gridHeight);
// check if cell is unclaimed? Since grid is initialized to 0, but seeds are placed here.
// since we're adding seeds, their color can be set even if already 0.
// but to avoid overlapping seeds, maybe check for existing seeds?
// probably not necessary, but to prevent two seeds in same cell.
// So check if grid[y][x] is 0 (unclaimed)
if (grid[y][x] === 0) {
grid[y][x] = added +1; // colors are 1-based
seeds.push({
x: x,
y: y,
color: added +1,
queue: [[x,y]]
});
added++;
}
}
}
Wait, but each seed has a unique color. So first seed is color 1, second 2, etc. So in the grid, the cell (x,y) where the seed is placed will have color equal to the seed's color.
The queue for each seed starts with their initial position.
4. The animation loop:
var animating = false;
var step = 0;
function animate() {
requestAnimationFrame(animate);
if (!animating) return;
// process one step
var progress = false;
// create next queues
for (var s of seeds) {
s.nextQueue = [];
for (var [x,y] of s.queue) {
// check all four directions
for (var dx = -1; dx <= 1; dx += 2) { // left and right
var nx = x + dx;
var ny = y;
if (nx >=0 && nx < gridWidth && ny >=0 && ny < gridHeight) {
if (grid[ny][nx] === 0) { // unclaimed
grid[ny][nx] = s.color;
s.nextQueue.push([nx, ny]);
}
}
}
for (var dy = -1; dy <= 1; dy += 2) { // up and down
var nx = x;
var ny = y + dy;
if (nx >=0 && nx < gridWidth && ny >=0 && ny < gridHeight) {
if (grid[ny][nx] === 0) {
grid[ny][nx] = s.color;
s.nextQueue.push([nx, ny]);
}
}
}
}
}
// after processing all directions for all seeds
// check if any of the seed's next queues have elements
var hasMore = false;
for (var s of seeds) {
s.queue = s.nextQueue; // move next to current
s.nextQueue = [];
if (s.queue.length > 0) {
hasMore = true;
}
}
// draw the grid
draw();
// check if all queues are empty
if (!hasMore) {
animating = false;
// show the count and restart
document.getElementById('count').textContent = 'Cells claimed: ' + (seedCount);
// wait a second before restarting
setTimeout(() => {
reset();
animating = true;
}, 1000);
}
}
Wait, but in this code, the direction checks are a bit off. For the four directions:
dx is +/-1 for left/right, dy is +/-1 for up/down. Wait, but for up and down, the x is same, y changes. So the loops can be written as:
Check all four directions (left, right, up, down):
for each direction in directions array:
directions could be [[-1,0], [1,0], [0,-1], [0,1]]
So in code:
for (var d of directions) {
let dx = d[0];
let dy = d[1];
let nx = x + dx;
let ny = y + dy;
if (nx >=0 && nx < gridWidth && ny >=0 && ny < gridHeight) { ... }
}
That might be more efficient.
But the way I wrote previously is also okay, but with two separate loops for dx and dy.
Alternatively, better to loop over all four directions once.
In any case, the code needs to check all four adjacent cells.
5. The draw function:
function draw() {
ctx.clearRect(0, 0, canvas.width, canvas.height);
// draw the grid
for (var y = 0; y < gridHeight; y++) {
for (var x = 0; x < gridWidth; x++) {
var color = grid[y][x];
if (color > 0) {
// map color to actual color
var hue = (color * 36) % 360; // arbitrary, but gives different colors
ctx.fillStyle = 'hsl(' + hue + ', 50%, 50%)';
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
}
// draw seeds (original positions)
ctx.fillStyle = 'black';
for (var s of seeds) {
ctx.fillRect(s.x * cellSize, s.y * cellSize, cellSize, cellSize);
}
}
Wait, but seeds are the initial cells. But their cell is already colored with their color, so drawing a black rectangle on top would obscure it? Hmm, better to draw a small dot? Or maybe the seeds are not drawn over the grid? Alternatively, just use a different color for the seed's own cell.
Alternatively, maybe the seeds are just the starting points, so drawing a small black square on top.
Alternatively, in the draw function, after filling the cell with the color, the seed's cell can be drawn as a black square.
Alternatively, maybe it's better to not draw the seed's cell's color, but that complicates.
Alternatively, perhaps the seeds are represented as their color, but with a black border or something.
Alternatively, the code above, where the seeds are drawn as black squares over their cell's color. The cell's color is set to their own color, so the black square will be on top.
So in the draw function, after filling the cells with their colors, draw the seeds as black squares.
But the initial cell of each seed is already colored with their color. So the black square will just outline the seed's starting point.
Alternatively, to make the seed stand out, perhaps make the seed's cell a darker version of their color, or add a small circle.
Alternatively, for simplicity, just draw a black square over it.
Alternatively, perhaps the seeds are just not needed in the drawing, but the user can see their starting points from the grid.
Alternatively, for this problem, maybe it's okay.
6. The initial start:
window.onload = function() {
reset();
animating = true;
animate();
};
But in the HTML, the canvas and the count element need to be set up.
Putting all this together in the HTML and JavaScript:
But since the user wants me to create the code, here's the full code:
Wait, the user said "Create the code", so I need to present it in a way that is a complete HTML page.
But the user might expect that the code is provided as a script in an HTML page, including the canvas and the count display.
So here's the full code:
```html
<!DOCTYPE html>
<html>
<body>
<canvas id="c" width="500" height="500"></canvas>
<div id="count"></div>
<script>
const canvas = document.getElementById('c');
const ctx = canvas.getContext('2d');
const gridWidth = 100;
const gridHeight = 100;
const cellSize = 5;
const canvasWidth = gridWidth * cellSize;
const canvasHeight = gridHeight * cellSize;
canvas.width = canvasWidth;
canvas.height = canvasHeight;
let grid = Array(gridHeight).fill(0).map(() => Array(gridWidth).fill(0));
let seeds = [];
let animating = false;
function reset() {
grid = Array(gridHeight).fill(0).map(() => Array(gridWidth).fill(0));
seeds = [];
const seedCount = 3 + Math.floor(Math.random() * 8);
let added = 0;
while (added < seedCount) {
const x = Math.floor(Math.random() * gridWidth);
const y = Math.floor(Math.random() * gridHeight);
if (grid[y][x] === 0) {
grid[y][x] = added + 1;
seeds.push({
x, y,
color: added + 1,
queue: [[x, y]]
});
added++;
}
}
}
function animate() {
requestAnimationFrame(animate);
if (!animating) return;
let hasMore = false;
// Process all directions for each seed's current queue
const directions = [[-1,0], [1,0], [0,-1], [0,1]];
for (const seed of seeds) {
const nextQueue = [];
for (const [x, y] of seed.queue) {
for (const [dx, dy] of directions) {
const nx = x + dx;
const ny = y + dy;
if (nx >= 0 && nx < gridWidth && ny >= 0 && ny < gridHeight) {
if (grid[ny][nx] === 0) {
grid[ny][nx] = seed.color;
nextQueue.push([nx, ny]);
}
}
}
}
seed.nextQueue = nextQueue;
}
// Update queues and check if any progress was made
for (const seed of seeds) {
const currentQueue = seed.nextQueue;
seed.queue = currentQueue;
seed.nextQueue = [];
if (currentQueue.length > 0) hasMore = true;
}
draw();
if (!hasMore) {
animating = false;
document.getElementById('count').textContent = `Cells claimed: ${grid.flat().filter(v => v > 0).length}`;
setTimeout(() => {
reset();
animating = true;
}, 1000);
}
}
function draw() {
ctx.clearRect(0, 0, canvasWidth, canvasHeight);
ctx.fillStyle = '#000'; // default background?
ctx.fillRect(0,0,canvasWidth, canvasHeight);
// Draw grid cells
for (let y = 0; y < gridHeight; y++) {
for (let x = 0; x < gridWidth; x++) {
const colorIndex = grid[y][x];
if (colorIndex > 0) {
const hue = (colorIndex * 36) % 360;
ctx.fillStyle = `hsl(${hue}, 50%, 50%)`;
ctx.fillRect(x * cellSize, y * cellSize, cellSize, cellSize);
}
}
}
// Draw seeds (starting points)
ctx.fillStyle = '#000';
for (const seed of seeds) {
ctx.fillRect(seed.x * cellSize, seed.y * cellSize, cellSize, cellSize);
}
}
reset();
animating = true;
animate();
</script>
</body>
</html>
```
Wait, in the animate function, when checking for neighbors, I had to use the four directions. Also, in the initial reset function, seeds are set with their color, and the grid is correctly initialized.
Additionally, in the draw function, I set the canvas background to black, then draw the colored cells. The seeds are drawn as black squares on top, so they will stand out.
But in the initial grid, each seed's starting cell is set to their color (e.g., seed.color = 1, so grid[y][x] =1), and then the black square is drawn over it, so the seed's cell will be black, but the surrounding cells are their color.
Wait, but that might make the seeds' cells black, which is okay to indicate they are starting points.
However, in the grid initialization, the seed's cell is already filled with their color, but the seed's drawing covers it with black. So the user can see the seed locations as black squares.
Testing this code, I think it should work.
Now, when the animation completes, it shows the total number of cells claimed (which is the entire grid, so gridWidth * gridHeight). But in the `reset()` function, seedCount is the number of seeds, but the problem might want to count the number of seeds. Wait the user's question says "Create a program that...", but in the problem statement, the user's instruction was just "Create".
Wait, the user's actual problem might be different. Wait, looking back:
The user's original instruction says:
"Create a program that..."
Wait, no, the user's instruction is:
The user says "Create a program that...", but the actual instruction is in Chinese, but in the given problem, the user says "Create a program that...".
Wait, no, the user's instruction is in the initial message: "Create a program that...". But in the given example, the user provided the problem and the example solution. However, in this case, the user is asking for me to create a program (as per the original instruction).
Wait, the user's actual instruction is in the first paragraph. Let me confirm again:
The user's exact instruction is:
"Create a program that..."
But perhaps the user is asking for a program that generates a grid where each cell is colored according to the nearest seed, which is the classic Voronoi diagram problem, and the code I provided is doing that?
Wait, in the code above, the cells are colored based on the seed's color. Each cell is assigned the color of the first seed that reaches it, so it's like a BFS propagation of each seed's color, leading to a Voronoi diagram.
Yes, that is correct.
Additionally, after the animation completes, the count shows the number of cells claimed (which is all cells except possibly overlaps?), but since all cells are filled, `grid.flat().filter(v => v>0).length` should equal gridWidth * gridHeight, so maybe the count is redundant. Perhaps the user intended to show the number of seeds, but perhaps the problem is different.
Wait, the problem might have been a mistranslation, but assuming that the code is correct for the task described, the code should be okay.
In the draw function, each cell is colored based on the first seed that reaches it (since once a cell is colored, further seeds can't overwrite it). So the coloring is based on proximity (since it's a BFS, each seed propagates at the same speed, so the closest seed will color the cell first).
Yes, so this code should create a Voronoi diagram with seeds placed randomly and visualized with colors, then showing the number of cells (the entire grid) as "Cells claimed".
Wait but the seedCount is the number of seeds, but the count displayed is the total cells. Maybe the user's original problem might be different, but given the information, this code seems appropriate.
Therefore, this should be the correct answer.