geoffb · January 12, 2011 18:59
diff --git a/astar.js b/astar.js
 var AStar;

 (function () {

 	var Node = function (index, x, y, parent) {
 		this.index = index;
 		this.x = x;
 		this.y = y;
 		this.parent = parent || null;
 		this.f = 0;
 		this.g = 0;
 	};

 	Node.prototype.getDistance = function (node) {
 		return (
 			Math.abs(this.x - node.x)
 			+ Math.abs(this.y - node.y)
 		);
 	};

 	var Map = function (grid) {
 		this.grid = grid;
 		this.width = grid[0].length;
 		this.height = grid.length;
 	};

 	Map.prototype.isWalkable = function (x, y) {
 		if (
 			x < 0
 			|| y < 0
 			|| x >= this.width
 			|| y >= this.height
 		) {
 			// Outside the map. Totally NOT walkable!
 			return false;
 		}
 		return (!this.grid[y][x]);
 	};

 	Map.prototype.makeNode = function (x, y, parent) {
 		return new Node(
 			(x + (y * this.width)),
 			x, y, parent
 		);
 	};

 	Map.prototype.getAdjacent = function (n) {
 		var a = [];
 		// North
 		if (this.isWalkable(n.x, n.y - 1)) {
 			a.push(this.makeNode(n.x, n.y - 1, n));
 		}
 		// South
 		if (this.isWalkable(n.x, n.y + 1)) {
 			a.push(this.makeNode(n.x, n.y + 1, n));
 		}
 		// West
 		if (this.isWalkable(n.x - 1, n.y)) {
 			a.push(this.makeNode(n.x - 1, n.y, n));
 		}
 		// East
 		if (this.isWalkable(n.x + 1, n.y)) {
 			a.push(this.makeNode(n.x + 1, n.y, n));
 		}
 		return a;
 	};

 	AStar = function (grid, startX, startY, goalX, goalY) {

 		// The search area
 		var map = new Map(grid);

 		// The start and goal nodes
 		var start = map.makeNode(startX, startY);
 		var goal = map.makeNode(goalX, goalY);

 		// List to keep track of open and closed nodes
 		var openList = [start];
 		var closedList = [];

 		var len = 0;
 		while (len = openList.length) {

 			var minF = {
 				index: -1,
 				f: Infinity
 			};

 			// Find the node on the open list
 			// with the lowest F
 			for (var i = 0; i < len; ++i) {
 				if (openList[i].f < minF.f) {
 					minF.f = openList[i].f;
 					minF.index = i;
 				}
 			}

 			// Remove this node from the open list
 			var node = openList.splice(minF.index, 1)[0];

 			if (node.index === goal.index) {

 				// Hooray! We found the goal node!

 				// Create the final path
 				var path = [];
 				do {
 					path.push([node.x, node.y]);
 				} while (node = node.parent);

 				// ...and flip it so it's in the right order
 				path.reverse();

 				return path;

 			} else {

 				// Haven't found the goal node yet...

 				// Get adjacent nodes
 				var adjacent = map.getAdjacent(node);

 				// Calculate values for adjacent nodes
 				// and add them to the open list if
 				// they aren't already closed
 				for (var i = 0, j = adjacent.length; i < j; ++i) {
 					var n = adjacent[i];
 					if (!closedList[n.index]) {
 						n.g = (node.g + n.getDistance(node));
 						n.f = (n.g + n.getDistance(goal));
 						openList.push(n);
 						closedList[n.index] = true;
 					}
 				}

 			}

 		}

 		// We didn't find a path to the goal :(
 		return null;

 	};

 }());
diff --git a/astar_example.html b/astar_example.html
 <!DOCTYPE html>
 <html lang="en">
 <head>
 	<title>A* Pathfinding Example</title>
 </head>
 <body>

 	<script src="astar.js"></script>

 	<script>

 		var map = [
 			[0, 0, 0, 1, 0],
 			[0, 1, 0, 1, 0],
 			[0, 1, 0, 0, 0],
 			[0, 1, 1, 1, 0],
 			[0, 0, 0, 1, 0]
 		];

 		var path = AStar(map, 0, 0, 4, 4);

 		if (path) {
 			for (var i = 0; i < path.length; ++i) {
 				console.log(path[i]);
 			}
 		} else {
 			console.log("No path found :(");
 		}

 	</script>

 </body>
 </html>
	var AStar;

	(function () {

	var Node = function (index, x, y, parent) {
	this.index = index;
	this.x = x;
	this.y = y;
	this.parent = parent \|\| null;
	this.f = 0;
	this.g = 0;
	};

	Node.prototype.getDistance = function (node) {
	return (
	Math.abs(this.x - node.x)
	+ Math.abs(this.y - node.y)
	);
	};

	var Map = function (grid) {
	this.grid = grid;
	this.width = grid[0].length;
	this.height = grid.length;
	};

	Map.prototype.isWalkable = function (x, y) {
	if (
	x < 0
	\|\| y < 0
	\|\| x >= this.width
	\|\| y >= this.height
	) {
	// Outside the map. Totally NOT walkable!
	return false;
	}
	return (!this.grid[y][x]);
	};

	Map.prototype.makeNode = function (x, y, parent) {
	return new Node(
	(x + (y * this.width)),
	x, y, parent
	);
	};

	Map.prototype.getAdjacent = function (n) {
	var a = [];
	// North
	if (this.isWalkable(n.x, n.y - 1)) {
	a.push(this.makeNode(n.x, n.y - 1, n));
	}
	// South
	if (this.isWalkable(n.x, n.y + 1)) {
	a.push(this.makeNode(n.x, n.y + 1, n));
	}
	// West
	if (this.isWalkable(n.x - 1, n.y)) {
	a.push(this.makeNode(n.x - 1, n.y, n));
	}
	// East
	if (this.isWalkable(n.x + 1, n.y)) {
	a.push(this.makeNode(n.x + 1, n.y, n));
	}
	return a;
	};

	AStar = function (grid, startX, startY, goalX, goalY) {

	// The search area
	var map = new Map(grid);

	// The start and goal nodes
	var start = map.makeNode(startX, startY);
	var goal = map.makeNode(goalX, goalY);

	// List to keep track of open and closed nodes
	var openList = [start];
	var closedList = [];

	var len = 0;
	while (len = openList.length) {

	var minF = {
	index: -1,
	f: Infinity
	};

	// Find the node on the open list
	// with the lowest F
	for (var i = 0; i < len; ++i) {
	if (openList[i].f < minF.f) {
	minF.f = openList[i].f;
	minF.index = i;
	}
	}

	// Remove this node from the open list
	var node = openList.splice(minF.index, 1)[0];

	if (node.index === goal.index) {

	// Hooray! We found the goal node!

	// Create the final path
	var path = [];
	do {
	path.push([node.x, node.y]);
	} while (node = node.parent);

	// ...and flip it so it's in the right order
	path.reverse();

	return path;

	} else {

	// Haven't found the goal node yet...

	// Get adjacent nodes
	var adjacent = map.getAdjacent(node);

	// Calculate values for adjacent nodes
	// and add them to the open list if
	// they aren't already closed
	for (var i = 0, j = adjacent.length; i < j; ++i) {
	var n = adjacent[i];
	if (!closedList[n.index]) {
	n.g = (node.g + n.getDistance(node));
	n.f = (n.g + n.getDistance(goal));
	openList.push(n);
	closedList[n.index] = true;
	}
	}

	}

	}

	// We didn't find a path to the goal :(
	return null;

	};

	}());
	<!DOCTYPE html>
	<html lang="en">
	<head>
	<title>A* Pathfinding Example</title>
	</head>
	<body>

	<script src="astar.js"></script>

	<script>

	var map = [
	[0, 0, 0, 1, 0],
	[0, 1, 0, 1, 0],
	[0, 1, 0, 0, 0],
	[0, 1, 1, 1, 0],
	[0, 0, 0, 1, 0]
	];

	var path = AStar(map, 0, 0, 4, 4);

	if (path) {
	for (var i = 0; i < path.length; ++i) {
	console.log(path[i]);
	}
	} else {
	console.log("No path found :(");
	}

	</script>

	</body>
	</html>