BreadthFirstSearch/breadthFirstSearch.pde

// Note #1: This version works using 'intersecting Lines' as a detection for Walls.
// Note #2: The ratio of constants 'cellsInWidth' and 'cellsInHeight' must remain the same as that of your screen.

// final int cells = 60;
final int cellsInWidth = 16;
final int cellsInHeight = 9;
final float verticalWall = .5;
final float horizontalWall = .5;
final int frameRate = 30; // Can't go above 60 or below 0 FPS!
final float timeout = 5;

int cIW = cellsInWidth, cIH = cellsInHeight;
float scl = 0, diameter = 0;
boolean solvedMaze = false, reachedOrigin = false;
ArrayList<Wall> walls = new ArrayList<Wall>();
ArrayList<Mover> movers = new ArrayList<Mover>();
ArrayList<Mover> visited = new ArrayList<Mover>();
ArrayList<Mover> finalPath = new ArrayList<Mover>();
Mover origin, pathFinder;

boolean outputToggle = false;
int previousUnsolvableMazes = 0;

int solvedFrameCountCapture = -1;

void setup() {
  fullScreen();
  
  generateMaze();
  
  frameRate(frameRate);
}

void draw() {
  background(0);
  
  /*
    translate(width / 2 - height / 2, 0);
    fill(0);
    stroke(0);
    rect(0, 0, height, height);
  */
  
  // Display Walls
  noFill();
  stroke(255);
  for (Wall w : walls) {
    w.show();
  }
  
  // Display spots that are to be moved to
  fill(0,255,0);
  stroke(0,255,0);
  for (Mover m : movers) {
    ellipse(m.position.x, m.position.y, diameter, diameter);
  }
  
  // Display origin spot
  fill(255,0,0);
  stroke(255,0,0);
  ellipse(origin.position.x, origin.position.y, diameter, diameter);
  
  if (!solvedMaze) {
    /*
      // Display previously visited spots
      fill(255,255,0);
      stroke(255,255,0);
      for (Mover m : visited) {
        if (!m.equals(origin)) {
          ellipse(m.position.x, m.position.y, diameter, diameter);
        }
      }
    */
    
    // As long as the maze isn't solved, keep stepping the algorithm
    breadthFirstSearchStep();
  } else {
    // When the maze is solved, display the last position and the path to get from the origin to there.
    fill(0,0,255);
    stroke(0,0,255);
    final Mover last = visited.get(visited.size()-1);
    ellipse(last.position.x, last.position.y, diameter, diameter);
    
    // Display path from origin to last visited.
    fill(255,255,0);
    stroke(255,255,0);
    for (Mover m : finalPath) {
      ellipse(m.position.x, m.position.y, diameter, diameter);
    }
    
    if (!outputToggle) {
      println("Previously genereted '" + previousUnsolvableMazes + "' mazes which were unsolvable.");
      outputToggle = true;
    }
    
    // Trace back the path from last visited to origin.
    if (!reachedOrigin) {
      for (Mover v : visited) {
        if (pathFinder.isNextOf(v)) {
          if (v.steps == 0) {
            reachedOrigin = true;
            break;
          }
          finalPath.add(v.copy());
          pathFinder = v.copy();
          break;
        }
      }
    } else {
      if (solvedFrameCountCapture == -1) {
        solvedFrameCountCapture = frameCount;
      } else if (frameCount-solvedFrameCountCapture == frameRate*timeout) {
        // Possible Error: 'frameCount-solvedFrameCountCapture' could be a negative number or similar.
        // Note: frameCount, as the name implies, counts how many frames has passed. At one point, it has to reset to 0 (?).
        // -> when resetting, no matter the result, the difference will never equal the wanted window or take too long to get there.
        
        outputToggle = false;
        solvedFrameCountCapture = -1;
        resetMaze(false);
        previousUnsolvableMazes = 0;
        generateMaze();
      }
    }
  }
}

void breadthFirstSearchStep() {
  // Idea: Move to every accessable (no walls inbetween the two) neighbor, when reaching the bottom, you have a path.
  // Note: I don't actually know if this is the same working principle as Breadth-First Search.
  
  ArrayList<Mover> nextGen = new ArrayList<Mover>();
  for (Mover m : movers) {
    visited.add(m.copy());
    
    if (m.position.y == height-scl/2) {
      solvedMaze = true;
      nextGen = new ArrayList<Mover>();
      
      pathFinder = m.copy();
      break;
    }
    
    final ArrayList<Mover> neighbors = m.getNeighbors();
    for (Mover n : neighbors) {
      boolean alreadyVisited = false;
      for (Mover v : visited) {
        if (n.equals(v)) {
          alreadyVisited = true;
          break;
        }
      }
      for (Mover s : nextGen) {
        if (n.equals(s)) {
          alreadyVisited = true;
          break;
        }
      }
      if (!alreadyVisited) {
        nextGen.add(n);
      }
    }
  }
  
  movers = new ArrayList<Mover>(nextGen);
}

void generateMaze() {
  while (true) {
    // While loop to reset when previous maze is unsolvable (from origin position).
  
    int randomScalor = floor(random(3,8));
    cIW *= randomScalor;
    cIH *= randomScalor;
    scl = (float) height / cIH;
    diameter = scl / 2;
    
    for (float i = 0; i < /*height*/width; i += scl) {
      for (float j = 0; j < height; j += scl) {
        if (random(1) <= verticalWall && i != 0) {
          walls.add(new Wall(
            new PVector(i, j),
            new PVector(i, j+scl)
          ));
        }
        if (random(1) <= horizontalWall && j != 0) {
          walls.add(new Wall(
            new PVector(i, j),
            new PVector(i+scl, j)
          ));
        }
      }
    }
    
    origin = new Mover((floor(random(/*cells*/cellsInWidth))+.5) * scl, scl/2, 0);
    movers.add(origin);
    
    // Check if maze is solvable by stepping through until solved.
    // Note: If there are no movers while the maze is unsolved, it means there are no spots to be visited and it's unsolvable.
    boolean isSolvable = false;
    while (!solvedMaze) {
      breadthFirstSearchStep();
      if (solvedMaze) {
        isSolvable = true;
        break;
      } else if (movers.size() == 0) {
        break;
      }
    }
    
    resetMaze(isSolvable);
    if (isSolvable) {
      break;
    }
  }
}

void resetMaze(boolean iS) {
  // Resetting variables depending on solvability of the maze.
  cIW = cellsInWidth;
  cIH = cellsInHeight;
  solvedMaze = false;
  reachedOrigin = false;
  movers = new ArrayList<Mover>();
  visited = new ArrayList<Mover>();
  finalPath = new ArrayList<Mover>();
  if (iS) {
    movers.add(origin);
  } else {
    previousUnsolvableMazes++;
    walls = new ArrayList<Wall>();
  }
}