|
|
|
This thread is locked; no one can reply to it.
|
| Floodfill...ish... math. |
|
Chris Katko
Member #1,881
January 2002
 |
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"} 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"} 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. -----sig: |
|
SiegeLord
Member #7,827
October 2006
 |
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: 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}
"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18 |
|
|
