int sizeX, sizeY;
int drawSize;
int curX, curY;

int visibility;;
int posX, posY;

int[][] maze;
ArrayList<String> stack;

float ms;

boolean displaySolution;

void setup()
{
  ms = millis();

  sizeX = 100;
  sizeY = 100;
  drawSize = 10;

  visibility = 20;

  sizeX = round(sizeX / 2) * 2 - 1;
  sizeY = round(sizeY / 2) * 2 - 1;

  size(sizeX * drawSize, sizeY * drawSize);

  maze = new int[sizeX][sizeY];
  stack = new ArrayList<String>();

  displaySolution = false;

  //Maze setup
  for (int x = 0; x < sizeX; x++) {
    for (int y = 0; y < sizeY; y++) {
      if ((x % 2 == 0) || (y % 2 == 0) || (x == 0) || (y == 0) || (x == sizeX - 1) || (y == sizeY - 1)) { // is a wall of some sort
        maze[x][y] = 2;
      }
      else {
        maze[x][y] = 0;
      }
    }
  }

  curX = 1;
  curY = 1;

  // set first cell to visited, add to stack
  stack.add(curX + " " + curY);

  while (stack.size () > 0) {
    maze[curX][curY] = 1; //set current cell to visited

    // find adjacent cells
    ArrayList<String> adjCells = new ArrayList<String>();
    if (curX > 1) {
      if (maze[curX - 2][curY] == 0) {
        adjCells.add((curX - 2) + " " + curY);
      }
    }

    if (curY > 1) {
      if (maze[curX][curY - 2] == 0) {
        adjCells.add(curX + " " + (curY - 2));
      }
    }

    if (curX < sizeX - 3) {
      if (maze[curX + 2][curY] == 0) {
        adjCells.add((curX + 2) + " " + curY);
      }
    }

    if (curY < sizeY - 3) {
      if (maze[curX][curY + 2] == 0) {
        adjCells.add(curX + " " + (curY + 2));
      }
    }

    if (adjCells.size() > 0) {
      if (adjCells.size() > 1) {
        stack.add(curX + " " + curY);
      }

      String rAdjCell = adjCells.get( randint(0, adjCells.size() - 1) );

      int newX = int(rAdjCell.split(" ")[0]);
      int newY = int(rAdjCell.split(" ")[1]);

      // remove the wall between the old cell and the new one
      maze[(curX + newX) / 2][(curY + newY) / 2] = 3;

      curX = newX;
      curY = newY;
    }
    else {
      // backtrack through the stack
      curX = int(stack.get(stack.size() - 1).split(" ")[0]);
      curY = int(stack.get(stack.size() - 1).split(" ")[1]);

      stack.remove(stack.size() - 1);
    }
  }



  //
  // now to solve the maze with breadth first search...
  //

  String[][] parentNodes = new String[sizeX][sizeY];
  ArrayList<String> activeNodes = new ArrayList<String>();

  activeNodes.add( (sizeX - 2) + " " + (sizeY - 2) );
  parentNodes[sizeX - 2][sizeY - 2] = "END";

  boolean breakOut = false;

  while (!breakOut) {
    ArrayList<String> newActiveNodes = activeNodes;

    for (int i = 0; i < activeNodes.size(); i++) {
      int cx = int(activeNodes.get(i).split(" ")[0]);
      int cy = int(activeNodes.get(i).split(" ")[1]);

      if (cx == 1 && cy == 1) { // FOUND IT
        String curParentNode = parentNodes[1][1];
        while (true) {
          maze[cx][cy] = 4;

          curParentNode = parentNodes[cx][cy];

          if (curParentNode == "END") {
            break;
          }

          cx = int(curParentNode.split(" ")[0]);
          cy = int(curParentNode.split(" ")[1]);
        }

        breakOut = true;
        break;
      }

      if ((maze[cx - 1][cy] <= 1 || maze[cx - 1][cy] == 3) && parentNodes[cx - 1][cy] == null) { // is white, not spread to yet
        newActiveNodes.add( (cx - 1) + " " + cy );
        parentNodes[cx - 1][cy] = cx + " " + cy;
      }

      if ((maze[cx + 1][cy] <= 1 || maze[cx + 1][cy] == 3) && parentNodes[cx + 1][cy] == null) {
        newActiveNodes.add( (cx + 1) + " " + cy );
        parentNodes[cx + 1][cy] = cx + " " + cy;
      }

      if ((maze[cx][cy - 1] <= 1 || maze[cx][cy - 1] == 3) && parentNodes[cx][cy - 1] == null) {
        newActiveNodes.add( cx + " " + (cy - 1) );
        parentNodes[cx][cy - 1] = cx + " " + cy;
      }

      if ((maze[cx][cy + 1] <= 1 || maze[cx][cy + 1] == 3) && parentNodes[cx][cy + 1] == null) {
        newActiveNodes.add( cx + " " + (cy + 1) );
        parentNodes[cx][cy + 1] = cx + " " + cy;
      }
    }

    activeNodes = newActiveNodes;
  }

  // remove the entrance and exit walls and set them as part of the solution
  maze[1][0] = 4;
  maze[sizeX - 2][sizeY - 1] = 4;

  posX = 1;
  posY = 0;

  //redraw = true;
}

void draw()
{
  background(0);

  noSmooth();
  noStroke();

  rectMode(CORNER);

  ArrayList<String> nodes = new ArrayList<String>();
  nodes.add(posX + " " + posY);
  String visitedCells = "";

  visibility = 40;
  for(int a = 0; a <= visibility; a++) {
    ArrayList<String> newNodes = new ArrayList<String>();
    for(int i = 0; i < nodes.size(); i++) {
      int nX = int(nodes.get(i).split(" ")[0]);
      int nY = int(nodes.get(i).split(" ")[1]);

      visitedCells += nX + " " + nY + ",";

      int cVal = (int) ((1.0 - a / ((float) visibility)) * 255.0);
      fill(255, 255, 255, cVal);
      rect(nX * drawSize, nY * drawSize, drawSize, drawSize);

      if(isCell(nX - 1, nY) && match(visitedCells, (nX - 1) + " " + (nY) + ",") == null) {
        newNodes.add( (nX - 1) + " " + (nY) );
      }

      if(isCell(nX + 1, nY) && match(visitedCells, (nX + 1) + " " + (nY) + ",") == null) {
        newNodes.add( (nX + 1) + " " + (nY) );
      }

      if(isCell(nX, nY - 1) && match(visitedCells, (nX) + " " + (nY - 1) + ",") == null) {
        newNodes.add( (nX) + " " + (nY - 1) );
      }

      if(isCell(nX, nY + 1) && match(visitedCells, (nX) + " " + (nY + 1) + ",") == null) {
        newNodes.add( (nX) + " " + (nY + 1) );
      }
    }

    nodes = newNodes;
  }

  fill(255, 0, 0);
  rect(posX * drawSize, posY * drawSize, drawSize, drawSize);
}

void mouseClicked()
{
  displaySolution = !displaySolution;
  redraw = true;
}

int randint(int low, int high)
{
  return round( random(low - 0.4999, high + 0.4999) );
}

boolean isCell(int xp, int yp)
{
  if((xp >= 0) && (yp >= 0) && (xp <= sizeX - 1) && (yp <= sizeY - 1)) {
    // not a wall
    return maze[xp][yp] != 2;
  } else {
    // outside the bounds of the maze, return false
    return false;
  }
}

void keyPressed()
{
  // Left = 37, Up = 38, Right = 39, Down = 40
  if(keyCode == 37 && isCell(posX - 1, posY)) { // left
    posX -= 1;
  }

  if(keyCode == 38 && isCell(posX, posY - 1)) { // up
    posY -= 1;
  }

  if(keyCode == 39 && isCell(posX + 1, posY)) { // right
    posX += 1;
  }

  if(keyCode == 40 && isCell(posX, posY + 1)) { // down
    posY += 1;
  }

  if(keyCode == 82) { // r key
    setup();
  }
}