// Cloned by Dheeraj Putta on 3 Nov 2020 from Mind "Complex Mind" by Starter user 
// 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 
// #### Created code ####

const depth = 3;

function Queue() {
    this.items = []

    this.enqueue = function (elm) {
        this.items.push(elm);
    }

    this.dequeue = function () {
        var temp = this.items[0];
        this.items.shift();
        return temp;
    }
}

function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
    this.score = null;
}

function Tree(data) {
    this.root = new Node(data);

    this.populateTree = function () {
        var queue = new Queue();

        this.addChildren(this.root);

        queue.enqueue(this.root);

        currentNode = queue.dequeue();

        var d = 0;

        while (currentNode && d < depth - 1) {
            for (var i = 0; i < currentNode.children.length; i++) {
                this.addChildren(currentNode.children[i]);
                queue.enqueue(currentNode.children[i]);
            }

            currentNode = queue.dequeue();
            d++;
        }
    };

    this.addChildren = function (parent) {
        for (var i = 0; i < parent.data.neighbors.length; i++) {
            var child = new Node(parent.data.neighbors[i])
            child.parent = parent;
            parent.children.push(child);
        }
    };

    // this.addChildren = function (parent) {
    //     for (var i = 0; i < parent.data.neighbors.length; i++) {
    //         if (parent.parent && parent.data.neighbors[i] != parent.parent.data) {
    //             var child = new Node(parent.data.neighbors[i])
    //             child.parent = parent;
    //             parent.children.push(child);
    //         }
    //         else if (!parent.parent) {
    //             var child = new Node(parent.data.neighbors[i])
    //             child.parent = parent;
    //             parent.children.push(child);
    //         }
    //     }
    // }

    this.miniMax = function (ei, ej) {
        (function recurse(node, d) {
            for (var i = 0; i < node.children.length; i++) {
                recurse(node.children[i], d + 1);
            }

            if (node.children.length == 0) {
                node.score = heuristicMind(node.data.i, node.data.j, ei, ej);
            }
            else if (d % 2 == 0) {
                node.score = Math.max(...node.children.map(x => x.score));
            }
            else {
                node.score = Math.min(...node.children.map(x => x.score));
            }
        })(this.root, 0)
    };

    this.getBest = function () {
        var score = -1;
        var best = null;
        for (var i = 0; i < this.root.children.length; i++) {
            if (score < this.root.children[i].score) {
                best = this.root.children[i];
                score = this.root.children[i].score;
            }
        }
        return best;
    };
    // this.addChildren = function (parent) {
    //     for (var i = 0; i < parent.data.neighbors.length; i++) {
    //         if (parent.parent && parent.data.neighbors[i] != parent.parent.data) {
    //             var child = new Node(parent.data.neighbors[i])
    //             child.parent = parent;
    //             parent.children.push(child);
    //         }
    //     }
    // }

    // this.removeParents = function (child) {
    //     var current = child;
    //     for (var i = 0; i < 4; i++) {
    //         try {
    //             removeFromArray(child.children, current.parent);
    //         }
    //         catch (err) {

    //         }
    //         current = current.parent;
    //     }
    // }
}

function heuristicMind(ai, aj, ei, ej) {
    if (!trapMove(ai, aj)) {
        var x = new THREE.Vector3(ai, 0, aj);
        var y = new THREE.Vector3(ei, 0, ej);
        return (x.manhattanDistanceTo(y));
    }
    else {
        return 0;
    }
}

function removeFromArray(arr, elt) {
    // Could use indexOf here instead to be more efficient
    arr.splice(arr.indexOf(elt), 1);
}

function occupiedMind(i, j) {
    if (GRID[i][j].type == GRID_WALL) return true;		// fixed objects	 
    if (GRID[i][j].type == GRID_MAZE) return true;

    return false;
}

function trapMove(i, j) { // detect if agent will become trapped
    var walls = [];

    //up
    walls.push(i < gridsize - 1 && occupiedMind(i + 1, j));

    //down
    walls.push(i > 0 && occupiedMind(i - 1, j));

    //right
    walls.push(j < gridsize - 1 && occupiedMind(i, j + 1));

    //left
    walls.push(j > 0 && occupiedMind(i, j - 1));

    if (walls.reduce((a, b) => a + b, 0) >= 3) {
        return true;
    }
    else {
        return false;
    }
}

AB.mind.getAction = function (x)		// 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];

    // if strictly move away, will get stuck at wall, so introduce randomness

    var tree = new Tree(GRID[ai][aj]);
    tree.populateTree();
    tree.miniMax(ei, ej);
    var move = tree.getBest().data
    console.log(tree);
    console.log("Agent move: ", move);

    // if MiniMax move will cause trap then or agent is moving to previous start location then pick a random move
    if (trapMove(move.i, move.j) || (AB.step > 0 && agentLastVisited.reduce((x, y) => x && [move.i, move.j].includes(y), true))) {
        var randomMoves = [...Array(GRID[ai][aj].neighbors.length).keys()];
        while (true) {
            var rand = AB.randomElementOfArray(randomMoves);
            move = GRID[ai][aj].neighbors[rand];
            if (trapMove(move.i, move.j)) {
                removeFromArray(randomMoves, rand);
            }
            else {
                return (move);
            }
        }
    }
    else {
        return (move);
    }
};