/* jorge blanco
student number 19214700
Default logic: G - using distance from Last Agent Move + H - using distance Chebyshev with Last Enemy Move
Reason i went with 'Chebyshev' - the enemy can move in 8 directions, while the agent only in 4.
I keep the agent active and punish for visiting old spots (want him/her to be on the move all the time) and areas close to the enemy.
I only look at the 4 moves the agent has next and ignore a wall or if the enemy is next (A* is not for moving objects). I dont want to exclude any moves
close to the enemy, so that we can get out of very tight areas. The agent does get in into the "U" trap and if the enemey is behind then game over.
I added the option to speed up / re-play current map / use Manhatan from the default strategy / also compare if it pays of to punished visited spots.
Next step: revisit the logic to try to reduce the number of bad steps, by combining A* with anothe strategy
*/
AB.newDiv("selectdiv");
AB.newDiv("speedDiv");
AB.newDiv("otherStategyDiv");
$("#selectdiv").css({
"padding-left": "30vw",
"color": "white"
});
$("#speedDiv").css({
"padding-left": "30vw",
"color": "white"
});
$("#otherStategyDiv").css({
"padding-left": "30vw",
"color": "white"
});
$("#selectdiv").html("<div>H - using distance Chebyshev with Last Enemy Move <br> G - using distance from Last Agent Move <br><br></div><div>Note: if stuck press 'resume'</div>Pick strategy: <span id='actorlist'><select onchange='setStragety(this)'><option value='punish'>1 Punish visited spots/close to enemy</option><option value='dontPunish'>2 Dont punish visited spots/close to enemy</option></select><button onclick='startAgain();'>re-play</button></span>");
$("#otherStategyDiv").html("<span id='actorlist'><input type='checkbox' value='manhatan' onclick='useManhatan(this);'>G + H Manhattan (NY)<br> </span>");
$("#speedDiv").html("Set speed: <span id='actorlist'><select onchange='setSpeed(this)'><option value='100'>100</option><option value='300'>300</option><option value='50'>50</option><option value='1'>1</option></select></span>");
var fistMoveAgent = null; // first move agent
var lastMoveAgent = null; // last move agent
var firstMoveEnemy = null; // first move enemy
var startPositionEnemy = null; // start position enemy
var lastMoveEnemy = null; // last move enemy
var openSet = []; // open set
var closedSet = []; // closed set
var grid = new Grid();
// configuration
var strategyScores = { 1: { d:[], m: [] }, 2: { d:[], m:[] } };
var strategySelectType = 1;
var useManhatanGH = false;
const average = arr => Math.round((arr.reduce( ( p, c ) => p + c, 0 ) / arr.length) * 100) / 100;
function setStragety(option) {
var value = option.value;
if (value == 'punish') {
strategySelectType = 1;
} else if (value == 'dontPunish') {
strategySelectType = 2;
}
startAgain();
}
function useManhatan(control) {
useManhatanGH = control.checked;
}
function setSpeed(option){
AB.controlPause();
AB.clockTick = option.value;
AB.controlRun();
}
// reset the world
function startAgain() {
AB.controlPause();
AB.step = 0;
AB.abortRun = false;
goodsteps = -2;
badsteps = 0;
ei = firstMoveEnemy.x;
ej = firstMoveEnemy.y;
ai = fistMoveAgent.x;
aj = fistMoveAgent.y;
AB.world.takeAction(4);
grid = new Grid();
AB.controlRun();
}
// update the details once the run has ended
AB.world.endRun = function() {
musicPause();
if ( AB.abortRun ) {
AB.msg ( " <br> <font color=red> <B> Agent trapped. Final score zero. </B> </font> ", 3 );
if (useManhatanGH) {
strategyScores[strategySelectType].m.push(0);
} else {
strategyScores[strategySelectType].d.push(0);
}
}
else {
AB.msg ( " <br> <font color=green> <B> Run over. </B> </font> ", 3 );
if (useManhatanGH) {
strategyScores[strategySelectType].m.push(AB.world.getScore());
} else {
strategyScores[strategySelectType].d.push(AB.world.getScore());
}
}
AB.msg ( "<br><br><span>Strategy 1: " + average(strategyScores[1].d) + "% /" + (strategyScores[1].d.length) + " - NY - " + average(strategyScores[1].m) + "% /" + (strategyScores[1].m.length) +" </span><br>"+
"<span>Strategy 2: " + average(strategyScores[2].d) + "% /" + (strategyScores[2].d.length) + " - NY - " + average(strategyScores[2].m) + "% /" + (strategyScores[2].m.length) + " </span>", 4);
};
AB.mind.getAction = function ( x ) {
var currentMoveAgent = grid.getElementPositionGrow(x[0], x[1]);
grid.markNoWall(currentMoveAgent);
console.log ("Current agent " + currentMoveAgent.x + '-' + currentMoveAgent.y);
var currentMoveEnemy = grid.getElementPositionGrow(x[2], x[3]);
grid.markNoWall(currentMoveEnemy);
console.log ("Current enemy " + currentMoveEnemy.x + '-' + currentMoveEnemy.y);
// mark agent
if (lastMoveAgent === null) {
lastMoveAgent = currentMoveAgent.clone();
fistMoveAgent = currentMoveAgent.clone();
}
else if (!lastMoveAgent.areSame(currentMoveAgent)) {
grid.markWall(lastMoveAgent);
console.log ("Agent hit a wall last move " + lastMoveAgent.x + '-' + lastMoveAgent.y);
}
else {
closedSet.push(lastMoveAgent);
}
// mark enemy
if (lastMoveEnemy === null) {
lastMoveEnemy = currentMoveEnemy.clone();
firstMoveEnemy = currentMoveEnemy.clone();
} else if (lastMoveEnemy.areSame(currentMoveEnemy)) {
currentMoveEnemy.samePosition ++;
console.log ("Enemy has not moved " + currentMoveEnemy.x + '-' + currentMoveEnemy.y + ' past ' + currentMoveEnemy.samePosition + ' moves');
}
var nextPossibleMove = getNextNode(currentMoveAgent, currentMoveEnemy);
if (!nextPossibleMove) {
console.log ("Agent has no more moves open - stay in the same place");
return 4; // dont move - not sure when we woudl get to this stage ??
}
lastMoveAgent = nextPossibleMove.move;
printStatusDistanceToEnemy(nextPossibleMove);
return nextPossibleMove.type;
};
function pushToOpenSet(current) {
this.openSet.push(current);
}
// get the next node the agent can use given current spot and the location of the agent
function getNextNode(currentMoveAgent, currentMoveEnemy) {
var next;
var neighbors = grid.getAvailableFourMoves(currentMoveAgent, currentMoveEnemy);
console.log ("Number of next moves (ignore past walls) " + neighbors.length);
currentMoveAgent.g = 0;
for (var i = 0; i < neighbors.length; i++)
{
var neighbor = neighbors[i];
if (neighbor !== null) {
var neighborMove = neighbor.move;
neighborMove.resetGFH();
//var tempG = currentMoveAgent.g + currentMoveAgent.distanceChebyshev(neighborMove);
var tempG = 0;
if (useManhatanGH) {
// calculate G using Manhattan
tempG = currentMoveAgent.g + currentMoveAgent.manhattanDistance(neighborMove);
console.log ("manhattan Distance g");
}
else {
// calculate G using last start position of the agent - this forces the agent to travel in streight line
tempG = (currentMoveAgent.g + currentMoveAgent.distanceUsingStart(neighborMove, lastMoveAgent));
console.log ("distance from last agent move");
}
console.log ("tempG " + tempG);
// punish moves that have been visited - i want the agent to be moving all the time
if (strategySelectType == 1) {
tempG = tempG - neighborMove.visited;
console.log ("punish past visited spot by " + neighborMove.visited);
// if we know we are about to go in to a bad area - punish as well
if (neighborMove.badstep()) {
tempG = tempG - 1;
console.log ("punish spot as moving in to the bad spot area");
}
}
var newPath = false;
if (openSet.includes(neighborMove)) {
if (tempG > neighborMove.g) {
neighborMove.g = tempG;
newPath = true;
console.log ("Found a position in OPENSET with a bigger G " + neighborMove.x + '-' + neighborMove.y);
}
}
else {
neighborMove.g = tempG;
newPath = true;
openSet.push(neighbor);
}
if (newPath)
{
if (useManhatanGH) {
// calculate h using manhattan
neighborMove.h = currentMoveEnemy.manhattanDistance(neighborMove);
console.log ("manhattan Distance h");
}
else {
// calculate h using hebyshev - as enemy can move in 8 directions
neighborMove.h = currentMoveEnemy.distanceChebyshev(neighborMove);
console.log ("Chebyshev Distance h");
}
// neighborMove.h = currentMoveEnemy.distanceUsingStart(neighborMove, lastMoveEnemy);
neighborMove.f = neighborMove.g + neighborMove.h;
console.log ("Calculate F " + neighborMove.f + " g:" + neighborMove.g + "h:" + neighborMove.h);
next = neighbor;
}
}
}
var nextMove = this.getOpenSetNodeBiggestF();
if (nextMove === null) {
console.log ("No next Move ???????");
return null;
}
this.clearOpenSet();
return nextMove;
}
// get the spot with biggest F - remember we want as much distance as possible
// if F is small, we will get closer - we dont want that
function getOpenSetNodeBiggestF() {
var winner = 0;
for (var i = 0; i < this.openSet.length; i++) {
var left = this.openSet[i].move,
right = this.openSet[winner].move;
if ( left.f > right.f ) {
// we have a spot with the biggest f
winner = i;
}
if ( left.f == right.f ) {
// if we are stuck with 2 identical F - pick one which is not close
if (left.distanceEnemyX > right.distanceEnemyX && left.distanceEnemyY > right.distanceEnemyX) {
winner = i;
}
else {
// -- this is last option ( the 2 spots have the same cost ) --
// the F values for two spots are the same -- since we are not sure if our next move could be a wall
// lets pick one out of the two possible values at random
winner = AB.randomPick ( winner, i );
}
}
}
if (openSet.length > winner) {
return openSet[winner];
}
return 0;
}
// remove a spot from OPENSET
function removeFromOpenSet(elt) {
for (var i = this.openSet.length - 1; i >= 0; i--) {
if (this.openSet[i] == elt) {
this.openSet.splice(i, 1);
return;
}
}
}
// clear OPENSET - it is no longer of any use to us
function clearOpenSet() {
this.openSet = [];
}
function printStatusDistanceToEnemy(spot) {
var agentMove = '';
if (spot.type == ACTION_UP) {
agentMove = ' up ';
} else if (spot.type == ACTION_DOWN) {
agentMove = ' down ';
} else if (spot.type == ACTION_RIGHT) {
agentMove = ' right ';
} else if (spot.type == ACTION_LEFT) {
agentMove = ' left ';
}
var s = '<h2> Next Move (' + spot.move.x + ',' + spot.move.y + '): ' + agentMove + '</h2>';
if (spot.move.badstep()) {
s +="<span style='background: red; color: white;'>DANGER</span>";
s += "<br>";
} else {
s +="<span style='background: green; color: white;'>KEEP RUNNING</span>";
s += "<br>";
}
AB.msg(s, 3);
}
// An object to describe the grid
function Grid()
{
this.maze = null; // grid is zero based
this.mazeMaxX = 0;
this.mazeMaxY = 0;
// get the 4 possible next moves the agent has
// ignore the once with a wall and mark any position that are possible to be bad
this.getAvailableFourMoves = function (currentMoveAgent, currentMoveEnemy) {
var result = [];
var move = this.getElementPositionGrow(currentMoveAgent.x, currentMoveAgent.y + 1);
if (move.wall !== true && !currentMoveEnemy.areSame(move)) {
console.log ('Possible H -> next up ' + move.x + '-' + move.y);
move.distanceEnemy(currentMoveEnemy);
result.push({ type: ACTION_UP, move: move });
}
var moveDown = this.getElementPositionGrow(currentMoveAgent.x, currentMoveAgent.y - 1);
if (moveDown.wall !== true && !currentMoveEnemy.areSame(moveDown)) {
console.log ('Possible H -> next down ' + moveDown.x + '-' + moveDown.y);
moveDown.distanceEnemy(currentMoveEnemy);
result.push({ type: ACTION_DOWN, move: moveDown });
}
var moveRight = this.getElementPositionGrow(currentMoveAgent.x + 1, currentMoveAgent.y);
if (moveRight.wall !== true && !currentMoveEnemy.areSame(moveRight)) {
console.log ('Possible H -> next right ' + moveRight.x + '-' + moveRight.y);
moveRight.distanceEnemy(currentMoveEnemy);
result.push({ type: ACTION_RIGHT, move: moveRight });
}
var moveLeft = this.getElementPositionGrow(currentMoveAgent.x - 1, currentMoveAgent.y);
if (moveLeft.wall !== true && !currentMoveEnemy.areSame(moveLeft)) {
console.log ('Possible H -> next left ' + moveLeft.x + '-' + moveLeft.y);
moveLeft.distanceEnemy(currentMoveEnemy);
result.push({ type: ACTION_LEFT, move: moveLeft });
}
return result;
};
// grow grid + add 2 to accomodate the border - entry function -> "public method"
this.growGridIfNeedTo = function(maxX, maxY) {
if (this.maze === null) {
this.maze = Array.from({ length: maxX + 2 }, () => Array.from({ length: maxY + 2 }, () => null));
this.mazeMaxX = this.maze.length;
this.mazeMaxY = this.maze[0].length;
}
else {
this.grow(maxX, maxY);
}
};
// grow the grid + add 2 to accomodate the border - never called directly -> "private method"
this.grow = function(maxX, maxY) {
var cols = (this.mazeMaxX < maxX)? maxX : this.mazeMaxX;
var rows = (this.mazeMaxY < maxY)? maxY : this.mazeMaxY;
//console.log ('Increase GRID by ' + (cols + 2) + '-' + (rows + 2) + ' from '+ this.mazeMaxX + '-' + this.mazeMaxY);
var newGrid = Array.from({ length: cols + 2 }, () => Array.from({ length: rows + 2 }, () => null));
if (cols > 0 && rows > 0) {
for (var i = 0; i < this.mazeMaxX; i++) {
for (var j = 0; j < this.mazeMaxY; j++) {
newGrid[i][j] = this.maze[i][j];
}
}
this.maze = newGrid;
this.mazeMaxX = this.maze.length;
this.mazeMaxY = this.maze[0].length;
}
else {
console.log ('cols and rows have no value in [function grow] -???');
}
};
// mark wall spot on the graph
this.markWall = function(currentMove) {
var spot = this.getElementPositionGrow(currentMove.x, currentMove.y);
spot.wall = true;
this.maze[spot.x][spot.y] = spot;
console.log ('Wall marked ' + spot.x + '-'+ spot.y);
};
// mark no wall spot on the graph
this.markNoWall = function(currentMove) {
var spot = this.getElementPositionGrow(currentMove.x, currentMove.y);
spot.wall = false;
spot.visited += 1;
this.maze[spot.x][spot.y] = spot;
console.log ('No Wall marked ' + spot.x + '-'+ spot.y);
};
// get element from position and grow graph if need to
this.getElementPositionGrow = function(x, y) {
var result = null;
if (this.maze && this.maze.length > x && this.maze[0].length > y) {
result = this.maze[x][y];
}
else {
this.growGridIfNeedTo(x, y);
result = this.maze[x][y];
}
if (result === null) {
result = new Spot(x, y);
}
return result;
};
}
// An object to describe a spot in the grid
function Spot(x, y)
{
// x and y
this.x = x;
this.y = y;
// x and y distance from enemy
this.distanceEnemyX = null;
this.distanceEnemyY = null;
//this.cost = 0;
this.samePosition = 0;
this.visited = 0;
// f, g, and h values for A*
this.f = 0;
this.g = 0;
this.h = 0;
this.wall = null;
this.neighbors = {};
// validate we have no idea what the spot is all about - wall no wall
this.isEmpty = function() {
return this.wall === null;
};
// generate a clone of the node
this.clone = function() {
var result = new Spot(this.x, this.y);
//result.cost = this.cost;
result.samePosition = this.samePosition;
result.visited = this.visited;
result.f = this.f;
result.g = this.g;
result.h = this.h;
result.wall = this.wall;
return result;
};
// Validate spots are the same
this.areSame = function(that) {
return this.x == that.x && this.y === that.y;
};
// get the distance between two nodes using Manhattan Distance
this.manhattanDistance = function (target) {
if (target === null) {
return -1;
}
var resultX = Math.abs(this.x - target.x);
var resultY = Math.abs(this.y - target.y);
return ( resultX + resultY );
};
// get the distance using first start node
this.distanceUsingStart = function (target, start) {
var dx1 = this.x - target.x,
dy1 = this.y - target.y,
dx2 = start.x - target.x,
dy2 = start.y - target.y;
return Math.abs(dx1*dy2 - dx2*dy1);
};
// get the distance using Chebyshev - D and D2 == 1
this.distanceChebyshev = function (target, start) {
var dx = Math.abs(this.x - target.x);
var dy = Math.abs(this.y - target.y);
var D = 1, D2 = 1;
return D * (dx + dy) + (D2 - 2 * D) * Math.min(dx, dy);
};
// reset all the values f, g, h -
this.resetGFH = function() {
this.f = 0;
this.g = 0;
this.h = 0;
};
// calculate disatnce to enemy
this.distanceEnemy = function(other) {
this.distanceEnemyX = Math.abs(this.x - other.x);
this.distanceEnemyY = Math.abs(this.y - other.y);
};
// calculate if we have a bad step in sight
this.badstep = function() {
if ( this.distanceEnemyX <= 2 && this.distanceEnemyY <= 2 ) {
return true;
}
return false;
};
}