// Cloned by Harpreet Singh on 29 Oct 2019 from World "Cube in a cube" by Harpreet Singh 
// Please leave this clone trail here.
 
// Cloned by Harpreet Singh on 5 Oct 2019 from World "One Cube World (P5)" by Starter user 
// Please leave this clone trail here.
 
function removeFromArray(arr, ele){
    for (var i=arr.length-1; i>=0; i--){
        if (arr[i] == ele){
            arr.splice(i, 1);
        }
    }
} 

function heuristic(a,b){
    var d = dist(a.i, a.j, b.i, b.j);
    //var d = abs(a.i-b.i) + abs(a.j-b.j);
    return d;
}


var cols = 50;
var rows = 50;

var openSet = [];
var closedSet = [];

var start;
var end;

var path = [];

var w, h; //to find how we split the canvas to available grid points
 
var grid = new Array(cols);

function Spot(i, j){
    this.i = i;
    this.j = j;
    
    this.f = 0;
    this.g = 0;
    this.h = 0;
    
    this.neighbours = [];
    this.previous = undefined;
    
    this.wall = false;
    
    if (random(1)<0.4){
        this.wall = true;
    }
    
    
    this.show = function(c){
        fill(c);
        noStroke();
        if(this.wall){
            fill(0);
        }
        rect(this.i*w, this.j*h, w-1, h-1);
    }
    
    this.addNeighbours = function(grid){
        var i = this.i;
        var j = this.j;
        
        if (i<cols-1){
            this.neighbours.push(grid[i+1][j]);
        }
        
        if (i>0){
            this.neighbours.push(grid[i-1][j]);
        }
        
        if (j<rows-1){
            this.neighbours.push(grid[i][j+1]);
        }
        
        if (j>0){
            this.neighbours.push(grid[i][j-1]);
        }
        
        
        //addd diagonal neighbours
        
        if (i>0 && j>0){
            this.neighbours.push(grid[i-1][j-1]);
        }
        
        if (i<cols-1 && j>0){
            this.neighbours.push(grid[i+1][j-1]);
        }
        
        if(i>0 && j<rows-1){
            this.neighbours.push(grid[i-1][j+1]);
        }
        
        if(i<cols-1 && j<rows-1){
            this.neighbours.push(grid[i+1][j+1]);
        }
        
    }
}

function setup()        // "setup" is called once at start of run 
{
  createCanvas (600, 600);
  console.log('A* Search');
  frameRate(5);
  
  w = width/cols;
  h = height/rows;
  
  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].addNeighbours(grid);
      }
  }
  
  start = grid[0][0];
  //end = grid[cols-1][rows-1];
  start.wall = false;
  //end.wall = false;
  
  openSet.push(start);
  console.log(grid);
}

function draw()         // "draw" is called every timestep during run 
{
    
    
    end = grid[AB.randomIntAtoB(1,cols-2)][AB.randomIntAtoB(1,rows-2)];
    //start.wall = false;
    end.wall = false;
    
    
    if (openSet.length > 0){
        //keep going
        
        //current := the node in openSet having the lowest fScore[] value
        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){
            //we are done
            noLoop();
            console.log('Done!caught the moving target')
        }
        
        removeFromArray(openSet, current);
        closedSet.push(current);
        
        var neighbours = current.neighbours;
        
        for(var i=0; i<neighbours.length; i++){
            var neighbour = neighbours[i];
            
            if(!closedSet.includes(neighbour) && !neighbour.wall){
                var tempG = current.g + 1;
                
                var newPath = false;
                
                if(openSet.includes(neighbour)){
                    if (tempG < neighbour.g){
                        neighbour.g = tempG;
                        newPath = true;
                    }
                }else{
                    neighbour.g = tempG;
                    openSet.push(neighbour);
                    newPath = true;
                }
                
                if (newPath == true){
                    neighbour.h = heuristic(neighbour, end);
                    neighbour.f = neighbour.g + neighbour.h;
                    neighbour.previous = current;    
                }
            }
        }
    } else{
        //no solution
        console.log('no solution');
        noLoop();
        return;
    }
    
    background(0);
    
    for(var i=0; i<cols; i++){
      for(var j=0; j<rows; j++){
          grid[i][j].show(color(255));
        }
    }
    
    
    
    
    path = [];
    var temp = current;
    path.push(temp);
    while(temp.previous){
        path.push(temp.previous);
        temp = temp.previous;
    }    
  
    
    noFill();
    stroke(0);
    beginShape();
    
    for (var n=0; n<path.length; n++){
        vertex(path[n].i*w+w/2, path[n].j*h+h/2);
    }
    
    endShape();
    
    if (path.length>0){
        var tempx = path[0].i;
        var tempy = path[0].j;
    
        grid[tempx][tempy].show(color(0,0,255));    
    }
    
}