Code viewer for World: A star (clone by Aoife Doh...

// Cloned by Aoife Doherty on 1 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


//Aoife: one thing that would be fun to do is to make the heuristic not optimistic.

// is diagonal move allowed 
    const diagonal = true ;  //Aoife: change this if you want to allow if diagonal moves are valid or not.

//Aoife: the question is why is A* so unimpressive when you take the walls and diagonals and turn them both off.

// canvas size 
    const cw = 900; //Aoife: this is the size of the world (width)
    const ch = 600;  //Aoife: this is the size of the world (height)

// How many columns and rows 
// different each time
var rando = AB.randomIntAtoB ( 1, 5 );
var cols = 9 * rando; //Aoife: this is how many columns and rows make up the grid
var rows = 6 * rando; //Aoife: this is how many columns and rows make up the grid

 
// how many walls to make, from 0 to 1 
// different each time
const wallAmount = AB.randomFloatAtoB ( 0, 0.6 );  //Aoife: this is how many walls there is in the middle.
//Aoife: in the exercise, there is a (tricky) question saying to take the walls and turn them off.
//Aoife: He's highlighting this section for that and says 'you make this zero'



const backcolor = 'white'; //Aoife: doesn't even need to go here, because these paths will be equal to or worse than the shortest path (don't have to search every square)
const wallcolor = 'black'; //Aoife: a wall you can't get through
const pathcolor = 'darkred';

const opencolor     = 'lightgreen'; //Aoife: a square we know about but haven't checked what's beyond them
const closedcolor   = 'lightpink'; //Aoife: We've checked them, and their neighbours out.


// 2D array
var grid = new Array(cols); //Aoife: This is a 2D array that stores information for every spot in the grid; but the first thing is just make the grid with the columns; each column will have an array for the rows

// Open and closed set
var openSet = []; //Aoife: array of nodes still to be evaluated. The algorithm finishes when (1) openset is empty (could be no solution; if empty and haven't gotten to end) or (2) found end; starts with just one node, just the starting node.
var closedSet = []; //Aoife: array that stores the list of all the nodes that have finished being evaluated; everything done that you don't need to revisit again.

// Start and end
var start; //Aoife: start node (top left, grid[0][0])
var end; //Aoife: end node (bottom right, grid[cols-1][rows-1])

// Width and height of each cell of grid
var w, h; //Aoife: this is because e.g if you've set the grid to be 400 X 400 but there's 10 columns and rows, this shows how wide each spot should be.

// The road taken
var path = [];





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

function heuristic(a, b) //Aoife: this is the distance to go (Euclidian)
{
    if ( diagonal ) return ( dist(a.i, a.j, b.i, b.j) );  //Aoife: the diagonal feeds into the heuristic; dist is a function that calculates the Euclidian line; could change this to a manhattan distance if no diagonal, see very end of video 1.

        // 2D distance (Aoife: if diagonal are allowed, if not allowed, what is the distance? ot's the distance across + the distance down, and is always optimistic)
        // 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 optimisticf
        // not this is not optimistic if we can do diagonal move 
}




// Function to delete element from the array
function removeFromArray(arr, elt) //Aoife: this is because there's no easy way to just remove an item from list in JS
{
  // Could use indexOf here instead to be more efficient
  for (var i = arr.length - 1; i >= 0; i--) //Aoife: elt == element. Loop through array backwards, if array index == elt, then splice (delete through index); going backwards so indexs don't change when you delete.
    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) //Aoife: links to the setup function below. Makes a spot (i,j) to record the cost (g,h and f value) of this spot.
{

  // Location
  this.i = i; //Aoife: this is the x point, so can draw
  this.j = j; //Aoife: this is the y point, so can draw

  // f, g, and h values for A*
  this.f = 0; //Aoife; the f value for this spot (f = g + h)
  this.g = 0; //Aoife: the g value is the distance from start to point
  this.h = 0; //Aoife: the h value is the guess from spot to end.

  // Neighbors
  this.neighbors = []; //Aoife: what should I add to the open set? anything neighbouring the particular node, as long as we didn't check them before.

  // Where did I come from?
  this.previous = undefined; //Aoife: where did the neighbour come from...this is unnecessary coz by definition it'll be undefined

  // Am I an wall?
  if (random(1) < wallAmount)   this.wall = true; //Aoife: make a wall if you pick a random number between 0 and 1 and it's less than 0.6
  else                          this.wall = false; //if it's not randomly assigned a wall, make it a wall

  // Display me
  this.show = function(col) //Aoife: this is linked to draw; 
  {
    if (this.wall) //if there's a wall, fill the colour with black (wallcolour)
    {
      fill(wallcolor); //Aoife: this is the colour of each cell
      noStroke(); //Aoife: think this is the line colour around each cell
      
      // wall fills square 
            rect ( this.i * w, this.j * h, w,h); //This is to draw the spot, the w and h are for scaling e.g. if window is 400 X 400 and there's 10 cols/rows; work out how wide each spot is; see 20.25 in video 1 for how to see the full grid (-1 index)
            
      // wall only partially fills square 
      //    ellipse (   this.i * w + w / 2,     this.j * h + h / 2,     w * 0.7,    h * 0.7     );

    }
    else if (col)
    {
      fill(col);
      rect(this.i * w, this.j * h, w, h); 
    }
  };
  

  // Figure out who my neighbors are
  this.addNeighbors = function(grid) //Aoife: to  add neighbours from a particular grid
  {
    var i = this.i; //Aoife: the current i
    var j = this.j; //Aoife: the current j
    
    //Aoife: and these are the four neighbours to this spot on grid.
    //Aoife: the if part (i < cols -1 ) etc is to say 'what if they're at the edge'
    if (i < cols - 1)   this.neighbors.push(grid[i + 1][j]);  //Aoife: [i][j]; i = column; j = row
    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) //Aoife: this is adding in the neighbours if diagonals are allowed
// 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); //Aoife: the speed the path is running. Want to slow this down -> will be in the exercise. Double click on it, it's in p5 (it's a p5 thing to speed up and slow down paths)
    
    
  createCanvas(cw, ch);

  // Grid cell size
  w = width / cols; //e.g. if grid is 400 and columns  = 10, then width of each cell is 40
  h = height / rows; //e.g. if grid is 400 and rows  = 10, then height of each cell is 40

  // Making a 2D array
  for (var i = 0; i < cols; i++) //Aoife: this is, for each column, creating an array of rows to refer to any spot by the column and row position.
    grid[i] = new Array(rows); //Aoife: makes an array of rows for each col (var Cols)
// Aoife: this makes a 2D array    
// Aoife: can then check this by console.log(grid) -> array of X, each X has an array of XX.

  //Aoife: so what should be on the grid?
  for (var i = 0; i < cols; i++) //Aoife: for each item in col array
    for (var j = 0; j < rows; j++)  //Aoife: for each item in row array
      grid[i][j] = new Spot(i, j); //Aoife: make a spot (this links to spot function)

  // All the neighbors
  for (var i = 0; i < cols; i++) //Aoife: this is finding the neighbours of the spot just made
    for (var j = 0; j < rows; j++) //Aoife: this is finding the neighbours of the spot just made
      grid[i][j].addNeighbors(grid); //Aoife: this is finding the neighbours of the spot just made


  // Start and end
  start     = grid[0][0]; //Aoife: this is the top left of the grid
  end       = grid[cols - 1][rows - 1]; //Aoife: this is the bottom right of the grid.
  start.wall    = false; //Aoife: make sure the start is never a wall
  end.wall      = false; //Aoife: marke sure the end is never a wall

  // openSet starts with beginning only
  openSet.push(start); //Aoife: start with openset, thing to iterate through and check every possibility/node (start node; top left) and check all the possibilities there
  
    console.log('start search');

}



function draw() 
// the search goes on over many timesteps 
// each timestep, check one more square and draw current partial solution 
{

  // --- begin still searching -----------------------------
  if (openSet.length > 0) //Aoife: while there are spots to be evaluate.
  {

    // Best next option
    var winner = 0; //Assuming winner has the lowest index (first one) in the OpenSet
    
    for (var i = 0; i < openSet.length; i++) //Aoife: for each item in OpenSet (nodes to be checked)
      if (openSet[i].f < openSet[winner].f) //Aoife: if f is lower than the current winner (i.e value less than index 0)
        winner = i; //Aoife: it's now the winner
        
    var current = openSet[winner]; //Aoife: node in the OpenSet with the lowest f. i.e. from a point, evaluate all the openSet possibilities and which has the lowest f

    // Did I finish?
    if (current === end) //if current node is the end, we're done; start with openset, if the one that's best is the end, then done.
    {
      noLoop();
      console.log("success - found path"); //Aoife: when the score (g + f combined); if it's the end square, then it's done
    }

    // Best option moves from openSet to closedSet
    removeFromArray(openSet, current); //Aoife: this is a manual function written, because JS doesn't have an easy way to just remove objects from list.
    closedSet.push(current); //Aoife: ??

    // Check all the neighbors
    var neighbors = current.neighbors; //Aoife: get all the neighbours of the current spot
    
    //--- start of for loop -----------
    for (var i = 0; i < neighbors.length; i++) //Aoife: checkinge each neighbour of the spot
    {
      var neighbor = neighbors[i]; //Aoife: this is a neighbour

      // Valid next spot?
      if (!closedSet.includes(neighbor) && !neighbor.wall) //if neighbor isn't in the closed set, and the neighbour isn't the wall
      {
        var tempG = current.g + heuristic(neighbor, current); //G increases by 1 each time, e.g. time point increases by 1 for each time point

        // Is this a better path than before?
        var newPath = false;
        
        //Aoife: this if loop is saying; if already in the openSet see if i've gotten there faster than previously or if not,I've gotten there so add to OpenSet.
        if (openSet.includes(neighbor)) //Aoife, is the neighbour in the OpenSet?
        {
          if (tempG < neighbor.g) //Aoife: if the node has been evaluated before, have I gotten there more efficiently now.
            neighbor.g = tempG; //Aoife: then I got a better G
            newPath = true;
          }
        }
        else   //Aoife: if it's not in the open list
        {
          neighbor.g = tempG;
          newPath = true;  //Aoife: newpath if newG is better than previous G
          openSet.push(neighbor); //push the neighbour to the openList
        }

        // Yes, it's a better path
        if (newPath) //Aoife: only updating if newpath is better then you need to calculate the heuristic
        {
          neighbor.h = heuristic(neighbor, end); //the heuristic between the neighbour and the end (how long can i guess that it'll take me to get to end; Euclidian line)
          neighbor.f = neighbor.g + neighbor.h; //Aoife: time to get to current point + guess to the end
          neighbor.previous = current; //Aoife: needs to know where it comes from to trace back to define optimal path
        }
      }
    }
    //--- end of for loop -----------
    
  }
  // --- end still searching -----------------------------
  

  else //Aoife: if openSet is empty, there are no more nodes to be checked but they haven't gotten to the end.
  {
    console.log('fail - no path exists'); //Aoife: write to console
    noLoop();//Aoife: stops the loops
    return;
  }


  // Draw current state of everything
  background(backcolor);

  for (var i = 0; i < cols; i++) //Aoife: this is to draw all the spots in the grid
    for (var j = 0; j < rows; j++) //Aoife: this is to draw all the spots in the grid
      grid[i][j].show(); //Aoife: this is to draw all the spots in the grid

  for (var i = 0; i < closedSet.length; i++) //Aoife: Make the closed set a different colour
    closedSet[i].show( closedcolor ); //Aoife: Make the closed set a different colour

  for (var i = 0; i < openSet.length; i++) //Aoife: Make the closed set a different colour
    openSet[i].show( opencolor ); //Aoife: Make the open set a different colour


  // Find the path by working backwards
  path = []; //Aoife: path is a array, put the end in the list...and then keep adding each step before it, which backtracks over path
  var temp = current; //Aoife: temp is current
  path.push(temp); //Aoife: As long as there exists a previous, push
  while (temp.previous) //Aoife: ??
  {
    path.push(temp.previous); //Aoife: ??
    temp = temp.previous; //Aoife: ??
  }


  
if (diagonal)
{
  // path as continuous line; this draws the actual line
  noFill();
  stroke(pathcolor);
  strokeWeight(w / 8);
  beginShape();
  for (var i = 0; i < path.length; i++) 
        // the w/2 is to draw the path through the centre of each cell
        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++) //Aoife: loop through path
     path[i].show(pathcolor); //Aoife: show path
}


}