// InkFall 0.2
// David A. Mellis
// 17 September 2004

// divide stream size when it splits
// fall slowly

int NONE = -1, TOP = 0, LEFT = 1, BOTTOM = 2, RIGHT = 3, CENTER = 4, NUM_DIRS = 5;
int[] dx = { 0, -1, 0, 1 };
int[] dy = { -1, 0, 1, 0 };
int CELLS_ACROSS = 10, CELLS_DOWN = 10;
boolean[][][] walls = new boolean[CELLS_ACROSS][CELLS_DOWN][4];
int[][] height = new int[CELLS_ACROSS][CELLS_DOWN];
int SIZE = 15;
int[][] lowest_from_here = new int[CELLS_ACROSS][CELLS_DOWN];
boolean[][] searched = new boolean[CELLS_ACROSS][CELLS_DOWN];
boolean[][] filled = new boolean[CELLS_ACROSS][CELLS_DOWN];
boolean[][] sliding = new boolean[CELLS_ACROSS][CELLS_DOWN];
boolean[][][] falling = new boolean[CELLS_ACROSS][CELLS_DOWN][NUM_DIRS];
boolean done = true;

void setup()
{
  size(CELLS_ACROSS * SIZE + 1, CELLS_DOWN * SIZE + 1);
  framerate(10);
}

void reset()
{
  background(200, 200, 200);

  // generate walls on the tops and bottoms of cells
  for (int i = 0; i < CELLS_ACROSS; i++) {
    for (int j = 0; j < CELLS_DOWN - 1; j++)
      walls[i][j][BOTTOM] = walls[i][j + 1][TOP] = random(10) < 5;
    
    walls[i][CELLS_DOWN - 1][BOTTOM] = true;
  }
        
  // generate walls on the sides of cells
  for (int j = 0; j < CELLS_DOWN; j++) {
    for (int i = 0; i < CELLS_ACROSS - 1; i++)
      walls[i][j][RIGHT] = walls[i + 1][j][LEFT] = random(10) < 5 && j > 0;
      
    walls[0][j][LEFT] = walls[CELLS_ACROSS - 1][j][RIGHT] = true;  
  }

  clear(height, CELLS_ACROSS, CELLS_DOWN, 0);
}
  
void loop()
{
  if (done)
    reset();

  done = true;
  clear(sliding, CELLS_ACROSS, CELLS_DOWN);
  clear(searched, CELLS_ACROSS, CELLS_DOWN);
  clear(filled, CELLS_ACROSS, CELLS_DOWN);
  clear(falling, CELLS_ACROSS, CELLS_DOWN, 5);
  clear(lowest_from_here, CELLS_ACROSS, CELLS_DOWN, -1);
  fall(CELLS_ACROSS / 2, 0, CENTER);
  
  drawInk();
  drawWalls();
}

void mouseReleased()
{
  reset();
}

void keyReleased()
{
  reset();
}

// returns whether or not ink can fall below this cell
void fall(int x, int y, int side)
{
  if (!inBounds(x, y))
    return;

  if (side != NONE)    
    falling[x][y][side] = true;
    
  if (!empty(x, y) || walls[x][y][BOTTOM])
    fill(x, y);
  else
    fall(x, y + 1, side);
}

void fill(int x, int y)
{
  int fill_at_or_below;
  
  // we do one search to find the lowest level that the ink can go...
  fill_at_or_below = findLowestInkDest(x, y);
  
  // ...and another search to fill the cells at that level
  fillAtOrBelow(x, y, NONE, fill_at_or_below);
}

// returns the lowest level (greatest y) that ink can get to from this cell
int findLowestInkDest(int x, int y)
{
  if (!inBounds(x, y))
    return -1;
    
  if (searched[x][y])
    return lowest_from_here[x][y];
    
  searched[x][y] = true;
  
  if (walls[x][y][BOTTOM] || full(x, y + dy[BOTTOM]))
    sliding[x][y] = true;

  // if ink can fall, we care only about the level it falls from, not the level it falls to    
  if (empty(x, y) && !walls[x][y][BOTTOM] && !full(x, y + dy[BOTTOM]))
    lowest_from_here[x][y] = y + dy[BOTTOM];
  else {    
    int greatest_y = -1;
    
    if (!full(x, y))
      greatest_y = y;
    
    // if this cell is full, ink can push up into cell above
    if (!walls[x][y][TOP] && full(x, y))
      greatest_y = max(greatest_y, findLowestInkDest(x, y + dy[TOP]));
      
    if (!walls[x][y][BOTTOM])
      greatest_y = max(greatest_y, findLowestInkDest(x, y + dy[BOTTOM]));
    
    if (!walls[x][y][LEFT])
      greatest_y = max(greatest_y, findLowestInkDest(x + dx[LEFT], y));
      
    if (!walls[x][y][RIGHT])
      greatest_y = max(greatest_y, findLowestInkDest(x + dx[RIGHT], y));
  
    lowest_from_here[x][y] = greatest_y;
  }
  
  return lowest_from_here[x][y];
}

void fillAtOrBelow(int x, int y, int side, int fill_at_or_below)
{
  if (!inBounds(x, y))
    return;
    
  // if the ink spills over, let it fall
  if (empty(x, y) && !walls[x][y][BOTTOM] && !full(x, y + dy[BOTTOM])) {
    fall(x, y + 1, side);
    return;
  }

  // if we do this before spilling over the sides, we won't draw ink
  // falling along both sides of a partially full cell    
  if (filled[x][y])
    return;
    
  filled[x][y] = true;
  
  // if this cell is full, ink can push up into cell above
  if (!walls[x][y][TOP] && full(x, y))
    fillAtOrBelow(x + dx[TOP], y + dy[TOP], side, fill_at_or_below);

  // do this after checking the cell above so we don't search above just filled cells      
  if (!full(x, y) && y >= fill_at_or_below) {
    height[x][y]++;
    done = false;
  }
    
  if (!walls[x][y][BOTTOM])
    fillAtOrBelow(x + dx[BOTTOM], y + dy[BOTTOM], side, fill_at_or_below);
    
  if (!walls[x][y][LEFT])
    fillAtOrBelow(x + dx[LEFT], y + dy[LEFT], RIGHT, fill_at_or_below);
      
  if (!walls[x][y][RIGHT])
    fillAtOrBelow(x + dx[RIGHT], y + dy[RIGHT], LEFT, fill_at_or_below);
}

boolean empty(int x, int y)
{
  return height[x][y] == 0;
}

boolean full(int x, int y)
{
  return height[x][y] == SIZE;
}

boolean inBounds(int x, int y)
{
  return x >= 0 && x < CELLS_ACROSS && y >= 0 && y < CELLS_DOWN;
}

void clear(boolean[][] m, int x, int y)
{
  for (int i = 0; i < x; i++)
    for (int j = 0; j < y; j++)
      m[i][j] = false;
}

void clear(int[][] m, int x, int y, int value)
{
  for (int i = 0; i < x; i++)
    for (int j = 0; j < y; j++)
      m[i][j] = value;
}

void clear(boolean[][][] m, int x, int y, int z)
{
  for (int i = 0; i < x; i++)
    for (int j = 0; j < y; j++)
      for (int k = 0; k < z; k++)
        m[i][j][k] = false;
}

void drawWalls()
{
  stroke(255, 0, 0);
  
  for (int i = 0; i < CELLS_ACROSS; i++)
    for (int j = 0; j < CELLS_DOWN; j++) {
      if (walls[i][j][BOTTOM])
        line(i * SIZE, (j + 1) * SIZE, (i + 1) * SIZE, (j + 1) * SIZE);
      if (walls[i][j][TOP])
        line(i * SIZE, j * SIZE, (i + 1) * SIZE, j * SIZE);
      if (walls[i][j][LEFT])
        line(i * SIZE, j * SIZE, i * SIZE, (j + 1) * SIZE);
      if (walls[i][j][RIGHT])
        line((i + 1) * SIZE, j * SIZE, (i + 1) * SIZE, (j + 1) * SIZE);
    }
}

void drawInk()
{
  fill(0, 0, 0);
  noStroke();
  
  for (int i = 0; i < CELLS_ACROSS; i++) {
    for (int j = 0; j < CELLS_DOWN; j++) {
      rect(i * SIZE + 1, (j + 1) * SIZE - height[i][j], SIZE, height[i][j]);
      
      if (sliding[i][j])
        rect(i * SIZE, (j + 1) * SIZE - 1, SIZE + 1, 1);

      for (int side = 0; side < NUM_DIRS; side++) {        
        if (falling[i][j][side]) {
          int[] offset = { -1, 1, -1, SIZE - 1, SIZE / 2 };
          rect(i * SIZE + offset[side], j * SIZE - 1, 1, SIZE + 1);
        }
      }
    }
  }
}