I presented at the Columbia MO web developer meetup on 12/15/2010. I talked about HTML canvas and JavaScript FileReader, Instant Sprite, JavaScript image processing, and other topics.
The slides for the talk are available at http://briangrinstead.com/canvasslides.
I am working on project that needs to read local files. This relies on the FileReader interface, and I couldn’t find any JavaScript libraries to help out with common usage for this, so I made one.
FileReader is a JavaScript interface that allows you to read local files as binary. This is available in supported browsers when a user drags and drops files into a browser window or selects files from an input with a type of file. See the FileReader specification for more information.
filereader.js is a wrapper for accessing this functionality. It can be called using:
FileReaderJS.setupInput(fileInput, opts); FileReaderJS.setupDrop(dropbox, opts);
If you use jQuery, you can access these calls with:
$("#fileInput").fileReaderJS(opts); $("#dropbox").fileReaderJS(opts);
To see the full range of options and functionality, view the readme.
filereader.js is available under the MIT License. See the full filereader.js code or the single file raw javascript source on github.
You can see an example project using filereader.js on Instant Sprite, a browser based CSS Sprite Generator that I am working on. Try dragging images onto the body, or clicking to add multiple image files to see what is possible.
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 |
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.
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 } }
* 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='graph.js'></script> <script type='text/javascript' src='astar.js'></script> <script type='text/javascript'> var graph = new Graph([ [0,0,0,0], // 0 is open, 1 is wall [1,0,0,1], [1,1,0,0] ]); 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>
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.
astar.js |
graph.js |
demo.js |
astar-list.js (old implementation)
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 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).
$(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" }); } });
$(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(...);
Note that this code has been updated. I have an updated blog post detailing what changed. The full source code is available at https://github.com/bgrins/javascript-astar
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
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 by using the online demo.
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.
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.
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. There are some performance issues that could be addressed, and 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.
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:
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; } };
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.
Feel free to view the demo, or download graph.js and astar.js to mess around with it.
We are what we pretend to be, so we must be careful about what we pretend to be.
Kurt Vonnegut’s Mother Night
Campbell had accepted the task of being an American spy at the beginning of the war. He transmitted messages through deliberate pauses, coughing, etc. in his radio transmissions. Throughout the war, he was the most reliable agent of his kind that America had and survived the war undetected.
Living a secretive and quiet life in New York City after the war, Campbell’s identity is suddenly exposed. The novel is a memoir that he is writing from inside an Israeli prison awaiting trial for his war crimes.
Campbell seems to be both good and evil at the same time. But is he essentially good or essentially evil?
In an internal sense, his actions were good – the information he was passing through the airwaves was helpful to the Allies and it took a total sacrifice of his reputation and his life to provide this service. His career as an author and playwright was gone, he lost his wife, he would never be accepted as a member of society in his home country and he continued to do his work in spite of these things.
However, the external Campbell, the person that the world saw, was clearly evil. When his father-in-law, who would have “been delighted” to figure out that Campbell had been a spy, was speaking with him near the end of the war he says:
You could have never served the enemy as well as you served us, … I realized that almost all the ideas that I hold now, that make me unashamed of anything I may have felt or done as a Nazi, came not from Hitler, not from Goebbels, not from Himmler–but from you… You alone kept me from concluding that Germany had gone insane.
When judging the morality of Campbell, which of these people matter, the inner or outer person?
This is perhaps the main question posed by the book. Which person is you? Vonnegut explicitly states the moral of the story at the beginning: “We are what we pretend to be, so we must be careful about what we pretend to be.” You are the sum of all of your parts. The actions that you take as a means to accomplish something are as much a part of you as the something that is accomplished in the end. No matter the circumstances in which you find yourself, you still have to live with the actions that you take.
Campbell seems surprised by this concept when visited by his “Blue Fairy Godmother” (the man who recruited him as an American spy) long after the war. They are speaking about how only 3 people in the world knew that Campbell was a spy.
“Three people in the world knew me for what I was–” I said. “And all the rest–” I shrugged.
“They knew you for what you were, too,” he said abruptly.
“That wasn’t me,” I said, startled by his sharpness.
“Whoever it was… he was one of the most vicious sons of bitches who ever lived.”
No matter what his intentions, Campbell was a Nazi.
Campbell is a fitting main character to portray this moral. He is not quite a hero and not quite an antihero. He is a lucid protagonist who is neither ignorant nor insane. He knew what he was doing at all times and he realized that the orders he took were either ignorant or insane, and he did them anyway. He is a reminder that even in difficult times, we need to take our actions for what they are, and not what we hope they will be.
I recently had to access a web API through C Sharp that required a file upload. This is pretty easy if you have an HTML page with a form tag and you want a user to directly upload the file.
<form method="POST" action="http://localhost/" enctype="multipart/form-data"> File : <input type="file" name="content" size="38" /><br /> <input type="hidden" name="id" value='fileUpload' /> </form>
However, this is not always a reasonable path to take. Sometimes you may be wanting to access a file that is already in a system and you don’t want a new upload. If you are accessing an external API, this is probably always the case. Unfortunately, building this post using C# is not quite as straightforward. I first tried using the WebClient UploadFile method, but it didn’t fit my needs because I wanted to upload form values (id, filename, other API specific parameters) in addition to just a file.
So, I needed to roll my own form post. Here is the Multipart Form RFC and the W3C Specification for multipart/form data. After reading these links and searching some forums, here is what I came up with.
Note: If anyone is interested in this code in Visual Basic, reader Mike Ferreira converted the code into VB.Net in a comment below.
public static class FormUpload { private static readonly Encoding encoding = Encoding.UTF8; public static HttpWebResponse MultipartFormDataPost(string postUrl, string userAgent, Dictionary<string, object> postParameters) { string formDataBoundary = "-----------------------------28947758029299"; string contentType = "multipart/form-data; boundary=" + formDataBoundary; byte[] formData = GetMultipartFormData(postParameters, formDataBoundary); return PostForm(postUrl, userAgent, contentType, formData); } private static HttpWebResponse PostForm(string postUrl, string userAgent, string contentType, byte[] formData) { HttpWebRequest request = WebRequest.Create(postUrl) as HttpWebRequest; if (request == null) { throw new NullReferenceException("request is not a http request"); } // Set up the request properties request.Method = "POST"; request.ContentType = contentType; request.UserAgent = userAgent; request.CookieContainer = new CookieContainer(); request.ContentLength = formData.Length; // We need to count how many bytes we're sending. using (Stream requestStream = request.GetRequestStream()) { // Push it out there requestStream.Write(formData, 0, formData.Length); requestStream.Close(); } return request.GetResponse() as HttpWebResponse; } private static byte[] GetMultipartFormData(Dictionary<string, object> postParameters, string boundary) { Stream formDataStream = new System.IO.MemoryStream(); foreach (var param in postParameters) { if (param.Value is FileParameter) { FileParameter fileToUpload = (FileParameter)param.Value; // Add just the first part of this param, since we will write the file data directly to the Stream string header = string.Format("--{0}\r\nContent-Disposition: form-data; name=\"{1}\"; filename=\"{2}\";\r\nContent-Type: {3}\r\n\r\n", boundary, param.Key, fileToUpload.FileName ?? param.Key, fileToUpload.ContentType ?? "application/octet-stream"); formDataStream.Write(encoding.GetBytes(header), 0, header.Length); // Write the file data directly to the Stream, rather than serializing it to a string. formDataStream.Write(fileToUpload.File, 0, fileToUpload.File.Length); // Thanks to feedback from commenters, add a CRLF to allow multiple files to be uploaded formDataStream.Write(encoding.GetBytes("\r\n"), 0, 2); } else { string postData = string.Format("--{0}\r\nContent-Disposition: form-data; name=\"{1}\"\r\n\r\n{2}\r\n", boundary, param.Key, param.Value); formDataStream.Write(encoding.GetBytes(postData), 0, postData.Length); } } // Add the end of the request string footer = "\r\n--" + boundary + "--\r\n"; formDataStream.Write(encoding.GetBytes(footer), 0, footer.Length); // Dump the Stream into a byte[] formDataStream.Position = 0; byte[] formData = new byte[formDataStream.Length]; formDataStream.Read(formData, 0, formData.Length); formDataStream.Close(); return formData; } public class FileParameter { public byte[] File { get; set; } public string FileName { get; set; } public string ContentType { get; set; } public FileParameter(byte[] file) : this(file, null) { } public FileParameter(byte[] file, string filename) : this(file, filename, null) { } public FileParameter(byte[] file, string filename, string contenttype) { File = file; FileName = filename; ContentType = contenttype; } } }
Here is the code to call the MultipartFormDataPost function with multiple parameters, including a file.
// Read file data FileStream fs = new FileStream("c:\\people.doc", FileMode.Open, FileAccess.Read); byte[] data = new byte[fs.Length]; fs.Read(data, 0, data.Length); fs.Close(); // Generate post objects Dictionary<string, object> postParameters = new Dictionary<string, object>(); postParameters.Add("filename", "People.doc"); postParameters.Add("fileformat", "doc"); postParameters.Add("file", new FormUpload.FileParameter(data, "People.doc", "application/msword")); // Create request and receive response string postURL = "http://localhost"; string userAgent = "Someone"; HttpWebResponse webResponse = FormUpload.MultipartFormDataPost(postURL, userAgent, postParameters); // Process response StreamReader responseReader = new StreamReader(webResponse.GetResponseStream()); string fullResponse = responseReader.ReadToEnd(); webResponse.Close(); Response.Write(fullResponse);
Hopefully this code can help someone, figuring out exactly where to place the boundary and newlines in between form key-value pairs caused a little bit of grief during development. This is some functionality that would be really nice inside of the language library, but it seems like in most languages this is something you end up coding yourself.