// Cloned by test on 26 Oct 2019 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;const MUSIC="/uploads/oneilf27/dark-techno-city.mp3";var music =newAudio( MUSIC );
music.loop =true;
music.play();// canvas size const cw =900;const ch =600;// How many columns and rows // different each timevar rando = AB.randomIntAtoB (1,5);var cols =9* rando;var rows =6* rando;// how many walls to make, from 0 to 1 // different each timeconst wallAmount = AB.randomFloatAtoB (0,0.8);const backcolor ='lightskyblue';const wallcolor ='navy';const pathcolor ='lightyellow';const opencolor ='palegreen';const closedcolor ='mediumpurple';// 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;// Am I an wall?if(random(1)< wallAmount)this.wall =true;elsethis.wall =false;// Display methis.show =function(col){if(this.wall){
fill(wallcolor);
noStroke();// wall fills square
rect (this.i * w,this.j * h, w, h );// wall only partially fills square // ellipse ( this.i * w + w / 2, this.j * h + h / 2, w * 0.7, h * 0.7 );}elseif(col){
fill(col);
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 (5);
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[0][0];
end = grid[cols -1][rows -1];
start.wall =false;
end.wall =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 {// --- begin still searching -----------------------------if(openSet.length >0){// Best next optionvar winner =0;for(var i =0; i < openSet.length; i++)if(openSet[i].f < openSet[winner].f)
winner = i;var current = openSet[winner];// Did I finish?if(current === end){
noLoop();
console.log("success - found path");}// Best option moves from openSet to closedSet
removeFromArray(openSet, current);
closedSet.push(current);// Check all the neighborsvar neighbors = current.neighbors;//--- start of for loop -----------for(var i =0; i < neighbors.length; i++){var neighbor = neighbors[i];// Valid next spot?if(!closedSet.includes(neighbor)&&!neighbor.wall){var tempG = current.g + heuristic(neighbor, current);// Is this a better path than before?var newPath =false;if(openSet.includes(neighbor)){if(tempG < neighbor.g){
neighbor.g = tempG;
newPath =true;}}else{
neighbor.g = tempG;
newPath =true;
openSet.push(neighbor);}// Yes, it's a better pathif(newPath){
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;}}}//--- end of for loop -----------}// --- end still searching -----------------------------else{
console.log('fail - no path exists');
noLoop();return;}// 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
path =[];var temp = current;
path.push(temp);while(temp.previous){
path.push(temp.previous);
temp = temp.previous;}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);}}