let rows = cols;

let grid = new Array(cols);

let space;

​

let openSet = [];

let closedSet = [];

let start;

let end;

let ww, hh;

let path = [];

let current;

​

​

function setup() {

  createCanvas(800, 800);

​

  ww = width/cols;

  hh = height/rows;

​

  // make 2D array

  for (let i = 0; i < cols; i++) {

    grid[i] = new Array(rows);

  }

​

  for (let i = 0; i < cols; i++) {

    for (let j = 0; j < rows; j++) {

      grid[i][j] = new Spot(i, j,0,0,0);

    }

  }

  for (let i = 0; i < cols; i++) {

    for (let 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);

​

}

​

function draw() {

  background(255);

​

  // Am I still searching?

  if(openSet.length > 0) {

​

    // Best next option

    let winner = 0;

    for(let i = 0; i < openSet.length; i++) {

      if(openSet[i].f < openSet[winner].f) {

        winner = i;

      }

    }

    current = openSet[winner];

​

    // Did I finish?

    if(current === end) {

      noLoop();

      console.log("DONE!");

    }

​

​

    // Best option moves from openSet to closedSet

    removeFromArray(openSet, current);

    closedSet.push(current);

​

    // check all the neighbors

    let neighbors = current.neighbors;

    for (let i = 0; i < neighbors.length; i++) {

      let neighbor = neighbors[i];

​

      // Valid next spot?

      if(!closedSet.includes(neighbor) && !neighbor.wall) {

        let tempG = current.g + heuristic(neighbor, current);

​

        // Is this a better path than before?

        let newPath = false;

        if(openSet.includes(neighbor)) {

          if(tempG < neighbor.g) {

            neighbor.g = tempG;

            newPath = true;

          }

        } else {

          neighbor.g = tempG;

          newPath = true;

          openSet.push(neighbor);

        }

​

        // Yes, it's a better path

        if(newPath) {

          neighbor.h = heuristic(neighbor, end);

          neighbor.f = neighbor.g + neighbor.h;

          neighbor.previous = current;

        }

      }

    }

​

    // Uh oh, no solution

  } else {

    // no solution

    console.log('no solution!');

    noLoop();

    return;

  }

​

​

​

​

​

​

  for (let i = 0; i < cols; i++) {

    for (let j = 0; j < rows; j++) {

      grid[i][j].show(color(255));

    }

  }

​

  for (let i = 0; i < closedSet.length; i++) {

    closedSet[i].show(color(255,55,0));

  }

  for (let i = 0; i < openSet.length; i++) {

    openSet[i].show(color(255,255,5));

  }

​

  path = [];

  let temp = current;

  path.push(temp);

  while(temp.previous) {

    path.push(temp.previous);

    temp = temp.previous;

  }

​

  // for (let i = 0; i < path.length; i++) {

  //   path[i].show(color(0,255,0));

  // }

​

  // Drawing path as continuous line

  strokeJoin(ROUND);

  noFill();

  stroke(0, 250, 200);

  strokeWeight(ww / 2);

  beginShape();

  for (let i = 0; i < path.length; i++) {

    vertex(path[i].x * ww + ww / 2, path[i].y * hh + hh / 2);

  }

  endShape();

​

}

​

​

const heuristic = (a, b) => {

  // Euclildean distance

  // let d = dist(a.x, a.y, b.x, b.y);

​

  // Manhattan distance

  // let d = abs(a.x - b.x) + abs(a.y - b.y);

​

  // Chebyshev distance

  let d = max(abs(a.x - b.x), abs(a.y - b.y));

  return d;

}

​

const removeFromArray = (arr, elt) => {

  for (let i = arr.length - 1; i >= 0; i--) {

    if (arr[i] == elt) {

      arr.splice(i, 1);

    }

  }

}

​

​

class Spot {

  constructor(x,y) {

    this.x = x;

    this.y = y;

    this.f = 0;

    this.g = 0;

    this.h = 0;

    this.neighbors = [];

    this.previous = undefined;

    this.wall = false;

​

    if(random(1) < 0.4) {

      this.wall = true;

    }

​

  }

​

  show(c) {

    // rectMode(CENTER);

    // stroke(255);

    noStroke();

    fill(c);

    if(this.wall) {

      fill(0);

    }

    rect(this.x*ww, this.y*hh, ww-1,hh-1);

​

  }

​

  addNeighbors(grid) {

    let i = this.x;

    let j = this.y;

    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 (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]);

    }

  }

}