Brian Grinstead

I wrote an article on the LANIT Development blog about a problem that I ran into when trying to set up a basic sortable table using jQuery UI. The columns would collapse down once the dragging began.

This was fixed by adjusting the helper object for the sortable function. Check out the article for all the details, but here is a sample of the code if you are just looking for the solution:

// Return a helper with preserved width of cells
var fixHelper = function(e, ui) {
	ui.children().each(function() {
		$(this).width($(this).width());
	});
	return ui;
};
 
$("#sort tbody").sortable({
	helper: fixHelper
}).disableSelection();

Or: Binding Events Inside of a Loop with jQuery

I wrote an article over on the LANIT Development Blog about saving the state of a variable inside a closure that is not executed immediately. For example, functions passed into event binding or setTimeout(). Here is a quick rundown of the problem and the solution (using the jQuery library).

The Problem

$(function() {
	$("body").append("<ul id='container'></ul>");
 
	for (var i = 0; i < 5; i++)
	{
		var $item = $("<li />").text("Item " + i);
		$("#container").append($item);
 
		$item.click(function() {
			alert("You clicked number " + i);  // always "You clicked number 5"
		});
	}
});

The Solution

$(function() {
	$("body").append("<ul id='container'></ul>");
 
	for (var i = 0; i < 5; i++)
	{
		var $item = $("<li />").text("Item " + i);
		$("#container").append($item);
 
		(function() { // Closure here here instead of "bindItem()"
			var ind = i;
			$item.click(function() {
				alert("You clicked number " + ind); // Works as expected
			});
		})(); // Execute immediately
	}
});

The solution uses an immediately executing function to create a new scope and declare a variable “ind” that is reserved a new space in memory instead of simply referencing “i”. Check out the full article for more details.

outerHTML is a property that is provided by Internet Explorer that returns the full HTML of an element (including start and end tags). In jQuery, the html() function returns the innerHTML of an element, which is just the HTML inside the element (not including the start and end tags).

There came a time that I wanted to get the outerHTML of an element, and I found that Brandon Aaron shared a jQuery code snippet that does this exactly. It does the trick for most cases, but there was one problem that I ran into. I wanted to get the outerHTML of an element inside of an iframe, and I got a ‘Permission Denied’ error in Internet Explorer.

The problem was that it was appending an element belonging to the iframes ‘contentDocument’ into an element belonging to the global ‘document’ element.
Using the jQuery(html, ownerDocument) overload of the jQuery core function, this error was fixed:

$.fn.outerHTML = function() {
    var doc = this[0] ? this[0].ownerDocument : document;
    return $('<div>', doc).append(this.eq(0).clone()).html();
};

One thing that has always been annoying about programming JavaScript in an ASP.NET Web Forms environment is that the ID attribute of HTML controls rendered out from ASP controls is unpredictable.

	<asp:TextBox runat="server" ID="txtPhoneNumber" />

renders out as something like:

	<input type="text" id="ctl00_ctl00_ctl00_main_Content_txtPhoneNumber" 
		name="ctl00$ctl00$ctl00$main$Content$txtPhoneNumber" />

I did a write up over on the LANIT development blog about a solution to this problem using jQuery.

Check out the post for more details, but here is the function:

	jQuery.expr[':'].asp = function(elem, i, match) {
		return (elem.id && elem.id.match(match[3] + "$"));
	};
 
	$(":asp(txtPhoneNumber)").keyup(...);

View the online demo

I first implemented the A* algorithm for a research group I was in through school (Computer Graphics and Image Understanding). A* is a best-first, graph search algorithm. Some basic information can be found on the Wikipedia page for A* and the external links contained in it. Please refer to that page for general reference about the algorithm, I will simply explain in my own words how it works and how I got it working.

A* algorithm in JavaScript

Why JavaScript?

Because it was easy to deploy!

Since I know JavaScript pretty well, and most of the examples you can find are in C, Java or a similar language that you cannot run without downloading source code or executables, I thought it would be a good idea to program it on an html page. This way, people could see what was going on and view the source very easily (download Firebug and give it a try if you don’t already have it).

My hope was to build a page that could be extended with other search algorithms by separating the UI code (that generates a graph with walls and animates the path that is determined by an algorithm), and the algorithm that finds the path. Maybe I will get around to plugging in some more algorithms sometime and making it into a little resource for graph search algorithms.

How?

search.html

Just a basic html file that includes jQuery, the excellent JavaScript library, main.css, graph.js, and astar.js. Also, I have a JavaScript block that initializes the page.

graph.js

The point of this file is to build the graph, call the search function, and animate the results after the search has returned. It also has an option to show the debugging information created by the search algorithm. I won’t get too into the code here, since it distracts from the search algorithm.

Please take a look at it, be aware that there are some improvements I would make if I was to rewrite this today. First, I would like to convert it to a jQuery plugin. Also, it modifies the Array.prototype to add on specific methods (findGraphNode and removeGraphNode) for search algorithms, which may not be ideal for bigger projects. For this little page, I’m not too worried about it, but if I do get around to adding in more algorithms, I will probably improve this code.

astar.js

This is the actual implementation of the algorithm. I will do my best to explain what is going on, but feel free to just look at the source of the example, or just download astar.js.

There are three functions that we keep track of for nodes that we look at:

• g(x): The total cost of getting to that node (pretty straightforward). If we reach a node for the first time or reach a node in less time than it currently took, then update the g(x) to the cost to reach this node.
• h(x): The estimated time to reach the finish from the current node. This is also called a heuristic. We online need to update this if it is not set already, since the distance to the finish will not change even if the path we took to arrive at a node changes. Note: There are many different ways to guess how far you are from the end, I use the Manhattan distance in this implementation.
• f(x): Simply g(x) + h(x). The lower the f(x), the better. Think about it like this: the best node is one that takes the least total amount of time to arrive at and to get to the end. So, a node that took only 1 step to arrive at and 5 to get to the end is more ideal than one that took 10 to arrive and and only 1 to get to the end.

Here is some high level pseudocode of what is happening in the algorithm. Also see the Wikipedia pseudocode for another example.

  push startNode onto openList
  while(openList is not empty) {
     currentNode = find lowest f in openList
     if currentNode is final, return the successful path
     push currentNode onto closedList and remove from openList
     foreach neighbor of currentNode {
         if neighbor is not in openList {
                save g, h, and f then save the current parent
                add neighbor to openList
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
         }
     }

Here is the JavaScript:

 
var astar = {
	init: function(grid) {
		for(var x = 0; x < grid.length; x++) {
			for(var y = 0; y < grid[x].length; y++) {
				grid[x][y].f = 0;
				grid[x][y].g = 0;
				grid[x][y].h = 0;
				grid[x][y].debug = "";
				grid[x][y].parent = null;
			}	
		}
	},
	search: function(grid, start, end) {
		astar.init(grid);
 
		var openList   = [];
		var closedList = [];
		openList.push(start);
 
		while(openList.length > 0) {
 
			// Grab the lowest f(x) to process next
			var lowInd = 0;
			for(var i=0; i<openList.length; i++) {
				if(openList[i].f < openList[lowInd].f) { lowInd = i; }
			}
			var currentNode = openList[lowInd];
 
			// End case -- result has been found, return the traced path
			if(currentNode.pos == end.pos) {
				var curr = currentNode;
				var ret = [];
				while(curr.parent) {
					ret.push(curr);
					curr = curr.parent;
				}
				return ret.reverse();
			}
 
			// Normal case -- move currentNode from open to closed, process each of its neighbors
			openList.removeGraphNode(currentNode);
			closedList.push(currentNode);
			var neighbors = astar.neighbors(grid, currentNode);
 
			for(var i=0; i<neighbors.length;i++) {
				var neighbor = neighbors[i];
				if(closedList.findGraphNode(neighbor) || neighbor.isWall()) {
					// not a valid node to process, skip to next neighbor
					continue;
				}
 
				// g score is the shortest distance from start to current node, we need to check if
				//	 the path we have arrived at this neighbor is the shortest one we have seen yet
				var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
				var gScoreIsBest = false;
 
 
				if(!openList.findGraphNode(neighbor)) {
					// This the the first time we have arrived at this node, it must be the best
					// Also, we need to take the h (heuristic) score since we haven't done so yet
 
					gScoreIsBest = true;
					neighbor.h = astar.heuristic(neighbor.pos, end.pos);
					openList.push(neighbor);
				}
				else if(gScore < neighbor.g) {
					// We have already seen the node, but last time it had a worse g (distance from start)
					gScoreIsBest = true;
				}
 
				if(gScoreIsBest) {
					// Found an optimal (so far) path to this node.	 Store info on how we got here and
					//	just how good it really is...
					neighbor.parent = currentNode;
					neighbor.g = gScore;
					neighbor.f = neighbor.g + neighbor.h;
					neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
				}
			}
		}
 
		// No result was found -- empty array signifies failure to find path
		return [];
	},
	heuristic: function(pos0, pos1) {
		// This is the Manhattan distance
		var d1 = Math.abs (pos1.x - pos0.x);
		var d2 = Math.abs (pos1.y - pos0.y);
		return d1 + d2;
	},
	neighbors: function(grid, node) {
		var ret = [];
		var x = node.pos.x;
		var y = node.pos.y;
 
		if(grid[x-1] && grid[x-1][y]) {
			ret.push(grid[x-1][y]);
		}
		if(grid[x+1] && grid[x+1][y]) {
			ret.push(grid[x+1][y]);
		}
		if(grid[x][y-1] && grid[x][y-1]) {
			ret.push(grid[x][y-1]);
		}
		if(grid[x][y+1] && grid[x][y+1]) {
			ret.push(grid[x][y+1]);
		}
		return ret;
	}
};

Conclusion

This A* search implementation could be used as a component to larger system (like a game – maybe tower defense or puzzle), or just for learning purposes. I have done my best to make the code understandable and to present the concepts in a way that would help someone who has never seen the algorithm before, or someone who is not very familiar with JavaScript. Hopefully, if you don’t know JavaScript, you will at some point take the time to learn it. It is a very useful language with a huge deployment platform (the Internet).

Feel free to view the demo, or download graph.js, astar.js, and search.css to mess around with it.