Code viewer for World: A star (clone by Jack O'Br...

// Cloned by junhao zhao on 15 Nov 2022 from World "A star (clone by Jack O'Brien) (clone by Jack O'Brien)" by Jack O'Brien 
// Please leave this clone trail here.
 


// Cloned by Jack O'Brien on 12 Nov 2020 from World "A star (clone by Jack O'Brien)" by Jack O'Brien 
// Please leave this clone trail here.
 


// Cloned by Jack O'Brien on 5 Nov 2020 from World "A star" by "Coding Train" project 
// Please leave this clone trail here.
 

// Port of 
// https://github.com/nature-of-code/NOC-S17-2-Intelligence-Learning/tree/master/week1-graphs/05_astar


// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// Part 1: https://youtu.be/aKYlikFAV4k
// Part 2: https://youtu.be/EaZxUCWAjb0
// Part 3: https://youtu.be/jwRT4PCT6RU

// is diagonal move allowed 
    const diagonal = true ;



// canvas size 
    const cw = 900;
    const ch = 600; 

// How many columns and rows 
// different each time
var rando = AB.randomIntAtoB ( 1, 5 );
var cols = 30;
var rows = 20;

 
// how many walls to make, from 0 to 1 
// different each time
// const wallAmount = AB.randomFloatAtoB ( 0, 0.2 );  
// const waterAmount = AB.randomFloatAtoB ( 0.4, 0.8 );

const backcolor = 'white';
const wallcolor = 'black';
const pathcolor = 'darkred';

const opencolor     = 'lightgreen';
const closedcolor   = 'lightpink';

const watercolor   = 'blue';


// 2D array
var grid = new Array(cols);

// Open and closed set
var openSet = [];
var closedSet = [];

// Start and end
var start;
var end;

// Width and height of each cell of grid
var w, h;

// The road taken
var path = [];





//=== heuristic ===========================
// this must be always optimistic - real time will be this or longer 

function heuristic(a, b) 
{
    if ( diagonal ) return ( dist(a.i, a.j, b.i, b.j) );

        // 2D distance
        // dist is a P5 function 

    else  return ( abs(a.i - b.i) + abs(a.j - b.j) );

        // else not diagonal, can only go across and down 
        // so this is optimistic
        // not this is not optimistic if we can do diagonal move 
}




// Function to delete element from the array
function removeFromArray(arr, elt) 
{
  // Could use indexOf here instead to be more efficient
  for (var i = arr.length - 1; i >= 0; i--) 
    if (arr[i] == elt) 
      arr.splice(i, 1);
}




// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning

// Part 1: https://youtu.be/aKYlikFAV4k
// Part 2: https://youtu.be/EaZxUCWAjb0
// Part 3: https://youtu.be/jwRT4PCT6RU

// An object to describe a spot in the grid
function Spot(i, j) 
{

  // Location
  this.i = i;
  this.j = j;

  // f, g, and h values for A*
  this.f = 0;
  this.g = 0;
  this.h = 0;

  // Neighbors
  this.neighbors = [];

  // Where did I come from?
  this.previous = undefined;


  // Display me
  this.show = function(col) 
  {
      fill(backcolor);
      stroke(51);
      rect(this.i * w, this.j * h, w, h);
    
  };
  

  // Figure out who my neighbors are
  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)
// diagonals are also neighbours:
{
    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() 
{
    // slower frame rate to see how it is working 
   // frameRate (2);
    
    
  createCanvas(cw, ch);

  // Grid cell size
  w = width / cols;
  h = height / rows;

  // Making a 2D array
  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);

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


  // Start and end
  start     = grid[AB.randomIntAtoB ( 0, cols - 1)][AB.randomIntAtoB ( 0, rows - 1)];
  end       = grid[AB.randomIntAtoB ( 0, cols - 1)][AB.randomIntAtoB ( 0, rows - 1)];
  
  start.wall    = false;
  end.wall      = false;
  start.water    = false;
  end.water      = false;

  // openSet starts with beginning only
  openSet.push(start);
  
    console.log('start search');

}



function draw() 
// the search goes on over many timesteps 
// each timestep, check one more square and draw current partial solution 
{
    
  // Draw current state of everything
  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 );



  // Find the path by working backwards
  
noFill();
  stroke(pathcolor);
  strokeWeight(w / 8);
  beginShape();
  for (var i = 0; i < 10; i++) 
        vertex (    (i * w) + w / 2,     (i * h) + h / 2   );
  endShape();

  
if (diagonal)
{
  // path as continuous line
  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 
{
    // path as solid blocks 
   for (var i = 0; i < path.length; i++) 
     path[i].show(pathcolor);
}


}