cssAudio - Activefile-genericCSS - ActiveGeneric - ActiveHTML - ActiveImage - ActiveJS - ActiveSVG - ActiveText - Activefile-genericVideo - ActiveLovehtmlicon-new-collectionicon-personicon-teamlog-outoctocatpop-outspinnerstartv

Pen Settings

CSS Base

Vendor Prefixing

Add External CSS

These stylesheets will be added in this order and before the code you write in the CSS editor. You can also add another Pen here, and it will pull the CSS from it. Try typing "font" or "ribbon" below.

Quick-add: + add another resource

Add External JavaScript

These scripts will run in this order and before the code in the JavaScript editor. You can also link to another Pen here, and it will run the JavaScript from it. Also try typing the name of any popular library.

Quick-add: + add another resource

Code Indentation

     

Save Automatically?

If active, Pens will autosave every 30 seconds after being saved once.

Auto-Updating Preview

If enabled, the preview panel updates automatically as you code. If disabled, use the "Run" button to update.

            
              <html>
	<title>A* Pathfinding in HTML5 Canvas</title>
	</head>
	<body onload='onload()'>
		<div>
			<p>Left Click to set Start and End points <b>|</b>
				Right Click to add/remove obstacles. <input type="button" onclick="clearWorld()" value="Clear"></input> <input type="button" onclick="createWorld()" value="Regen"></input>
			</p>
		</div>
		<div>
			<canvas id="gameCanvas"></canvas>
		</div>
	</body>
</html>

            
          
!
            
              body 
{
  padding:0; margin:0; height:100%; width:100%; 
}
div 
{ 
  font-family:arial; 
  font-size:16px; 
  font-weight:bold; 
  text-align:center; 
}
            
          
!
            
              // A* Pathfinding in HTML5 Canvas
// by Stas Darevskiy
// size in the world in sprite tiles
var worldWidth = 15;
var worldHeight = 15;

// size of a tile in pixels
var tileWidth = 32;
var tileHeight = 32;

// the game's canvas element
var canvas,
	ctx,
	spritesheet;

// true when the spritesheet has been downloaded
var spritesheetLoaded = false;

// the world grid: a 2d array of tiles
var world = [
	[]
];

// 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()
{
	canvas = document.getElementById('gameCanvas');
	canvas.width = worldWidth * tileWidth;
	canvas.height = worldHeight * tileHeight;
	canvas.addEventListener("click", canvasClick, false);
	canvas.oncontextmenu = rightClick;
	ctx = canvas.getContext("2d");
	spritesheet = new Image();
	spritesheet.src = 'data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAKAAAAAgCAYAAACVf3P1AAAABGdBTUEAALGOfPtRkwAAACBjSFJNAAB6JQAAgIMAAPn/AACA6QAAdTAAAOpgAAA6mAAAF2+SX8VGAAAACXBIWXMAAAsRAAALEQF/ZF+RAAAAGXRFWHRTb2Z0d2FyZQBwYWludC5uZXQgNC4wLjEyQwRr7AAABRJJREFUeF7tmOmvnVMUhy/amFpKzXMV5SLmOaYa26LmOWKeCRFqiBhiFjF9wAd8EIIEX/0H/Ffb7znda5/Vc1ebtMnaV3L3Sp5095z3vL919vvc/b77zKnKUmZFWVzK3IpFJZqTzoQvLhlmhehNJEVPojnpzHTQuXwTpSzri+U2EXQ5erJAQPdeF2YFLPN9sVw/6Fy+iVCSTCx3CFjnIpIkE8v1g87lmwglycRyh4B1LiJJMrFcP+hcvolQkkwsdwhY5yKSJBPL9YPO5ZsIJcnEcoeAdS4iSTKxXD/oXL6JUJJMLHcIWOcikiQTy/WDzuWbCCXJxHKHgHUuIkkysVw/6Fy+iVCSTCx3CFjnIpIkE8v1g87lmwglycRy/y8CqpeuNQSc5k6IJMnEck0EjbuW5Q4B3aBz+SZCSTKx3CZCKQeKc8W19d9jxWniKrFBXC8uFUeK5eJQcYrguL3EnuJ4wXHrxclipThO8DnOAZxvvuVuR0Ads684SVxWWSt0cDlKXF45QnAsHCPOFnyP3QQ9HSYOFsvraVsNAae5EyJJMrHcJkIpN4gt4n3xuLhS3CY+EH+Jb8XL4hzBRUayF8S9govPa3eJ38XH4jlxqrhCcN5fxM/iTbG55QYC6n1EQ6aHxduCz28Sp4s7BT2+I+4X+4k9xCPiE3GB4I/hcHGNQN5V9dSthoDT3AmRJJlYbhOhlK/F3QKRWLn2F7uLowUX/HyxTJ/h4HXidvGqeElcJPjcLQLBkABxkI9zwWPA56mWGwt4pnhS3CNOEKvEGnGzeEWwurIifi4uFpyf8XeCY1j1WHnpEXFX11O3GgJOcyfMCpKN5TYRSvlUfCG4ha4WJlsk4NXiDvGgYKXjM1x0VsPvxRMCIc4SrEY7KyC37EfFJeJEgdCMHxCvCW6xrHzXCYQ8Q7wuyH1WkIu4Q8AdlG9iGzl6YLlNhK3PTNxW3xPv1vE+YhsBBUJxq31IbBb3CVZO3ufW/a9AwqfEQYKT76qA3ELJIP8t8bx4UXgBWXF5/ybBqscfEqsgz6dDwB2Ub2KBINlYromgsd5owiHXM1y4+n8v4Lzgov8m/hS/io8Et1+eGT8UN4rPBJsIbuO7IiCysWlhI8S5Wdl45uQ5lA0KfbEaItnf4g/xk/hH0Dv98rw4BNxO+SYWCJKN5TYRSnlasHlgBXlDsPrYhfYCstJwLFLw/HWr4DkQwVit2DBw2+TWjByHiJ0VkJ0uz3/0843gdm63esTk/18JVmo2GT8IVsPzBM+OQJ88o/4ovhT0vKZG6MsPAX0TCwTJxnKbCFs3Ehsr/AzD6sfqhYTsfLmdcuvjpxaer2yTwgaBTQm3PHbD7FRZSTmG1/k8P9swXqfMSbXcWECO51z81MLunMcBVl6eM8lhVWN1ZKfMaxeKvetn+emFLDYt9M334Xi+3wGTANUQcJo7IZIkE8s1ETTuWpYbCdijhoDT3AmRJJlYbhNBl6MnLXcIOB10Lt9EKEkmlttEqGL0ouVWEWbfT2cI2HInRJJkYrlDwDoXkSSZWK4fdC7fRChJJpY7BKxzEUmSieX6QefyTYSSZGK5Q8A6F5EkmViuH3Qu30QoSSaWOwSscxFJkonl+kHn8k2EkmRiuUPAOheRJJlYrh90Lt9EKEkmljsErHMRSZKJ5fpB5/JNhJJkYrlDwDoXkSSZWK4bLElMhMWiCbhIRHPSmfDFJcOsEL2JpOhJNCf9mCv/AbdfUB70DXufAAAAAElFTkSuQmCC';
	spritesheet.onload = loaded;
}

// the spritesheet is ready
function loaded()
{
	console.log('Spritesheet loaded.');
	spritesheetLoaded = true;
	createWorld();
}

function clearWorld()
{
	console.log('Clearing maze...');

	// create emptiness
	for (var x = 0; x < worldWidth; x++)
	{
		world[x] = [];

		for (var y = 0; y < worldHeight; y++)
		{
			world[x][y] = 0;
		}
	}

	// remove old path
	pathStart = [0, 0];
	pathEnd = [0, 0];
	currentPath = findPath(world, pathStart, pathEnd);
	redraw();
}

// fill the world with walls
function createWorld()
{
	console.log('Generating maze...');

	// create emptiness
	for (var x = 0; x < worldWidth; x++)
	{
		world[x] = [];

		for (var y = 0; y < worldHeight; y++)
		{
			world[x][y] = 0;
		}
	}

	// Generate a maze
	var moves = [];

	var posX = 1;
	var posY = 1;
	world[posX][posY] = 1;
	moves.push(posY + posY * worldWidth);

	for (var i = 0; i < worldWidth * worldHeight; i++)
	{
		if (moves.length)
		{
			var possibleDirections = "";
			if (posX + 2 > 0 && posX + 2 < worldHeight && world[posX + 2][posY] == 0)
			{
				possibleDirections += "S";
			}
			if (posX - 2 > 0 && posX - 2 < worldHeight && world[posX - 2][posY] == 0)
			{
				possibleDirections += "N";
			}
			if (posY - 2 > 0 && posY - 2 < worldWidth && world[posX][posY - 2] == 0)
			{
				possibleDirections += "W";
			}
			if (posY + 2 > 0 && posY + 2 < worldWidth && world[posX][posY + 2] == 0)
			{
				possibleDirections += "E";
			}
			if (possibleDirections)
			{
				var move = Math.floor(Math.random() * possibleDirections.length) + 0;
				switch (possibleDirections[move])
				{
					case "N":
						world[posX - 2][posY] = 1;
						world[posX - 1][posY] = 1;
						posX -= 2;
						break;
					case "S":
						world[posX + 2][posY] = 1;
						world[posX + 1][posY] = 1;
						posX += 2;
						break;
					case "W":
						world[posX][posY - 2] = 1;
						world[posX][posY - 1] = 1;
						posY -= 2;
						break;
					case "E":
						world[posX][posY + 2] = 1;
						world[posX][posY + 1] = 1;
						posY += 2;
						break;
				}
				moves.push(posY + posX * worldWidth);
			}
			else
			{
				var back = moves.pop();
				posX = Math.floor(back / worldWidth);
				posY = back % worldWidth;
			}
		}
	}

	world[0][0] = 1;
	world[worldWidth - 1][0] = 1;
	world[worldWidth - 1][worldHeight - 1] = 1;
	world[0][worldHeight - 1] = 1;

	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 right click events on the canvas
function rightClick(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 right clicked tile ' + cell[0] + ',' + cell[1]);

	// toggle it into an obstacle
	world[cell[0]][cell[1]] = (world[cell[0]][cell[1]] == 1) ? 0 : 1;

	// calculate path
	currentPath = findPath(world, pathStart, pathEnd);
	redraw();

	// Prevent context menu
	return false;
}

var path = 0;

// 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)
	];
  
  // Prevent placing inside obstacle
  if (world[cell[0]][cell[1]] == 0)
  {
    if (!path)
    {
      // remove old path
      pathStart = cell;
      pathEnd = cell;
      currentPath = findPath(world, pathStart, pathEnd);
      redraw();
    }

    // now we know while tile we clicked
    console.log('we clicked tile ' + cell[0] + ',' + cell[1]);

    path = !path;

    if (path)
    {
      pathStart = cell;
    }
    else
    {
      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;
	}

	return calculatePath();
}
            
          
!
999px
Loading ..................

Console