// 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 timevar 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 arrayvar grid =newArray(cols);// Open and closed setvar openSet =[];var closedSet =[];// Start and endvar start;var end;// Width and height of each cell of gridvar w, h;// The road takenvar 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 elsereturn( 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 arrayfunction removeFromArray(arr, elt){// Could use indexOf here instead to be more efficientfor(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 gridfunctionSpot(i, j){// Locationthis.i = i;this.j = j;// f, g, and h values for A*this.f =0;this.g =0;this.h =0;// Neighborsthis.neighbors =[];// Where did I come from?this.previous =undefined;// Display methis.show =function(col){
fill(backcolor);
stroke(51);
rect(this.i * w,this.j * h, w, h);};// Figure out who my neighbors arethis.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 arrayfor(var i =0; i < cols; i++)
grid[i]=newArray(rows);for(var i =0; i < cols; i++)for(var j =0; j < rows; j++)
grid[i][j]=newSpot(i, j);// All the neighborsfor(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);}}