int WINDOW_SIZE = 500;
int NUM_CELLS = 15;
Cell[][] cells;
int step = 0;   // counter
Cell currentCell;
Cell exitCell;
Stack stack;
boolean finishedGenerating = false;
boolean finishedSolving = false;

void setup() {
 //frameRate(30);
 size(WINDOW_SIZE,WINDOW_SIZE);
 initialize();
}

void initialize() {
 background(0);
 stroke(127);

 float lhs = map(0, 0, NUM_CELLS, 0, width);
 float rhs = map(1, 0, NUM_CELLS, 0, width);
 float cellSize = (rhs-lhs);
 println("Calculated cellSize as " + cellSize);

 cells = new Cell[NUM_CELLS][NUM_CELLS];
 for (int i=0;i<NUM_CELLS;i++) {
   for (int j=0;j<NUM_CELLS;j++) {
     cells[i][j] = new Cell(i,j,cellSize);
   }
 }
 int randx = int(random(NUM_CELLS));
 int randy = int(random(NUM_CELLS));
 currentCell = cells[randx][randy];
 currentCell.visit();
 currentCell.mazeExit = true;
 stack = new Stack();
 stack.push(currentCell);
 exitCell = currentCell;
 finishedGenerating = false;
}

void mouseMoved() {
 String s = "("+nf(getCellX(),0)+","+nf(getCellY(),0)+")";
 //println(s);
}

int getCellX() {
 return (int) map(mouseX,0,width,0,NUM_CELLS);
}
int getCellY() {
 return (int) map(mouseY,0,height,0,NUM_CELLS);
}

void mousePressed() {
 println("Clicked");
 if (finishedGenerating) {
   stack = new Stack();
   for (int i=0;i<NUM_CELLS;i++) {
    for (int j=0;j<NUM_CELLS;j++) {
     cells[i][j].unsearch();
    }
   }
   finishedSolving = false;
   int curx = getCellX();
   int cury = getCellY();
   currentCell = cells[curx][cury];
   currentCell.search();
   currentCell.searchStart = true;
   stack.push(currentCell);
 } else {
   initialize();
 }
}

void draw() {
 if (!finishedGenerating) { generateStep(); }
 if (currentCell != null && finishedGenerating && !finishedSolving) { solveStep(); }
 for (int i=0;i<NUM_CELLS;i++) {
   for (int j=0;j<NUM_CELLS;j++) {
     cells[i][j].draw();
   }
 }
}

void solveStep() {
 println("Solving");
if (finishedSolving) { return; }
// if (stack.search(currentCell) < 0) { stack.push(currentCell); }
boolean valid = false;
 ArrayList available_dirs = new ArrayList();
 if (!currentCell.top) available_dirs.add(0);
 if (!currentCell.right) available_dirs.add(1);
 if (!currentCell.bottom) available_dirs.add(2);
 if (!currentCell.left) available_dirs.add(3);

 while (!valid) {
   int curx = currentCell.getX();
   int cury = currentCell.getY();
   int dir_idx = int(random(available_dirs.size()));
   int dir = ((Integer)available_dirs.get(dir_idx)).intValue();
   println("Search " + dir);

   switch(dir) {
    case 0:
     if (cury > 0 && cells[curx][cury-1].notSearched()) {
       println("Searching north");
       currentCell = cells[curx][cury-1];
       currentCell.search();
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 1:
     if (curx < NUM_CELLS-1 && cells[curx+1][cury].notSearched()) {
       println("Searching east");
       currentCell = cells[curx+1][cury];
       currentCell.search();
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 2:
      if (cury < NUM_CELLS-1 && cells[curx][cury+1].notSearched()) {
       println("Searching south");
       currentCell = cells[curx][cury+1];
       currentCell.search();
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 3:
      if (curx > 0 && cells[curx-1][cury].notSearched()) {
       println("Searching west");
       currentCell = cells[curx-1][cury];
       currentCell.search();
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
   }  // end switch

   if (finishedGenerating && exitCell.equals(currentCell)) {
    finishedSolving = true; 
    valid = true;
   }

   if (!valid && available_dirs.size() == 0) {
//      if (!stack.empty()) { currentCell = (Cell)stack.pop(); }
     if (!stack.empty()) { stack.pop(); currentCell = (Cell)stack.peek(); }
     valid = true; 
   }
 } // end while
}

void generateStep() {
 if (finishedGenerating) { return; }
 boolean valid = false;
 ArrayList available_dirs = new ArrayList();
 for (int i=0;i<4;i++) { available_dirs.add(i); }
 while (!valid) {
   int curx = currentCell.getX();
   int cury = currentCell.getY();
   int dir_idx = int(random(available_dirs.size()));
   int dir = ((Integer)available_dirs.get(dir_idx)).intValue();

   switch(dir) {
    case 0:
     if (cury > 0 && cells[curx][cury-1].notVisited()) {
       println("Going north");
       currentCell.top = false;
       currentCell = cells[curx][cury-1];
       currentCell.visit();
       currentCell.bottom = false;
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 1:
     if (curx < NUM_CELLS-1 && cells[curx+1][cury].notVisited()) {
       println("Going east");
       currentCell.right = false;
       currentCell = cells[curx+1][cury];
       currentCell.visit();
       currentCell.left = false;
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 2:
      if (cury < NUM_CELLS-1 && cells[curx][cury+1].notVisited()) {
        println("Going south");
        currentCell.bottom = false;
       currentCell = cells[curx][cury+1];
       currentCell.visit();
       currentCell.top = false;
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
    case 3:
      if (curx > 0 && cells[curx-1][cury].notVisited()) {
        println("Going west");
        currentCell.left = false;
       currentCell = cells[curx-1][cury];
       currentCell.visit();
       currentCell.right = false;
       stack.push(currentCell);
       valid = true;
     } else { available_dirs.remove(new Integer(dir)); }
     break;
   }  // end switch
   if (!valid && available_dirs.size() == 0) {
     if (!stack.empty()) { currentCell = (Cell)stack.pop(); }
     else { finishedGenerating = true; currentCell = null; }
     valid = true; 
   }
 } // end while
}

class Cell {
 private int x,y;
 float s;
 private boolean visited = false;
 private boolean searched = false;
 public boolean top,left,right,bottom;
 public boolean mazeExit;
 public boolean searchStart;

 Cell(int x, int y, float s) {
   this.x = x;
   this.y = y;
   this.s = s;
   top = true; left = true; right = true; bottom = true;
 }
 public int getX() { return this.x; }
 public int getY() { return this.y; }
 public void visit() { this.visited = true; }
 public void search() { this.searched = true; }
 public void unsearch() { this.searched = false; this.searchStart = false; }
 public boolean notVisited() { return !this.visited; }
 public boolean notSearched() { return !this.searched; }

 void draw() {
   noStroke();
   if (this.mazeExit) {
    fill(#005500); 
   } else if (this.searchStart) {
     fill(#AA0000);
   } else if (this.equals(currentCell)) {
    fill(#FF0000); 
   } else {
     fill(this.visited?#000000:68);
   }

   float lx = x*s;
   float rx = x*s+s;
   float ty = y*s;
   float by = y*s+s;

   rect(lx,ty,s,s);

   stroke(255);

   // top
   if (top) line(lx, ty, rx, ty);
   // right
   if (right) line(rx, ty, rx, by);
   //left
   if (left) line(lx, ty, lx, by);
   //bottom
   if (bottom) line(lx, by, rx, by);

   if (this.searched && (stack.search(this) > -1 )) {
     fill(#EEE8AA);
     ellipse((lx+rx)/2,(ty+by)/2,s/3,s/3);
   }
 }
}