A more efficient room flooding algorithm

Processing Coding Questions
1

I am attempting to program the visualizations from this video. Essentially, it is a problem of propagating a signal through a graph. In this case, the graph is the canvas, the vertices are the pixels, the links exist between neighboring pixels (so each pixel has at most 4 links), and the signal is their color. Until the canvas isn’t fully colored, I pick an uncolored pixel and begin propagating the data by visiting the neighbors of this pixel that I haven’t visited yet. I store the pixels that have already been visited, but which still contain unvisited neighbors, in a stack data structure, and when its size reaches 0, that tells me the given room has been fully flooded, so then I move onto the next room (if there is one). The video also talks about a parameter that determines the probability with which each link is initialized as “open” vs “closed”. To me, the most interesting case is when the probability is 50%, which is why I’ve decided to hard-code this in - the probability is chosen with (int)random(2), and the result represents the 50/50 case.

Now then, below is my code, and my question is, is there any way to optimize it further? It’s already pretty fast, as I tried my best to make it efficient. Also, one small thing that I did not anticipate is how much memory it uses - I have to allocate gigabytes of RAM for canvas sizes above 1000×1000, and I do not know why that is; is it normal for this kind of program?

int colors = 256 * 256 * 256, offset;
PGraphics pg;

class Cell {
  int group = -1, id, x, y;
  int[][] next;
  boolean dirCond[];
  color c;
  Cell(int id) {
    this.id = id;
    this.x = id % pg.width;
    this.y = id / pg.width;
    next = new int[][]{
      {id - pg.width, (int)random(2)},
      {id - 1, (int)random(2)},
      {id + 1, (int)random(2)},
      {id + pg.width, (int)random(2)}
    };
    if (x > 0) next[1][1] = cells[id - 1].next[2][1];
    if (y > 0) next[0][1] = cells[id - pg.width].next[3][1];
    dirCond = new boolean[]{y > 0, x > 0, x < pg.width - 1, y < pg.height - 1};
  }
}

Cell[] cells;

void setup() {
  pg = createGraphics(600, 600);
  cells = new Cell[pg.width * pg.height];
  offset = (int)random(colors);
  for (int i = 0; i < cells.length; i++)
    cells[i] = new Cell(i);
  int[] stack = new int[cells.length];
  for (int id = 0, g = 0; id != -1; g++, id = getNext(id)) {
    int rand = (int)random(colors);
    color c = color(rand % 256, rand / 256 % 256, rand / 256 / 256);
    cells[stack[0] = id].group = g;
    for (int ptr = 0; ptr != -1; ptr--) {
      Cell cell = cells[stack[ptr]];
      cell.c = c;
      for (int i = 0; i < 4; i++) {
        int next = cell.next[i][0];
        if (cell.dirCond[i] && cells[next].group == -1 && cell.next[i][1] < 1)
          cells[stack[ptr++] = next].group = cell.group;
      }
    }
  }
  pg.beginDraw();
  for (Cell cell : cells) {
    pg.stroke(cell.group == -1 ? 255 : cell.c);
    pg.point(cell.x, cell.y);
  }
  pg.endDraw();
  pg.save("image.png");
  exit();
}

int getNext(int prev) {
  for (int i = prev + 1; i < cells.length; i++) {
    if (cells[i].group == -1)
      return i;
  }
  return -1;
}
2

So managed to get it running a bit faster for you by using the pixels of a PImage instead of drawing points to a PGraphics layer, ive commented all the changes i made and commented out the drawing of the points, have a look through and see if its what you were wanting, I didnt change the overall method but still, using pixels is far faster

int colors = 256 * 256 * 256, offset;
PImage pg; // CHANGED FROM PGRAPHICS

class Cell {
  int group = -1, id, x, y;
  int[][] next;
  boolean dirCond[];
  color c;
  Cell(int id) {
    this.id = id;
    this.x = id % pg.width;
    this.y = id / pg.width;
    next = new int[][]{
      {id - pg.width, (int)random(2)},
      {id - 1, (int)random(2)},
      {id + 1, (int)random(2)},
      {id + pg.width, (int)random(2)}
    };
    if (x > 0) next[1][1] = cells[id - 1].next[2][1];
    if (y > 0) next[0][1] = cells[id - pg.width].next[3][1];
    dirCond = new boolean[]{y > 0, x > 0, x < pg.width - 1, y < pg.height - 1};
  }
}

Cell[] cells;

void setup() {
  pg = createImage(600, 600, RGB); // CREATE PIMAGE FOR DISPLAY
  cells = new Cell[pg.width * pg.height];
  offset = (int)random(colors);
  for (int i = 0; i < cells.length; i++)
    cells[i] = new Cell(i);
  int[] stack = new int[cells.length];
  for (int id = 0, g = 0; id != -1; g++, id = getNext(id)) {
    int rand = (int)random(colors);
    color c = color(rand % 256, rand / 256 % 256, rand / 256 / 256);
    cells[stack[0] = id].group = g;
    for (int ptr = 0; ptr != -1; ptr--) {
      Cell cell = cells[stack[ptr]];
      cell.c = c;
      for (int i = 0; i < 4; i++) {
        int next = cell.next[i][0];
        if (cell.dirCond[i] && cells[next].group == -1 && cell.next[i][1] < 1)
          cells[stack[ptr++] = next].group = cell.group;
      }
    }
  }
  pg.loadPixels(); // LOAD PIXELS INSTEAD OF BEGINDRAW
  for (Cell cell : cells) {
    // COMMENTED OUT BOTH THESE LINES TO USE THE PIXELS INSTEAD
    
    //pg.stroke(cell.group == -1 ? 255 : cell.c);
    //pg.point(cell.x, cell.y);
    
    int index = cell.x + cell.y * pg.width; // CREATES INDEX INTO PIXEL 1D ARRAY
    pg.pixels[index] = color(cell.group == -1 ? 255 : cell.c); // COLORS THE INDIVIDUAL PIXEL
  }
  pg.updatePixels(); // UPDATE PIXELS INSTEAD OF ENDDRAW
  pg.save("image.png");
  exit();
}

int getNext(int prev) {
  for (int i = prev + 1; i < cells.length; i++) {
    if (cells[i].group == -1)
      return i;
  }
  return -1;
}
1 Like
3

After running a millis timer on it, yours takes about 1.5 seconds on my pc but with the pixel operation changeover it takes less than 400 milliseconds, so its more than 3 times the speed with that simple alteration, as for a better algorithm maybe someone has an even better idea.

1 Like
4

That’s a pretty cool improvement indeed. Is it constant or linear? It seems it should be constant, meaning it shouldn’t matter, unless for some reason the image writing part scales worse than the algorithm itself, which would be an interesting twist.

5

Im not to sure mate, it just goes through every pixel on the PImage array and colors them one by one, would be far better as a shader that could offload the rendering to the graphics card and do all the pixels in parallel but havent been able to completely figure out how to do that

1 Like
6

Both of your algorithms (and mine below) are O(N) in number of pixels. You are visiting each pixel a fixed number of times independent of how many pixels are in the image. So if you generate an image 4x as big, it should take 4x as long to generate. IN THEORY.

In practice, unless you are doing a very complicated computation, which this is not, computers are nearly always waiting for memory accesses. That means, if you want speed, you need to reduce as many memory queries, especially to random access objects, as you can. Flat arrays of native types are the ideal. Even then, when your arrays are big enough, they will overflow memory caches which will cause bigger slow-downs at various thresholds. While 4x size might take 4x time, 5x size might be 20x time.

So, in my version, I got rid of your array of Cell objects and your stack and replaced them with an array of a single byte per cell (along with the RGB image which probably takes up 32-bits per pixel internally). The byte stores a 0 for unvisited cells or a direction 1-4 to the previous cell or 5 if it’s the first cell in the group. When I use the direction, I subtract 1 from it so they are 0-3 with 4 representing the base cell.

I don’t pre-generate or store the openings between neighboring cells, but instead test them on the fly only when needed. In theory, the existence or not of neighboring doors should be based on a spatial hash function which given an (i,j) and direction always gives the same door value (open or closed) no matter what order we test them in. In practice, we can get away with using a generic linear random() function as long as we only test each door a single time which my code does.

I take an extra shortcut in wrapping the image in that my left and right edges are one pixel off – the right edge wraps to the left one pixel down. You could fix it by breaking ic into i and j coordinates and doing the wrapping if that’s what you need, but it’ll slow it a bit. Aesthetically, it make no difference.

I included a scaleFactor that generates images multiple sizes bigger than the window. On my 8 year old machine, with a factor of 2, I generate 2400x2400 images in approximately 420ms. I don’t think shaders would provide any simple mechanism for speeding it up, but there might be some convoluted way to do so.

PImage im;
void setup() {
  size( 1200, 1200, P2D );
  int scaleFactor = 1;
  im = createImage( width*scaleFactor, height*scaleFactor, ARGB );
  noLoop();
}

void draw() {
  int t = millis();
  percolate( im, 0.5 );
  println( millis()-t );
  image( im, 0, 0, width, height );
}

void keyPressed() {
  redraw();
}

void percolate( PImage im, float pc ) {
  int N = im.width * im.height;
  im.loadPixels();
  byte[] cells = new byte[N];
  int[] next = { 1, im.width, -1, -im.width, 0 };
  for( int i=0; i<N; i++ ) {
    if( cells[ i ] != 0 ) continue;
    color clr = color( random(255), random(255), random(255) );
    int ic = i;
    int d = 4;
    do {
      ic = (ic + next[d] + N) % N;
      int startDir = 0;
      if( cells[ic] == 0 ) {
        if( d < 4 ) d = (d+2)%4;  // reverse the direction
        cells[ic] = (byte)(d+1);
        im.pixels[ic] = clr;
      } else {
        startDir = ((d+2)%4) + 1;  // reverse dir + 1
        d = cells[ic] - 1;
      }
      for( int dir=startDir; dir<4; dir++ ) {
        if( cells[ (ic + next[dir] + N) % N ] == 0 && random(1) < pc ) {
          d = dir;
          break;
        }
      }
    } while( d != 4 );
  }
  im.updatePixels();
}
2 Likes
7

The program outputs “The sketch has been resized from 1200?1200 to 1200?1061 by the window manager.” and when I check the size of the image (if I choose to save it), that’s indeed the dimensions it has. How do I fix this?

8

size() is too big for your monitor. Set the size() to something smaller and use scaleFactor to generate a higher resolution image if that’s what you want. Like if you want 1200x1200, use size(600,600); and scaleFactor = 2;. And use im.save("whatever.png"); to save.

1 Like