/* Initialise any constants. */
const ch = 600;
const cw = 900;
const diagonal = true ;
const backcolor = 'white';
const closedcolor = 'lightpink';
const opencolor = 'lightgreen';
const pathcolor = 'darkred';
const wallAmount = AB.randomFloatAtoB(0, 0.6);
const wallcolor = 'black';

/* Initialise any variables. */
var random = AB.randomIntAtoB(1, 5);
var cols = 9 * random;
var grid = new Array(cols);
var rows = 6 * random;

/* The set of open and closed nodes. */
var closedSet = [];
var openSet = [];

/* The start and end nodes. */
var end;
var start;

/* The width and height of each cell in the grid. */
var w, h;

/* The path taken. */
var path = [];

/* The heuristic evaluation function that we will use. */
function heuristic(a, b) {
    /* If diagonal moves are allowed, calculate the 2D distance between a and b. */
    if (diagonal) return (dist(a.i, a.j, b.i, b.j));
    /* Otherwise, calculate the distance across, plus the distance down. */
    else return (abs(a.i - b.i) + abs(a.j - b.j));
}

/* Delete the specified element from the specified array. */
function removeFromArray(arr, elt) {
    for (var i = arr.length - 1; i >= 0; i--) {
        if (arr[i] == elt) {
            arr.splice(i, 1);
        }
    }
}

/* Represents a single spot on the grid. */
function Spot(i, j) {
    /* The coordinates for the spot. */
    this.i = i;
    this.j = j;

    /* The f, g, and h values to be used in our heuristic. */
    this.f = 0;
    this.g = 0;
    this.h = 0;

    /* The spot in question's neighbours. */
    this.neighbors = [];

    /* The previous spot that was traversed to reach this spot. */
    this.previous = undefined;

    /* Whether or not this spot is a wall. */
    if (random(1) < wallAmount) this.wall = true;
    else this.wall = false;

    /* Display the spot in question. */
    this.show = function(col) {
        if (this.wall) {
            fill(wallcolor);
            noStroke();
            rect(this.i * w, this.j * h, w, h);
        } else if (col) {
            fill(col);
            rect(this.i * w, this.j * h, w, h);
        }
    };
  
    /* Determine the neighbours of this spot. */
    this.addNeighbors = function(grid) {
        var i = this.i;
        var j = this.j;
    
        if (i < cols - 1) this.neighbors.push(grid[i + 1][j]);
        if (i > 0) this.neighbors.push(grid[i - 1][j]);
        if (j < rows - 1) this.neighbors.push(grid[i][j + 1]);
        if (j > 0) this.neighbors.push(grid[i][j - 1]);
    
        if (diagonal) {
            if (i > 0 && j > 0) this.neighbors.push(grid[i - 1][j - 1]);
            if (i < cols - 1 && j > 0) this.neighbors.push(grid[i + 1][j - 1]);
            if (i > 0 && j < rows - 1) this.neighbors.push(grid[i - 1][j + 1]);
            if (i < cols - 1 && j < rows - 1) this.neighbors.push(grid[i + 1][j + 1]);
        }
    }
}

function setup() {
    frameRate(60)
    createCanvas(cw, ch);
    w = width / cols;
    h = height / rows;
    
    for (var i = 0; i < cols; i++) 
        grid[i] = new Array(rows);

    for (var i = 0; i < cols; i++) 
        for (var j = 0; j < rows; j++) 
            grid[i][j] = new Spot(i, j);
  
    for (var i = 0; i < cols; i++) 
        for (var j = 0; j < rows; j++) 
            grid[i][j].addNeighbors(grid);

    start = grid[0][0];
    end = grid[cols - 1][rows - 1];
    start.wall = false;
    end.wall = false;

    openSet.push(start);
    console.log('Starting search...');
}

function draw() {
    if (openSet.length > 0) {
        var winner = 0;
    
        for (var i = 0; i < openSet.length; i++)
            if (openSet[i].f < openSet[winner].f) 
                winner = i;
        
        var current = openSet[winner];

        if (current === end) {
            noLoop();
            console.log("Success - found path.");
        }

        removeFromArray(openSet, current);
        closedSet.push(current);

        var neighbors = current.neighbors;
    
        for (var i = 0; i < neighbors.length; i++) {
            var neighbor = neighbors[i];

            if (!closedSet.includes(neighbor) && !neighbor.wall) {
                var tempG = current.g + heuristic(neighbor, current);

                var newPath = false;
                if (openSet.includes(neighbor)) {
                    console.log('Comparing current spot (' + current.i + ',' + current.j + ') with neighbour (' + neighbor.i + ',' + neighbor.j + '):')
                    console.log('f(a) - ' + current.f, ', g(a) - ' + current.g + ', h(a) - ' + current.h)
                    console.log('f(b) - ' + neighbor.f, ', g(b) - ' + neighbor.g + ', h(b) - ' + neighbor.h)
                    if (tempG < neighbor.g) {
                        neighbor.g = tempG;
                        newPath = true;
                    }
                } else {
                    neighbor.g = tempG;
                    newPath = true;
                    openSet.push(neighbor);
                }

                if (newPath) {
                    neighbor.h = heuristic(neighbor, end);
                    neighbor.f = neighbor.g + neighbor.h;
                    neighbor.previous = current;
                }
            }
        }
    } else {
        console.log('Fail - no path exists.');
        noLoop();
        return;
    }
    
    background(backcolor);
    
    for (var i = 0; i < cols; i++) 
        for (var j = 0; j < rows; j++) 
            grid[i][j].show();

    for (var i = 0; i < closedSet.length; i++) 
        closedSet[i].show(closedcolor);

    for (var i = 0; i < openSet.length; i++) 
        openSet[i].show(opencolor);

    path = [];
    var temp = current;
    path.push(temp);
    while (temp.previous) {
        path.push(temp.previous);
        temp = temp.previous;
    }
  
    if (diagonal) {
        noFill();
        stroke(pathcolor);
        strokeWeight(w / 8);
        beginShape();
        
        for (var i = 0; i < path.length; i++) 
            vertex((path[i].i * w) + w / 2, (path[i].j * h) + h / 2);
        
        endShape();
    } else {
        for (var i = 0; i < path.length; i++) 
            path[i].show(pathcolor);
    }
}