// Cloned by sk on 9 Nov 2022 from World "Complex World a*" by Brendan // Please leave this clone trail here.// Cloned by Brendan on 28 Oct 2019 from World "Complex World" by Starter user// Please leave this clone trail here./**
// MCM Foundations of AI
// Stucent Name: Brendan Bonner
// Code Submission for A* assignment
// Description: AB Starter World with addtional functions whenever the logicalMoveEnemy() function is called.
// The A* function uses a standalone grid made up of objects containg the A data elements, includeing the hueristic,
// distance, whether diagonal avaiable or not and the parent.
// The sets are managed by a sorted array containing the open set, while the closed set is based on a flag
// in the A* array.
// The visuals and the sound have been replaced by blue boxes and a click that gets slightly louder and faster
// when the enemy and agent are close to each other.
**/// ==== Starter World ===============================================================================================// (c) Ancient Brain Ltd. All rights reserved.// This code is only for use on the Ancient Brain site.// This code may be freely copied and edited by anyone on the Ancient Brain site.// This code may not be copied, re-published or used on any other website.// To include a run of this code on another website, see the "Embed code" links provided on the Ancient Brain site.// ==================================================================================================================// =============================================================================================// 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 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;// Take screenshot on this step. (All resources should have finished loading.) Default 50.//---- global constants: -------------------------------------------------------const show3d =true;// Switch between 3d and 2d view (both using Three.js)const TEXTURE_WALL ='/uploads/brendanb/box_tron1.jpg';const TEXTURE_MAZE ='/uploads/brendanb/box_tron1.jpg';const TEXTURE_AGENT ='/uploads/brendanb/pacload.png';const TEXTURE_ENEMY ='/uploads/starter/ghost.3.png';//const TEXTURE_ENEMY = '/uploads/brendan/1570456293.png';const gridsize =20;// number of squares along side of world NB: Pacman was 28const NOBOXES =Math.trunc((gridsize * gridsize)/10);// density of maze - number of internal boxes// (bug) use trunc or can get a non-integerconst squaresize =20;// size of square in pixelsconst MAXPOS = gridsize * squaresize;// length of one side in pixelsconst SKYCOLOR =0xddffdd;// a number, not a stringconst startRadiusConst = MAXPOS *0.8;// distance from centre to start the camera atconst maxRadiusConst = MAXPOS *10;// maximum distance from camera we will render things//--- change ABWorld defaults: -------------------------------ABHandler.MAXCAMERAPOS = maxRadiusConst;ABHandler.GROUNDZERO =true;// "ground" exists at altitude zero//--- 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/CubeTextureLoaderconst SKYBOX_ARRAY =["/uploads/brendanb/radial_gradient_blue.png","/uploads/brendanb/radial_gradient_blue.png","/uploads/brendanb/radial_gradient_lightblue.png","/uploads/brendanb/radial_gradient_darkblue.png","/uploads/brendanb/radial_gradient_blue.png","/uploads/brendanb/radial_gradient_blue.png",];//--- Mind can pick one of these actions -----------------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)// contents of a grid squareconst GRID_BLANK =0;const GRID_WALL =1;const GRID_MAZE =2;const GRID_ENEMY =10;// added information if grid contains the actors, rather than checking globalsconst GRID_AGENT =20;// added information if grid contains the actors, rather than checking globalsvar BOXHEIGHT;// 3d or 2d box heightvar GRID =newArray(gridsize);// can query GRID about whether squares are occupied, will in fact be initialised as a 2D arrayvar theagent, theenemy;var wall_texture, agent_texture, enemy_texture, maze_texture;// enemy and agent position on squaresvar ei, ej, ai, aj;// added new class to make it easier to pass coordinatesclass coordinates {
constructor(i, j){this.i = i;this.j = j;}}var start =new coordinates();var target =new coordinates();var badsteps;var goodsteps;const MAX_OPENSET = gridsize * gridsize;// diagonal option enabled significantly increases performance of the enemy bot// and allows access to shorter routesvar diagonal =true;// if you want to see A* in actionconst PROOF =true;var proofArray =[];function loadResources()// asynchronous file loads - call initScene() when all finished{var loader1 =new THREE.TextureLoader();var loader2 =new THREE.TextureLoader();var loader3 =new THREE.TextureLoader();var loader4 =new THREE.TextureLoader();
loader1.load(TEXTURE_WALL,function(thetexture){
thetexture.minFilter = THREE.LinearFilter;
wall_texture = thetexture;if(asynchFinished()) initScene();// if all file loads have returned});
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();});}function asynchFinished()// all file loads returned{if(wall_texture && agent_texture && enemy_texture && maze_texture)returntrue;elsereturnfalse;}//--- grid system -------------------------------------------------------------------------------// my numbering is 0 to gridsize-1function occupied(i, j)// is this square occupied{// Added check to ensure that occupied square is in grid.if(i <= gridsize && j <= gridsize &&
i >=0&& j >=0){switch(GRID[i][j]){case GRID_WALL:case GRID_MAZE:case GRID_ENEMY:case GRID_AGENT:returntrue;default:returnfalse;}}// off the gridreturntrue;}function iswall(i, j)// is this square occupied{switch(GRID[i][j]){case GRID_WALL:case GRID_MAZE:returntrue;default:returnfalse;}}// translate my (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 origin, subtract (MAXPOS/2) from all dimensionsfunction translate(i, j){var v =new THREE.Vector3();
v.y =-squaresize;
v.x =(i * squaresize)-(MAXPOS /2);
v.z =(j * squaresize)-(MAXPOS /2);return v;}function initScene()// all file loads have returned{var i, j, shape, thecube;// set up GRID as 2D arrayfor(i =0; i < gridsize; i++)
GRID[i]=newArray(gridsize);// set up wallsfor(i =0; i < gridsize; i++)for(j =0; j < gridsize; j++)if((i ===0)||(i == gridsize -1)||(j ===0)||(j == gridsize -1)){
GRID[i][j]= GRID_WALL;
shape =new THREE.BoxGeometry(squaresize, BOXHEIGHT, squaresize);
thecube =new THREE.Mesh(shape);
thecube.material =new THREE.MeshBasicMaterial({
map: wall_texture
});
thecube.position.copy(translate(i, j));// translate my (i,j) grid coordinates to three.js (x,y,z) coordinatesABWorld.scene.add(thecube);}else
GRID[i][j]= GRID_BLANK;// set up mazefor(var c =1; c <= NOBOXES; c++){
i = AB.randomIntAtoB(1, gridsize -2);// inner squares are 1 to gridsize-2
j = AB.randomIntAtoB(1, gridsize -2);
GRID[i][j]= GRID_MAZE;
shape =new THREE.BoxGeometry(squaresize, BOXHEIGHT, squaresize);
thecube =new THREE.Mesh(shape);
thecube.material =new THREE.MeshBasicMaterial({
map: maze_texture
});
thecube.position.copy(translate(i, j));// translate my (i,j) grid coordinates to three.js (x,y,z) coordinatesABWorld.scene.add(thecube);}// set up enemy// start in random locationdo{
i = AB.randomIntAtoB(1, gridsize -2);
j = AB.randomIntAtoB(1, gridsize -2);}while(occupied(i, j));// search for empty square
ei = i;
ej = j;// shape = new THREE.BoxGeometry ( squaresize, BOXHEIGHT, squaresize );
shape =new THREE.SphereGeometry(squaresize /2, BOXHEIGHT /2, squaresize /2);
theenemy =new THREE.Mesh(shape);
theenemy.material =new THREE.MeshBasicMaterial({
map: enemy_texture
});ABWorld.scene.add(theenemy);
drawEnemy();// set up agent// start in random locationdo{
i = AB.randomIntAtoB(1, gridsize -2);
j = AB.randomIntAtoB(1, gridsize -2);}while(occupied(i, j));// search for empty square
ai = i;
aj = j;
shape =new THREE.SphereGeometry(squaresize /2, BOXHEIGHT /2, squaresize /2);
theagent =new THREE.Mesh(shape);
theagent.material =new THREE.MeshBasicMaterial({
map: agent_texture
});ABWorld.scene.add(theagent);
drawAgent();
GRID[ai][aj]= GRID_AGENT;
GRID[ei][ej]= GRID_ENEMY;// finally skybox// setting up skybox is simple// just pass it array of 6 URLs and it does the asych loadABWorld.scene.background =new THREE.CubeTextureLoader().load(SKYBOX_ARRAY,function(){ABWorld.render();
AB.removeLoading();
AB.runReady =true;// start the run loop});}// --- draw moving objects -----------------------------------function drawEnemy()// given ei, ej, draw it{
theenemy.position.copy(translate(ei, ej));// translate my (i,j) grid coordinates to three.js (x,y,z) coordinatesABWorld.lookat.copy(theenemy.position);// if camera moving, look back at where the enemy is}function drawAgent()// given ai, aj, draw it{
theagent.position.copy(translate(ai, aj));// translate my (i,j) grid coordinates to three.js (x,y,z) coordinatesABWorld.follow.copy(theagent.position);// follow vector = agent position (for camera following agent)}// A* Support Functions// This is the set of new A* functions, the first is to create a spot location data type// this contains the location, A* paramenters, as well as pointer array to the neighboursfunction gridSpot(i, j){// Locationthis.i = i;this.j = j;// f, g, and h values for A*this.f =0;this.g =0;this.h =0;// Neighborsthis.neighbors =[];// Where did I come from?this.parent =undefined;this.closed =false;// are we in closed set// Figure out who my neighbors arethis.addNeighbors =function(){var i =this.i;var j =this.j;if(i < gridsize -1)this.neighbors.push(aStarGrid[i +1][j]);if(i >0)this.neighbors.push(aStarGrid[i -1][j]);if(j < gridsize -1)this.neighbors.push(aStarGrid[i][j +1]);if(j >0)this.neighbors.push(aStarGrid[i][j -1]);if(diagonal)// diagonals are also neighbours:{if(i >0&& j >0)this.neighbors.push(aStarGrid[i -1][j -1]);if(i < gridsize -1&& j >0)this.neighbors.push(aStarGrid[i +1][j -1]);if(i >0&& j < gridsize -1)this.neighbors.push(aStarGrid[i -1][j +1]);if(i < gridsize -1&& j < gridsize -1)this.neighbors.push(aStarGrid[i +1][j +1]);}};}// Create Global A* Grid Arrayvar aStarGrid =[];// initialise a astar grid in parallel to main "GRID"function aStarInit(){var i, j;// create the aStarGridfor(i =0; i < gridsize; i++){
aStarGrid[i]=[];for(j =0; j < gridsize; j++){
aStarGrid[i][j]=new gridSpot(i, j);// console.log("A* Initialise: " + i + ", " + j);}}for(i =0; i < gridsize; i++){for(j =0; j < gridsize; j++){
aStarGrid[i][j].addNeighbors();}}
console.info("A* Initialise: Complete");}// A* function that returns the next position in the as a coordinate (i,j)function aStar(grid, start, target){// Initialize both open and closed listvar openSet =[];var child;var completed =false;var targetNode = aStarGrid[target.i][target.j];// define the targetvar startNode = aStarGrid[start.i][start.j];// define the targetvar currentNode;var nextMove =new coordinates(start.i, start.j);// Push the start node onto the openlist to start the analysis
openSet.push(startNode);// push startnode onto Openset// clearup previous search - need to be more efficient with memory
console.info("cleaning up previous results");for(i =0; i < gridsize; i++){for(j =0; j < gridsize; j++){
currentNode = aStarGrid[i][j];
currentNode.f = currentNode.h = currentNode.g =0;
currentNode.closed =false;
currentNode.parent =null;}}// loop through all of the a* openlist or until target or error foundwhile((openSet.length >0)&&!completed){if(openSet.length > MAX_OPENSET){// Prevent Memory Issues when debugging OpenSet
console.error("there is a problem with the openset, bail out!");
completed =true;return nextMove;}// Sort the list based on the f value
openSet.sort((a, b)=>(a.f > b.f)?1:-1);//sort set by f
currentNode = openSet.shift();// shift the first entry of OpenSet
currentNode.closed =true;// quick check for closed
console.info("Current: "+ currentNode.i +", "+ currentNode.j +" - (O/C) is "+ openSet.length);if(currentNode == targetNode){// Proof arrayif(PROOF){
proofArray.push(targetNode);}// Found Target - now backtrack to get next nodewhile(currentNode.parent != startNode){// if we require proof, push store pathif(PROOF){
proofArray.push(currentNode);}// backtrack to return the next move
currentNode = currentNode.parent;}
completed =true;// Proof arrayif(PROOF){
proofArray.push(startNode);}}else{// if we are not at target, build openSetfor(n =0; n < currentNode.neighbors.length; n++){// for each of the neighbours, calculate the children
child = currentNode.neighbors[n];// check if in closedSet or occupiedif(child.closed){// move to next child}elseif(iswall(child.i, child.j)){// closedSet.push(child);
child.closed =true;}else{// calculate values and add to openSetif((child.i == currentNode.i)||(child.j == currentNode.j))
child.g = currentNode.g +10;// if not diagonal, use 10 as metricelse
child.g = currentNode.g +14;// rougly the square path if diagonal
child.h = aStarHeuristics(child, targetNode);
child.f = child.g + child.h;
child.parent = currentNode;if(openSet.indexOf(child)<0){// if not in openSet
openSet.push(child);}}// check if closedSet}// loop through neighbours}//check if we have reached target}
nextMove.i = currentNode.i;
nextMove.j = currentNode.j;
console.info("returning form a*: ");return nextMove;// end of openSet, and not completed.}function aStarHeuristics(start, end){if(diagonal)return(Math.pow(start.i - end.i,2)+Math.pow((start.j - end.j),2));elsereturn(Math.abs(start.i - start.i)+Math.abs(start.j - end.j));}// --- take actions -----------------------------------function moveLogicalEnemy(){// move towards agent// put some randomness in so it won't get stuck with barriersvar i, j;
start.i = ei;
start.j = ej;
target.i = ai;
target.j = aj;// call the a* algorithm to provide the best path between targets (GRID not necessary, as globals used)
bestPath = aStar(GRID, start, target);// Only Move if the space is emptyif(!occupied(bestPath.i, bestPath.j)){
GRID[ei][ej]= GRID_BLANK;// Store Agents Position// move enemy to new position
ei = bestPath.i;
ej = bestPath.j;
GRID[ei][ej]= GRID_ENEMY;}
console.info("enemy moving to : "+ ei +","+ ej)}function moveLogicalAgent(a)// this is called by the infrastructure that gets action a from the Mind{var i = ai;var j = aj;// depending on the agent move, spin the sphereswitch(a){case ACTION_LEFT:
i--;
theagent.rotation.y =0;break;case ACTION_RIGHT:
i++;
theagent.rotation.y =-1;break;case ACTION_UP:
j++;
theagent.rotation.y =-2;break;case ACTION_DOWN:
j--;
theagent.rotation.y =2;break;default:break;}if(!occupied(i, j)){
GRID[ai][aj]= GRID_BLANK;// Clear Agents Previous Position
ai = i;
aj = j;
GRID[ai][aj]= GRID_AGENT;// Store Agents Position}}// --- 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// have to turn off Mind actions to really see user key control// we will handle these keys:var OURKEYS =[37,38,39,40];function ourKeys(event){return(OURKEYS.includes(event.keyCode));}function keyHandler(event){if(!AB.runReady)returntrue;// not ready yet// if not one of our special keys, send it to default key handling:if(!ourKeys(event))returntrue;// else handle key and prevent default handling: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);// 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();returnfalse;}// --- score: -----------------------------------function badstep()// is the enemy within one square of the agent{if((Math.abs(ei - ai)<2)&&(Math.abs(ej - aj)<2))returntrue;elsereturnfalse;}function agentBlocked()// agent is blocked on all sides, run over{return(occupied(ai -1, aj)&&
occupied(ai +1, aj)&&
occupied(ai, aj +1)&&
occupied(ai, aj -1));}function updateStatusBefore(a)// 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{var x = AB.world.getState();
AB.msg("Step: "+ AB.step +"<br>x = ("+ x.toString()+")");// <br>a = (" + a + ")<br>");}function updateStatusAfter()// agent and enemy have moved, can calculate score{// new state after both have movedvar y = AB.world.getState();var score =(goodsteps / AB.step)*100;//AB.msg("y = (" + y.toString() + ") <br>" +
AB.msg(" Bad steps: "+ badsteps +" Good steps: "+ goodsteps +" Score: "+ score.toFixed(2)+"% ",2);}function playSound()// is the enemy within one square of the agent{// load click sound & based on distance, speed up and change volumevar sound =newAudio('/uploads/brendanb/click.ogg');var soundRate =1+(((Math.abs(ei - ai))+Math.abs((ej - aj)))/(gridsize));
console.log("PlaybackRate: "+ soundRate);
sound.playbackRate = soundRate;
sound.volume =1/ soundRate;if(Math.abs(ei - ai)+Math.abs(ej - aj)<2){
sound.playbackRate = soundRate *2;
sound.play();}
sound.play();}// Debugging using AB was not the friendliest, so created function to debug using node.js// prints a 2D text grid containing elementsfunction consoleGrid(){var gridString ="";for(var i = gridsize -1; i >=0; i--){
gridString ="";for(var j =0; j < gridsize; j++){switch(GRID[i][j]){case GRID_WALL:
gridString = gridString +".";break;case GRID_MAZE:
gridString = gridString +"+";break;case GRID_AGENT:
gridString = gridString +"A";break;case GRID_ENEMY:
gridString = gridString +"E";break;default:
gridString = gridString +" ";break;}}
console.log(gridString);}
start.i = ei;
start.j = ej;
target.i = ai;
target.j = aj;// console.log("Heuristic: " + aStarHeuristics(start, target));}
AB.world.newRun =function(){
AB.loadingScreen();
AB.runReady =false;
badsteps =0;
goodsteps =0;
aStarInit();if(show3d){
BOXHEIGHT = squaresize;ABWorld.init3d(startRadiusConst, maxRadiusConst, SKYCOLOR);}else{
BOXHEIGHT =1;ABWorld.init2d(startRadiusConst, maxRadiusConst, SKYCOLOR);}
loadResources();// aynch file loads// calls initScene() when it returns// Initiailise A* Array
document.onkeydown = keyHandler;};
AB.world.getState =function(){var x =[ai, aj, ei, ej];return(x);};var enemyAngle =0;var cameraAngle;
AB.world.takeAction =function(a){
updateStatusBefore(a);// show status line before moves
console.info("-: Agent: "+ ai +","+ aj +" Enemy: "+ ei +","+ ej);
moveLogicalAgent(a);if((AB.step %2)===0){// slow the enemy down to every nth step
playSound();
moveLogicalEnemy();}
console.info("+: Agent: "+ ai +","+ aj +" Enemy: "+ ei +","+ ej);// consoleGrid();if(badstep()) badsteps++;else goodsteps++;// Spin the enemy around every turn
enemyAngle +=0.2;
theenemy.rotation.y = enemyAngle;// theagent.rotation.y -= 0.2;
drawAgent();
drawEnemy();
updateStatusAfter();// show status line after moves// enemy will agressively pin agen to wall, if score reaches 10%, generally pointless (and// and exponentially increasing time to claim run overif(agentBlocked()||((goodsteps / AB.step)<0.10))// if agent blocked in, run over{
AB.abortRun =true;
goodsteps =0;// you score zero as far as database is concerned// musicPause();// soundAlarm();}// Proof arrayif(PROOF){
drawProof();}};
AB.world.endRun =function(){// musicPause();if(AB.abortRun) AB.msg(" <br> <font color=red> <B> Agent trapped.</B> </font> ",3);else AB.msg(" <br> <font color=green> <B> Run over. </B> </font> ",3);};
AB.world.getScore =function(){// only called at end - do not use AB.step because it may have just incremented past AB.maxStepsvar s =(goodsteps / AB.maxSteps)*100;// float like 93.4372778var x =Math.round(s *100);// 9344return(x /100);// 93.44};// Draw the A* algortihm on the screen// Needs more work in terms of the path changing and colours, but good enough// To slow down the path and see it.var lastProofLine =[];var previousLine;function drawProof(){var point1;// local "Spots"var point2;// local "Spots"var line;var oldMaterial =new THREE.LineBasicMaterial({color:0x222222, linewidth:1});// clear old lineif(lastProofLine.length >0){
line = lastProofLine.shift();
lastProofLine[0].material = oldMaterial;if(previousLine){ABWorld.scene.remove(previousLine);}ABWorld.scene.add(line);
previousLine = line;}var mat =new THREE.LineBasicMaterial({color:'blue', linewidth:2});var geo =new THREE.Geometry();// in the proofArrayfor( i = proofArray.length; i >1; i--){
point1 = proofArray.shift();// geo.vertices.push( translate(point1.i, point1.j) );if(point1.parent){
point1 = point1.parent;// drawline between proofArrayPoints
geo.vertices.push( translate(point1.i, point1.j));
console.log("Line between "+ point1.i +","+ point1.j +" and ")}else{
geo.vertices.push( translate(point1.i, point1.j));
console.log("Line between "+ point1.i +","+ point1.j +" and ")}}
line =new THREE.Line(geo, mat);// line.castShadow = true;
lastProofLine.push(line);ABWorld.scene.add(line);}