/*
Author: Kieron Drumm.
Student Number: 13314446.
Module: CA686 (Foundations of Artifical Intelligence).
Assignment: Practical 1.
Stage: Stage 1 (Modifying the enemy to use the A* algorithm when seeking out its opponent).
Theme: I have modified the theme of the world to reflect the time of year, paying homage to the classic 1972 slasher movie: "Halloween".
*/
// Cloned by Kieron on 23 Oct 2022 from World "Complex World" by Starter user
// Please leave this clone trail here.
// ==== Starter World =================================================================================================
// This code is designed for use on the Ancient Brain site.
// This code may be freely copied and edited by anyone on the Ancient Brain site.
// To include a working run of this program on another site, see the "Embed code" links provided on Ancient Brain.
// ====================================================================================================================
// =============================================================================================
// More complex starter World
// 3d-effect Maze World (really a 2-D problem)
// Movement is on a semi-visible grid of squares
//
// This more complex World shows:
// - Skybox
// - Internal maze (randomly drawn each time)
// - Enemy actively chases agent
// - Music/audio
// - 2D world (clone this and set show3d = false)
// - User keyboard control (clone this and comment out Mind actions to see)
// =============================================================================================
// =============================================================================================
// Scoring:
// Bad steps = steps where enemy is within one step of agent.
// Good steps = steps where enemy is further away.
// Score = good steps as percentage of all steps.
//
// There are situations where agent is trapped and cannot move.
// If this happens, you score zero.
// =============================================================================================
// ===================================================================================================================
// === Start of tweaker's box ========================================================================================
// ===================================================================================================================
/* The speed of a single run: Step every n milliseconds. Default 100. */
AB.clockTick = 100;
/* Length of run: Maximum length of run in steps. Default 1000. */
AB.maxSteps = 1000;
/* Take screenshot on this step. (All resources should have finished loading.) Default 50. */
AB.screenshotStep = 50;
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Modifications made to the agent, enemy, and wall textures. I also
// added a "pool of blood" graphic to represent the path currently
// being taken by the enemy, in accordance with the "Halloween"
// theme.
// ================================================================================
/* Initialise any global constants. */
// credits:
// https://www.looper.com/img/gallery/laurie-strodes-relationship-to-michael-myers-in-halloween-explained/l-intro-1634322794.jpg
// https://d.newsweek.com/en/full/1186553/michael-myers-halloween-2018.jpg
// http://commons.wikimedia.org/wiki/File:Old_door_handles.jpg
// http://en.wikipedia.org/wiki/File:Inscription_displaying_apices_(from_the_shrine_of_the_Augustales_at_Herculaneum).jpg
// https://media.istockphoto.com/vectors/blood-splash-drop-paint-on-black-background-vector-id1308070006?b=1&k=20&m=1308070006&s=612x612&w=0&h=vq3semeP2MWnJ1Tx0fDVfJBl8TvZ-a2o6Gu_9JKqncQ=
// https://www.photos-public-domain.com/wp-content/uploads/2012/05/black-brick-wall-texture.jpg
const show3d = true;
const TEXTURE_AGENT = '/uploads/drummk2/Laurie_Strode.jpg';
const TEXTURE_ENEMY = '/uploads/drummk2/Michael_Myers.jpg';
const TEXTURE_MAZE = '/uploads/starter/latin.jpg';
const TEXTURE_PATH = '/uploads/drummk2/Pool_Of_Blood.jpg';
const TEXTURE_WALL = '/uploads/drummk2/Dark_Brick_Wall.jpg';
// credits:
// https://www.bensound.com/royalty-free-music/track/creepy
// http://soundbible.com/1542-Air-Horn.html
const MUSIC_BACK = '/uploads/drummk2/Creepy.mp3';
const SOUND_ALARM = '/uploads/starter/air.horn.mp3';
/* The number of squares in the world. */
const gridsize = 50;
/* Density of maze - number of internal boxes. */
const NOBOXES = Math.trunc((gridsize * gridsize) / 8);
/* The size of each square in pixels. */
const squaresize = 100;
/* The length of one side in pixels. */
const MAXPOS = gridsize * squaresize;
/* The colour of the sky. */
const SKYCOLOR= 0xddffdd;
/* The distance from the centre, from where the camere should be started. */
const startRadiusConst = MAXPOS * 0.8;
/* The maximum distance from the centre, where anything will be rendered. */
const maxRadiusConst = MAXPOS * 10;
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: To be used when deciding whether or not any new squares are walls.
// ================================================================================
/* The value to be used when determining whether or not a new square is a wall. */
const wallCutOff = AB.randomFloatAtoB(0, 0.6);
/* Some ABWorld default variables. */
ABHandler.MAXCAMERAPOS = maxRadiusConst;
ABHandler.GROUNDZERO = true;
//--- skybox: -------------------------------
// skybox is a collection of 6 files
// x,y,z positive and negative faces have to be in certain order in the array
// https://threejs.org/docs/#api/en/loaders/CubeTextureLoader
// space skybox, credit:
// http://en.spaceengine.org/forum/21-514-1
const SKYBOX_ARRAY = [
"/uploads/starter/sky_pos_z.jpg",
"/uploads/starter/sky_neg_z.jpg",
"/uploads/starter/sky_pos_y.jpg",
"/uploads/starter/sky_neg_y.jpg",
"/uploads/starter/sky_pos_x.jpg",
"/uploads/starter/sky_neg_x.jpg"
];
// ===================================================================================================================
// === End of tweaker's box ==========================================================================================
// ===================================================================================================================
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Created a "Square" class, based on Daniel Shiffman's "Spot"
// class. To be used to simplify the process of modifying each
// square on the grid, and for the purpose of implementing the
// A* search algorithm.
// ================================================================================
// Adapted from code written in the following video series:
// Daniel Shiffman
// Nature of Code: Intelligence and Learning
// https://github.com/shiffman/NOC-S17-2-Intelligence-Learning
// Part 1: https://youtu.be/aKYlikFAV4k
// Part 2: https://youtu.be/EaZxUCWAjb0
// Part 3: https://youtu.be/jwRT4PCT6RU
/* Represents a single square on the grid. */
function Square(i, j, squareType, isWall) {
/* The unique ID for this square (to be used when highlighting). */
this.uniqueId;
/* The coordinates for the spot. */
this.i = i;
this.j = j;
/* To be used for the purpose of implementing the A* algorithm. */
this.f = 0;
this.g = 0;
this.h = 0;
/* The spot in question's neighbours. */
this.neighbors = [];
/* The previous spot that was traversed to reach this spot. */
this.previous = undefined;
/* Is the piece a maze piece, blank space or a wall? */
this.squareType = squareType;
/* Whether or not this spot is a wall. */
this.isWall = isWall;
/* Display the square in question. */
this.show = function() {
shape = new THREE.BoxGeometry(squaresize, BOXHEIGHT, squaresize);
thecube = new THREE.Mesh(shape);
if (this.squareType == GRID_WALL) {
thecube.material = new THREE.MeshBasicMaterial({ map: wall_texture });
} else if (this.squareType == GRID_MAZE) {
thecube.material = new THREE.MeshBasicMaterial({ map: maze_texture });
}
thecube.position.copy(translate(this.i, this.j));
ABWorld.scene.add(thecube);
};
/* Highlight the square as a part of the path currently being plotted out. */
this.highlight = function(addHighlighting) {
if (addHighlighting) {
shape = new THREE.BoxGeometry(squaresize, 0.001, squaresize);
thecube = new THREE.Mesh(shape);
//thecube.material.color.setHex(0x880808);
thecube.material = new THREE.MeshBasicMaterial({ map: path_texture });
thecube.position.copy(translate(this.i, this.j));
ABWorld.scene.add(thecube);
this.uniqueId = thecube.uuid;
} else {
/* Clear this point on the grid. */
var highlightedSquare = ABWorld.scene.getObjectByProperty("uuid", this.uniqueId);
ABWorld.scene.remove(highlightedSquare);
this.uniqueId = null;
}
};
/* Determine the neighbours of this square. */
this.addNeighbors = function(grid) {
if (this.i < gridsize - 1) this.neighbors.push(grid[this.i + 1][this.j]);
if (this.i > 0) this.neighbors.push(grid[this.i - 1][this.j]);
if (this.j < gridsize - 1) this.neighbors.push(grid[this.i][this.j + 1]);
if (this.j > 0) this.neighbors.push(grid[this.i][this.j - 1]);
};
}
/* Initialise any constants. */
/* The actions that the mind can make. */
const ACTION_LEFT = 0;
const ACTION_RIGHT = 1;
const ACTION_UP = 2;
const ACTION_DOWN = 3;
const ACTION_STAYSTILL = 4;
/* In initial view, (smaller-larger) on i axis is aligned with (left-right).
In initial view, (smaller-larger) on j axis is aligned with (away from you - towards you). */
/* The constants of a grid square. */
const GRID_BLANK = 0;
const GRID_WALL = 1;
const GRID_MAZE = 2;
/* Initialise any variables. */
/* The height of a 3D box. */
var BOXHEIGHT;
/* The grid, initialised as a 2D array, to store all of the grid squares. */
var GRID = new Array(gridsize);
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Using two arrays for our winning path for our open and closed
// sets, previously used in the A* algorithm lab exercise.
// ================================================================================
/* The set of open and closed squares (to be used by our A* algorithm). */
var closedSet = [];
var openSet = [];
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Record the path that the A8 algorithm has decided upon, as we go.
// ================================================================================
/* Record the path currently being taken. */
var path = [];
/* The enemy and agent sprites. */
var theagent, theenemy;
/* Miscellaneous textures to be rendered. */
var wall_texture, agent_texture, enemy_texture, maze_texture, path_texture;
/* The positions of the enemy and agent. */
var ei, ej, ai, aj;
/* The number of bad steps made. */
var badsteps;
/* The number of good steps made. */
var goodsteps;
/* Load all necessary texture resources asynchronously. */
function loadResources() {
var loader1 = new THREE.TextureLoader();
var loader2 = new THREE.TextureLoader();
var loader3 = new THREE.TextureLoader();
var loader4 = new THREE.TextureLoader();
var loader5 = new THREE.TextureLoader();
loader1.load(TEXTURE_WALL, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
wall_texture = thetexture;
if (asynchFinished()) initScene();
});
loader2.load(TEXTURE_AGENT, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
agent_texture = thetexture;
if (asynchFinished()) initScene();
});
loader3.load(TEXTURE_ENEMY, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
enemy_texture = thetexture;
if (asynchFinished()) initScene();
});
loader4.load(TEXTURE_MAZE, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
maze_texture = thetexture;
if (asynchFinished()) initScene();
});
loader5.load(TEXTURE_PATH, function(thetexture) {
thetexture.minFilter = THREE.LinearFilter;
path_texture = thetexture;
if (asynchFinished()) initScene();
});
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Simplified the return statement to minimise the size of the file.
// ================================================================================
function asynchFinished() {
return (wall_texture && agent_texture && enemy_texture && maze_texture && path_texture);
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Modified the occupied check to use the "Square" class,
// specifically the "SquareType" property.
// ================================================================================
// The grid system is numbered from 0 to 'gridsize' - 1.
/* Is the grid square with the specified coordinates currently occupied. */
function occupied(i, j) {
/* Is the grid square in question occupied by the enemy or agent? */
if ((ei === i) && (ej === j)) return true;
if ((ai === i) && (aj === j)) return true;
/* Is the grid square in question occupied by an obstacle or a maze piece? */
if (GRID[i][j].squareType === GRID_WALL) return true;
if (GRID[i][j].squareType === GRID_MAZE) return true;
return false;
}
// Translates (i,j) grid coordinates to three.js (x,y,z) coordinates.
// Logically, coordinates are: y=0, x and z all positive (no negative).
// logically my dimensions are all positive 0 to MAXPOS.
// To centre everything on the origin, subtract (MAXPOS/2) from all dimensions.
function translate(i, j) {
var v = new THREE.Vector3();
v.y = 0;
v.x = (i * squaresize) - (MAXPOS / 2);
v.z = (j * squaresize) - (MAXPOS / 2);
return v;
}
/* To be run, once all file loads have been completed. */
function initScene() {
var i,j, shape, thecube;
/* Initialise the grid as a 2D array. */
for (i = 0; i < gridsize ; i++) {
GRID[i] = new Array(gridsize);
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Modified the wall initialisation code to use the "Square" class.
// ================================================================================
/* Initialise all of the walls. */
for (i = 0; i < gridsize; i++) {
for (j = 0; j < gridsize; j++) {
if ((i === 0) || (i === gridsize - 1) || (j === 0) || (j === gridsize - 1)) {
/* Add a new wall to the grid. */
GRID[i][j] = new Square(i, j, GRID_WALL, true);
GRID[i][j].show();
} else {
/* Initialise the square as a blank space. */
GRID[i][j] = new Square(i, j, GRID_BLANK, false);
}
}
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Modified the maze initialisation code to use the "Square" class.
// ================================================================================
/* Initialise the maze pieces. */
for (var c = 1; c <= NOBOXES; c++) {
/* Ensure that the coordinates generated are within the walls of the maze. */
i = AB.randomIntAtoB(1, gridsize - 2);
j = AB.randomIntAtoB(1, gridsize - 2);
/* Add a new maze piece to the grid. */
GRID[i][j] = new Square(i, j, GRID_MAZE, true);
GRID[i][j].show();
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: We must determine the neighbours for all squares, once the grid
// has been fully initialised.
// ================================================================================
/* Determine the neighbours for all squares on the grid. */
for (i = 0; i < gridsize; i++) {
for (j = 0; j < gridsize; j++) {
GRID[i][j].addNeighbors(GRID);
}
}
/* Initialise an enemy in a random location. */
/* Ensure that the enemy is spawned in an empty sqaure. */
do {
i = AB.randomIntAtoB(1, gridsize - 2);
j = AB.randomIntAtoB(1, gridsize - 2);
} while (occupied(i, j));
/* Ensure that the enemy is spawned in an empty sqaure. */
ei = i;
ej = j;
shape = new THREE.BoxGeometry(squaresize, BOXHEIGHT, squaresize);
theenemy = new THREE.Mesh(shape);
theenemy.material = new THREE.MeshBasicMaterial({ map: enemy_texture });
ABWorld.scene.add(theenemy);
drawEnemy();
/* Initialise an agent in a random location. */
/* Ensure that the agent is spawned in an empty sqaure. */
do {
i = AB.randomIntAtoB(1, gridsize - 2);
j = AB.randomIntAtoB(1, gridsize - 2);
} while (occupied(i,j));
ai = i;
aj = j;
shape = new THREE.BoxGeometry(squaresize, BOXHEIGHT, squaresize);
theagent = new THREE.Mesh(shape);
theagent.material = new THREE.MeshBasicMaterial({ map: agent_texture });
ABWorld.scene.add(theagent);
drawAgent();
/* Initialise the 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(SKYBOX_ARRAY, function() {
ABWorld.render();
AB.removeLoading();
AB.runReady = true;
});
}
/* Draw any moving objects. */
/* Draw the enemy. */
function drawEnemy() {
theenemy.position.copy(translate(ei, ej));
ABWorld.lookat.copy(theenemy.position);
}
/* Draw the agent. */
function drawAgent() {
theagent.position.copy(translate(ai, aj));
ABWorld.follow.copy(theagent.position);
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Added a function for calculating the heuristic cost of going from
// the enemy to the agent, previously used in the A* algorithm lab
// exercise.
// ================================================================================
/* Using our heuristic evaluation method of choice, calculate the heuristic cost for a given square. */
function heuristic(a, b) {
/* Given that diagonal moves are not allowed, calculate the distance across, plus the distance down. */
return (Math.abs(a.i - b.i) + Math.abs(a.j - b.j));
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: An implementation of the A* algorithm to determine our enemy's
// best next step.
// ================================================================================
function determineNextStep() {
console.log("Determining the ideal move from (" + ei + ", " + ej + ").");
/* Clear the highlighted path, before we begin a new iteration of our search. */
for (const highlightedSquare of path) { highlightedSquare.highlight(false); }
/* Clear the closed and open sets, and the path, before we begin a new iteration of the A* algorithm. */
closedSet.splice(0, closedSet.length);
openSet.splice(0, openSet.length);
path.splice(0, path.length);
/* Set the starting square in the open set to be the position of our enemy. */
var enemySquare = GRID[ei][ej];
openSet.push(enemySquare);
/* Are there any nodes left to be searched? */
while (openSet.length > 0) {
/* The index of the winning node (so far). */
var winner = 0;
/* Determine which of the currently open squares had the highest fitness. */
for (var i = 0; i < openSet.length; i++) {
if (openSet[i].f < openSet[winner].f) {
winner = i;
}
}
/* Determine where the agent and enemy currently reside. */
var current = openSet[winner];
var end = GRID[ai][aj];
/* Have we found a path to the enemy? */
if (current === end) {
/* Trace our way back to the enemy, and return the next best square to which it should move. */
var winningSquare = current;
while (winningSquare.previous !== enemySquare) {
/* Highlight the path that we have found. Then, add each square to our stored path, for later. */
winningSquare.highlight(true);
path.push(winningSquare);
/* Work our way backwards, following our path back to the enemy. */
winningSquare = winningSquare.previous;
}
console.log("Search complete - moving to (" + winningSquare.i + ", " + winningSquare.j + ").");
return winningSquare;
}
/* Transfer the current square from the open set to the closed set. */
openSet.splice(openSet.indexOf(current), 1);
closedSet.push(current);
/* Get the neighbouring squares for the current square. */
var neighbors = current.neighbors;
/* Iterate through, and evaluate each of the neighbouring squares. */
for (var i = 0; i < neighbors.length; i++) {
var neighbor = neighbors[i];
/* Confirm that the square has not already been searched, and is not a wall or maze piece. */
if (!closedSet.includes(neighbor) && !neighbor.isWall) {
var tempG = current.g + heuristic(neighbor, current);
var newPath = false;
if (openSet.includes(neighbor)) {
if (tempG < neighbor.g) {
neighbor.g = tempG;
newPath = true;
}
} else {
neighbor.g = tempG;
newPath = true;
openSet.push(neighbor);
}
if (newPath) {
neighbor.h = heuristic(neighbor, end);
neighbor.f = neighbor.g + neighbor.h;
neighbor.previous = current;
}
}
}
}
}
/* Take the appropriate action. */
function moveLogicalEnemy() {
/* Make a move towards the agent. */
/* Run an A* search to map out the ideal route to the agent, and move accordingly. */
var nextBestSquare = determineNextStep();
/* Move the enemy to the square that the A* algorithm has deemed as being the next best step,
ensuring that the square in question is not currently occupied. */
if (!occupied(nextBestSquare.i, nextBestSquare.j)) {
ei = nextBestSquare.i;
ej = nextBestSquare.j;
}
}
/* Take the appropriate action as the agent, provided by the mind. */
function moveLogicalAgent(a) {
var i = ai;
var j = aj;
if (a == ACTION_LEFT) i--;
else if (a == ACTION_RIGHT) i++;
else if (a == ACTION_UP) j++;
else if (a == ACTION_DOWN) j--;
if (!occupied(i, j)) {
ai = i;
aj = j;
}
}
/* Key handling. */
/* This is hard to see while the Mind is also moving the agent:
AB.mind.getAction() and AB.world.takeAction() are constantly running in a loop at the same time
Mind actions must be turned off to really see user key control. */
var OURKEYS = [37, 38, 39, 40];
function ourKeys (event) {
return (OURKEYS.includes(event.keyCode));
}
function keyHandler(event) {
if (!AB.runReady) return true;
if (!ourKeys(event)) return true;
if (event.keyCode == 37) moveLogicalAgent(ACTION_LEFT);
if (event.keyCode == 38) moveLogicalAgent(ACTION_DOWN);
if (event.keyCode == 39) moveLogicalAgent(ACTION_RIGHT);
if (event.keyCode == 40) moveLogicalAgent(ACTION_UP);
event.stopPropagation();
event.preventDefault();
return false;
}
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Simplified the return statement to minimise the size of the file.
// ================================================================================
/* Measure the amount of bad and good steps that have been made. */
/* Is the enemy within one square of the agent? */
function badstep() {
return ((Math.abs(ei - ai) < 2) && (Math.abs(ej - aj) < 2));
}
/* Is the agent currently blocked? */
function agentBlocked() {
return (occupied(ai - 1, aj) && occupied(ai + 1, aj) && occupied(ai, aj + 1) && occupied(ai, aj - 1));
}
/* This is called before anyone has moved on this step, when the agent has just proposed an action.
Update the status to show the old state and proposed move. */
function updateStatusBefore(a) {
var x = AB.world.getState();
AB.msg("Step: " + AB.step + " x = (" + x.toString() + ") a = (" + a + ") ");
}
/* Calculate the score, once the agent and enemy have moved. */
function updateStatusAfter() {
var y = AB.world.getState();
var score = (goodsteps / AB.step) * 100;
AB.msg(
" y = (" + y.toString() + ") <br>" +
" Bad steps: " + badsteps +
" Good steps: " + goodsteps +
" Score: " + score.toFixed(2) + "% ", 2);
}
AB.world.newRun = function() {
AB.loadingScreen();
AB.runReady = false;
badsteps = 0;
goodsteps = 0;
if (show3d) {
BOXHEIGHT = squaresize;
ABWorld.init3d(startRadiusConst, maxRadiusConst, SKYCOLOR);
} else {
BOXHEIGHT = 1;
ABWorld.init2d(startRadiusConst, maxRadiusConst, SKYCOLOR);
}
loadResources();
document.onkeydown = keyHandler;
};
/* Get the current states of the agent and enemy. */
AB.world.getState = function() {
var x = [ai, aj, ei, ej];
return (x);
};
AB.world.takeAction = function(a) {
updateStatusBefore(a);
moveLogicalAgent(a);
/* Slow the enemy down to move every nth step. */
if ((AB.step % 2) === 0)
moveLogicalEnemy();
if (badstep()) badsteps++;
else goodsteps++;
drawAgent();
drawEnemy();
updateStatusAfter();
if (agentBlocked()) {
AB.abortRun = true;
goodsteps = 0;
musicPause();
soundAlarm();
}
};
// ================================================================================
// Assignment-Related Modification
// ================================================================================
// Author: Kieron Drumm
// Modification: Applied a ternary operator to simplify the code below.
// ================================================================================
AB.world.endRun = function() {
musicPause();
AB.msg(AB.abortRun
? "<br> <font color=red> <B> Agent trapped. Final score zero. </B> </font>"
: "<br> <font color=green> <B> Run over. </B> </font>", 3);
};
AB.world.getScore = function() {
var s = (goodsteps / AB.maxSteps) * 100;
var x = Math.round(s * 100);
return (x / 100);
};
/* The music and sound effects. */
var backmusic = AB.backgroundMusic(MUSIC_BACK);
function musicPlay() { backmusic.play(); }
function musicPause() { backmusic.pause(); }
function soundAlarm() {
var alarm = new Audio(SOUND_ALARM);
alarm.play();
}