www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Graphical progressive fill

reply Joel <joelcnz gmail.com> writes:
I've been trying to fill in areas with a colour but can't work it 
out. I want something like the effect where it fills with 
diamonds. Not all at once but building up in the main program 
loop.
Dec 10 2022
next sibling parent thebluepandabear <therealbluepandabear protonmail.com> writes:
On Sunday, 11 December 2022 at 06:50:44 UTC, Joel wrote:

 I've been trying to fill in areas with a colour but can't work 
 it out. I want something like the effect where it fills with 
 diamonds. Not all at once but building up in the main program 
 loop.


























There should be some ANSI sequences that allow you to do such a 
thing (as in clearing the console and refreshing), not familiar 
with any though from the top of my head.
Dec 11 2022
prev sibling next sibling parent reply Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
On Sunday, 11 December 2022 at 06:50:44 UTC, Joel wrote:

 I've been trying to fill in areas with a colour but can't work 
 it out. I want something like the effect where it fills with 
 diamonds. Not all at once but building up in the main program 
 loop.


I'm not sure if I understood the question correctly, but maybe 
https://en.wikipedia.org/wiki/Breadth-first_search approach will 
do the job?

Basically have a queue for point coordinates. Add your starting 
point to it (or multiple starting points). In a loop keep 
extracting points from the front of the queue, paint this point 
with a color and add non-painted neighbors of this point to the 
end of the queue. Keep going until the queue is empty.

Example:
```D
import std;

const width = 78;
const height = 10;
const number_of_starting_points = 5;

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; }

   DList!xpoint queue;
   foreach (p ; starting_points)
     queue.insertBack(xpoint(p.x, p.y, 0));

   int current_dist = 0;
   while (!queue.empty) {
       auto p = queue.front;
       queue.removeFront;

       if (grid[p.y][p.x] != '.')
         continue; // only fill the dots

       if (p.dist_from_start > current_dist) {
         show_grid(grid);
         current_dist = p.dist_from_start;
       }



       if (p.y + 1 < height)
         queue.insertBack(xpoint(p.x, p.y + 1, p.dist_from_start + 
1));
       if (p.y - 1 >= 0)
         queue.insertBack(xpoint(p.x, p.y - 1, p.dist_from_start + 
1));
       if (p.x + 1 < width)
         queue.insertBack(xpoint(p.x + 1, p.y, p.dist_from_start + 
1));
       if (p.x - 1 >= 0)
         queue.insertBack(xpoint(p.x - 1, p.y, p.dist_from_start + 
1));
   }
   show_grid(grid);
}

void main() {
   auto grid = new char[][](height, width);
   foreach (ref row ; grid)
     row[] = '.';

   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);
}
```

Instead of a slow DList, it's also possible to just use a regular 
static array and two indexes for the start and the end of the 
queue. With a good implementation of BFS, this array won't need 
to store more than `grid_width * grid_height` elements. My 
implementation isn't a good one, but can be improved to do it.
Dec 11 2022
parent Joel <joelcnz gmail.com> writes:
On Monday, 12 December 2022 at 04:49:09 UTC, Siarhei Siamashka 
wrote:

 On Sunday, 11 December 2022 at 06:50:44 UTC, Joel wrote:

 I've been trying to fill in areas with a colour but can't work 
 it out. I want something like the effect where it fills with 
 diamonds. Not all at once but building up in the main program 
 loop.


 I'm not sure if I understood the question correctly, but maybe 
 https://en.wikipedia.org/wiki/Breadth-first_search approach 
 will do the job?

 Basically have a queue for point coordinates. Add your starting 
 point to it (or multiple starting points). In a loop keep 
 extracting points from the front of the queue, paint this point 
 with a color and add non-painted neighbors of this point to the 
 end of the queue. Keep going until the queue is empty.

 Example:
 ```D
 import std;

 const width = 78;
 const height = 10;
 const number_of_starting_points = 5;

 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; }

   DList!xpoint queue;
   foreach (p ; starting_points)
     queue.insertBack(xpoint(p.x, p.y, 0));

   int current_dist = 0;
   while (!queue.empty) {
       auto p = queue.front;
       queue.removeFront;

       if (grid[p.y][p.x] != '.')
         continue; // only fill the dots

       if (p.dist_from_start > current_dist) {
         show_grid(grid);
         current_dist = p.dist_from_start;
       }



       if (p.y + 1 < height)
         queue.insertBack(xpoint(p.x, p.y + 1, p.dist_from_start 
 + 1));
       if (p.y - 1 >= 0)
         queue.insertBack(xpoint(p.x, p.y - 1, p.dist_from_start 
 + 1));
       if (p.x + 1 < width)
         queue.insertBack(xpoint(p.x + 1, p.y, p.dist_from_start 
 + 1));
       if (p.x - 1 >= 0)
         queue.insertBack(xpoint(p.x - 1, p.y, p.dist_from_start 
 + 1));
   }
   show_grid(grid);
 }

 void main() {
   auto grid = new char[][](height, width);
   foreach (ref row ; grid)
     row[] = '.';

   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);
 }
 ```

 Instead of a slow DList, it's also possible to just use a 
 regular static array and two indexes for the start and the end 
 of the queue. With a good implementation of BFS, this array 
 won't need to store more than `grid_width * grid_height` 
 elements. My implementation isn't a good one, but can be 
 improved to do it.


Thanks for the help. I got it working with my crazy 
drawing/animation program. Though I want to be able to do stuff 
while it's slowly filling the areas (including more filling 
spots). (I might've used the second example if I was paying more 
attention).

```D
     struct Fill {
         Dot print; // what it draws
         Dot sample; // what it draws on
         bool wipe;
         struct xpoint { int x, y, dist_from_start; }
         DList!xpoint queue;
         int current_dist;

         void start(Dot d) {
             print=d;
             sample=g_df.sample(d.pos);
             if (print==sample) {
                 g_history.updateHistory("Redundant filling (print 
and sample colours identcal)");
                 return;
             }

             queue.insertBack(xpoint(print.pos.Xi, print.pos.Yi, 
0));
             current_dist=0;
             // fillOn=true;
             process;
         }

         void process() {
             // if (queue.empty) {
             //     fillOn=doFillDraw=false;
             //     return;
             // }

             bool done = false;
             while(!queue.empty && ! done && ! 
g_keys[SDL_SCANCODE_ESCAPE].keyTrigger) {
                 //Handle events on queue
                 while(SDL_PollEvent(&gEvent)!=0) {
                     //User requests quit
                     if (gEvent.type == SDL_QUIT)
                         done = true;
                 }

                 SDL_PumpEvents();

                 auto p = queue.front;
                 queue.removeFront;

                 sample.pos=Point(p.x, p.y);
                 if (g_df.sample(p.x,p.y)!=sample) {
                     continue; // only fill the dots
                 }

                 if (p.dist_from_start > current_dist) {
                     if (slow) {
                         g_df.drawTex;
                         SDL_RenderPresent(gRenderer);
                         SDL_Delay(20);
                     }

                     current_dist = p.dist_from_start;
                 }

                 g_df.drawDot(print, p.x,p.y);

                 if (p.y + 1 < HEIGHT)
                     queue.insertBack(xpoint(p.x, p.y + 1, 
p.dist_from_start + 1));
                 if (p.y - 1 >= 0)
                     queue.insertBack(xpoint(p.x, p.y - 1, 
p.dist_from_start + 1));
                 if (p.x + 1 < WIDTH)
                     queue.insertBack(xpoint(p.x + 1, p.y, 
p.dist_from_start + 1));
                 if (p.x - 1 >= 0)
                     queue.insertBack(xpoint(p.x - 1, p.y, 
p.dist_from_start + 1));
             } // while
         } // process
     }
```
Dec 12 2022
prev sibling parent reply Ferhat =?UTF-8?B?S3VydHVsbXXFnw==?= <aferust gmail.com> writes:
On Sunday, 11 December 2022 at 06:50:44 UTC, Joel wrote:

 I've been trying to fill in areas with a colour but can't work 
 it out. I want something like the effect where it fills with 
 diamonds. Not all at once but building up in the main program 
 loop.


























https://rosettacode.org/wiki/Bitmap/Flood_fill
Dec 11 2022
parent Siarhei Siamashka <siarhei.siamashka gmail.com> writes:
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);

     }
   }

   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);

       }
       if (p.y - 1 >= 0 && grid[p.y - 1][p.x] == '.') {
         queue[end++] = xpoint(p.x, p.y - 1, p.dist_from_start + 
1);

       }
       if (p.x + 1 < width && grid[p.y][p.x + 1] == '.') {
         queue[end++] = xpoint(p.x + 1, p.y, p.dist_from_start + 
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);

       }
   }
}

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"):
```

....    ..

























```
Dec 11 2022