// Cloned by Aoife Doherty on 2 Nov 2020 from World "A star (clone by Aoife Doherty)" by Aoife Doherty
// Please leave this clone trail here.
// 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
}
}