// Cloned by Venkatraman Palani on 10 Nov 2023 from Mind "A Star " by Himanshu Warekar
// Please leave this clone trail here.
/**
* A Star implementation on grid
* himanshu.warekar2@mail.dcu.ie
*/
/**
* Node for initializing at every GRID position which contains
* the information for A Star.
*/
/**
* Analytics to save the totalSteps, goodSteps, badSteps, score, agentBlocked
* for analytics.
*/
class Analytics {
constructor() {
this.API_URL = "https://api.airtable.com/v0/appaNU1MlDvrEYsnk/Table%201";
this.API_KEY = "a2V5T1BOeXRjUElpV3pCU0c=";
}
sendAnalytics(world, totalSteps, goodSteps, badSteps, score, agentBlocked) {
let data = {
"records": [
{
"fields": {
"world": world,
"totalSteps": totalSteps,
"goodSteps": goodSteps,
"badSteps": badSteps,
"score": score,
"agentBlocked": agentBlocked
}
}
]
};
$.ajax({
type: "POST",
url: this.API_URL,
contentType: "application/json",
data: JSON.stringify(data),
headers: {
"Authorization": "Bearer " + atob(this.API_KEY)
},
success: function() {}
});
}
}
/**
* Initialises the Complex world for A Star.
*/
class complexWorld {
constructor() {
// ===================================================================================================================
// === Start of tweaker's box ========================================================================================
// ===================================================================================================================
// The easiest things to modify are in this box.
// You should be able to change things in this box without being a JavaScript programmer.
// Go ahead and change some of these. What's the worst that could happen?
AB.clockTick = 100;
// Speed of run: Step every n milliseconds. Default 100.
AB.maxSteps = 1000;
// Length of run: Maximum length of run in steps. Default 1000.
AB.screenshotStep = 50;
this.WORLD = "A Star World"
// Switch between 3d and 2d view (both using Three.js)
this.show3d = true;
this.TEXTURE_WALL = "/uploads/starter/door.jpg";
this.TEXTURE_MAZE = "/uploads/starter/latin.jpg";
this.TEXTURE_AGENT = "/uploads/starter/pacman.jpg";
this.TEXTURE_ENEMY = "/uploads/starter/ghost.3.png";
this.MUSIC_BACK = "/uploads/starter/Defense.Line.mp3";
this.SOUND_ALARM = "/uploads/starter/air.horn.mp3";
// number of squares along side of world
this.gridSize = 10;
this.NOBOXES = Math.trunc((this.gridSize * this.gridSize) / 1);
console.log(this.NOBOXES);
// density of maze - number of internal boxes
// (bug) use trunc or can get a non-integer
this.squareSize = 100; // size of square in pixels
this.MAXPOS = this.gridSize * this.squareSize; // length of one side in pixels
this.SKYCOLOR = 0xddffdd; // a number, not a string
this.startRadiusConst = this.MAXPOS * 0.8; // distance from centre to start the camera at
this.maxRadiusConst = this.MAXPOS * 10; // maximum distance from camera we will render things
//--- change ABWorld defaults: -------------------------------
ABHandler.MAXCAMERAPOS = this.maxRadiusConst;
ABHandler.GROUNDZERO = true; // "ground" exists at altitude zero
this.SKYBOX_ARRAY = [
"/uploads/hrwx/black.jpg",
"/uploads/hrwx/black.jpg",
"/uploads/hrwx/black.jpg",
"/uploads/hrwx/black.jpg",
"/uploads/hrwx/black.jpg",
"/uploads/hrwx/black.jpg",
];
this.ACTION_LEFT = 0;
this.ACTION_RIGHT = 1;
this.ACTION_UP = 2;
this.ACTION_DOWN = 3;
this.ACTION_STAYSTILL = 4;
this.GRID_BLANK = 0;
this.GRID_WALL = 1;
this.GRID_MAZE = 2;
this.BOXHEIGHT; // 3d or 2d box height
this.GRID = new Array(this.gridSize); // can query GRID about whether squares are occupied, will in fact be initialised as a 2D array
this.theAgent = null;
this.theEnemy = null;
this.wall_texture = null;
this.agent_texture = null;
this.enemy_texture = null;
this.maze_texture = null;
// enemy and agent position on squares
this.enemyIdx = null;
this.enemyJdx = null;
this.agentIdx = null;
this.agentJdx = null;
this.badSteps = null;
this.goodSteps = null;
this._goodSteps = null; //Used to store good steps information for analytics incase agent is trapped.
this.OURKEYS = [37, 38, 39, 40];
this.initialized = false;
this.path = [];
this.pathColor = "darkred";
this.openColor = new THREE.Color(0, 1, 0);
this.closedColor = new THREE.Color(0, 0, 1);
// ===================================================================================================================
// === End of tweaker's box ==========================================================================================
// ===================================================================================================================
this.loadResources();
this.initMusic();
this.initAnalytics();
}
loadResources() {
this.initWallTexture();
this.initAgentTexture();
this.initEnemyTexture();
this.initMazeTexture();
}
initAnalytics() {
this.analytics = new Analytics();
}
initWallTexture() {
let me = this;
let wall_texture_loader = new THREE.TextureLoader();
wall_texture_loader.load(this.TEXTURE_WALL, function (thetexture) {
thetexture.minFilter = THREE.LinearFilter;
me.wall_texture = thetexture;
if (me.resourcesLoaded()) me.initScene();
});
}
initAgentTexture() {
let me = this;
let agent_texture_loader = new THREE.TextureLoader();
agent_texture_loader.load(this.TEXTURE_AGENT, function (thetexture) {
thetexture.minFilter = THREE.LinearFilter;
me.agent_texture = thetexture;
if (me.resourcesLoaded()) me.initScene();
});
}
initEnemyTexture() {
let me = this;
let enemy_texture_loader = new THREE.TextureLoader();
enemy_texture_loader.load(this.TEXTURE_ENEMY, function (thetexture) {
thetexture.minFilter = THREE.LinearFilter;
me.enemy_texture = thetexture;
if (me.resourcesLoaded()) me.initScene();
});
}
initMazeTexture() {
let me = this;
let maze_texture_loader = new THREE.TextureLoader();
maze_texture_loader.load(this.TEXTURE_MAZE, function (thetexture) {
thetexture.minFilter = THREE.LinearFilter;
me.maze_texture = thetexture;
if (me.resourcesLoaded()) me.initScene();
});
}
initMusic() {
this.music = AB.backgroundMusic(this.MUSIC_BACK);
}
playMusic() {
this.music.play();
}
soundAlarm() {
let alarm = new Audio(this.SOUND_ALARM);
alarm.play();
}
pauseMusic() {
this.music.pause();
}
resourcesLoaded() {
return (
this.wall_texture &&
this.agent_texture &&
this.enemy_texture &&
this.maze_texture
);
}
newRun() {
AB.loadingScreen();
AB.runReady = false;
this.badSteps = 0;
this.goodSteps = 0;
if (this.show3d) {
this.BOXHEIGHT = this.squareSize;
ABWorld.init3d(this.startRadiusConst, this.maxRadiusConst, this.SKYCOLOR);
} else {
this.BOXHEIGHT = 1;
ABWorld.init2d(this.startRadiusConst, this.maxRadiusConst, this.SKYCOLOR);
}
this.loadResources();
document.onkeydown = AB.world.customKeyHandler;
}
endRun() {
this.pauseMusic();
if (AB.abortRun) {
AB.msg(
" <br> <font color=red> <B> Agent trapped. Final score zero. </B> </font>",
3
);
} else {
AB.msg(" <br> <font color=green> <B> Run over. </B> </font>", 3);
}
let score = (this._goodSteps / (AB.step - 1)) * 100;
this.analytics.sendAnalytics(this.WORLD, AB.step - 1, this._goodSteps, this.badSteps, parseFloat(score.toFixed(2)), this.isAgentBlocked());
}
isOccupied(idx, jdx) {
// variable objects
if (this.enemyIdx === idx && this.enemyJdx === jdx) return true;
if (this.agentIdx === idx && this.agentJdx === jdx) return true;
if (this.GRID[idx][jdx].isWall()) return true;
return false;
}
isBadStep() {
// is the enemy within one square of the agent
return Math.abs(this.enemyIdx - this.agentIdx) < 2 &&
Math.abs(this.enemyJdx - this.agentJdx) < 2
? true
: false;
}
isAgentBlocked() {
// agent is blocked on all sides, run over
return (
this.isOccupied(this.agentIdx - 1, this.agentJdx) &&
this.isOccupied(this.agentIdx + 1, this.agentJdx) &&
this.isOccupied(this.agentIdx, this.agentJdx - 1) &&
this.isOccupied(this.agentIdx, this.agentJdx + 1)
);
}
ourKeys(event) {
return this.OURKEYS.includes(event.keyCode);
}
initScene() {
if (this.initialized) return;
this.setupWalls();
this.setupMaze();
this.setupNeighbours();
this.setupEnemy();
this.setupAgent();
this.initialized = true;
}
setupWalls() {
let shape = null;
let theCube = null;
for (let iCounter = 0; iCounter < this.gridSize; iCounter++) {
this.GRID[iCounter] = new Array(this.gridSize);
for (let jCounter = 0; jCounter < this.gridSize; jCounter++) {
if (
!iCounter ||
iCounter === this.gridSize - 1 ||
!jCounter ||
jCounter === this.gridSize - 1
) {
let node = new Node(this, iCounter, jCounter);
node.setAsGridWall();
this.GRID[iCounter][jCounter] = node;
shape = new THREE.BoxGeometry(
this.squareSize,
this.BOXHEIGHT,
this.squareSize
);
theCube = new THREE.Mesh(shape);
theCube.material = new THREE.MeshBasicMaterial({
map: this.wall_texture,
});
theCube.position.copy(this.translate(iCounter, jCounter)); // translate my (i,j) grid coordinates to three.js (x,y,z) coordinates
ABWorld.scene.add(theCube);
} else {
let node = new Node(this, iCounter, jCounter);
node.setAsEmpty();
this.GRID[iCounter][jCounter] = node;
}
}
}
}
setupMaze() {
let idx = null;
let jdx = null;
let shape = null;
let theCube = null;
for (let count = 1; count <= this.NOBOXES; count++) {
idx = AB.randomIntAtoB(1, this.gridSize - 2); // inner squares are 1 to gridSize-2
jdx = AB.randomIntAtoB(1, this.gridSize - 2);
let node = new Node(this, idx, jdx);
node.setAsMazeWall();
this.GRID[idx][jdx] = node;
shape = new THREE.BoxGeometry(
this.squareSize,
this.BOXHEIGHT,
this.squareSize
);
theCube = new THREE.Mesh(shape);
theCube.material = new THREE.MeshBasicMaterial({
map: this.maze_texture,
});
theCube.position.copy(this.translate(idx, jdx)); // translate my (i,j) grid coordinates to three.js (x,y,z) coordinates
ABWorld.scene.add(theCube);
}
}
setupNeighbours() {
for (let iCounter = 0; iCounter < this.gridSize; iCounter++) {
for (let jCounter = 0; jCounter < this.gridSize; jCounter++) {
this.GRID[iCounter][jCounter].addNeighbours(this.GRID);
}
}
}
setupEnemy() {
// set up enemy
// start in random location
// search for empty square
let idx = null;
let jdx = null;
let shape = null;
do {
idx = AB.randomIntAtoB(1, this.gridSize - 2);
jdx = AB.randomIntAtoB(1, this.gridSize - 2);
} while (this.isOccupied(idx, jdx));
this.enemyIdx = idx;
this.enemyJdx = jdx;
shape = new THREE.BoxGeometry(
this.squareSize,
this.BOXHEIGHT,
this.squareSize
);
this.theEnemy = new THREE.Mesh(shape);
this.theEnemy.material = new THREE.MeshBasicMaterial({
map: this.enemy_texture,
});
ABWorld.scene.add(this.theEnemy);
this.drawEnemy();
}
setupAgent() {
// set up agent
// start in random location
// search for empty square
let idx = null;
let jdx = null;
let shape = null;
do {
idx = AB.randomIntAtoB(1, this.gridSize - 2);
jdx = AB.randomIntAtoB(1, this.gridSize - 2);
} while (this.isOccupied(idx, jdx)); // search for empty square
this.agentIdx = idx;
this.agentJdx = jdx;
shape = new THREE.BoxGeometry(
this.squareSize,
this.BOXHEIGHT,
this.squareSize
);
this.theAgent = new THREE.Mesh(shape);
this.theAgent.material = new THREE.MeshBasicMaterial({
map: this.agent_texture,
});
ABWorld.scene.add(this.theAgent);
this.drawAgent();
// finally skybox
// setting up skybox is simple
// just pass it array of 6 URLs and it does the asych load
ABWorld.scene.background = new THREE.CubeTextureLoader().load(
this.SKYBOX_ARRAY,
function () {
ABWorld.render();
AB.removeLoading();
AB.runReady = true; // start the run loop
}
);
}
translate(idx, jdx) {
let vector = new THREE.Vector3();
vector.y = 0;
vector.x = idx * this.squareSize - this.MAXPOS / 2;
vector.z = jdx * this.squareSize - this.MAXPOS / 2;
return vector;
}
drawEnemy() {
// translate my (i,j) grid coordinates to three.js (x,y,z) coordinates
// if camera moving, look back at where the enemy is
this.theEnemy.position.copy(this.translate(this.enemyIdx, this.enemyJdx));
ABWorld.lookat.copy(this.theEnemy.position);
}
drawAgent() {
// translate my (i,j) grid coordinates to three.js (x,y,z) coordinates
// if camera moving, look back at where the enemy is
this.theAgent.position.copy(this.translate(this.agentIdx, this.agentJdx));
ABWorld.lookat.copy(this.theAgent.position);
}
addPath(node) {
this.path.push(node);
}
setPath(path) {
this.path = path;
}
/**
* Computes manhattan distance
* @param {object} startNode initial node
* @param {object} endNode end node
* @returns {integer} manhattan distance
*/
heuristic(startNode, endNode) {
return (
Math.abs(startNode.idx - endNode.idx) +
Math.abs(startNode.jdx - endNode.jdx)
);
}
resetNodeParameters() {
for (let idx = 0; idx < this.gridSize; idx++) {
for (let jdx = 0; jdx < this.gridSize; jdx++) {
let node = this.GRID[idx][jdx];
if (node && !node.isWall()) {
node.removeTemperoryPath();
node.calculatedTotal = null;
node.stepCost = null;
node.heuristicEstimate = null;
node.previous = null;
}
}
}
}
/**
* Moves the enemy in the direction of the path returned by A star
*/
moveLogicalEnemy() {
// move towards agent
// put some randomness in so it won't get stuck with barriers
this.resetNodeParameters();
let startNode = this.GRID[this.enemyIdx][this.enemyJdx];
let endNode = this.GRID[this.agentIdx][this.agentJdx];
let openNodes = [startNode];
let closedNodes = [];
let currentNode = null;
let tempPath = [];
let idx = null;
let jdx = null;
while (openNodes.length) {
let _winner = 0;
for (let iCounter = 0; iCounter < openNodes.length; iCounter++) {
if (
openNodes[iCounter].calculatedTotal <
openNodes[_winner].calculatedTotal
) {
_winner = iCounter;
}
}
currentNode = openNodes[_winner];
// Did I finish?
if (currentNode === endNode) {
// console.log("success - found path");
break;
}
openNodes = this.removeFromArray(openNodes, currentNode);
closedNodes.push(currentNode);
for (
let iCounter = 0;
iCounter < currentNode.neighbours.length;
iCounter++
) {
let node = currentNode.neighbours[iCounter];
if (closedNodes.includes(node) || node.isWall()) {
continue;
}
let _stepCost = node.stepCost + this.heuristic(node, currentNode);
let newPath = false;
if (openNodes.includes(node)) {
if (_stepCost < node.stepCost) {
node.stepCost = _stepCost;
newPath = true;
}
} else {
node.stepCost = _stepCost;
newPath = true;
openNodes.push(node);
}
if (newPath) {
node.heuristicEstimate = this.heuristic(node, endNode);
node.calculatedTotal = node.stepCost + node.heuristicEstimate;
node.previous = currentNode;
}
}
}
tempPath.push(currentNode);
while (currentNode && currentNode.previous) {
tempPath.push(currentNode.previous);
currentNode = currentNode.previous;
if (!currentNode || !currentNode.previous) {
break;
}
currentNode.showTemperoryPath();
}
let nextStep = tempPath[tempPath.length - 2];
idx = nextStep.idx;
jdx = nextStep.jdx;
if (!this.isOccupied(idx, jdx)) {
// if no obstacle then move, else just miss a turn
this.enemyIdx = idx;
this.enemyJdx = jdx;
this.addPath(this.GRID[this.enemyIdx][this.enemyJdx]);
}
}
_moveLogicalAgent() {
let idx = null;
let jdx = null;
if (this.enemyIdx < this.agentIdx) {
idx = AB.randomIntAtoB(this.enemyIdx, this.enemyIdx + 1);
} else if (this.enemyIdx === this.agentIdx) {
idx = this.enemyIdx;
} else if (this.enemyIdx > this.agentIdx) {
idx = AB.randomIntAtoB(this.enemyIdx - 1, this.enemyIdx);
}
if (this.enemyJdx < this.agentJdx) {
jdx = AB.randomIntAtoB(this.enemyJdx, this.enemyJdx + 1);
} else if (this.enemyJdx === this.agentJdx) {
jdx = this.enemyJdx;
} else if (this.enemyJdx > this.agentJdx) {
jdx = AB.randomIntAtoB(this.enemyJdx - 1, this.enemyJdx);
}
if (!this.isOccupied(idx, jdx)) {
// if no obstacle then move, else just miss a turn
this.enemyIdx = idx;
this.enemyJdx = jdx;
}
}
moveLogicalAgent(agent) {
// this is called by the infrastructure that gets action a from the Mind
let idx = this.agentIdx;
let jdx = this.agentJdx;
if (agent === this.ACTION_LEFT) {
idx--;
} else if (agent === this.ACTION_RIGHT) {
idx++;
} else if (agent === this.ACTION_UP) {
jdx++;
} else if (agent === this.ACTION_DOWN) {
jdx--;
}
if (!this.isOccupied(idx, jdx)) {
this.agentIdx = idx;
this.agentJdx = jdx;
}
}
renderTemperoryPath(path) {
for (let node of path) {
node.showTemperoryPath();
}
}
renderPath() {
for (let node of this.path) {
node.showPermanentPath();
}
}
keyHandler(event) {
if (!AB.runReady) return true; // not ready yet
// if not one of our special keys, send it to default key handling:
if (!this.ourKeys(event)) return true;
// else handle key and prevent default handling:
let keyMap = {
37: this.ACTION_LEFT,
38: this.ACTION_DOWN,
39: this.ACTION_RIGHT,
40: this.ACTION_UP,
};
this.moveLogicalAgent(keyMap[event.keyCode]);
// when the World is embedded in an iframe in a page, we want arrow key events handled by World and not passed up to parent
event.stopPropagation();
event.preventDefault();
return false;
}
getScore() {
let steps = (this.goodSteps / AB.maxSteps) * 100;
let score = Math.round(steps * 100);
return score / 100;
}
getState() {
return [this.agentIdx, this.agentJdx, this.enemyIdx, this.enemyJdx];
}
updateStatusBefore(agent) {
// this is called before anyone has moved on this step, agent has just proposed an action
// update status to show old state and proposed move
let state = this.getState();
AB.msg(
" Step: " +
AB.step +
" x = (" +
state.toString() +
") a = (" +
agent +
") "
);
}
updateStatusAfter() {
// agent and enemy have moved, can calculate score
// new state after both have moved
let state = this.getState();
let score = (this.goodSteps / AB.step) * 100;
AB.msg(
" y = (" +
state.toString() +
") <br>" +
" Bad steps: " +
this.badSteps +
" Good steps: " +
this.goodSteps +
" Score: " +
score.toFixed(2) +
"% ",
2
);
}
takeAction(agent) {
this.updateStatusBefore(agent);
this.moveLogicalAgent(agent);
if (AB.step % 2 === 0) {
this.moveLogicalEnemy();
}
this.isBadStep() ? this.badSteps++ : this.goodSteps++;
this.drawAgent();
this.drawEnemy();
// show status line after moves
this.updateStatusAfter();
// set for analytics
this._goodSteps = this.goodSteps;
if (this.isAgentBlocked()) {
// if agent blocked in, run over
// you score zero as far as database is concerned
AB.abortRun = true;
this.goodSteps = 0;
this.pauseMusic();
this.soundAlarm();
this.renderPath();
}
}
getAction(location) {
let agentIdx = location[0];
let agentJdx = location[1];
let enemyIdx = location[2];
let enemyJdx = location[3];
if (enemyJdx < agentJdx) {
return AB.randomPick(
this.ACTION_UP,
AB.randomPick(this.ACTION_RIGHT, this.ACTION_LEFT)
);
} else if (enemyJdx > agentJdx) {
return AB.randomPick(
this.ACTION_DOWN,
AB.randomPick(this.ACTION_RIGHT, this.ACTION_LEFT)
);
} else if (enemyIdx < agentIdx) {
return AB.randomPick(
this.ACTION_RIGHT,
AB.randomPick(this.ACTION_UP, this.ACTION_DOWN)
);
} else if (enemyIdx > agentIdx) {
return AB.randomPick(
this.ACTION_LEFT,
AB.randomPick(this.ACTION_UP, this.ACTION_DOWN)
);
} else {
return AB.randomIntAtoB(0, 3);
}
}
getKeyMap() {
return {
37: this.ACTION_LEFT,
38: this.ACTION_DOWN,
39: this.ACTION_RIGHT,
40: this.ACTION_UP,
};
}
removeFromArray(array, element) {
let index = array.indexOf(element);
if (index !== -1) {
array.splice(index, 1)
}
return array;
}
}
// Initialises ComplexWorld object and attaches it to window object
window.world = new complexWorld();
/**
* Overrides the AB.world functions to run the functions defined in Complex World
*/
AB.world = {
newRun: function () {
window.world.newRun();
},
endRun: function () {
window.world.endRun();
},
getScore: function () {
// only called at end - do not use AB.step because it may have just incremented past AB.maxSteps
return window.world.getScore();
},
getState: function () {
return window.world.getState();
},
takeAction: function (agent) {
window.world.takeAction(agent);
},
customKeyHandler: function (event) {
if (!AB.runReady) return true; // not ready yet
// if not one of our special keys, send it to default key handling:
if (!window.world.ourKeys(event)) return true;
// else handle key and prevent default handling:
let keyMap = window.world.getKeyMap();
window.world.moveLogicalAgent(keyMap[event.keyCode]);
// when the World is embedded in an iframe in a page,
// we want arrow key events handled by World and not passed up to parent
event.stopPropagation();
event.preventDefault();
return false;
},
};
AB.mind = {
getAction: function (location) {
return window.world.getAction(location);
},
};