Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
609 lines (493 sloc) 23 KB
<!DOCTYPE html>
<html lang="en" xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta charset="utf-8" />
<title></title>
<script>
//Anastacio Gianareas
window.onload = function () {
main();
};
//Object (structure) for setting up the nodes. Change this directly from your DOM and recreate grid by calling the NodeContext() methods
var GlobalSetters = {
maxY: 40,
maxX: 40,
nodeWidth: 30,
nodeHeight: 30
};
//Object for holding start and goal. This is not the best option if being used for a game project.
var NodesToSearch = {
start: null,
goal: null
};
//Main function (Start here)
function main() {
var nodesContainer = new NodeContext( 'canvas' );
nodesContainer.generateNodeList();
nodesContainer.drawNodes();
//controls
var run = document.getElementById( 'run' );
run.onclick = function () {
Algorithms( nodesContainer );
};
var clear = document.getElementById( 'clear' );
clear.onclick = function () {
nodesContainer.deleteNodeList();
delete nodesContainer;
NodesToSearch.start = null;
NodesToSearch.goal = null;
main();
};
var setupGrid = document.getElementById( 'gridSize' );
setupGrid.onclick = function () {
GlobalSetters.maxX = parseInt( prompt( 'Set maxX: (How many columns)', GlobalSetters.maxX ) );
GlobalSetters.maxY = parseInt( prompt( 'Set maxY: (How many rows)', GlobalSetters.maxY ) );
GlobalSetters.nodeWidth = parseInt( prompt( 'Set width: (square width size)', GlobalSetters.nodeWidth ) );
GlobalSetters.nodeHeight = parseInt( prompt( 'Set height: (square height size)', GlobalSetters.nodeHeight ) );
var c = document.getElementById( 'clear' );
c.onclick.apply( c ); //Executes clear btn onclick function. I always forget!
}
}
//Node class which holds basic info of only one node and its current neighbors. Note: if a neighbor node doesn't exist it will hold a null value. In your algorithm check for nulls before using that node. Works diagonals.
function Node() {
this.id;
this.x;
this.y;
this.width = 50;
this.height = 50;
this.neightbors = [];
this.color;
this.parent = null;
//this.visited = false; //Used in other examples.ignore
this.walkable = true; //not using it for A* and dijkstra
this.weight = 0.5; //If its 1.0 or more is a wall, dont let it go less than 0 (Negative graphs). Also this is important for heightmap representation
//this.internalVisited = false; //Used as a hack in other examples. ignore
this.heuristicCost = null;
//Weighted
this.f; //total for f = g +h and use f as heuristic
this.g; //initial cost from starting node to the current node.
this.inOpen = false;
this.inClosed = false;
}
//Main Class controller. Holds main array of nodes, it has multiple utilities methods for node creation and deletion
function NodeContext( canvasID ) {
var nodesList = [];
var canvas = document.getElementById( canvasID ); //We want to be able to create multiple nodes container
var hdc = canvas.getContext( '2d' );
this.getHdc = function () {
return hdc;
}
this.getCanvas = function () {
return canvas;
}
var getNodeList = function () {
return nodesList;
}
this.generateNodeList = function () {
for ( var y = 0; y < GlobalSetters.maxY; y++ ) {
for ( var x = 0; x < GlobalSetters.maxX; x++ ) {
var tempNode = new Node();
tempNode.id = x + y * GlobalSetters.maxX;
tempNode.x = x;
tempNode.y = y;
tempNode.width = GlobalSetters.nodeWidth;
tempNode.height = GlobalSetters.nodeHeight;
nodesList[x + y * GlobalSetters.maxX] = tempNode;
tempNode = null;
}
}
//Set Neighbors
for ( var y = 0; y < GlobalSetters.maxY; y++ ) {
for ( var x = 0; x < GlobalSetters.maxX; x++ ) {
var t = nodesList[x + y * GlobalSetters.maxX];
//north
if ( y == 0 ) {
t.neightbors.push( null );
}
else {
t.neightbors.push( nodesList[t.id - GlobalSetters.maxX] );
}
//South
if ( y == GlobalSetters.maxY - 1 ) {
t.neightbors.push( null );
}
else {
t.neightbors.push( nodesList[t.id + GlobalSetters.maxX] );
}
//East
if ( x == GlobalSetters.maxX - 1 ) {
t.neightbors.push( null );
}
else {
t.neightbors.push( nodesList[t.id + 1] );
}
//West
if ( x == 0 ) {
t.neightbors.push( null );
}
else {
t.neightbors.push( nodesList[t.id - 1] );
}
//Diagonals
//NorthEast
if ( y == 0 || x == GlobalSetters.maxX - 1 ) {
t.neightbors.push( null );
} else {
t.neightbors.push( nodesList[( t.id + 1 ) - GlobalSetters.maxX] );
}
//NorthWest
if ( y == 0 || x == 0 ) {
t.neightbors.push( null );
} else {
t.neightbors.push( nodesList[( t.id - 1 ) - GlobalSetters.maxX] );
}
//SouthEast
if ( y == GlobalSetters.maxY - 1 || x == GlobalSetters.maxX - 1 ) {
t.neightbors.push( null );
} else {
t.neightbors.push( nodesList[( t.id + 1 ) + GlobalSetters.maxX] );
}
//SouthWest
if ( y == GlobalSetters.maxY - 1 || x == 0 ) {
t.neightbors.push( null );
} else {
t.neightbors.push( nodesList[( t.id - 1 ) + GlobalSetters.maxX] );
}
nodesList[x + y * GlobalSetters.maxX].neightbors = t.neightbors;
t = null;
}
}
};
this.deleteNodeList = function () {
nodesList = null;
hdc.clearRect( 0, 0, 950, 600 );
NodesToSearch.start = null;
NodesToSearch.goal = null;
canvas.removeEventListener( 'click' );
canvas.removeEventListener( 'dblclick' );
canvas = null;
};
this.drawNodes = function () {
for ( var y = 0; y < GlobalSetters.maxY; y++ ) {
for ( var x = 0; x < GlobalSetters.maxX; x++ ) {
var t = nodesList[x + y * GlobalSetters.maxX];
hdc.strokeStyle = "#e4e4e4";
hdc.lineWidth = 1;
hdc.strokeRect( t.x * t.width, t.y * t.height, t.width, t.height );
}
}
//This is for adding start and end goal
canvas.addEventListener( 'dblclick', function ( e ) {
var This = this;
var dblclickNode = pick2DCoords.call( this, nodesList, canvas, e );
if ( dblclickNode !== undefined ) {
if ( NodesToSearch.start == null ) {
NodesToSearch.start = dblclickNode;
NodesToSearch.start.walkable = true;
hdc.strokeStyle = "#e4e4e4";
hdc.fillStyle = "#4cff00";
hdc.fillRect( NodesToSearch.start.x * NodesToSearch.start.width, NodesToSearch.start.y * NodesToSearch.start.height, NodesToSearch.start.width, NodesToSearch.start.height );
}
else if ( NodesToSearch.goal == null ) {
NodesToSearch.goal = dblclickNode;
NodesToSearch.goal.walkable = true;
hdc.strokeStyle = "#e4e4e4";
hdc.fillStyle = "red";
hdc.fillRect( NodesToSearch.goal.x * NodesToSearch.goal.width, NodesToSearch.goal.y * NodesToSearch.goal.height, NodesToSearch.goal.width, NodesToSearch.goal.height );
}
}
} );
//For wall dragging!
var paint = false;
canvas.addEventListener( 'mousedown', function ( e ) {
paint = true;
hdc.fillStyle = "black";
var This = this;
var clickedNode = pick2DCoords.call( this, nodesList, canvas, e );
if ( clickedNode !== undefined && clickedNode !== NodesToSearch.start && clickedNode !== NodesToSearch.goal ) {
if ( clickedNode.walkable ) {
clickedNode.walkable = false;
clickedNode.weight = 1.0;
hdc.strokeStyle = "#e4e4e4";
hdc.fillStyle = '#000';
hdc.fillRect( clickedNode.x * clickedNode.width, clickedNode.y * clickedNode.height, clickedNode.width, clickedNode.height );
} else {
hdc.strokeStyle = "#e4e4e4";
clickedNode.weight = 0.5;
hdc.clearRect( clickedNode.x * clickedNode.width, clickedNode.y * clickedNode.height, clickedNode.width, clickedNode.height );
hdc.strokeRect( clickedNode.x * clickedNode.width, clickedNode.y * clickedNode.height, clickedNode.width, clickedNode.height );
clickedNode.walkable = true;
}
}
} );
canvas.addEventListener( 'mouseup', function () { paint = false; } );
canvas.addEventListener( 'mousemove', function ( e ) {
if ( paint ) {
var clickedNode = pick2DCoords.call( this, nodesList, canvas, e );
if ( clickedNode !== undefined && clickedNode !== NodesToSearch.start && clickedNode !== NodesToSearch.goal ) {
if ( clickedNode.walkable ) {
clickedNode.walkable = false;
clickedNode.weight = 1.0;
hdc.strokeStyle = "#e4e4e4";
hdc.fillStyle = '#000';
hdc.fillRect( clickedNode.x * clickedNode.width, clickedNode.y * clickedNode.height, clickedNode.width, clickedNode.height );
}
}
}
} );
};
}//End of nodeContext
/* HELPER OBJECTS */
function pick2DCoords( n, cvnObject, e ) {
var rect = cvnObject.getBoundingClientRect();
var x = parseInt(( e.pageX - rect.left ), 10 );
var y = parseInt(( e.pageY - rect.top ), 10 );
console.log( 'click: ' + x + '/' + y );
//O(N)
for ( var i = 0; i < n.length; i++ ) {
var left = n[i].x * n[i].width;
var right = n[i].x * n[i].width + n[i].width;
var top = n[i].y * n[i].height;
var bottom = n[i].y * n[i].height + n[i].height;
if ( right >= x
&& left <= x
&& bottom >= y
&& top <= y ) {
console.log( 'NodeId: ' + n[i].id );
return n[i];
}
}
};
var helpers = {
manhattan: function ( start, end ) {
var startX = start.x * start.width;
var endX = end.x * end.width;
var startY = start.y * end.height;
var endY = end.y * end.height;
return parseInt( Math.abs( endX - startX ) + Math.abs( endY - startY ), 10 );
},
euclidean: function ( start, end ) {
var startX = start.x * start.width;
var endX = end.x * end.width;
var startY = start.y * end.height;
var endY = end.y * end.height;
//THIS IS SLOW, BUT ITS FINE FOR THIS EXMAPLE. One optimization is to multiple * multiple instead of pow!
var result = Math.pow(( startX - endX ), 2 ) + Math.pow(( startY - endY ), 2 );
return parseInt( Math.sqrt( result ), 10 );
}
};
/*END OF HELPERS */
//The algorithm object, place your algorithm here
function Algorithms( nodesContainer ) {
if ( NodesToSearch.start != null && NodesToSearch.goal != null ) {
aStar( nodesContainer, NodesToSearch.start, NodesToSearch.goal )
}
}
function aStar( nodesContainer, start, goal ) {
//No need for a closed list, attached a closed boolean to each node like
// node.prototype.inClosed = false;
//resetting nodes
for ( var i = 0; i < nodesContainer.length; i++ ) {
nodesContainer[i].f = Number.MAX_VALUE;
nodesContainer[i].g = Number.MAX_VALUE;
nodesContainer[i].inOpen = false;
nodesContainer[i].inClosed = false;
nodeContainer[i].parent = null;
}
var openQueue = new priorityQueue();
start.g = 0;
start.f = helpers.manhattan( start, goal ); //here
start.inOpen = true;
start.parent = null
openQueue.push( start, start.f );
var found = false;
var intervalLoop = setInterval( function () {
if ( found || openQueue.length() <= 0 ) {
clearInterval( intervalLoop );
return false;
}
var n = openQueue.popMin();
if ( n == null ) {
clearInterval( intervalLoop );
return false;
}
n.inOpen = false;
//Change color so we can follow searching path
if ( n !== goal && n !== start && n.weight < 1.0 ) {
nodesContainer.getHdc().strokeStyle = "#0072ff";
nodesContainer.getHdc().fillStyle = "#ededed";
nodesContainer.getHdc().strokeRect( n.x * n.width, n.y * n.height, n.width, n.height ); nodesContainer.getHdc().fillRect( n.x * n.width, n.y * n.height, n.width, n.height );
}
if ( n === goal ) {
var makePath = function () {
nodesContainer.getHdc().beginPath();
while ( n.parent !== null ) {
nodesContainer.getHdc().moveTo(( n.x * n.width ) + ( n.width / 2 ), ( n.y * n.height ) + ( n.height / 2 ) );
//nodesContainer.getHdc().bezierCurveTo( 140, 10, 388, 10, 388, 170 );
if ( n.parent !== null ) {
nodesContainer.getHdc().lineTo(( n.parent.x * n.width ) + ( n.width / 2 ), ( n.parent.y * n.height ) + ( n.height / 2 ) );
}
nodesContainer.getHdc().lineWidth = 3;
// line color
nodesContainer.getHdc().strokeStyle = '#ffd800';
nodesContainer.getHdc().stroke();
n = n.parent;
}
nodesContainer.getHdc().closePath();
}
clearInterval( intervalLoop );
makePath();
return true;
}
else {
for ( var i = 0; i < n.neightbors.length; i++ ) {
var child = n.neightbors[i];
//if ( child != null && child.walkable === true ) {
if ( child != null && child.weight < 1.0 ) {
var cost = 1.0;
//This will only work because I added diagonals after position 4. Hardcoded.
if ( i > 3 ) {
cost = 1.41;
}
cost += child.weight; //for different terrains
var inlist = false;
var newG = n.g + cost;
//var d = helpers.manhattan( n, child );
var newF = newG + helpers.manhattan( child, goal );
//var newF = newG
if ( child.inOpen || child.inClosed ) {
if ( newF < child.f ) {
child.g = newG;
child.f = newF;
child.parent = n;
}
inlist = true;
}
if ( !inlist ) {
child.f = newF;
child.g = newG;
child.parent = n;
child.inOpen = true;
openQueue.push( child, child.f );
}
}
}
n.inClosed = true;
}
}, 10 );//End loop
}
//Not using heap structure. This is a basic inefficient priority queue which serves the purpose perfectly.
function priorityQueue() {
var list = [];
this.push = function ( object, number ) {
var o = {
data: object,
priority: number
}
list.push( o );
}
this.popMin = function () {
if ( list.length > 0 ) {
var priority = list[0];
var index = list.indexOf( priority )
for ( var i = 0; i < list.length; i++ ) {
var t = list[i];
if ( t.priority < priority.priority ) {
priority = t;
index = list.indexOf( priority );
}
}
list.splice( index, 1 );
return priority.data;
} else {
return null;
}
};
this.popMax = function () {
if ( list.length > 0 ) {
var priority = list[0];
var index = list.indexOf( priority )
for ( var i = 0; i < list.length; i++ ) {
var t = list[i];
if ( t.priority > priority.priority ) {
priority = t;
index = list.indexOf( priority );
}
}
list.splice( index, 1 );
return priority.data;
} else {
return null;
}
};
this.length = function () {
return list.length;
};
this.isInside = function ( o ) {
for ( var i = 0 ; i < list.length; i++ ) {
if ( list[i].data === o ) {
return true;
}
}
return false;
};
this.removeItem = function ( o ) {
for ( var i = 0 ; i < list.length; i++ ) {
if ( list[i].data === o ) {
list.splice( list[i], 1 );
}
}
};
}
</script>
<style>
.body {
color: #393939;
font-family: 'Lucida Sans Unicode', sans-serif;
}
.canvas {
-ms-user-select: none;
-webkit-user-select: none;
-khtml-user-select: none;
-moz-user-select: none;
user-select: none;
-webkit-touch-callout: none;
-webkit-user-drag: none;
background-color: #fff;
border: solid 6px #00cbf8;
}
.btn {
border-radius: 4px;
color: #000;
background-color: #f2f2f2;
font-size: 14px;
padding: 8px 20px;
margin: 10px;
text-decoration: none;
}
.btn:hover {
color: #ffd800;
background-color: #000;
}
.info {
background-color: #f2f2f2;
padding: 8px;
margin: 4px;
}
</style>
</head>
<body>
<div id="nodeContainer">
<input type="button" class="btn" id="run" value="Run Pathfinding" />
<input type="button" class="btn" id="clear" value="Clear Screen" />
<input type="button" class="btn" id="gridSize" value="Change Grid Size" />
<div id="info" class="info">
<h4>A* (A star shall guide us!)</h4>
<p>JavaScript (Canvas) Implementation by <strong>Anastacio Gianareas</strong></p>
<p>Instructions: Place a wall (Hold Click + Drag. Click to clear wall), Place Start and Goal (Double Click), Press Run</p>
<p>You are more than welcome to use the code for learning! (Note this is just a basic implantation, so no optimizations</p>
</div>
</div>
<canvas id="canvas" class="canvas" width="950" height="600"></canvas>
</body>
</html>
You can’t perform that action at this time.