Graphical progressive fill

Joel joelcnz at gmail.com
Mon Dec 12 19:02:59 UTC 2022


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;
>       }
>
>       grid[p.y][p.x] = '#';
>
>       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
     }
```


More information about the Digitalmars-d-learn mailing list