Code viewer for World: A star v2 (clone by rohan)

// Cloned by rohan on 13 Nov 2021 from World "A star v2" by Tony Forde 
// Please leave this clone trail here.
 
// Cloned by Tony Forde on 3 Nov 2021 from World "A star (clone by Tony Forde) (clone by Tony Forde)" by Tony Forde 
// Please leave this clone trail here.
 


// Cloned by Tony Forde on 3 Nov 2021 from World "A star (clone by Tony Forde)" by Tony Forde 
// Please leave this clone trail here.
 
const cols = 4;
const rows = 4;
const diagonal = false;
const speed = 10;
const percentageWalls = 0.2;

var grid = new Array(cols);

var openSet = []; // Unvisited nodes
var closedSet = []; // Visited nodes
var start; // Start
var end; // End
var path = []; // Path to goal
var currentSquare = 1;
var w; // Width
var h; // Height
var nextMovej;
var nextMovei;


function Spot(i, j) {
  this.i = i;
  this.j = j;
  this.f = 0;
  this.g = 0;
  this.h = 0;
  this.neighbors = []; // An array to store all neighbors of Spot
  this.previous = undefined;
  this.wall = false; // Add an obstacle. By default, every sppt added is NOT a wall.

  // Set % number of wall spots and randomise
  if (random(1) < percentageWalls) this.wall = true;

  this.show = function (col) {
    fill(col);
    if (this.wall) fill(0); // Walls are black
    noStroke();
    //ellipse(this.i * w + w / 2, this.j * h + h / 2, w / 2, h / 2);
    rect(this.i * w, this.j * h, w - 1, h - 1);
  };

  this.addNeighbors = function (grid) {
    var i = this.i;
    var j = this.j;

    // Neighbors' comparative grid positions depend on where current node
    // is on the grid, e.g. corner, edge, middle, etc... different options.
    // Below allows for non-diagonal travel, i.e. it only caters for:
    // 1. UP 2. DOWN 3. LEFT 4. RIGHT
    

    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]);
    
    // Below allows for non-diagonal travel, i.e. it also caters for:
    // 5. TOP LEFT 6. TOP RIGHT 7. BOTTOM LEFT 8. BOTTOM RIGHT
    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() {
  createCanvas(400, 400);
  console.log("A*");
  console.log("starting at square 1 and moving to...");
  w = width / cols;
  h = width / rows;
  
  frameRate(speed);

  // Making a 2D array
  for (var i = 0; i < cols; i++) grid[i] = new Array(rows);

  // Create a new object for each spot in the grid
  // so we can assign some values to, i.e. f, g and h values for starters
  for (var i = 0; i < cols; i++)
    for (var j = 0; j < rows; j++) grid[i][j] = new Spot(i, j);

  // Add the neighbors of the spot
  for (var i = 0; i < cols; i++)
    for (var j = 0; j < rows; j++) grid[i][j].addNeighbors(grid);

  start = grid[2][3];
  end = grid[1][1];
//   start = grid[0][0];
//   end = grid[cols - 1][rows - 1];

  // Make sure start and end spots are never a wall
  start.wall = false;
  end.wall = false;

  openSet.push(start);

  console.log(grid);
}

function draw() {
  if (openSet.length > 0) {
    // While Open Set is not empty, keep going...
    // console.log('Open set length =  ' + openSet.length);
    var winner = 0; // Set the lowest, i.e. WINNING, index

    // Check which one is the lowest, i.e. current WINNER
    for (var i = 0; i < openSet.length; i++)
      if (openSet[i].f < openSet[winner].f) {
        winner = i;
      }

    var current = openSet[winner];

    // If current node equals END node, then we are done!
    if (current === end) {
      noLoop();
      console.log("DONE!");
    // console.log('Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
    }
    // Else continue below...

    // Remove current node from Open Set
    removeFromArray(openSet, current);

    // And push current to Closed Set
    closedSet.push(current);

    // Evaluate all neighbors before pushing them to Open Set
    var neighbors = current.neighbors;
    
    for (var i = 0; i < neighbors.length; i++) {
      var neighbor = neighbors[i];
      // var newPath = false; // Default    // TFXXXXXXXXXXXXX

      // If Closed Set does NOT include the neighbor
      // AND it is NOT a wall
      if (!closedSet.includes(neighbor) && !neighbor.wall) {
        // var tempG = current.g + 1;  // TFXXXXXXXXXXXXX
        var tempG = current.g + heuristic(neighbor, current); // TFXXXXXXXXXXXXX
        var newPath = false; // Default    // TFXXXXXXXXXXXXX
        // Check if Open Set includes neighbor
        if (openSet.includes(neighbor)) {
          if (tempG < neighbor.g) {
            neighbor.g = tempG;
            newPath = true;
          }
        } else {
          neighbor.g = tempG;
          newPath = true;
          openSet.push(neighbor);
        }

        if (newPath) {
          // Only need to calulate heuristic if we've found a new path
          // Now assign a heuristic value to the neighbor, i.e. distance to end goal:
          neighbor.h = heuristic(neighbor, end);

          // Now calculate f(n) = g(n) + h(n):
          neighbor.f = neighbor.g + neighbor.h;
          currentSquare++;
          console.log("current winner is square " + winner + 1);
          console.log("current winner has f(n) = " + openSet[winner].f);
          console.log("now check square " + currentSquare + " where..."); 
          console.log("g(" + currentSquare + ") = " + neighbor.g);
          console.log("h(" + currentSquare +  ") = " + neighbor.h);
          console.log("f(" + currentSquare +  ") = " + neighbor.f);

          // Set current spot to be parent of the next one (in next for loop interation)
          neighbor.previous = current;
        }
      }
    }
    // increase the g, i.e. distance from the start, for each additional neighbor

    // Now add all neighbors of current ONLY IF they have not been visted before.
  } else {
    console.log("No solution.");
    noLoop();
    return;
    // No solution
  }

  background(255);

  for (var i = 0; i < cols; i++)
    for (var j = 0; j < rows; j++) grid[i][j].show(color(255));

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

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

  path = [];
  var temp = current;
  path.push(temp);
  while (temp.previous) {
    // While there is a path history, i.e. previous node
    path.push(temp.previous);
    temp = temp.previous;
  }

  //for (var i = 0; i < path.length; i++) path[i].show(color(0, 0, 255));

  // Draw path line
  noFill();
  stroke(255, 0, 200);
  strokeWeight(w / 4);
  beginShape();
   for (var i = 0; i < path.length; i++) {
     vertex(path[i].i * w + w / 2, path[i].j * h + h / 2);
   }
       for (var i =  path.length-1; i >= 0; i--) {
         console.log('Path - row, col: ' + path[i].j + ', ' + path[i].i);
         var firstIndex = path.length - 1;
         var nextMoveIndex;
         //console.log('firstIndex: ' + firstIndex);
         //console.log('Start - row / col: ' + path[firstIndex].j + ' ,' + path[firstIndex].i);
         if (firstIndex > 0) {
            nextMoveIndex = path.length - 2;
            //console.log('nextMoveIndex: ' + nextMoveIndex);
            nextMovej = path[nextMoveIndex].j;
            nextMovei = path[nextMoveIndex].i;
            //console.log('Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
         }
         console.log('*** Next Move - row / col: ' + nextMovej + ' ,' + nextMovei);
   }
  endShape();
}

function removeFromArray(arr, elt) {
  // Custom function to remove an object from an array.
  // Loop backwards through array.
  // Only reason for going backwards is if we delete something it shortens the array length.
  // So we could skip an element in the loop.
  for (var i = arr.length - 1; i >= 0; i--) if (arr[i] == elt) arr.splice(i, 1); // Splice deletes a particular element in an array at an index
}

function heuristic(a, b) {
  // Custom function to estimate distance from points a to b.
  var d;

  if (diagonal) {
    // Calculate the Euclidean or 2D distance for diagonal search
    d = dist(a.i, a.j, b.i, b.j);
  } else {
    // Calculate the "Manhattan" or "Taxi Cab" distance for non-diagonal search
    d = abs(a.i - b.i) + abs(a.j - b.j);
  }
  return d;
}