// A* Pathfinding for HTML5 Canvas Tutorial
// by Christer (McFunkypants) Kaitila
// http://www.mcfunkypants.com
// http://twitter.com/McFunkypants
// Based on Edsger Dijkstra's 1959 algorithm and work by:
// Andrea Giammarchi, Alessandro Crugnola, Jeroen Beckers,
// Peter Hart, Nils Nilsson, Bertram Raphael
// Permission is granted to use this source in any
// way you like, commercial or otherwise. Enjoy!
// the game's canvas element
var canvas = null;
// the canvas 2d context
var ctx = null;
// an image containing all sprites
var spritesheet = null;
// true when the spritesheet has been downloaded
var spritesheetLoaded = false;
// the world grid: a 2d array of tiles
var world = [[]];
// size in the world in sprite tiles
var worldWidth = 16;
var worldHeight = 16;
// size of a tile in pixels
var tileWidth = 32;
var tileHeight = 32;
// start and end of path
var pathStart = [worldWidth,worldHeight];
var pathEnd = [0,0];
var currentPath = [];
// ensure that concole.log doesn't cause errors
if (typeof console == "undefined") var console = { log: function() {} };
// the html page is ready
function onload()
{
console.log('Page loaded.');
canvas = document.getElementById('gameCanvas');
canvas.width = worldWidth * tileWidth;
canvas.height = worldHeight * tileHeight;
canvas.addEventListener("click", canvasClick, false);
if (!canvas) alert('Blah!');
ctx = canvas.getContext("2d");
if (!ctx) alert('Hmm!');
spritesheet = new Image();
// spritesheet.src = 'spritesheet.png';
// the image above has been turned into a data url
// so that no external files are required for
// this web page - useful for included in a
// "gist" or "jsfiddle" page
spritesheet.src = 'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKAAAAAgCAYAAACVf3P1AAAACXBIWXMAAAsTAAALEwEAmpwYAAAABGdBTUEAALGOfPtRkwAAACBjSFJNAAB6JQAAgIMAAPn/AACA6QAAdTAAAOpgAAA6mAAAF2+SX8VGAAAIN0lEQVR42mJMWaLzn4FEoCrxC86+/YINRQzER2aj68GmnhDgOx6EV/6T5Tqy7S9zvsnIMAoGDAAEEGPnHrX/6IkAFDm4EgZy4kNPhMSaQUgdTAyW8Oz1pMC0sAw7irq3T36C6YOXnqEkRlLsnx19eTQBDiAACCAWWImBHFnEJD7kkgYbICbykc1Btx+U+NATnqKhBpruG2AySEYRniAPAvWBEiGx9sNzYiQj3prg//L/jLQ0b72zN171gXu3kmQ/qebZiEv9/8fwn+E/UNdfIPEXyPsHpMEYKH/53RuS7CfWPIAA7JXhCoBACIPn9Crq/d83VncghEf0O0GQ4eafD2T1qmbgjf0xVyDOAK1glSfDN+oJ361lXaDKJ7/67f2/gCMadg+s7licaCRoBlN/zLsyI7Apkw63npn2TgHEQqhahEUivioNW7uL2CoQHbxcH4GS+NCrXWRw//wNDDGQelCJCC4NgWbxoVXNhACpJR2p5hAqGUkt6Ug1B1fJyM3KyvDn3z+GTY/uUcX+nU8fYjXHWETs/z8kPkAAsWBrvBPqfOBLiKRWwej2v8SS8LCVftgSH6q6GxhVMykJcaQBHmBJ9evfP5rbAyoF//7/C+cDBBALsaUeMYmP0o4HrPTD1eZDTnTIcjDxM5svgvUiV80gOZRSEZgQxQNXkFU6D2cAShgMDPRIgKhVMEAAseArydBLNPQSktjOC6HqnRgAS2S42oIweVAie/vkIrwURU+I9gxS4KqZAWnoZhQwMPz4+weI/9J+2AWc+hBJECCAmEjtscISDjmRh6wH21giPoDe4cCWOLG1F9ETLkzNaOJDBT+B1S8oEdIaMKF1aQACiAm5tMOVQEgZiiGlR4zRo75/H2V8j1gAS5wgbOKrj7NdiJ6AR6thBPj+5w/DdzokQHQAEEAsuEo4QpGDa/CZmMRHbFsRVHrhKvVwqYVVtbiqa1zup1bvl9zeMbV6v+T2jrc/eUAX+4+8fIZiD0AAMWFLIPgSB7ocKe05UmZXYKUgKEFh6/EiJzyYPHJ1S2zCHQUDCwACiAm5x0ssIGYYBlcbD1vvF109qARDb8+hJ0JsCZNQwsOXkEfBwACAAGIhp2ok1HNGb0sit/UIlbD4hmCQq2RSSzjkxAdqa4pb4lTqAMT5QCwAxI1ArADE8UjyF4C4EMpeD8QTgfgAlL8fSh+A6k3Ao5dYUADE/kD8AaoXRPdD3QWyewNUHcgufSTzDaB4wWBOgAABxIStQ0CNXiJyQiTGrCN95gyqiop4OxrklmIk6qkH4kQgdgTiB9AIdITKOSJFcAA0QcWj6XeEJg4HPHqJBf1IehOREt9CqFg8NJExQBOpANRuBihbnqapJ9T5PxhTAAACiAk94SGXWsTOjBDSi88sZPvR538pBeilJnLb8uHG3/i0wkrAB3jU+ENLIAMkMQFowlMgoJdYADJ7AlJpBhODlbgToe6A2XcQmjFoD5ATHgWJECCAmHAlKmJLQFxjgrg6K5QAUjoX+AauCQBQyfIQiOdDqzVsAFbSfIAmhgAk8Xyo2AMqRrcBtGQ2gNqJLcNshFbH8UOpDQgQQEy4SjRsJSOpHRRizSBQGmEkKljJhq1qRRbHVW2DqnqOr2b47F0ArfJwRWYANLHthyYKf6g4KNEFIslTK/EtQCr1GJDM9oeWeg7QBLoerRqmHVi9lxErm0QAEEAs+Hqx2PjI4qTM/xIDQAtLYQsI0KtO9KEWQu07CoZh9iOxG/FUv4FIpdx5NPmJ0FKpkcIgKYSWxLBSbyNUDJbQDkDlLkAzDKwzAmufJkATJwNSW5Q2iZBMABBAjLiW5GNLgPiqVGwJlFjwcpkhvAOCvBiB2GoZW2LEVfqBFyRAV1CDesObti4aXRE9gAAggJiwtf3IGRskpB5XhwVWDSJ3QPBNxcHk8LUH8SU+WnR2RgH5ACCAmHD1VPENNhMq4YiZH8Ymhi9hQFa5/ERZ4ULFoZdRMEAAIICY8HUkiF0LiCyPa6YDVzUO6gzgG/9DBrCqGV/iQl+aRUypCm6LRDL+J7RamRoAlz2glcqE9nFQA+CyR19I5L8uENPafnR7AAKIhZg1faQuTCCmDYisBrndhy2hYBPDNcwCEsemHt18kJ2w1TejgAG8V+P///90twcggFiQOxCkdh4IdThw7R9GZr9ESmTY5oBJqWrREx6ubZywHvcoQE0Y/wbAHoAAYsG3rIrYxIUvYRKzegaUGLC1/0hdF4gr8WEzB1T6sYueGE15UIC+V4Ne9gAEEAs1Eh+uZfbEVN3iUecZbi+DClzC3ylBTkj4SjdCiQ9W+gm4so+mPHjCIG/7JaX2AAQQyathCPVwYb1pUk5XQE6EyOOB6AkG21ANriob26kJmKXfaAKEAdBe4L//mWhuD/qeEIAAYsHXeSB2TR+lnRZYIgSNCd6+j0gkyAkSX1WNXvXiSnwwM39wn2IQx1H64eoJU/tkBHy9VGzi1D4ZAR1wMbOCaUsxyf/UOBkhSEHlPzsTEwMHMwvYrC9//jB8/f0bY08IQACxkNrGo8a0G67SUd4fFAiQhMjP9Q+aaJD0ETFcg574kHu6oIQHAjCzRwECcLKwgA7SACaPvwx/gAnmDzCIfv8DHa4BzExk9I4hpyEwMbAwARPcPyac1TtAAOGdikOuUolJfLgSFq5pPWLamXtmMsITzM/XFvCEiH56AmyKDX1oBZToQPo/fkNULy7p/+H2jx5ONLAAIIBwno6Fq0rGt3EJ37Fo6ImZmKofmzgoQYIGr3EBUNsOObHBEq9pLCNW+0ePZxtYABBgAEdytom0/RTgAAAAAElFTkSuQmCC';
spritesheet.onload = loaded;
}
// the spritesheet is ready
function loaded()
{
console.log('Spritesheet loaded.');
spritesheetLoaded = true;
createWorld();
}
// fill the world with walls
function createWorld()
{
console.log('Creating world...');
// create emptiness
for (var x=0; x < worldWidth; x++)
{
world[x] = [];
for (var y=0; y < worldHeight; y++)
{
world[x][y] = 0;
}
}
// scatter some walls
for (var x=0; x < worldWidth; x++)
{
for (var y=0; y < worldHeight; y++)
{
if (Math.random() > 0.75)
world[x][y] = 1;
}
}
// calculate initial possible path
// note: unlikely but possible to never find one...
currentPath = [];
while (currentPath.length == 0)
{
pathStart = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];
pathEnd = [Math.floor(Math.random()*worldWidth),Math.floor(Math.random()*worldHeight)];
if (world[pathStart[0]][pathStart[1]] == 0)
currentPath = findPath(world,pathStart,pathEnd);
}
redraw();
}
function redraw()
{
if (!spritesheetLoaded) return;
console.log('redrawing...');
var spriteNum = 0;
// clear the screen
ctx.fillStyle = '#000000';
ctx.fillRect(0, 0, canvas.width, canvas.height);
for (var x=0; x < worldWidth; x++)
{
for (var y=0; y < worldHeight; y++)
{
// choose a sprite to draw
switch(world[x][y])
{
case 1:
spriteNum = 1;
break;
default:
spriteNum = 0;
break;
}
// draw it
// ctx.drawImage(img,sx,sy,swidth,sheight,x,y,width,height);
ctx.drawImage(spritesheet,
spriteNum*tileWidth, 0,
tileWidth, tileHeight,
x*tileWidth, y*tileHeight,
tileWidth, tileHeight);
}
}
// draw the path
console.log('Current path length: '+currentPath.length);
for (rp=0; rp<currentPath.length; rp++)
{
switch(rp)
{
case 0:
spriteNum = 2; // start
break;
case currentPath.length-1:
spriteNum = 3; // end
break;
default:
spriteNum = 4; // path node
break;
}
ctx.drawImage(spritesheet,
spriteNum*tileWidth, 0,
tileWidth, tileHeight,
currentPath[rp][0]*tileWidth,
currentPath[rp][1]*tileHeight,
tileWidth, tileHeight);
}
}
// handle click events on the canvas
function canvasClick(e)
{
var x;
var y;
// grab html page coords
if (e.pageX != undefined && e.pageY != undefined)
{
x = e.pageX;
y = e.pageY;
}
else
{
x = e.clientX + document.body.scrollLeft +
document.documentElement.scrollLeft;
y = e.clientY + document.body.scrollTop +
document.documentElement.scrollTop;
}
// make them relative to the canvas only
x -= canvas.offsetLeft;
y -= canvas.offsetTop;
// return tile x,y that we clicked
var cell =
[
Math.floor(x/tileWidth),
Math.floor(y/tileHeight)
];
// now we know while tile we clicked
console.log('we clicked tile '+cell[0]+','+cell[1]);
pathStart = pathEnd;
pathEnd = cell;
// calculate path
currentPath = findPath(world,pathStart,pathEnd);
redraw();
}
// world is a 2d array of integers (eg world[10][15] = 0)
// pathStart and pathEnd are arrays like [5,10]
function findPath(world, pathStart, pathEnd)
{
// shortcuts for speed
var abs = Math.abs;
var max = Math.max;
var pow = Math.pow;
var sqrt = Math.sqrt;
// the world data are integers:
// anything higher than this number is considered blocked
// this is handy is you use numbered sprites, more than one
// of which is walkable road, grass, mud, etc
var maxWalkableTileNum = 0;
// keep track of the world dimensions
// Note that this A-star implementation expects the world array to be square:
// it must have equal height and width. If your game world is rectangular,
// just fill the array with dummy values to pad the empty space.
var worldWidth = world[0].length;
var worldHeight = world.length;
var worldSize = worldWidth * worldHeight;
// which heuristic should we use?
// default: no diagonals (Manhattan)
var distanceFunction = ManhattanDistance;
var findNeighbours = function(){}; // empty
/*
// alternate heuristics, depending on your game:
// diagonals allowed but no sqeezing through cracks:
var distanceFunction = DiagonalDistance;
var findNeighbours = DiagonalNeighbours;
// diagonals and squeezing through cracks allowed:
var distanceFunction = DiagonalDistance;
var findNeighbours = DiagonalNeighboursFree;
// euclidean but no squeezing through cracks:
var distanceFunction = EuclideanDistance;
var findNeighbours = DiagonalNeighbours;
// euclidean and squeezing through cracks allowed:
var distanceFunction = EuclideanDistance;
var findNeighbours = DiagonalNeighboursFree;
*/
// distanceFunction functions
// these return how far away a point is to another
function ManhattanDistance(Point, Goal)
{ // linear movement - no diagonals - just cardinal directions (NSEW)
return abs(Point.x - Goal.x) + abs(Point.y - Goal.y);
}
function DiagonalDistance(Point, Goal)
{ // diagonal movement - assumes diag dist is 1, same as cardinals
return max(abs(Point.x - Goal.x), abs(Point.y - Goal.y));
}
function EuclideanDistance(Point, Goal)
{ // diagonals are considered a little farther than cardinal directions
// diagonal movement using Euclide (AC = sqrt(AB^2 + BC^2))
// where AB = x2 - x1 and BC = y2 - y1 and AC will be [x3, y3]
return sqrt(pow(Point.x - Goal.x, 2) + pow(Point.y - Goal.y, 2));
}
// Neighbours functions, used by findNeighbours function
// to locate adjacent available cells that aren't blocked
// Returns every available North, South, East or West
// cell that is empty. No diagonals,
// unless distanceFunction function is not Manhattan
function Neighbours(x, y)
{
var N = y - 1,
S = y + 1,
E = x + 1,
W = x - 1,
myN = N > -1 && canWalkHere(x, N),
myS = S < worldHeight && canWalkHere(x, S),
myE = E < worldWidth && canWalkHere(E, y),
myW = W > -1 && canWalkHere(W, y),
result = [];
if(myN)
result.push({x:x, y:N});
if(myE)
result.push({x:E, y:y});
if(myS)
result.push({x:x, y:S});
if(myW)
result.push({x:W, y:y});
findNeighbours(myN, myS, myE, myW, N, S, E, W, result);
return result;
}
// returns every available North East, South East,
// South West or North West cell - no squeezing through
// "cracks" between two diagonals
function DiagonalNeighbours(myN, myS, myE, myW, N, S, E, W, result)
{
if(myN)
{
if(myE && canWalkHere(E, N))
result.push({x:E, y:N});
if(myW && canWalkHere(W, N))
result.push({x:W, y:N});
}
if(myS)
{
if(myE && canWalkHere(E, S))
result.push({x:E, y:S});
if(myW && canWalkHere(W, S))
result.push({x:W, y:S});
}
}
// returns every available North East, South East,
// South West or North West cell including the times that
// you would be squeezing through a "crack"
function DiagonalNeighboursFree(myN, myS, myE, myW, N, S, E, W, result)
{
myN = N > -1;
myS = S < worldHeight;
myE = E < worldWidth;
myW = W > -1;
if(myE)
{
if(myN && canWalkHere(E, N))
result.push({x:E, y:N});
if(myS && canWalkHere(E, S))
result.push({x:E, y:S});
}
if(myW)
{
if(myN && canWalkHere(W, N))
result.push({x:W, y:N});
if(myS && canWalkHere(W, S))
result.push({x:W, y:S});
}
}
// returns boolean value (world cell is available and open)
function canWalkHere(x, y)
{
return ((world[x] != null) &&
(world[x][y] != null) &&
(world[x][y] <= maxWalkableTileNum));
};
// Node function, returns a new object with Node properties
// Used in the calculatePath function to store route costs, etc.
function Node(Parent, Point)
{
var newNode = {
// pointer to another Node object
Parent:Parent,
// array index of this Node in the world linear array
value:Point.x + (Point.y * worldWidth),
// the location coordinates of this Node
x:Point.x,
y:Point.y,
// the heuristic estimated cost
// of an entire path using this node
f:0,
// the distanceFunction cost to get
// from the starting point to this node
g:0
};
return newNode;
}
// Path function, executes AStar algorithm operations
function calculatePath()
{
// create Nodes from the Start and End x,y coordinates
var mypathStart = Node(null, {x:pathStart[0], y:pathStart[1]});
var mypathEnd = Node(null, {x:pathEnd[0], y:pathEnd[1]});
// create an array that will contain all world cells
var AStar = new Array(worldSize);
// list of currently open Nodes
var Open = [mypathStart];
// list of closed Nodes
var Closed = [];
// list of the final output array
var result = [];
// reference to a Node (that is nearby)
var myNeighbours;
// reference to a Node (that we are considering now)
var myNode;
// reference to a Node (that starts a path in question)
var myPath;
// temp integer variables used in the calculations
var length, max, min, i, j;
// iterate through the open list until none are left
while(length = Open.length)
{
max = worldSize;
min = -1;
for(i = 0; i < length; i++)
{
if(Open[i].f < max)
{
max = Open[i].f;
min = i;
}
}
// grab the next node and remove it from Open array
myNode = Open.splice(min, 1)[0];
// is it the destination node?
if(myNode.value === mypathEnd.value)
{
myPath = Closed[Closed.push(myNode) - 1];
do
{
result.push([myPath.x, myPath.y]);
}
while (myPath = myPath.Parent);
// clear the working arrays
AStar = Closed = Open = [];
// we want to return start to finish
result.reverse();
}
else // not the destination
{
// find which nearby nodes are walkable
myNeighbours = Neighbours(myNode.x, myNode.y);
// test each one that hasn't been tried already
for(i = 0, j = myNeighbours.length; i < j; i++)
{
myPath = Node(myNode, myNeighbours[i]);
if (!AStar[myPath.value])
{
// estimated cost of this particular route so far
myPath.g = myNode.g + distanceFunction(myNeighbours[i], myNode);
// estimated cost of entire guessed route to the destination
myPath.f = myPath.g + distanceFunction(myNeighbours[i], mypathEnd);
// remember this new path for testing above
Open.push(myPath);
// mark this node in the world graph as visited
AStar[myPath.value] = true;
}
}
// remember this route as having no more untested options
Closed.push(myNode);
}
} // keep iterating until the Open list is empty
return result;
}
// actually calculate the a-star path!
// this returns an array of coordinates
// that is empty if no path is possible
return calculatePath();
} // end of findPath() function
// start running immediately
onload();
<div>
HTML5 Pathfinding Tutorial by
<a href='http://twitter.com/McFunkypants'>@McFunkypants</a>
<input type='button' onClick='createWorld()' value='New World'>
</div>
<div><canvas id="gameCanvas"></canvas></div>
body { padding:0; margin:0; height:100%; width:100%; }
div { font-family:arial; font-size:16px; font-weight:bold; text-align:center; }