// Cloned by AMARA on 26 Nov 2020 from World "Akshara's A star" by AMARA
// Please leave this clone trail here.
//A* path finding tutorial
var rows = 100;
var cols = 100;
var canvasW = 500;
var canvasH = 500;
var grid = new Array(cols); // the grid is an array of cols
// openset stores a list of all the nodes that still need to be evaluated, ie everything that you need to visit,
// the open set starts with just one node, the starting node.
// the algorothm is finished when the openset is empty and it still hasn't managed to find the end node.
var openSet = [];
// closed set stores a list of all the nodes that have finished being evaluated, ie everything that you dontt need to revisit
// closed set starts empty
var closedSet = [];
var start;
var end;
var w;
var h;
var path = [];
//var nosolution = false;
function removeFromArray(arr, elt){
for(var i =arr.length-1 ; i>=0 ;i--){
if(arr[i] == elt) {
arr.splice(i,1);
}
}
}
function heuristic(a,b) {
// its doing what is known as a Eucilidean distance that uses the pythagorean theorem.
var d = dist(a.i,a.j,b.i,b.j);
// we also get good results when we do it with the manhattan distance
//var d = abs(a.i-b.i)+abs(a.j-b.j);
return d;
}
//constructor function to create an Object-12.41
function Spot(i,j) {
this.f = 0; // this is f(n)
this.g = 0 // this is g(n) and it has to start with a high number
this.h = 0;// this is h(n)
// inorder to show the spot where it is
this.i = i;
this.j = j;
//previous
this.previous = undefined;
// we can add the is wall attribute
this.wall = false;
if (random(1)<0.3){
this.wall = true;
}
//this.solved = false;
//1----identify all the neighbours of current--1.11.17....
//one way of doing this is writing a an array to spot
this.neighbors = [];
this.addNeighbors = function(){
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(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]);
}
//but there is a possibility that I could be on the edege
}
this.show = function(col) {
fill(col);
if(this.wall){
fill(0);
}
noStroke();
//rect(this.i*w,this.j*h, w-1,h-1);
ellipse(this.i*w+w/2,this.j*h+h/2, w-1,h-1);
}
}
function setup() {
createCanvas(canvasH,canvasW);
console.log('A*');
w = canvasW/cols;
h = canvasH/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);
}
}
for(var i=0; i<cols;i++)
{
for(var j=0;j<rows;j++){
grid[i][j].addNeighbors(grid);
}
}
start = grid[0][0];
end = grid[cols-1][rows-1];
start.wall = false;
end.wall = false;
openSet.push(start);
// console.log(grid);
}
// changed from mousePressed to mouse pressed
function draw(){
//as long as there are spots to be evaluated, you need to do this , but because you already have the draw fuunction which laready does this
if (openSet.length > 0){
// we can keep going
// current should be a node in the openset with the lowest f, evaluate al the openn set possibilities and what has the lowest f,
//whats gonna be the best this getting me to the end. so how do we find wht somethings F is and which has the lowest F.
var winner = 0;
for(var i=0;i<openSet.length;i++){
if(openSet[i].f < openSet[winner].f){
winner = i;
}
}
var current = openSet[winner];
if(current === end){
// it finishes at the point when the spot in the openset , with the lowest f score---- then you are done. next you have to find the path
//----2----path was innitially here but he decides to move it because he wants to evaluate the path in every frama
noLoop();
console.log('DONE');
}
//openSet.remove(current); // However this is not possible in javascript hence a function is required
removeFromArray(openSet, current);
closedSet.push(current);
var neighbors = current.neighbors;
for(var i=0;i<neighbors.length;i++) {
var neighbor = neighbors[i]; //we are now checking every neighbor
// except we dont want to do this, because what if the neighbor is in the closed set?
//neighbor.g = neighbor.g + 1;
// so how do you say if an object is a part of an object?, this is again where he wants to doo some kind of efficientsearch alg,
// but a search within a search, so we want to make that more efficient out here, but the way he chooses to do this is-look
// for javascript array methods.
if(!closedSet.includes(neighbor) && !neighbor.wall) {
//identify the tentative gscore, and thats the reason why you dont want to just automatically give the neighbor a gscore
//is because he might have already gotten to that, even though it is not in the closed set.it could still be something that has already been
//evaluated and he might have gotten to it already in a more efficient way. because if its in the open set already, but its a neighbor,
// he might have to it with a lower gscore and he will want to keep that lower gscore. so what we're gonna do is say
//tentative_gScore := gScore[current] + d(current, neighbor)
var tempG = current.g + 1;
var newPath = false;
// now he wants to figure out if its something thats already in th eopenlist.
// so does the opens set include that neighbor
if(openSet.includes(neighbor)) {
//he wants to check if its something that he's evaluated before, because if its something that he's evaluated befoe, then, he would like to
// figure out if its a better g
if (tempG<neighbor.g){
//because if that the case then he has a better g
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
// so basically all of these things are already in th eopenset, and if theyare already in th eopn set, and if it needs to be evaluated
// still you need to check if I can get there faster than i did previously.
// and if they are not in th eopen set... then ive gotten there and I will add it to th eopen list
newPath = true;
openSet.push(neighbor);
// now you need to figure out whats its Gscore and what is its Fscore and hence firstly find the heuristic.
}
// the heuristic is the approximate distance between the neighbor and the end. a heuristic is an educated guess and there are lots heuris-
//tics, but in this case, he uses the eucilidean distance. we write a function for the heuristic and you should find it at the top
//along with all the other defininitions
if(newPath)
{
neighbor.h = heuristic(neighbor,end);
neighbor.f = neighbor.g + neighbor.h;
// it is important for each node to remember how it got to that position. It helps it trace back to the source after it has found its
// destination
neighbor.previous = current;
}
}
}
} else{
// otherwise no solution
console.log('no solution');
//nosolution = true;
noLoop();
return;
}
background(255);
// in order to debug this as we are going along, we are going to draw all the spots in the grid
for(var i=0;i<cols;i++){
for(var j=0;j<rows;j++){
grid[i][j].show(color(255)); // each spot is going to have a function to show itself.
}
}
for (var i=0;i<openSet.length;i++){
//openSet[i].show(color(0,0,255));
}
for (var i=0;i<closedSet.length;i++){
//closedSet[i].show(color(0,255,0));
}
path = [];
var temp = current;
path.push(temp);
while(temp.previous) {
path.push(temp.previous);
temp = temp.previous;
}
//for(var i=0;i<path.length;i++) {
//path[i].show(color(255,0,0));
//}
stroke(0,200,255);
strokeWeight(w/4);
noFill();
beginShape();
for(var i = 0; i < path.length; i++){
vertex(path[i].i*w+w/2, path[i].j*h+h/2)
}
endShape();
}