The JavaScript code below implements a simple (and, frankly, unattractive) clone of the old arcade game Pac-Man. To see it in action, copy it into an .html file and open that file in a web browser that runs JavaScript. Or, for an online version, visit https://thiscouldbebetter.neocities.org/mazeeater.html.
As usual, there’s a lot of room for improvement. The bad guys don’t actually have any artificial intelligence, they just pick a junction in the maze at random, go there, and repeat. The stupidity of the opponents somewhat makes up for the fact that the power-ups aren’t implemented, the escape tunnel is actually pair of long and dangerous dead-ends, and you have to traverse an entire segment of hallway in one go rather than being able to eat the dots from one side, turning around to avoid capture, and returning later for the others.
<html> <body> <script type='text/javascript'> // main function main() { var network0 = new Network ( "Network0", NetworkNode.buildManyFromMapAsStrings ( new Coords(3.6, 3.6), [ "..........................................................", "..........................................................", "....00........01..........02..03..........04........05....", "..........................................................", "..........................................................", "..........................................................", "....06........07....08....09..10....11....12........13....", "..........................................................", "..........................................................", "....14........15....16....17..18....19....20........21....", "..........................................................", "..........................................................", "....................22....232425....26....................", "..........................................................", "..........................................................", "27............28....29......30......31....32............33", "..........................................................", "..........................................................", "....................34..............35....................", "..........................................................", "..........................................................", "....36........37....38....39..40....41....42........43....", "..........................................................", "..........................................................", "....44..45....46....47....484950....51....52....53..54....", "..........................................................", "..........................................................", "....55..56....57....58....59..60....61....62....63..64....", "..........................................................", "..........................................................", "....65....................66..67....................68....", "..........................................................", "..........................................................", ] ), // nodeIndexPairsAdjacent [ // top [0, 1], [1, 2], [3, 4], [4, 5], [0, 6], [1, 7], [2, 9], [3, 10], [4, 12], [5, 13], [6, 7], [7, 8], [8, 9], [9, 10], [10, 11], [11, 12], [12, 13], [6, 14], [7, 15], [8, 16], [11, 19], [12, 20], [13, 21], [14, 15], [16, 17], [18, 19], [20, 21], [15, 28], [17, 23], [18, 25], [20, 32], [22, 23], [23, 24], [24, 25], [25, 26], [22, 29], [24, 30], [26, 31], // midline [27, 28], [28, 29], [31, 32], [32, 33], [29, 34], [31, 35], [34, 35], [34, 38], [35, 41], [36, 37], [37, 38], [38, 39], [40, 41], [41, 42], [42, 43], [36, 44], [37, 46], [39, 48], [40, 50], [42, 52], [43, 54], [44, 45], [46, 47], [47, 48], [48, 49], [49, 50], [50, 51], [51, 52], [53, 54], [45, 56], [46, 57], [47, 58], [51, 61], [52, 62], [53, 63], [55, 56], [56, 57], [58, 59], [60, 61], [62, 63], [63, 64], [55, 65], [59, 66], [60, 67], [64, 68], // bottom [65, 66], [66, 67], [67, 68], ], // indicesOfNodesWithPowerups [ 0, ], 4, // numberOfEnemiesToSpawn 49, // indexOfNodeToSpawnPlayerFrom 30 // indexOfNodeToSpawnEnemiesFrom ); var path = Path.findPathBetweenNodesInNetwork ( network0.nodes[0], network0.nodes[network0.nodes.length - 1], network0 ); Globals.Instance.initialize ( 100, // millisecondsPerTimerTick new Coords(100, 120), // viewSizeInPixels network0 ); } // classes function Coords(x, y) { this.x = x; this.y = y; } { Coords.prototype.absolute = function() { this.x = Math.abs(this.x); this.y = Math.abs(this.y); return this; } Coords.prototype.add = function(other) { this.x += other.x; this.y += other.y; return this; } Coords.prototype.clone = function() { return new Coords(this.x, this.y); } Coords.prototype.divideScalar = function(scalar) { this.x /= scalar; this.y /= scalar; return this; } Coords.prototype.dotProduct = function(other) { return this.x * other.x + this.y * other.y; } Coords.prototype.equals = function(other) { return (this.x == other.x && this.y == other.y); } Coords.prototype.magnitude = function() { return Math.sqrt ( this.x * this.x + this.y * this.y ); } Coords.prototype.multiply = function(other) { this.x *= other.x; this.y *= other.y; return this; } Coords.prototype.multiplyScalar = function(scalar) { this.x *= scalar; this.y *= scalar; return this; } Coords.prototype.normalize = function() { var magnitude = this.magnitude(); if (magnitude > 0) { this.divideScalar(magnitude); } return this; } Coords.prototype.overwriteWith = function(other) { this.x = other.x; this.y = other.y; return this; } Coords.prototype.subtract = function(other) { this.x -= other.x; this.y -= other.y; return this; } Coords.prototype.sumOfComponents = function() { return this.x + this.y; } Coords.prototype.toString = function() { return "x" + this.x + "y" + this.y; } } function Direction(name, offset) { this.name = name; this.offset = offset; } { Direction.Instances = new Direction_Instances(); function Direction_Instances() { this.East = new Direction("East", new Coords(1, 0)); this.North = new Direction("North", new Coords(0, -1)); this.South = new Direction("South", new Coords(0, 1)); this.West = new Direction("West", new Coords(-1, 0)); this._All = [ this.East, this.North, this.South, this.West, ]; for (var i = 0; i < this._All.length; i++) { var direction = this._All[i]; this._All[direction.name] = direction; } } } function DisplayHelper() { DisplayHelper.prototype.drawBackground = function() { this.graphics.fillStyle = "White"; this.graphics.strokeStyle = "Gray"; this.graphics.fillRect ( 0, 0, this.viewSize.x, this.viewSize.y ); this.graphics.strokeRect ( 0, 0, this.viewSize.x, this.viewSize.y ); } DisplayHelper.prototype.drawNetwork = function(networkToDraw) { this.graphics.strokeStyle = "Gray"; var links = networkToDraw.links; var nodes = networkToDraw.nodes; var movers = networkToDraw.movers; for (var i = 0; i < links.length; i++) { var link = links[i]; this.drawNetwork_Link ( networkToDraw, link ); } for (var i = 0; i < nodes.length; i++) { var node = nodes[i]; this.drawNetwork_Node ( networkToDraw, node ); } for (var i = 0; i < movers.length; i++) { var mover = movers[i]; this.drawNetwork_Mover ( networkToDraw, mover ); } } DisplayHelper.prototype.drawNetwork_Link = function(network, link) { this.graphics.strokeStyle = ( link.hasBeenTraversedByPlayer == true ? "Black" : "Gray" ); var startPos = network.nodes[link.nodeIndicesFromTo[0]].pos; var endPos = network.nodes[link.nodeIndicesFromTo[1]].pos this.graphics.beginPath(); this.graphics.moveTo(startPos.x, startPos.y); this.graphics.lineTo(endPos.x, endPos.y); this.graphics.stroke(); } DisplayHelper.prototype.drawNetwork_Mover = function(network, mover) { if (mover.name == "Player") { this.drawNetwork_Mover_Player(network, mover); } else { this.drawNetwork_Mover_Enemy(network, mover); } } DisplayHelper.prototype.drawNetwork_Mover_Enemy = function(network, mover) { var cursorSize = 8; var cursorSizeHalf = cursorSize / 2; var drawPos = mover.pos(); var colorToUse = ( mover.hasBeenEaten == true ? "LightGray" : "Gray" ); this.graphics.strokeStyle = colorToUse; this.graphics.moveTo(drawPos.x, drawPos.y - cursorSizeHalf), this.graphics.lineTo(drawPos.x + cursorSizeHalf, drawPos.y + cursorSizeHalf), this.graphics.lineTo(drawPos.x - cursorSizeHalf, drawPos.y + cursorSizeHalf), this.graphics.closePath(); this.graphics.stroke(); } DisplayHelper.prototype.drawNetwork_Mover_Player = function(network, mover) { var cursorSize = 8; var cursorSizeHalf = cursorSize / 2; var nodePrevPos = network.nodes[mover.nodeIndexPrev].pos; var nodeNextPos; var linkBeingTraversed = mover.linkBeingTraversed; if (linkBeingTraversed == null) { nodeNextPos = nodePrevPos; } else { var nodeNextIndex = ( linkBeingTraversed.nodeIndicesFromTo[0] == mover.nodeIndexPrev ? linkBeingTraversed.nodeIndicesFromTo[1] : linkBeingTraversed.nodeIndicesFromTo[0] ); var nodeNextPos = network.nodes[nodeNextIndex].pos; } var displacementFromNodePrevToNext = nodeNextPos.clone().subtract ( nodePrevPos ); var distanceFromNodePrevToNext = displacementFromNodePrevToNext.magnitude(); var drawPos = nodePrevPos.clone(); if (distanceFromNodePrevToNext > 0) { var displacementFromNodePrevToMover = displacementFromNodePrevToNext.divideScalar ( distanceFromNodePrevToNext ).multiplyScalar ( mover.distanceAlongLinkBeingTraversed ); drawPos.add ( displacementFromNodePrevToMover ); } this.graphics.strokeStyle = "Black"; this.graphics.beginPath(); this.graphics.moveTo(nodePrevPos.x, nodePrevPos.y); this.graphics.lineTo(drawPos.x, drawPos.y); this.graphics.stroke(); var colorToUse = ( mover.powerUpTicksRemaining > 0 ? "Black" : "Gray" ); this.graphics.strokeStyle = "Gray"; this.graphics.strokeRect ( drawPos.x - cursorSizeHalf, drawPos.y - cursorSizeHalf, cursorSize, cursorSize ); } DisplayHelper.prototype.drawNetwork_Node = function(network, node) { if (node.hasPowerup == true) { var powerupSize = 8; var powerupSizeHalf = powerupSize / 2; var drawPos = node.pos; this.graphics.strokeStyle = "Gray"; this.graphics.beginPath(); this.graphics.moveTo(drawPos.x - powerupSizeHalf, drawPos.y); this.graphics.lineTo(drawPos.x, drawPos.y - powerupSizeHalf); this.graphics.lineTo(drawPos.x + powerupSizeHalf, drawPos.y); this.graphics.lineTo(drawPos.x, drawPos.y + powerupSizeHalf); this.graphics.closePath(); this.graphics.stroke(); } } DisplayHelper.prototype.initialize = function(viewSize) { this.viewSize = viewSize; var canvas = document.createElement("canvas"); canvas.width = this.viewSize.x; canvas.height = this.viewSize.y; document.body.appendChild(canvas); this.graphics = canvas.getContext("2d"); } } function Globals() {} { // instance Globals.Instance = new Globals(); // instance methods Globals.prototype.handleEventTimerTick = function() { this.network.updateForTimerTick(); this.inputHelper.updateForTimerTick(); this.displayHelper.drawBackground(); this.displayHelper.drawNetwork ( this.network ); } Globals.prototype.initialize = function ( millisecondsPerTimerTick, viewSizeInPixels, network ) { this.network = network; this.displayHelper = new DisplayHelper(); this.displayHelper.initialize(viewSizeInPixels); this.inputHelper = new InputHelper(); this.inputHelper.initialize(); this.interval = setInterval ( this.handleEventTimerTick.bind(this), millisecondsPerTimerTick ); } } function InputHelper() {} { InputHelper.prototype.handleEventKeyDown = function(event) { this.keyCodePressed = event.keyCode; } InputHelper.prototype.initialize = function() { document.body.onkeydown = this.handleEventKeyDown.bind(this); } InputHelper.prototype.updateForTimerTick = function() { this.keyCodePressed = null; } } function Intelligence_Human() { // do nothing } { Intelligence_Human.prototype.actionDecide = function(network, actor) { var directionToMove; var directionsAll = Direction.Instances._All; var keyCodePressed = Globals.Instance.inputHelper.keyCodePressed; if (keyCodePressed == 65) // a { directionToMove = directionsAll.West.offset; } else if (keyCodePressed == 68) // d { directionToMove = directionsAll.East.offset; } else if (keyCodePressed == 83) // s { directionToMove = directionsAll.South.offset; } else if (keyCodePressed == 87) // w { directionToMove = directionsAll.North.offset; } else { directionToMove = null; } return directionToMove; } } function Intelligence_Machine() { // do nothing } { Intelligence_Machine.prototype.actionDecide = function(network, actor) { var nodeCurrent = network.nodes[actor.nodeIndexPrev]; if (actor.path == null) { var nodeIndexToTarget; if (actor.hasBeenEaten == true) { nodeIndexToTarget = network.indexOfNodeToSpawnEnemiesFrom; } else { nodeIndexToTarget = Math.floor ( Math.random() * network.nodes.length ); } var nodeTarget = network.nodes[nodeIndexToTarget]; var pathToNodeTarget = Path.findPathBetweenNodesInNetwork ( nodeCurrent, nodeTarget, network ); actor.path = pathToNodeTarget; } var pathNodes = actor.path.networkNodesStartToGoal; var nodeNext = pathNodes[0]; if (nodeNext == nodeCurrent) { pathNodes.splice(0, 1); if (pathNodes.length == 0) { nodeNext = nodeCurrent; actor.path = null; } else { nodeNext = pathNodes[0]; } } var returnValue = nodeNext.pos.clone().subtract ( nodeCurrent.pos ).normalize(); return returnValue; } } function Mover(name, intelligence, nodeIndexInitial) { this.name = name; this.intelligence = intelligence; this.nodeIndexPrev = nodeIndexInitial; this.linkBeingTraversed = null; this.distanceAlongLinkBeingTraversed = 0; this.directionAlongLinkBeingTraversed = 0; this.hasBeenEaten = false; this.powerUpTicksRemaining = 0; } { Mover.prototype.pos = function() { var network = Globals.Instance.network; var nodePrevPos = network.nodes[this.nodeIndexPrev].pos; var nodeNextPos; var linkBeingTraversed = this.linkBeingTraversed; if (linkBeingTraversed == null) { nodeNextPos = nodePrevPos; } else { var nodeNextIndex = ( linkBeingTraversed.nodeIndicesFromTo[0] == this.nodeIndexPrev ? linkBeingTraversed.nodeIndicesFromTo[1] : linkBeingTraversed.nodeIndicesFromTo[0] ); var nodeNextPos = network.nodes[nodeNextIndex].pos; } var displacementFromNodePrevToNext = nodeNextPos.clone().subtract ( nodePrevPos ); var distanceFromNodePrevToNext = displacementFromNodePrevToNext.magnitude(); var returnValue = nodePrevPos.clone(); if (distanceFromNodePrevToNext > 0) { var displacementFromNodePrevToMover = displacementFromNodePrevToNext.divideScalar ( distanceFromNodePrevToNext ).multiplyScalar ( this.distanceAlongLinkBeingTraversed ); returnValue.add ( displacementFromNodePrevToMover ); } return returnValue; } Mover.prototype.updateForTimerTick = function(network) { var directionToMove = this.intelligence.actionDecide ( network, this // actor ); this.updateForTimerTick2(network, directionToMove); } Mover.prototype.updateForTimerTick2 = function(network, directionToMove) { var moverNodeIndexNext; if (this.linkBeingTraversed == null) { moverNodeIndexNext = this.nodeIndexPrev; } else { moverNodeIndexNext = ( this.linkBeingTraversed.nodeIndicesFromTo[0] == this.nodeIndexPrev ? this.linkBeingTraversed.nodeIndicesFromTo[1] : this.linkBeingTraversed.nodeIndicesFromTo[0] ); } if (directionToMove != null) { var moverNodePrev = network.nodes[this.nodeIndexPrev]; if (this.linkBeingTraversed == null) { var nodeIndicesAdjacent = moverNodePrev.nodeIndicesAdjacent; for (var n = 0; n < nodeIndicesAdjacent.length; n++) { var nodeIndexAdjacent = nodeIndicesAdjacent[n]; var nodeAdjacent = network.nodes[nodeIndexAdjacent]; var directionToNodeAdjacent = nodeAdjacent.pos.clone().subtract ( moverNodePrev.pos ); if (directionToNodeAdjacent.dotProduct(directionToMove) > 0) { this.linkBeingTraversed = network.linkConnectingNodeIndices ([ this.nodeIndexPrev, nodeIndexAdjacent ]); this.directionAlongLinkBeingTraversed = 1; break; } } } else { var moverNodeNext = network.nodes[moverNodeIndexNext]; var directionToNodeNext = moverNodeNext.pos.clone().subtract ( moverNodePrev.pos ); var value = directionToNodeNext.dotProduct(directionToMove) * this.directionAlongLinkBeingTraversed; var shouldDirectionBeReversed = (value < 0); if (shouldDirectionBeReversed == true) { this.directionAlongLinkBeingTraversed *= -1; } } } if (this.linkBeingTraversed != null) { var moverSpeed = 2; // hack var moverVelocity = moverSpeed * this.directionAlongLinkBeingTraversed; this.distanceAlongLinkBeingTraversed += moverVelocity; if (moverVelocity > 0) { var lengthOfLink = this.linkBeingTraversed.length(network); if (this.distanceAlongLinkBeingTraversed >= lengthOfLink) { if (this.name == "Player") { if (this.linkBeingTraversed.hasBeenTraversedByPlayer == false) { this.linkBeingTraversed.hasBeenTraversedByPlayer = true; network.numberOfLinksTraversedByPlayer++; if (network.numberOfLinksTraversedByPlayer >= network.links.length) { alert("You win!"); } } var nodeArrivedAt = network.nodes[moverNodeIndexNext]; if (nodeArrivedAt.hasPowerup == true) { nodeArrivedAt.hasPowerup = false; this.powerUpTicksRemaining = 100; } } else if (this.name.indexOf("Enemy") == 0) { if (this.hasBeenEaten == true) { if (moverNodeIndexNext == network.indexOfNodeToSpawnEnemiesFrom) { this.hasBeenEaten = false; } } } this.nodeIndexPrev = moverNodeIndexNext; this.linkBeingTraversed = null; this.distanceAlongLinkBeingTraversed = 0; this.directionAlongLinkBeingTraversed = 0; } } else if (this.distanceAlongLinkBeingTraversed <= 0) { this.linkBeingTraversed = null; this.distanceAlongLinkBeingTraversed = 0; this.directionAlongLinkBeingTraversed = 0; } } } } function Network ( name, nodes, nodeIndexPairsAdjacent, indicesOfNodesWithPowerups, numberOfEnemiesToSpawn, indexOfNodeToSpawnPlayerFrom, indexOfNodeToSpawnEnemiesFrom ) { this.name = name; this.nodes = nodes; this.links = []; for (var p = 0; p < nodeIndexPairsAdjacent.length; p++) { var nodeIndexPair = nodeIndexPairsAdjacent[p]; var nodeIndex0 = nodeIndexPair[0]; var nodeIndex1 = nodeIndexPair[1]; this.nodes[nodeIndex0].nodeIndicesAdjacent.push(nodeIndex1); this.nodes[nodeIndex1].nodeIndicesAdjacent.push(nodeIndex0); var link = new NetworkLink ( [ nodeIndex0, nodeIndex1 ] ); this.links.push(link); for (var n = 0; n < link.nodeIndicesFromTo.length; n++) { var nodeIndexThis = link.nodeIndicesFromTo[n]; var nodeIndexOther = link.nodeIndicesFromTo[1 - n]; var nodeIndexThisAsString = "_" + nodeIndexThis; var nodeIndexOtherAsString = "_" + nodeIndexOther; var linksFromThisNode = this.links[nodeIndexThisAsString]; if (linksFromThisNode == null) { linksFromThisNode = []; this.links[nodeIndexThisAsString] = linksFromThisNode } linksFromThisNode[nodeIndexOtherAsString] = link; } } for (var i = 0; i < indicesOfNodesWithPowerups.length; i++) { var indexOfNodeWithPowerup = indicesOfNodesWithPowerups[i]; var nodeWithPowerup = this.nodes[indexOfNodeWithPowerup]; nodeWithPowerup.hasPowerup = true; } this.movers = []; this.indexOfNodeToSpawnPlayerFrom = indexOfNodeToSpawnPlayerFrom; this.moverForPlayer = new Mover ( "Player", new Intelligence_Human(), this.indexOfNodeToSpawnPlayerFrom ); this.movers.push(this.moverForPlayer); this.moversForEnemies = []; this.numberOfEnemiesToSpawn = numberOfEnemiesToSpawn; this.indexOfNodeToSpawnEnemiesFrom = indexOfNodeToSpawnEnemiesFrom; for (var i = 0; i < numberOfEnemiesToSpawn; i++) { var moverForEnemy = new Mover ( "Enemy" + i, new Intelligence_Machine(), this.indexOfNodeToSpawnEnemiesFrom ); this.moversForEnemies.push(moverForEnemy); this.movers.push(moverForEnemy); } this.numberOfLinksTraversedByPlayer = 0; } { // instance methods Network.prototype.updateForTimerTick = function() { for (var i = 0; i < this.movers.length; i++) { var mover = this.movers[i]; mover.updateForTimerTick(this); } if (this.moverForPlayer.hasBeenEaten == true) { return; } var collisionRadius = 4; for (var i = 0; i < this.moversForEnemies.length; i++) { var moverForEnemy = this.moversForEnemies[i]; if (moverForEnemy.hasBeenEaten == false) { var distanceFromEnemyToPlayer = this.moverForPlayer.pos().subtract ( moverForEnemy.pos() ).magnitude(); if (distanceFromEnemyToPlayer <= collisionRadius) { if (this.moverForPlayer.powerUpTicksRemaining == 0) { this.moverForPlayer.hasBeenEaten = true; this.movers.splice ( this.movers.indexOf(this.moverForPlayer), 1 ); document.write("You lose!"); break; } else { moverForEnemy.hasBeenEaten = true; } } } } if (this.moverForPlayer.powerUpTicksRemaining > 0) { this.moverForPlayer.powerUpTicksRemaining--; } } } { Network.prototype.linkConnectingNodeIndices = function(nodeIndicesConnectedByLink) { var node0IndexAsString = "_" + nodeIndicesConnectedByLink[0]; var node1IndexAsString = "_" + nodeIndicesConnectedByLink[1]; var returnValue = this.links[node0IndexAsString][node1IndexAsString]; return returnValue; } } function NetworkLink(nodeIndicesFromTo) { this.nodeIndicesFromTo = nodeIndicesFromTo; this.hasBeenTraversedByPlayer = false; } { NetworkLink.prototype.length = function(network) { var returnValue = network.nodes[this.nodeIndicesFromTo[1]].pos.clone().subtract ( network.nodes[this.nodeIndicesFromTo[0]].pos ).magnitude(); return returnValue; } } function NetworkNode(index, pos, nodeIndicesAdjacent) { this.index = index; this.pos = pos; this.nodeIndicesAdjacent = nodeIndicesAdjacent; if (this.nodeIndicesAdjacent == null) { this.nodeIndicesAdjacent = []; } this.hasPowerup = false; } { // static methods NetworkNode.buildManyFromMapAsStrings = function ( mapCellSizeInPixels, mapAsStrings ) { var charsPerCell = 2; var nodes = []; var mapSizeInCells = new Coords ( mapAsStrings[0].length / charsPerCell, mapAsStrings.length ); var cellPos = new Coords(0, 0); for (var y = 0; y < mapSizeInCells.y; y++) { cellPos.y = y; var mapRowAsString = mapAsStrings[y]; for (var x = 0; x < mapSizeInCells.x; x++) { cellPos.x = x; var nodeIndexAsString = mapRowAsString.substr ( cellPos.x * charsPerCell, charsPerCell ); var nodeIndex = parseInt(nodeIndexAsString); if (nodeIndex != null) { var nodePos = cellPos.clone().multiply ( mapCellSizeInPixels ); var node = new NetworkNode ( nodeIndex, nodePos, [] ); nodes[nodeIndex] = node; } } } return nodes; } NetworkNode.buildManyFromPositions = function(nodePositions) { var returnValues = []; for (var i = 0; i < nodePositions.length; i++) { var nodePos = nodePositions[i]; var node = new NetworkNode(i, nodePos); returnValues.push(node); } return returnValues; } // instance methods NetworkNode.prototype.nodesAdjacentInNetworkAddToList = function(network, listToAddTo) { for (var i = 0; i < this.nodeIndicesAdjacent.length; i++) { var nodeIndexAdjacent = this.nodeIndicesAdjacent[i]; var nodeAdjacent = network.nodes[nodeIndexAdjacent]; listToAddTo.push(nodeAdjacent); } } } function Path(networkNodesStartToGoal) { this.networkNodesStartToGoal = networkNodesStartToGoal; } { Path.findPathBetweenNodesInNetwork = function ( networkNodeStart, networkNodeGoal, network ) { var returnValue = null; var networkNodesToConsider = []; var pathNodesToConsider = []; var networkNodesAlreadyConsidered = []; var networkNodesAdjacentToCurrent = []; var pathNodeStart = new PathNode ( networkNodeStart, 0, // costFromStart // costFromStartToGoalEstimated networkNodeGoal.pos.clone().subtract ( networkNodeStart.pos ).magnitude(), null // prev ); networkNodesToConsider.push(networkNodeStart); pathNodesToConsider.push(pathNodeStart); while (pathNodesToConsider.length > 0) { returnValue = Path.findPathBetweenNodesInNetwork_2 ( networkNodeStart, networkNodeGoal, network, pathNodesToConsider, networkNodesToConsider, networkNodesAlreadyConsidered, networkNodesAdjacentToCurrent ); if (returnValue != null) { break; } } return returnValue; } Path.findPathBetweenNodesInNetwork_2 = function ( networkNodeStart, networkNodeGoal, network, pathNodesToConsider, networkNodesToConsider, networkNodesAlreadyConsidered, networkNodesAdjacentToCurrent ) { var returnValue; var pathNodeCurrent = pathNodesToConsider[0]; var networkNodeCurrent = pathNodeCurrent.networkNode; if (networkNodeCurrent.pos.equals(networkNodeGoal.pos) == true) { var networkNodesInPathStartToGoal = []; while (pathNodeCurrent != null) { networkNodesInPathStartToGoal.splice ( 0, 0, pathNodeCurrent.networkNode ); pathNodeCurrent = pathNodeCurrent.prev; } returnValue = new Path(networkNodesInPathStartToGoal); } else { pathNodesToConsider.splice(0, 1); networkNodesToConsider.splice(0, 1); networkNodesAlreadyConsidered.push(networkNodeCurrent); networkNodesAdjacentToCurrent.length = 0; networkNodeCurrent.nodesAdjacentInNetworkAddToList ( network, networkNodesAdjacentToCurrent ); for (var i = 0; i < networkNodesAdjacentToCurrent.length; i++) { var networkNodeAdjacent = networkNodesAdjacentToCurrent[i] Path.findPathBetweenNodesInNetwork_3 ( networkNodeStart, networkNodeGoal, network, pathNodesToConsider, networkNodesToConsider, networkNodesAlreadyConsidered, pathNodeCurrent, networkNodeCurrent, networkNodeAdjacent ); } returnValue = null; } return returnValue; } Path.findPathBetweenNodesInNetwork_3 = function ( networkNodeStart, networkNodeGoal, network, pathNodesToConsider, networkNodesToConsider, networkNodesAlreadyConsidered, pathNodeCurrent, networkNodeCurrent, networkNodeAdjacent ) { if (networkNodesAlreadyConsidered.indexOf(networkNodeAdjacent) == -1) { var costFromStartThroughCurrentToAdjacent = pathNodeCurrent.costFromStartBestSoFar + networkNodeAdjacent.pos.clone().subtract ( networkNodeCurrent.pos ).magnitude(); var costFromAdjacentToGoalEstimated = networkNodeGoal.pos.clone().subtract ( networkNodeAdjacent.pos ).magnitude(); var indexOfNodeAdjacentInListToConsider = networkNodesToConsider.indexOf(networkNodeAdjacent); var pathNodeAdjacent; var shouldCostsBeUpdated = false; if (indexOfNodeAdjacentInListToConsider == -1) { shouldCostsBeUpdated = true; pathNodeAdjacent = new PathNode ( networkNodeAdjacent, costFromStartThroughCurrentToAdjacent, costFromStartThroughCurrentToAdjacent + costFromAdjacentToGoalEstimated, pathNodeCurrent ); var j = 0; for (j = 0; j < pathNodesToConsider.length; j++) { var pathNodeExisting = pathNodesToConsider[j]; var costOfAdjacentMinusExisting = pathNodeAdjacent.costFromStartToGoalEstimated; - pathNodeExisting.costFromStartToGoalEstimated; if (costOfAdjacentMinusExisting <= 0) { break; } } pathNodesToConsider.splice(j, 0, pathNodeAdjacent); networkNodesToConsider.splice(j, 0, networkNodeAdjacent); } else { pathNodeAdjacent = pathNodesToConsider[indexOfNodeAdjacentInListToConsider]; if (costFromStartThroughCurrentToAdjacent < pathNodeAdjacent.costFromStartBestSoFar) { shouldCostsBeUpdated = true; } } if (shouldCostsBeUpdated == true) { pathNodeAdjacent.costFromStartBestSoFar = costFromStartThroughCurrentToAdjacent; pathNodeAdjacent.costToGoalEstimated = pathNodeAdjacent.costFromStartBestSoFar + costFromAdjacentToGoalEstimated; } } } // instance methods Path.prototype.toString = function() { var nodePositions = []; for (var i = 0; i < this.networkNodesStartToGoal.length; i++) { var nodePos = this.networkNodesStartToGoal[i].pos; nodePositions.push(nodePos); } return nodePositions.toString(); } } // end class Path function PathNode ( networkNode, costFromStartBestSoFar, costFromStartToGoalEstimated, prev ) { this.networkNode = networkNode; this.costFromStartBestSoFar = costFromStartBestSoFar; this.costFromStartToGoalEstimated = costFromStartToGoalEstimated; this.prev = prev; } // run main(); </script> </body> </html>