Single function that implements A-Star pathfinding algorithm in ~75 lines of code

astar.js

// PUBLIC DOMAIN
//
// Single function that implements A-Star pathfinding algorithm in ~75 lines of code
//
// (why use a huge library..?)
//
// Parameters:
//   solid   array of booleans (of size width * height) that determine if a tile is solid
//   width   width of the map
//   height  height of the map
//   start   starting point as an array of [x, y]
//   end     ending point as an array of [x, y]
//   diag    boolean if diagonal movements are allowed
//
// Returns:
//   array of points, where array[0] is the start and array[array.length - 1] is the end
//   or `false` if no path is found
// 
function astar(solid, width, height, start, end, diag){
	function heuristic(p1, p2){
		return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
	}
	function applydir(pt, d, amt){
		switch (d){
			case 0: pt[0] -= amt;               return pt;
			case 1: pt[0] -= amt; pt[1] -= amt; return pt;
			case 2:               pt[1] -= amt; return pt;
			case 3: pt[0] += amt; pt[1] -= amt; return pt;
			case 4: pt[0] += amt;               return pt;
			case 5: pt[0] += amt; pt[1] += amt; return pt;
			case 6:               pt[1] += amt; return pt;
			case 7: pt[0] -= amt; pt[1] += amt; return pt;
		}
	}
	var open = [];
	var from = [];
	var steps = [];
	var inopen = [];
	for (var i = 0, size = width * height; i < size; i++){
		from.push(-1);
		steps.push(-1);
		inopen.push(false);
	}
	open.push([start[0], start[1], heuristic(start, end)]);
	inopen[start[0] + width * start[1]] = true;
	steps[start[0] + width * start[1]] = 0;
	while (open.length > 0){
		var cur = open.shift();
		var curk = cur[0] + cur[1] * width;
		if (cur[0] == end[0] && cur[1] == end[1]){
			var path = [];
			var pp = [end[0], end[1]];
			while (true){
				path.unshift(pp);
				if (pp[0] == start[0] && pp[1] == start[1])
					return path;
				pp = applydir([pp[0], pp[1]], from[pp[0] + pp[1] * width], -1);
			}
		}
		inopen[curk] = false;
		for (var d = 0, dstep = diag ? 1 : 2; d < 8; d += dstep){
			var nxt = applydir([cur[0], cur[1]], d, 1);
			var nk = nxt[0] + nxt[1] * width;
			if (nxt[0] < 0 || nxt[0] >= width || nxt[1] < 0 || nxt[1] >= height || solid[nk])
				continue;
			var nsteps = steps[curk] + ((d % 2) ? 1.4142135623730951 : 1);
			if (steps[nk] >= 0 && nsteps >= steps[nk])
				continue;
			from[nk] = d;
			steps[nk] = nsteps;
			nxt.push(nsteps + heuristic(nxt, end));
			var inserted = false;
			var hasold = inopen[nk];
			inopen[nk] = true;
			for (var i = 0; i < open.length && (hasold || !inserted); i++){
				if (hasold && open[i][0] == nxt[0] && open[i][1] == nxt[1]){
					open.splice(i, 1);
					i--;
					hasold = false;
				}
				else if (!inserted && open[i][2] > nxt[2]){
					open.splice(i, 0, nxt);
					inserted = true;
				}
			}
			if (!inserted)
				open.push(nxt);
		}
	}
	return false;
}

// demo
astar([
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
	1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
	1, 0, 0, 1, 0, 0, 0, 0, 0, 1,
	1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
	1, 0, 0, 1, 0, 0, 1, 0, 0, 1,
	1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
	1, 0, 0, 0, 0, 0, 1, 0, 0, 1,
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
	10, 8,
	[1, 1], [8, 6],
	true);

// => [[1,1],[2,2],[2,3],[2,4],[3,5],[4,4],[5,3],[6,2],[7,3],[8,4],[8,5],[8,6]]

public domain