MazeGeneration/mazeGeneration.pde

/*

Maze Generation:

Idea:
Generate a Maze in which you only use a grid of "cells" without defined walls.
Have every cell be either "alive" or "dead", with "dead" standing for being a wall.
cellsW and cellsH must be an uneven number because we always need to skip 1 (= the wall). 

- Make a Grid out of x Amount of "Cells"
- Have the all "Cells" start off "dead"
- Start top left cell being "alive":
  - Go to random (non-diagonal) neighboring cell and make it "alive"
  - Make 1 cell inbetween the two "alive" as in that one being an opening in the walls
  - Repeat until no more "dead" neighboring cells or finished Maze

*/

final int cellsW = 15 * 3 * 3; // cells in 1 row
final int cellsH =  9 * 3 * 3; // cells in 1 col
final int cellAmount = cellsW * cellsH; // total cells
ArrayList<Cell> Cells = new ArrayList<Cell>();
float scaleW = -1, scaleH = -1; // Width and Height of a Cell

ArrayList<Cell> path = new ArrayList<Cell>(); // Current path from Start to currentCell
Cell currentCell, inBetween; // Cell currently being processed

ArrayList<Cell> solved; // Solved Path from start to finish
boolean isDone = false; // Finish declarator

Cell start, finish;

int normalFPS = 60;
int slowmoFPS =  5;

void setup() {
  fullScreen(P3D);
  
  // Initialize Cells in order
  for (int y = 0; y < cellsH; y++) {
    for (int x = 0; x < cellsW; x++) {
      Cell c = new Cell(x, y);
      Cells.add(c);
    }
  }
  
  // Initialize current to starting Cell
  start = Cells.get(0);
  finish = getCell(Cells, cellsW - 1, cellsH - 1);
  currentCell = start;
  
  // Set Width and Height of every cell in (amount of) Pixels
  scaleW = (float) width  / cellsW;
  scaleH = (float) height / cellsH;
  
  frameRate(normalFPS);
}

void mousePressed() {
  frameRate(slowmoFPS);
}

void mouseReleased() {
  frameRate(normalFPS);
}

void draw() {
  background(0);

  // Upon reaching the Goal, set "solved" path to current "path"
  if (currentCell == finish) {
    solved = new ArrayList<Cell>();
    for (Cell c : path) {
      solved.add(c);
    }
    solved.add(currentCell);
    isDone = true;
    frameRate(1000);
  }

  // Save Cells for coloring
  ArrayList<Cell> savedCells = new ArrayList<Cell>();
  savedCells.add(currentCell);
  
  // The actual Algorithm step by step of the generation.
  currentCell.state = true;
  if (inBetween != null)
    inBetween.state = true;
  ArrayList<Cell> neighbors = currentCell.getNeighbors();
  if (neighbors.size() > 0) {
    // If Cell has Neighbors, choose a random one,
    // Make that one and the one between it and current "alive",
    // Save current Cell into path and become that neighbor.
    
    int randomIndex = floor(random(neighbors.size()));
    Cell next = neighbors.get(randomIndex);
    inBetween = next.getBetween(currentCell);
    
    path.add(currentCell);
    
    currentCell = next;
    for (Cell c : neighbors) {
      if (c != next) {
        savedCells.add(c);
      }
    }
    savedCells.add(next);
  }
  
  // For-Each loop to display all cells
  for (Cell c : Cells) {
    color col = (c.state) ? color(0) : color(255); // Set color according to state
    if (c == finish)                               { col = color(0,255,0); }; // Set Goal to Green
    if (c == start)                                { col = color(255,0,0); }; // Set Start to Red
    if (c == savedCells.get(0) && !isDone)         { col = color(0,0,255); }; // Set current Cell to Blue
    if (c == currentCell && savedCells.size() > 1) { col = color(255,0,0); }; // Set chosen Neighbor to Red
    // Set other Neighbors to Yellow
    for (int i = 1; i < savedCells.size()-1; i++) {
      if (c == savedCells.get(i)) {
        col = color(255,255,0);
      }
    }
    // Set color and draw cell
    fill(col);
    stroke(0);
    rect(c.x * scaleW, c.y * scaleH, scaleW, scaleH);
  }
  
  noFill();
  stroke(255);
  if (isDone) {
    // Draw path from start to finish
    for (int i = 0; i < solved.size()-1; i++) {
      float cx = solved.get(i  ).x * scaleW + scaleW/2;
      float cy = solved.get(i  ).y * scaleH + scaleH/2;
      float px = solved.get(i+1).x * scaleW + scaleW/2;
      float py = solved.get(i+1).y * scaleH + scaleH/2;
      line(cx, cy, px, py);
    }
  } else {
    // Draw path from start to current cell
    for (int i = 0; i < path.size()-1; i++) {
      float cx = path.get(i  ).x * scaleW + scaleW/2;
      float cy = path.get(i  ).y * scaleH + scaleH/2;
      float px = path.get(i+1).x * scaleW + scaleW/2;
      float py = path.get(i+1).y * scaleH + scaleH/2;
      line(cx, cy, px, py);
      if (i==path.size()-2 && path.get(i+1)!=savedCells.get(0)) {
        float ccx = savedCells.get(0).x * scaleW + scaleW/2;
        float ccy = savedCells.get(0).y * scaleH + scaleH/2;
        line(ccx, ccy, px, py);
      }
    }
  }

  // If no neighbors that are "dead" exist, backtrack to find some
  if (path.size() > 0 && neighbors.size() == 0 && savedCells.size() == 1) {
    currentCell = path.get(path.size()-1);
    path.remove(path.size()-1);
  }

  // Display Framerate
  noStroke();
  fill(255,0,0);
  textSize(24);
  text(nfs(frameRate, 2, 2),24,24);
}