Floodfill...ish... math.
Chris Katko

Okay.

Given a square grid that operates with a Von Neumann neighborhood.

Each grid cell has a value. That value can be anything, but let's go with air pressure.

We want each complete logic frame to have every cell "spread out" with its neighbor. All higher pressure cells flow into lower pressure cells as long as there are no obstructing cells.

{"name":"1MVP88Z.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/e\/2ef7530b2d90c9afad20fa99b2204092.png","w":527,"h":518,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/2\/e\/2ef7530b2d90c9afad20fa99b2204092"}1MVP88Z.png

Currently becomes:

{"name":"pAVBrYX.png","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/d\/4da074644056e4172c81fd918d23c6dc.png","w":539,"h":527,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/4\/d\/4da074644056e4172c81fd918d23c6dc"}pAVBrYX.png

The algorithm being used right now, computes for every cell, sum the pressure of all adjacent cells and itself, divided by the number of applicable cells (obstructions are excluded). Cells that have previously been computed for, are noted, and ignored, to prevent overlap. It's all just being averaged.

That all works reasonable enough, eh? But here's the problem, as you might notice from the second image after I explain it:

Say you have a source cell with a value of 256 flowing into an empty hallway. The next one becomes 128. The next, 64, 32, 16, and so on. My math might be off, but you should notice that periodically averaging the pressures each step doesn't "flow" down hallways very well. It stagnants.

I'll end up with a large room with 124, and then a hallway with 110, 95, 80, 66, 52, 39, ... 25. Even after say, 100 iterations, those far away tiles are never going to change much.

SiegeLord

Averaging the values of the cells to get the new value is just a special case of diffusion, which obeys Fick's law. In particular, it is straightforward to show that the 'wavefront' spreads as a square root of iteration.

That said, without sinks your environment should eventually get filled to the value of the source. It happens in my example program:

#SelectExpand
1#include <allegro5/allegro.h> 2#include <allegro5/allegro_font.h> 3 4#include <vector> 5 6int main() 7{ 8 const size_t w = 16; 9 int buffer_idx = 0; 10 std::vector<double> field[2]; 11 12 field[0].resize(w * w, 0); 13 field[1].resize(w * w, 0); 14 15 al_init(); 16 auto d = al_create_display(512, 512); 17 al_init_font_addon(); 18 auto q = al_create_event_queue(); 19 al_register_event_source(q, al_get_display_event_source(d)); 20 21 auto bmp = al_create_bitmap(w, w); 22 23 auto font = al_create_builtin_font(); 24 25 for(int ii = 0; ii < 1000; ii++) 26 { 27 al_set_target_bitmap(bmp); 28 al_lock_bitmap(bmp, ALLEGRO_PIXEL_FORMAT_ANY, ALLEGRO_LOCK_READWRITE); 29 for(int y = 0; y < w; y++) 30 { 31 for(int x = 0; x < w; x++) 32 { 33 double new_v = 0.0; 34 if(x == w / 2 && y == w / 2) 35 { 36 new_v = 1.0; 37 } 38 else 39 { 40 auto v = field[buffer_idx][x + y * w]; 41 42 int count = 1; 43 if(x > 1) 44 { 45 v += field[buffer_idx][x - 1 + (y + 0) * w]; 46 count += 1; 47 } 48 if(x < w - 1) 49 { 50 v += field[buffer_idx][x + 1 + (y + 0) * w]; 51 count += 1; 52 } 53 if(y > 1) 54 { 55 v += field[buffer_idx][x + 0 + (y - 1) * w]; 56 count += 1; 57 } 58 if(y < w - 1) 59 { 60 v += field[buffer_idx][x + 0 + (y + 1) * w]; 61 count += 1; 62 } 63 new_v = v / count; 64 } 65 field[1 - buffer_idx][x + y * w] = new_v; 66 al_put_pixel(x, y, al_map_rgb_f(new_v, new_v, new_v)); 67 } 68 } 69 al_unlock_bitmap(bmp); 70 al_set_target_bitmap(al_get_backbuffer(d)); 71 al_draw_scaled_bitmap(bmp, 0, 0, w, w, 0, 0, al_get_display_width(d), al_get_display_height(d), 0); 72 al_draw_textf(font, al_map_rgb_f(1, 1, 1), 5, 5, ALLEGRO_ALIGN_LEFT, "Iteration: %d", ii); 73 al_flip_display(); 74 al_rest(0.01); 75 buffer_idx = 1 - buffer_idx; 76 } 77 78 al_flush_event_queue(q); 79 ALLEGRO_EVENT e; 80 al_wait_for_event(q, &e); 81}

Thread #614543. Printed from Allegro.cc