JavaScript A* with Manhattan Distance

gistfile1.js

	// A*
	// Much thanks to http://www.geeksforgeeks.org/a-search-algorithm/

	// Extending array
	Array.prototype.empty = function() {
		return this.length == 0;
	};

	// Constants
	var SQUARE_SIZE = 100;
	var ROW = 9;
	var COL = 10;

	// Set up canvas
	var c =  document.getElementById('c');
	var ctx = c.getContext("2d");
	var width = c.width;
	var height = c.height;	
	ctx.fillStyle="#FFFFFF";

	// Graphic methods
	var drawSquare = function(i,j) {
		ctx.fillRect(j*SQUARE_SIZE, i*SQUARE_SIZE, SQUARE_SIZE, SQUARE_SIZE);
	};

	var drawCanvas = function() {
		ctx.fillStyle="#FFFFFF";
		ctx.clearRect(0, 0, width, height);
		for (var i = 0; i < height/SQUARE_SIZE; i++) {
			for (var j = 0; j < width/SQUARE_SIZE; j++ ) {
				if (grid[i][j] == 1) {
					drawSquare(i,j);
				}
			}
		}
	};

	var drawSrcDest = function() {
		ctx.fillStyle="#FF0000";
		ctx.fillRect(src.j*SQUARE_SIZE, src.i*SQUARE_SIZE, SQUARE_SIZE, SQUARE_SIZE);

		ctx.fillStyle="#FF66FF";
		ctx.fillRect(dest.j*SQUARE_SIZE, dest.i*SQUARE_SIZE, SQUARE_SIZE, SQUARE_SIZE);
	};

	var drawPath = function (p) {
		ctx.fillStyle="#339e68";
		ctx.fillRect(p.j*SQUARE_SIZE, p.i*SQUARE_SIZE, SQUARE_SIZE, SQUARE_SIZE);
	};


	// A* Search

	// Control Objects
	var grid = [
		[ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
        [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 1 ],
        [ 1, 1, 1, 0, 1, 1, 0, 1, 0, 1 ],
        [ 0, 0, 1, 0, 1, 0, 0, 0, 0, 1 ],
        [ 1, 1, 1, 0, 1, 1, 1, 0, 1, 0 ],
        [ 1, 0, 1, 1, 1, 1, 0, 1, 0, 0 ],
        [ 1, 0, 0, 0, 0, 1, 0, 0, 0, 1 ],
        [ 1, 0, 1, 1, 1, 1, 0, 1, 1, 1 ],
        [ 1, 1, 1, 0, 0, 0, 1, 0, 0, 1 ]
    ];
    var closedList = [];
    var cellDetails = [];
    var openList = [];

    function Cell() {
    	this.parent_i = -1;
    	this.parent_j = -1;
    	this.f = Number.MAX_SAFE_INTEGER;
    	this.g = Number.MAX_SAFE_INTEGER;
    	this.h = Number.MAX_SAFE_INTEGER;
    }

    function MetaPair() {
    	this.f;
    	this.cord = {
    		i : -1,
    		j : -1,
    	};
    };

	// Setup grid
	for (var i = 0; i < height/SQUARE_SIZE; i++) {
		closedList.push([]);
		cellDetails.push([]);
		for (var j = 0; j < width/SQUARE_SIZE; j++ ) {
			closedList[i].push(false);

			// Initialize Cells
			var tempCell = new Cell();
			cellDetails[i].push(tempCell);
		}
	}

	var src = {i: 8, j: 0};
	var dest = {i: 0, j: 0};

	// Initialize first cell
	var i = src.i; var j = src.j;
	cellDetails[src.i][src.j].f = 0;
	cellDetails[src.i][src.j].g = 0;
	cellDetails[src.i][src.j].h = 0;
	cellDetails[src.i][src.j].parent_i = i;
	cellDetails[src.i][src.j].parent_j = j;

	// Initialize the open list
	var tempMetaPair = new MetaPair();
	tempMetaPair.f = 0;
	tempMetaPair.cord.i = i;
	tempMetaPair.cord.j = j;
	openList.push(tempMetaPair);


	var isValid = function(row, col) {
		return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL);
	}

	// uses destination
	var isDestination = function(row, col) {
		return row == dest.i && col == dest.j;
	};

	// Uses grid
	var isUnBlocked = function(row, col) {
		return grid[row][col] == 1;
	};

	// Uses destination
	var calculateHValue = function(row, col) {
		// return Math.sqrt(Math.pow(row - dest.i,2) + Math.pow(col - dest.j,2));
		return Math.abs(row - dest.i) + Math.abs(col - dest.j); 
	};

	// Uses cellDetails and destination
	var tracePath = function() {
		console.log("The Path Is: ");
		var row = dest.i;
		var col = dest.j;

		var path = [];
		while(!(cellDetails[row][col].parent_i == row && cellDetails[row][col].parent_j == col)) {
			path.unshift({i : row, j : col});
			var temp_row = cellDetails[row][col].parent_i;
			var temp_col = cellDetails[row][col].parent_j;
			row = temp_row;
			col = temp_col;
		}

		path.unshift({i : row, j : col});
		while(!path.empty()) {
			var p = path.shift();
			console.log("-> " + p.i + ", " + p.j);

			if (!(p.i == src.i && p.j == src.j) && !(p.i == dest.i && p.j == dest.j))
				drawPath(p);
		}
	};

	var foundDest = false;
	var aStarSearch = function() {

		while (!openList.empty()) {

			// Get first item and remove from list
			var p = openList.shift();
			i = p.cord.i;
			j = p.cord.j;
			closedList[i][j] = true;

			// Store the successor f, g, and h values
			var gNew, hNew, fNew;


			// North
			// Test Bounds
			if (isValid(i-1, j)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i-1, j)) {
					cellDetails[i-1][j].parent_i = i;
					cellDetails[i-1][j].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i-1][j] == false && isUnBlocked(i-1,j) == true) {
					gNew = cellDetails[i][j].g + 1;
					hNew = calculateHValue(i-1,j);
					fNew = gNew + hNew;

					if (cellDetails[i-1][j].f == Number.MAX_SAFE_INTEGER || cellDetails[i-1][j].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i-1;
						tempMeta.cord.j = j;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i-1][j].f = fNew;
	                    cellDetails[i-1][j].g = gNew;
	                    cellDetails[i-1][j].h = hNew;
	                    cellDetails[i-1][j].parent_i = i;
	                    cellDetails[i-1][j].parent_j = j;
					}
				}
			}

			// South
			// Test Bounds
			if (isValid(i+1, j)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i+1, j)) {
					cellDetails[i+1][j].parent_i = i;
					cellDetails[i+1][j].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i+1][j] == false && isUnBlocked(i+1,j) == true) {
					gNew = cellDetails[i][j].g + 1;
					hNew = calculateHValue(i+1,j);
					fNew = gNew + hNew;

					if (cellDetails[i+1][j].f == Number.MAX_SAFE_INTEGER || cellDetails[i+1][j].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i+1;
						tempMeta.cord.j = j;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i+1][j].f = fNew;
	                    cellDetails[i+1][j].g = gNew;
	                    cellDetails[i+1][j].h = hNew;
	                    cellDetails[i+1][j].parent_i = i;
	                    cellDetails[i+1][j].parent_j = j;
					}
				}
			}	

			// East
			if (isValid(i, j+1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i, j+1)) {
					cellDetails[i][j+1].parent_i = i;
					cellDetails[i][j+1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i][j+1] == false && isUnBlocked(i,j+1) == true) {
					gNew = cellDetails[i][j].g + 1;
					hNew = calculateHValue(i,j+1);
					fNew = gNew + hNew;

					if (cellDetails[i][j+1].f == Number.MAX_SAFE_INTEGER || cellDetails[i][j+1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i;
						tempMeta.cord.j = j+1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i][j+1].f = fNew;
	                    cellDetails[i][j+1].g = gNew;
	                    cellDetails[i][j+1].h = hNew;
	                    cellDetails[i][j+1].parent_i = i;
	                    cellDetails[i][j+1].parent_j = j;
					}
				}
			}	

			// West
			if (isValid(i, j-1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i, j-1)) {
					cellDetails[i][j-1].parent_i = i;
					cellDetails[i][j-1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i][j-1] == false && isUnBlocked(i,j-1) == true) {
					gNew = cellDetails[i][j].g + 1;
					hNew = calculateHValue(i,j-1);
					fNew = gNew + hNew;

					if (cellDetails[i][j-1].f == Number.MAX_SAFE_INTEGER || cellDetails[i][j-1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i;
						tempMeta.cord.j = j-1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i][j-1].f = fNew;
	                    cellDetails[i][j-1].g = gNew;
	                    cellDetails[i][j-1].h = hNew;
	                    cellDetails[i][j-1].parent_i = i;
	                    cellDetails[i][j-1].parent_j = j;
					}
				}
			}	

			// Northeast
			/*
			if (isValid(i-1, j+1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i-1, j+1)) {
					cellDetails[i-1][j+1].parent_i = i;
					cellDetails[i-1][j+1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i-1][j+1] == false && isUnBlocked(i-1,j+1) == true) {
					gNew = cellDetails[i][j].g + 1.414;
					hNew = calculateHValue(i-1,j+1);
					fNew = gNew + hNew;

					if (cellDetails[i-1][j+1].f == Number.MAX_SAFE_INTEGER || cellDetails[i-1][j+1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i-1;
						tempMeta.cord.j = j+1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i-1][j+1].f = fNew;
	                    cellDetails[i-1][j+1].g = gNew;
	                    cellDetails[i-1][j+1].h = hNew;
	                    cellDetails[i-1][j+1].parent_i = i;
	                    cellDetails[i-1][j+1].parent_j = j;
					}
				}
			}	

			// Northwest
			if (isValid(i-1, j-1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i-1, j-1)) {
					cellDetails[i-1][j-1].parent_i = i;
					cellDetails[i-1][j-1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i-1][j-1] == false && isUnBlocked(i-1,j-1) == true) {
					gNew = cellDetails[i][j].g + 1.414;
					hNew = calculateHValue(i-1,j-1);
					fNew = gNew + hNew;

					if (cellDetails[i-1][j-1].f == Number.MAX_SAFE_INTEGER || cellDetails[i-1][j-1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i-1;
						tempMeta.cord.j = j-1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i-1][j-1].f = fNew;
	                    cellDetails[i-1][j-1].g = gNew;
	                    cellDetails[i-1][j-1].h = hNew;
	                    cellDetails[i-1][j-1].parent_i = i;
	                    cellDetails[i-1][j-1].parent_j = j;
					}
				}
			}				

			// Southeast
			if (isValid(i+1, j+1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i+1, j+1)) {
					cellDetails[i+1][j+1].parent_i = i;
					cellDetails[i+1][j+1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i+1][j+1] == false && isUnBlocked(i+1,j+1) == true) {
					gNew = cellDetails[i][j].g + 1.414;
					hNew = calculateHValue(i+1,j+1);
					fNew = gNew + hNew;

					if (cellDetails[i+1][j+1].f == Number.MAX_SAFE_INTEGER || cellDetails[i+1][j+1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i+1;
						tempMeta.cord.j = j+1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i+1][j+1].f = fNew;
	                    cellDetails[i+1][j+1].g = gNew;
	                    cellDetails[i+1][j+1].h = hNew;
	                    cellDetails[i+1][j+1].parent_i = i;
	                    cellDetails[i+1][j+1].parent_j = j;
					}
				}
			}

			// Southwest
			if (isValid(i+1, j-1)) {
				// Test if we are at the destination
				// Next test if we have already closed this node and that it's unblocked
				if (isDestination(i+1, j-1)) {
					cellDetails[i+1][j-1].parent_i = i;
					cellDetails[i+1][j-1].parent_j = j;
					console.log("DESTINATION FOUND");
					tracePath();
					foundDest = true;
					return
				} else if (closedList[i+1][j-1] == false && isUnBlocked(i+1,j-1) == true) {
					gNew = cellDetails[i][j].g + 1.414;
					hNew = calculateHValue(i+1,j-1);
					fNew = gNew + hNew;

					if (cellDetails[i+1][j-1].f == Number.MAX_SAFE_INTEGER || cellDetails[i+1][j-1].f > fNew) {
						// Add our new optimum value to openList
						var tempMeta = new MetaPair();
						tempMeta.f = fNew;
						tempMeta.cord.i = i+1;
						tempMeta.cord.j = j-1;
						openList.push(tempMeta);

						// Update cellDetails
	                    cellDetails[i+1][j-1].f = fNew;
	                    cellDetails[i+1][j-1].g = gNew;
	                    cellDetails[i+1][j-1].h = hNew;
	                    cellDetails[i+1][j-1].parent_i = i;
	                    cellDetails[i+1][j-1].parent_j = j;
					}
				}
			}
			*/

		}

		if (!foundDest)
			console.log("FAILED TO FIND DESTINATION");

		return;
	};

	// Run Process
	drawCanvas();
	drawSrcDest();
	aStarSearch();