Brian Grinstead

See the updated pathfinding demo of A* Search in JavaScript.

Get all the updated source code from github.

When I first wrote the A* Search in JavaScript article I knew there were some things that could make the pathfinding faster. I didn't know realize that it would be this much faster. Here are my (totally unscientific) results:

Observed Speed of A* Search on Chrome 6.0.472.55 on OS X
# rows	original	updated
100	700-2500ms (wildly variant)	5-10ms
50	160ms	5-10ms
15	0-5ms	0-2ms

Here's What Changed

I got some feedback about using a heap or a priority queue instead of a list (basically keep the open items in sorted order the whole time so we can just grab it off of the top instead of needing to traverse the whole list every time. As predicted, this makes a huge difference as the number of nodes goes up, but may actually be a little slower for a very low number of nodes because of the overhead of keeping them sorted. I found a binary heap implementation from http://eloquentjavascript.net/appendix2.html and put it in.

Also, I realized two places that I was traversing lists that could be avoided. Getting rid of extra traversals (especially ones that ran inside nested loops) made a very big difference in performance.

1. I was keeping all of the nodes inside a closed list, which required traversing that list every time to see if it was already closed. This was replaced with a simple bit on the node to track if it had been closed.
2. I was checking to see if a node was visited already by seeing if it was in the open list. This was replaced by a simple bit to see if it had been visited.

Old Pseudocode

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
    }
  }
}

Updated Pseudocode (* lines have changed)

* push startNode onto openHeap
while(openList is not empty) {
  * currentNode = pop from openHeap
  if currentNode is final, return the successful path
  * set currentNode as closed
  foreach neighbor of currentNode {
    * if neighbor is not set visited {
      * save g, h, and f then save the current parent and set visited
      * add neighbor to openHeap
    }
    if neighbor is in openList but the current g is better than previous g {
      save g and f, then save the current parent
      * reset position in openHeap (since f changed)
    }
  }
}

I also did some general cleanup, getting rid of dependancies on the demo, and I split out the code so that the search function can be used standalone (taking a two dimensional array as a parameter), so if someone just wanted the optimized astar search, you could call it like so:

<script type='text/javascript' src='astar.js'></script>
<script type='text/javascript'>
var graph = new Graph([
  [1,1,1,1], // 1 is open, 0 is wall
  [0,1,1,0],
  [0,0,1,1]
]);
var start = graph.nodes[0][0];
var end = graph.nodes[1][2];
var result = astar.search(graph.nodes, start, end);
// result is an array containing the shortest path
</script>

What Could Make It Better?

Last time I posted about this, I got a lot of feedback (mostly about how slow it was). If anyone reading this knows of anything that could make it better, let me know.

Source Code (direct links)

astar.js |

graph.js |

demo.js |

astar-list.js (old implementation with open and closed values swapped)

Sometimes, I want to have a JavaScript event that doesn't fire until the native event stops firing for a short timeout. I've needed to use that pattern in almost every project I have worked on.

For example, you want to use JavaScript to resize an iframe to 100% height when the window resizes. The resize() event can fire dozens of times, and calculating and setting the new height can slow down your page. I used to implement it like this (notice the extra global variable and indentation with the anonymous function):

var timeout;
function doResize(e) {
   clearTimeout(timeout);
   timeout = setTimeout(function() {
      // run some code
   }, 200);
}
$(function() {
   $(window).bind("resize",doResize);
});

I wrote a plugin to make this pattern easier, it is called "bindWithDelay". The source code is online, as is a mini project page with a demo.

This is what the same code looks like with the plugin:

function doResize(e) {
  // run some code
}
$(function() {
   $(window).bindWithDelay("resize", doResize, 200);
});

I wrote an article, Make Table Rows Sortable Using jQuery UI Sortable on the Foliotek 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();

I had used C# for at least a year before I found out a couple of nice shorthand ways to convert types. These are the is and as expressions, and using them can help make your code more readable.

The is Expression

The is expression will return true if the provided expression is non-null and can be cast to the specific type.

private string GetDisplayField(object val)
{
  if (val is string)
  {
    string text = (string)val;
    return "Value was text: " + text;
  }
  else if (val is DateTime)
  {
    DateTime time = (DateTime)val;
    return "Value was date: " + time.ToShortDateString();
  }

  return "Could not match type";
}

The as Expression

The as expression will try to cast the object into the given type, and returns an object of that type if the cast was successful, or return null if unsuccessful.

This buys a little bit more functionality for you, as it assigns the variable with an already casted value if successful. It is functionally equivalent to: expression is type ? (type)expression : (type)null

private string GetDisplayField(object val)
{
  string text = val as string;
  DateTime? time = val as DateTime?;

  if (text != null)
  {
    return "Value was text: " + text;
  }
  if (time.HasValue)
  {
    return "Value was date: " + time.Value.ToShortDateString();
  }

  return "Could not match type";
}

Testing out the functions

Console.WriteLine(GetDisplayField(1));              // Output: "Could not match type"
Console.WriteLine(GetDisplayField("Hello"));        // Output: "Value was text: Hello"
Console.WriteLine(GetDisplayField(DateTime.Now));   // Output: "Value was date: 7/21/2009"

They are both readable ways to perform a type conversion - but pick one or the other! Using both of them is redundant.

Or: Binding Events Inside of a Loop with jQuery

I wrote an article on the Foliotek 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 = ; 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"
    });
  }
});

A Solution

$(function() {
  $("body").append("<ul id='container'></ul>");
  for (var i = ; 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.