Code viewer for Mind: A* Andross with Smart Fox ...

// Cloned by Philip on 29 Nov 2020 from Mind "A* Andross with Smart Fox mind do nothing if blocked" by Philip 
// Please leave this clone trail here.
 


// Cloned by Philip on 28 Nov 2020 from Mind "A* Andross Mind" by Philip 
// Please leave this clone trail here.
 


// Cloned by Philip on 24 Nov 2020 from Mind "Complex Mind (clone by Philip)" by Philip 
// Please leave this clone trail here.


// =================================================================================================
// Sample Mind for more complex starter World  
// =================================================================================================

// World tells us agent position and enemy position
// World does not tell us of existence of walls
// if return invalid move (not empty square) World just ignores it and we miss a turn 


var openSet = [];
var closedSet = [];
var map = null;
var targetSpot = null;
var result = null;
var drawSpotFunction = null;
var world = null;

AB.mind.getAction = function (x) //This is fed by the get state method		// x is an array of [ ai, aj, ei, ej ]
{
    var ai = x[0];
    var aj = x[1];
    var ei = x[2];
    var ej = x[3];
    map = x[4];
    drawSpotFunction = x[5];
    world= x[6];
    intialiseParameters();
    getEnemy();
    openSet = [];
    closedSet = [];
    getAgent();
    return result;
};

function getEnemy(){
    try{
    initiateSearch([ei, ej], [ai, aj])

    result.enemy.action = decideAction(result.enemy.nextSquare, ei, ej);  
    
}
    catch(error){
        console.log("error finding agent path")
    }
}

function getAgent(){
    try{
    initiateAgentSearch([ai, aj], [ei, ej]);
    if(result.agent.nextSquare) //This means it didn't find a square, likely because it was blocked by enemy
    result.agent.action = decideAction(result.agent.nextSquare, ai, aj);
    else 
    agentBackupStrategy();
    }
    catch(error){
        console.log("error finding agent path")
    }
}

function agentBackupStrategy(){
     result.agent.action =decideAction(result.enemy.path[result.enemy.path.length-1], ai, aj);
}
function decideAction(nextSquare, i, j){
    if(nextSquare){
     if (nextSquare.j > j) return ACTION_UP;
     if (nextSquare.j < j) return ACTION_DOWN;

     if (nextSquare.i > i) return ACTION_RIGHT;
     if (nextSquare.i < i) return ACTION_LEFT;
    }
    
    return ACTION_STAYSTILL;
}


function initiateAgentSearch(agentCoords, enemeyCoords){
    var initialSpot = new Space(agentCoords[0], agentCoords[1]);
    initialSpot.g = 0;
    targetSpot = new Space(enemeyCoords[0], enemeyCoords[1]);
    
    openSet.push(initialSpot);
    var winnerIndex = 0;
    var winningPath = findWorsePathWrapper(initialSpot);
    return winningPath;
}

function findWorsePathWrapper(initialSpot){
    
    var result;
    var limit = 0;
    result = {
        current : initialSpot, 
        winningIndex :0,
        maxedDepth: true
    }
    do {
        findWorsePath(result.current, result.winningIndex, 0);
        limit = limit +1;
    }
    while (!result.maxedDepth || limit < 200) //The size of this limit controls how far the agent looks per scan, its not really needed on smaller mazes but might be handy on bigger ones
    return result;
}

//I want to find a path back to the enemy to make sure I don't get stuck. 
//I need to make sure that this path 
//One thing, simply don't bother examinging thats in the path of the enemy
//This should then find the shortest path that doesn't overlap, which should be the second shortest path
//THis might not work in every scenario but should lead to a ring around the rosy type situation
//Im running into depth issues so I need to limit the length of the recursion to have it break and restart
function findWorsePath(initialSpot, winningIndex, depth){
    if(depth > 10) //The purpose of this is to break the recursion before the stack size gets too big
    return {
        current : initialSpot, 
        winningIndex :winningIndex,
        maxedDepth: true
    }
    
    for (var i = 0; i < openSet.length; i++)
        if (openSet[i].f < openSet[winningIndex].f) //Some mechanism to prune bad paths needs to be added
            winningIndex = i;
    
    current = openSet[winningIndex];
   // drawSpotFunction(world.scene, current.i, current.j); //This has a big performance hit but if you turn this on and stop after the first search then it caa be seen what the agent has checked.
    
    if(!current){
        console.log("failure - agent path not found");
        return {trapped : true};
    }
    
    if (current.i == targetSpot.i && current.j == targetSpot.j) {
        console.log("success - agent path found");
        return findNextMove(current, null, result.agent);
    } else {
        removeFromArray(openSet, current);
        closedSet.push(current);

        current.addNeighbours();
        current.neighbours.forEach(neighbour => {

            if (!neighbour.wall && !closedSet.includes(neighbour) && ((neighbour.i == targetSpot.i && neighbour.j == targetSpot.j) ||!ArrayIncludesSpot(result.enemy.path, neighbour))) {
                var tempG = current.g + heuristic(current, neighbour);
                var newPath = false;

                if (!neighbour.g || tempG < neighbour.g) {
                    neighbour.g = tempG;
                    newPath = true;
                }

                if (!ArrayIncludesSpot(openSet, neighbour))
                    openSet.push(neighbour);

                // Yes, it's a better path
                if (newPath) {
                    neighbour.h = heuristic(neighbour, targetSpot);
                    neighbour.f = neighbour.g + neighbour.h;
                    neighbour.parent = current;
                }
            }
        });

        //Time to recurse
        var output = findWorsePath(current, winningIndex, depth+1);
        return output;
    }
}

function initiateSearch(intialCoords, targetCoords) {
    var initialSpot = new Space(intialCoords[0], intialCoords[1]);
    initialSpot.g = 0;
    targetSpot = new Space(targetCoords[0], targetCoords[1]);

    openSet.push(initialSpot);
    var winnerIndex = 0;
    var winningPath = findShortestPath(initialSpot, winnerIndex);
    return winningPath;
}

//Need to add a no avaialable path clause but not sure what that looks like
function findShortestPath(current, winningIndex) {

    for (var i = 0; i < openSet.length; i++)
        if (openSet[i].f < openSet[winningIndex].f)
            winningIndex = i;

    current = openSet[winningIndex];

    if(!current){
        console.log("failure - enemy path not found");
        return {pathFound : false}
    }
    
    if (current.i == targetSpot.i && current.j == targetSpot.j) {
        console.log("success - enemy path found");
        return findNextMove(current, null, result.enemy);
    }
    else {

        removeFromArray(openSet, current);
        closedSet.push(current);

        current.addNeighbours();
        current.neighbours.forEach(neighbour => {

            if (!neighbour.wall && !closedSet.includes(neighbour)) {
                var tempG = current.g + heuristic(current, neighbour);
                var newPath = false;

                if (!neighbour.g || tempG < neighbour.g) {
                    neighbour.g = tempG;
                    newPath = true;
                }

                if (!ArrayIncludesSpot(openSet, neighbour))
                    openSet.push(neighbour);

                // Yes, it's a better path
                if (newPath) {
                    neighbour.h = heuristic(neighbour, targetSpot);
                    neighbour.f = neighbour.g + neighbour.h;
                    neighbour.parent = current;
                }
            }
        });

        //Time to recurse
        var output = findShortestPath(current, winningIndex);
        return output;
    }
}

function findNextMove(current, child, entity) {

    if (current.parent) { //If there is a parent, go to it and then check if it has a parent and so on
        entity.path.unshift(current.parent);
        findNextMove(current.parent, current, entity);
    }
    else
        entity.nextSquare = child; //if this doesn't have a parent, its where we started, so this is where we need to go
}

//Lets reset the parameters at the start of each run to make sure the objects are properly formed.
function intialiseParameters() {
    openSet = [];
    closedSet = [];
    targetSpot = null;
    result = new Entities();
}


//It'll be easier to use an object to handle each location
function Space(i, j) {
    this.i = i;
    this.j = j;
    this.wall = (map[i][j] !== 0);

    this.f = 0;
    this.g = null; //Remember to do a null check where this can be encountered as a null
    this.h = 0;
    this.neighbours = [];
    this.parent = undefined;

    this.addNeighbours = function () {
        var rows = map.length;
        var columns = map[0].length;
        var i = this.i;
        var j = this.j;

        if (i < columns - 1) this.neighbours.push(new Space(i + 1, j));
        if (i > 0) this.neighbours.push(new Space(i - 1, j));
        if (j < rows - 1) this.neighbours.push(new Space(i, j + 1));
        if (j > 0) this.neighbours.push(new Space(i, j - 1));

    }
}

function Entity() {
    this.nextSquare = null;
    this.path = [];
    this.action = null;
    this.pathFound = null;
}

//This is going to hold the data of all the entities that have been added
function Entities() {
    this.enemy = new Entity();
    this.agent = new Entity();
}

//**************** Utility Methods *******************//
// Function to delete element from the array
function removeFromArray(arr, elt) {
    // Could use indexOf here instead to be more efficient
    for (var i = arr.length - 1; i >= 0; i--) {
        if (arr[i].i == elt.i && arr[i].j == elt.j)
            arr.splice(i, 1);

    }

}

function ArrayIncludesSpot(arr, x) {
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].i == x.i && arr[i].j == x.j)
            return true
    }
    return false;
}

//Centralise the hueristic control so its easily changed
function heuristic(a, b) {
    //While I'm working on the algorithm, set this to something that will easily show movement
    return (Math.abs(a.i - b.i) + Math.abs(a.j - b.j));

}