// by Mark Luffel, Georgia Tech, 2009
boolean showEverything = false;
int N = 6;

float[][] potential; // the electric potential at all points
boolean[][] isCandidate; // record which pixels might be selected next
boolean[][] isForm; // record which pixels are part of the dendrite
ArrayList candidates; // record the list of pixels that might be selected next, to prevent rescanning each time
float maxValue, minValue; // the values

public void setup() {
 size(640,480);
 dataSetup();
}

void dataSetup() {
 potential = new float[width][height];
 isCandidate = new boolean[width][height];
 isForm = new boolean[width][height];
 candidates = new ArrayList();

 isCandidate[width/2][height/2] = true; // this is important
 addPixel(width/2, height/2);
}

// index offsets for the local neighborhood
int[][] neighborhood = new int[][] {
 {-1,-1}, {0,-1}, {1,-1},
 {-1, 0},         {1, 0},
 {-1, 1}, {0, 1}, {1, 1}
};
void addPixel(int x, int y) {
 isForm[x][y] = true;
 // remove this location from the candidates
 for(int i = 0; i < candidates.size(); i++) {
   Candidate loc = (Candidate) candidates.get(i);
   if(loc.x == x && loc.y == y) {
     candidates.remove(i);
     break;
   }
 }
 
 if(showEverything) { // this is slow, show the potential field
   for(int i = 0; i < width; i++) {
     for(int j = 0; j < height; j++) {
       potential[i][j] += incrPotential(i,j, x,y);
     }
   }
 } else { // this is the fast-path
   for(int i = 0; i < candidates.size(); i++) {
     Candidate loc = (Candidate)candidates.get(i);
     potential[loc.x][loc.y] += incrPotential(loc.x,loc.y, x,y);
   }
 }
 
 // make any neighbors into candidates if they aren't already
 for(int i = 0; i < neighborhood.length; i++) {
   int
   nx = x+neighborhood[i][0], 
   ny = y+neighborhood[i][1];
   if(nx < 0 || nx >= width || ny < 0 || ny >= height) continue; // skip out-of-bounds neighbors
   if(!isCandidate[nx][ny]) {
     isCandidate[nx][ny] = true; // become a candidate
     float newPotential = potential[nx][ny] = fullPotential(nx, ny); // compute potential from everything that exists
     candidates.add(new Candidate(nx,ny,newPotential));
   }
 }
}

// calculate the potential for a point from scratch
// used when adding a new candidate whose potential hasn't been tracked
float fullPotential(int x, int y) {
 float sum = 0;
 // scan the entire screen
 for(int i = 0; i < width; i++) {
   for(int j = 0; j < height; j++) {
     if(isForm[i][j]) { // if a pixel is part of the dendrite
       // compute its contribution to the potential at this point
       sum += incrPotential(i,j, x,y);
     }
   }
 }
 return sum;
}

// calculate the change in potential
// this is symmetric and isotropic
// changes to this function can result in more complex shapes
float incrPotential(int x, int y, int sx, int sy) {
  // a square distance here works, but it denser and more square ;) 
  return 1 - 0.5f/dist(x,y, sx,sy);
}

// 
void step() {
 // slurp the potential back into our candidate list
 for(int i = 0; i < candidates.size(); i++) {
   Candidate v = (Candidate) candidates.get(i);
   v.potential = potential[v.x][v.y];
 }
 
 // candidates.sort(key = lambda v: v[2])
 Collections.sort(candidates, new PotentialComparator());
 
 // we need the min and max to scale our potentials into the 0-1 range
 // so that our N parameter works
 minValue = ((Candidate)candidates.get(0)).potential;
 maxValue = ((Candidate)candidates.get(candidates.size()-1)).potential;
 float scaling;
 if(minValue == maxValue) {
   scaling = 1;
 } else {
   scaling = 1f/(maxValue-minValue);
 }
 
 // calculate the partial sum,
 // this enables us to pick a uniformly random sample from 0 - potentialSum
 // and then binary search to find use the candidate whose partial sum is closest
 // because the partial sum is sorted by definition,
 // we don't need to sort the list beforehand,
 // the sorting above is just to get the min and max
 float prev = 0;
 for(int i = 0; i < candidates.size(); i++) {
   Candidate loc = (Candidate)candidates.get(i);
   float value = loc.potential;
   value = (value-minValue)*scaling;
   value = pow(value,N); 
   prev = loc.potential = (prev + value);
 }
 float potentialSum = prev;
 
 // pick a candidate
 int index = Collections.binarySearch(candidates, new Candidate(-1, -1, random(potentialSum)), new PotentialComparator());
 if(index < 0) index = -index-1; // get the insertion index, see Collections.binarySearch to understand this ;)
 
 // and add it
 Candidate loc = (Candidate) candidates.get(index);
 addPixel(loc.x, loc.y);
}

// simple placeholder for a site that may be selected for growth
class Candidate {
  public Candidate(int x, int y, float p) {
    this.x = x;
    this.y = y;
    this.potential = p;
  }
  int x,y;
  float potential;
}

// define an ordering based on the potential value of a candidate
// used for sorting and sampling
class PotentialComparator implements Comparator {
 public int compare(Object o1, Object o2) {
   Candidate loc1 = (Candidate)o1, loc2 = (Candidate)o2;
   return Float.compare(loc1.potential, loc2.potential);
 }
}

public void draw() {
 int black = color(0), white = color(255);
 // draw all the pixels, includes some ad-hocery
 loadPixels();
 float scaling = 10/(maxValue-minValue);
 for(int i = 0; i < width; i++) {
   for(int j = 0; j < height; j++) {
     int c;
     if(isForm[i][j]) { // the shape itself
       c = white;
     } else if(showEverything) { // a visualization of the potential field
       // TODO: make this more visually stable
       float t = 64-cos(scaling*(maxValue-potential[i][j]))*64;
       c = color(t,t*0.75f,0);
     } else { // if no visualization
       c = black;
     }
     pixels[i+j*width] = c;
   }
 }
 updatePixels();
 // add 20 pixels each time
 for(int i = 0; i < 20; i++) step();
}

public void keyPressed() {
  // press a number to select sparse (high numbers) vs dense (lower numbers)
  if(key == '1') N = 0;
  if(key == '2') N = 2;
  if(key == '3') N = 4;
  if(key == '4') N = 6;
  if(key == '5') N = 8;
  if(key == '6') N = 10;
  if(key == '7') N = 12;
  if(key == '8') N = 14;
  if(key == '9') N = 16;
  if(key == '0') N = 18;
  if(key == ' ') { // toggle showing potential field
    showEverything = !showEverything;
  }
  
  dataSetup();
}