let grid;

let start = [5,7];

let target = [n-3,n-8];

let path;

let R = []; // Should be implemented as a min heap

let finish = false;

let play = false;

let walls = [];

​

function h(i1, i2) {

  let j1 = target[0];

  let j2 = target[1];

  return sqrt((i1-j1)*(i1-j1) + (i2-j2)*(i2-j2));

}

​

function get_adj(u){

  let i = u[0];

  let j = u[1];

  let a = [];

  // 4 corners

  if(i == 0 && j == 0) {

    a = [[0,1],[1,0],[1,1]];

  }

  else if(i == n-1 && j == n-1) {

    a = [[n-2, n-1],[n-1,n-2],[n-2,n-2]];

  }

  else if(i == 0 && j == n-1) {

    a = [[0, n-2],[1,n-2],[1, n-1]];

  }

  else if(i == n-1 && j == 0) {

    a = [[n-1,1],[n-2,1],[n-2,0]];

  }

  // Up Edge

  else if(i == 0) {

    a = [[0, j-1],[1,j-1],[1,j],[1,j+1],[0,j+1]];

  }

  // Left Edge

  else if(j == 0) {

    a = [[i-1,0],[i-1,1],[i,1],[i+1,0],[i+1,1]];

  }

  // Right Edge

  else if(j == n-1){

    a = [[i-1,n-1],[i-1,n-2],[i,n-2],[i+1,n-2],[i+1,n-1]];

  }

  // Down Edge

  else if(i == n-1){

    a = [[n-1,j-1],[n-2,j-1],[n-2,j],[n-2,j+1],[n-1,j+1]];

  }

  else {

    a = [[i-1,j],[i-1,j+1],[i,j+1],[i+1,j+1],[i+1,j],[i+1,j-1],[i,j-1],[i-1,j-1]];

  }

  let b = a.filter((el) => {

    let m = true;

    walls.forEach((wall) => {

      if(el[0] == wall[0] && el[1] == wall[1]) m = false;

    })

    return m;

  });

  return b;

}

​

​

function setup() {

  createCanvas(800, 800);

  grid = new Array(n);

  path = new Array(n);

  biasedPath = new Array(n);

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

    let colGrid = new Array(n);

    let colPath = new Array(n);

    let colBiased = new Array(n);

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

      colGrid[j] = 0;

      colPath[j] = [Infinity, [null, null]];

      colBiased[j] = Infinity;

    }

    grid[i] = colGrid;

    path[i] = colPath;

    biasedPath[i] = colBiased;

  }

  let i = start[0];

  let j = start[1];

  let k = target[0];

  let l = target[1];

  path[i][j] = [0, [null,null]];

  grid[k][l] = 3;

  biasedPath[i][j] = h(i, j);

  R.push([biasedPath[i][j], [i, j]]);

}

​

​

function draw() {

  background(220);

  show_grid();

  show_squares();

  if(R != [] && !finish && play) {

    R.sort();

    let u = R.shift()[1];

    if(u[0] == target[0] && u[1] == target[1]) {

      finish = true;

    }

    grid[u[0]][u[1]] = 2;

    adj = get_adj(u);

    adj.forEach((v) => {

        if(path[u[0]][u[1]][0] + 1 < path[v[0]][v[1]][0]){

          path[v[0]][v[1]][0] = path[u[0]][u[1]][0] + 1;

          path[v[0]][v[1]][1] = u;

​

          biasedPath[v[0]][v[1]] =

            path[v[0]][v[1]][0] + h(v[0],v[1]);

          R.push([biasedPath[v[0]][v[1]], [v[0], v[1]]]);

          grid[v[0]][v[1]] = 1;

        }

    });

  }

  else {

    // reset

  }

}

​

function show_grid() {

  for(let x = 0; x <= width; x += width/n) {

    line(x, 0, x, height);

  }

  for(let y = 0; y <= height; y += height/n){

    line(0, y, width, y);

  }

}

​

function show_squares() {

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

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

      noFill();

      if(i == start[0] && j == start[1]) {

        fill(255);

      }

      else if(grid[i][j] == 1) {

        fill(0, 100, 0);

      }

      else if(grid[i][j] == 2) {

        fill(100, 0, 0);

      }

      else if(grid[i][j] == 3) {

        fill(0);

      }

      else if(grid[i][j] == 4) {

        fill(255);

      }

      else if(grid[i][j] == 5) {

        fill(80, 0, 80);

      }

      square(i*(width/n), j*(height/n), width/n);

    }

  }

}

​

​

function mouseDragged() {

  let x = floor(mouseX/width*n);

  let y = floor(mouseY/height*n);

  if ((x < n) && (y < n )) {

    if(!walls.includes([x,y])){

        walls.push([x,y]);

      grid[x][y] = 5;

    }

  }

}

​

function keyPressed() {

  play = true;

}