Author: Erin

My Final Project was a maze generator that you can solve!

How to Play: Wait for the maze generator to run in the background, once the loading screen is gone you are ready to play. Use your arrow keys to navigate the green dot through the maze to the red dot.

//Erin Fuller
//Section A
//efuller@andrew.cmu.edu
//Final Project

//This Maze Generator + Game uses first depth search and recursive backtracking
//to generate the maze.  

//https://en.wikipedia.org/wiki/Maze_generation_algorithm#Depth-first_search
//https://en.wikipedia.org/wiki/Maze_generation_algorithm#Recursive_backtracker

var cols, rows; // dividing canvas into grid array
var w = 30; // cell width
var grid = []; 

var sX = 0; // solver x position
var sY = 0; // solver y position

var distance = 0, longdist = 0;
var longest;
var current;
var mazeGen = false; //maze generator not finished

var stack = []; // stack of current cells maze is genrating

// wall array directions 
var up = 0; 
var right = 1;
var down = 2;
var left = 3;

function setup() {
    createCanvas(480, 480);
    cols = width / w;
    rows = height / w;
    for (var i = 0; i < rows; i++) {
        for (var j = 0; j < cols; j++) {
            var cell = new Cell(j, i); //creates cell object
            grid.push(cell); //pushes object into grid array
        }
    }
    current = grid[0]; //starts grid at top left corner
    current.visited = true;
}

function draw() {
    mazeDraw(); 
    if (mazeGen) { 
        solve(); //when maze is finsihed generating it calls a solve function
    } else {
        preText(); //shows instruction while maze is generating
    }
}

function mazeDraw() {
    background(165, 202, 218); //LIGHT BLUE
    for (var i = 0; i < grid.length; i++) {
        grid[i].show();
    } 
    // Step 1: randomly choose of the unvisited neighbors
    var next = current.checkNeighbors();
    if (next) {
        next.visited = true;
        // Step 2: push the current cell to the stack
        stack.push(current);
        // Step 3: Remove wall between current cell and chosen cell
        removeWalls(current, next);
        // Step 4: Make chosen cell the current cell and mark as visited
        current = next;
        distance++;
    } else {
        if (stack.length > 0) { 
        	current = stack.pop();
        } else { 
        	current = grid[0];
    		mazeGen = true;
        	distance;
        }
    }
    if (longdist < distance) {
            longdist = distance;
            longest = current;
    }
}

function index(i, j) {
    if (i < 0 || j < 0 || i > cols - 1 || j > rows - 1) {
        return -1; //return negative/invalid index
    } else {
    	return i + j * cols;
    }
}

function Cell(i, j) {
    this.i = i;
    this.j = j;
    this.walls = [true, true, true, true]; // N, E, S, W
    this.visited = false;

    this.checkNeighbors = function() {
        var neighbors = [];
        var n = grid[index(i, j - 1)]; // top line (N)
        var e = grid[index(i + 1, j)]; //right line (E)
        var s = grid[index(i, j + 1)]; //bottom line (S)
        var w = grid[index(i - 1, j)]; //left line (W)

        //Avoided the "conditional AND operator" because WordPress converts it to a "logical ND" operator
        if (n) {
            if (!n.visited) {
                neighbors.push(n);
            } 
        }
        if (e) {
            if (!e.visited) {
                neighbors.push(e);
            } 
        }
        if (s) {
            if (!s.visited) {
                neighbors.push(s);
            } 
        }
        if (w) {
            if (!w.visited) {
                neighbors.push(w);
            } 
        }

        if (neighbors.length > 0) {
            var r = floor(random(0, neighbors.length));
            return neighbors[r];
        } else {
            return undefined;
        }
    }

    this.show = function() {
        var x = this.i * w;
        var y = this.j * w;
        
        stroke(0);
        strokeWeight(1);

        if (this.walls[up]) {
            line(x, y, x + w, y); // top line (N)
        }
        if (this.walls[right]) {
            line(x + w, y, x + w, y + w); //right line (E)
        }
        if (this.walls[down]) {
            line(x + w, y + w, x, y + w); //bottom line (S)
        }
        if (this.walls[left]) {
            line(x, y, x, y + w); //left line (W)
        }         
    }
}

function removeWalls(a, b) {
    var x = a.i - b.i; //x = diffrence between current cell and its neighbor
    if (x === 1) {
        a.walls[left] = false; //remove left/west wall on current
        b.walls[right] = false; //removes right/east wall on neighbor
    } else if (x === -1) {
        a.walls[right] = false; //remove right/east wall on current
        b.walls[left] = false; //removes left/west wall on neighbor
    }

    var y = a.j - b.j; //x = diffrence between current cell and its neighbor
    if (y === 1) {
        a.walls[up] = false; //remove up/north wall on current
        b.walls[down] = false; //removes down/south wall on neighbor
    } else if (y === -1) {
        a.walls[down] = false; //remove down/south wall on current
        b.walls[up] = false; //removes up/north wall on neighbor
    }
}

function keyPressed() {
	var solver = grid[index(sX, sY)]; 

    //Avoided the "conditional AND operator" because WordPress converts it to a "logical ND" operator
    if (keyCode === LEFT_ARROW) { 
        if (!solver.walls[left]) {
            sX --; 
        } 
    }    

    if (keyCode === RIGHT_ARROW) { 
        if (!solver.walls[right]) {
            sX ++; 
        } 
    }	    

    if (keyCode === UP_ARROW) { 
        if (!solver.walls[up]) {
            sY --; 
        } 
    }

    if (keyCode === DOWN_ARROW) { 
        if (!solver.walls[down]) {
            sY ++;
        } 
    }
}

function solve() { 
	var a = 0.5 * w;
	noStroke();
	
	fill(214, 247, 52); //green "solver" dot 
    var gX = a + (w * sX); //controlled by arrow keys
    var gY = a + (w * sY);	
	ellipse(gX, gY, a, a);
    
    fill(250, 29, 59); //red "end" dot
    var rX = a + (w * longest.i);
    var rY = a + (w * longest.j);
    ellipse(rX, rY, a, a);

    if (dist(gX, gY, rX, rY) < a) { //if green dot reaches red dot
    	winner();
  	}
}

function preText() {
    fill(165, 202, 218); //blue background
    rect(0, 0, width, height);

    textAlign(CENTER);
    
    noStroke();
    fill(255);
    textSize(75);
    text('Get Ready.', width / 2, height / 2);

    textSize(20);
    text('The maze is loading. Use your arrow keys to navigate the green dot to the red dot.', 
        width / 2 - 150, height / 2 + 45, 300, 200);
}

function winner() {
    fill(165, 202, 218); //blue background
    rect(0, 0, width, height);

    textAlign(CENTER);
    noStroke();
    fill(255);

    textSize(87);
    text('YOU WON!', width / 2, height / 2);

    textSize(25);
    text('Refresh to play again.', width / 2, height / 2 + 45);
}

This was a big task for me. The maze was generated using Recursive Backtracking, a form of First Depth Search (more info can be found on this Wikipedia page). In short, the canvas is gridded into cells and the generator randomly chooses a neighbor cell to visit, removing the wall between it, until all the cells have been visited and a maze is created. A lot of this was new concepts for me, so big thanks to Professor Dannenberg for pointing me in the right direction and Dan Shiffman‘s Coding Train for having some material on this.

The end goal is generated to be the furthest point along the maze from the origin. The start/player begins in the top left corner and moves along the maze to the red dot. Getting the solver dot to stay inside the lines was probably the biggest challenge.

Some Errors: The red dot that signifies the target is supposed to be the furthest distance in the maze from the start. Sometimes it works, but sometimes the target is very close to the origin. I think this is because it may classify the last unvisited cell as the furthest even though the may be very close.