// Created by Theo Delettre (21262281) on 27 Oct 2021

function enemyThink(ai, aj, ei, ej, GRID){
    const gridsize = GRID.length;
    
    // The open set of positions left to visit
    var open = [];
    
    //AMAP serves as a way to add info to seen grid coords and so also serves as 
    // the "closed" set
    var AMAP = new Array(gridsize);
    for ( i = 0; i < gridsize ; i++ ) {
        AMAP[i] = new Array(gridsize);
        for ( j = 0; j < gridsize ; j++ ) {
	        AMAP[i][j] = null;
	    }
    }
    
    // We start by exploring our starting position, where the enemy currently is
    //  this also addsw it to our open set.
    addPos(ei,ej,0,null);
    var curr = open[0];
    
    // As long as we haven't reached our objective or ran out of unvisited points we run the algorithm
    while(curr !== null){
        // if heuristics is 0, we reached our objective and can stop searching
        if(curr.h===0){
            curr.isClosed = true;
            break;
        } else {
            // We identify all the neighboring positions and their properties
            //  & add them to the open set
            addNeighbors(curr.i,curr.j,curr.g);
            
            //The current position has now been closed and we can close it
            curr.isClosed = true;
            open.splice(open.indexOf(curr), 1);
            
            //restart the process but with the next best position (F) in the open set
            curr = maxOpen();
        }
    }
    
    // Once we found the path (or lack thereof), we send the info back to the world
    if(curr!==null){
        //Important to send the last position to find the whole path (through previous)
        var lastcurr = curr;
        
        // we get the values of the first step in our path
        if(curr.prev !== null)
        {
            while(curr.prev.prev!==null){
                curr = curr.prev;
            }
        }
        return {
            nexti:curr.i ,
            nextj: curr.j,
            AMAP: AMAP,
            last: lastcurr,
        };
    } else {
        return {
            nexti:ei ,
            nextj: ej,
            AMAP: AMAP,
            last: null,
        };
    }
    
    // This is our Pos class, each found coordinate in AMAP contains an instance of this
    function Pos(i,j,g,prev) {
        //coordinates
        this.i = i;
        this.j = j;
        
        // g, heuristic, and f values
        this.g = g;
        // Our heuristic is distance to the agent ( h = number of steps for the best case scenario, < otherwise )
        // The -1 is there because the objective is actually being in an adjacent square to the agent (we cannot move on top of agent)
        this.h = Math.abs(distance2D(ai,aj,this.i,this.j) - 1);
        this.f = this.g + this.h;
        
        // We start in the open set
        this.isClosed = false;
        
        // The Pos object we came from. Important to identify final path
        this.prev = prev;
        
        // If this position can be reached with a better path, we replace its values and origin
        this.update = function(newG, from) {
            if(newG < this.g){
                this.g = newG;
                this.f = this.g + this.h;
                this.prev = from;
            }
        }
    }
    
    function distance2D(ai,aj,bi,bj){
        return Math.abs(bi-ai)+Math.abs(bj-aj);
    }
    
    // Adds information to the given coordinate and adds them to the open set,
    // or tries to update them if they are already known but unvisited
    function addPos(i,j,newG,from){
        if(AMAP[i][j]===null){
            AMAP[i][j] = new Pos(i,j,newG,from);
            open.push(AMAP[i][j]);
        } else if(!AMAP[i][j].isClosed){
            AMAP[i][j].update(newG,from);
        }
    }
    
    // Identify all neighboring positions and adds them to the open set 
    function addNeighbors(x,y,currG){
        for ( i = x-1; i <= x+1 ; i++ ) {
            for ( j = y-1; j <= y+1 ; j++ ) {
                //if(x >=0 && y>=0 && x<gridsize && y<gridsize) { //Not necessary since there should be a wall outline
                
                if(GRID[i][j] != 1 && GRID[i][j] != 2 && !(x==i && y==j) && (x!= ai || y!=aj)){
                    addPos(i,j, currG + distance2D(x,y,i,j), AMAP[x][y])
                }
    	    }
        }
    }
    
    //finds the Pos with minimum F in the open set and returns in
    function maxOpen(){
        var maxPos = null;
        for ( i = 0; i < open.length ; i++ ) {
            if(maxPos===null){
                maxPos = open[i];
            } else if (open[i].f < maxPos.f){
                maxPos = open[i];
            }
        }
        return maxPos;
    }
}