// 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("pathNot found")
}
}
function getAgent(){
try {
initiateAgentSearch([ai, aj], [ei, ej]);
result.agent.action = decideAction(result.agent.nextSquare, ai, aj);
}
catch(error){
console.log("pathNot found");
}
}
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));
}