On Monday, 12 December 2022 at 06:02:27 UTC, Ferhat Kurtulmuş
wrote:
https://rosettacode.org/wiki/Bitmap/Flood_fill
The https://rosettacode.org/wiki/Bitmap/Flood_fill#D looks like a
DFS implementation. The end result is the same, but the order in
which the pixels to fill are reached is different. My
understanding is that the requested "progressive fill" and "not
all at once but building up" means that some sort of animation is
needed with multiple frames showing how the area is getting
gradually filled.
Here's a better implementation of my BFS code:
```D
import std;
struct point { int x, y; }
void show_grid(char[][] grid) {
foreach (ref row ; grid)
writeln(row);
writeln;
}
void animated_fill(char[][] grid, point[] starting_points) {
auto height = grid.length;
if (height == 0)
return;
auto width = grid[0].length;
struct xpoint { int x, y, dist_from_start; }
auto queue = uninitializedArray!(xpoint[])(width * height);
size_t start, end;
foreach (p ; starting_points) {
if (grid[p.y][p.x] == '.') {
queue[end++] = xpoint(p.x, p.y, 0);
grid[p.y][p.x] = '#';
}
}
int current_dist = -1;
while (start < end) {
auto p = queue[start++];
if (p.dist_from_start > current_dist) {
show_grid(grid);
current_dist = p.dist_from_start;
}
if (p.y + 1 < height && grid[p.y + 1][p.x] == '.') {
queue[end++] = xpoint(p.x, p.y + 1, p.dist_from_start +
1);
grid[p.y + 1][p.x] = '#';
}
if (p.y - 1 >= 0 && grid[p.y - 1][p.x] == '.') {
queue[end++] = xpoint(p.x, p.y - 1, p.dist_from_start +
1);
grid[p.y - 1][p.x] = '#';
}
if (p.x + 1 < width && grid[p.y][p.x + 1] == '.') {
queue[end++] = xpoint(p.x + 1, p.y, p.dist_from_start +
1);
grid[p.y][p.x + 1] = '#';
}
if (p.x - 1 >= 0 && grid[p.y][p.x - 1] == '.') {
queue[end++] = xpoint(p.x - 1, p.y, p.dist_from_start +
1);
grid[p.y][p.x - 1] = '#';
}
}
}
void main() {
auto grid = ["....@.....".dup,
"....@@@@..".dup,
"..........".dup];
auto height = grid.length.to!int;
auto width = grid[0].length.to!int;
const number_of_starting_points = 2;
auto random_points = new point[](number_of_starting_points);
foreach (ref p ; random_points)
p = point(uniform(0, width), uniform(0, height));
animated_fill(grid, random_points);
}
```
And here's a possible result with a small grid (the "@" cells are
acting as "walls"):
```
...#@.....
....@@@@..
.......#..
..##@.....
...#@@@@..
......###.
.###@.....
..##@@@@#.
...#.#####
####@...#.
.###@@@@##
..########
####@..###
####@@@@##
.#########
####@.####
####@@@@##
##########
####@#####
####@@@@##
##########
```
