Navigating a Maze

My goal with my drawing program and moving icon programs is to be able to combine them so that the icons will treat the drawn lines as walls. This is my initial pass at that.

I started with the icon mover from last time which already had a Map class.  I added helper methods that will disconnect adjacent cells. breakCells to disconnect a cell from its neighbor and breakPoint to disconnect the two pairs of points that are diagonally touching at a point. breakCells takes a grid cell point, and breakPoint takes a lattice point. The relationship is that a grid cell has the same coordinates as the lattice point at its upper left corner.

  1 Map.prototype.breakCells = function(point, dir) {
  2   var cell = this.getCell(point);
  3   if (cell) cell.eraseEdge(dir); 
  4   cell = this.getAdjacentCell(point, dir);
  5   if (cell) cell.eraseEdge(dir.opposite());
  6 } 
  7 Map.prototype.breakPoint = function(point) {
  8   this.breakCells(point, Dir.NORTHWEST); 
  9   this.breakCells(point.delta(-1, 0), Dir.NORTHEAST); 
 10 }

The cell.eraseEdge just marks that edge as non-traversable so that it won't be included when the cell.getNeighbors call is made.

For this initial implementation I am sticking to the simpler case of just handling horizontal and vertical lines. I want to break apart any two cells that has a line that crosses between them and break any point that a line touches. I added a method breakGridLine which does this.

  1 Map.prototype.breakGridLine = function(line, dir, dx, dy){
  2   var p1 = line.p1; 
  3   while (!p1.eq(line.p2)) { 
  4     this.breakPoint(p1); 
  5     this.breakCells(p1, dir); 
  6     p1 = p1.delta(dx, dy); 
  7   } 
  8   this.breakPoint(line.p2); 
  9 }

dx and dy are the deltas that describe how to traverse the line and dir is the direction of the cells that are on the other side of the line.

Now I just added another method that loops over all the lines and breaks them apart.

  1 Map.prototype.breakLines = function(lines) {
  2   for (var i in lines) {
  3     var line = lines[i]; 
  4     if (line.slope.rise == 0) {
  5       this.breakGridLine(line, Dir.NORTH, 1, 0);
  6     } else if (line.slope.run == 0) {
  7       this.breakGridLine(line, Dir.WEST, 0, 1);
  8     } else { 
  9       // ignore diagonal lines for now 
 10     } 
 11   } 
 12 }

If we call this method with the lines from a drawn map, our existing BFS searching algorithm will now cause our icons to traverse the grid. Now its just a matter of calling the breakLines method when we start to move icons.

  1 IconControls.prototype.setLines = function(lines) {
  2   this.map = new Map(this.iconLayer.grid.width, this.iconLayer.grid.height);
  3   this.map.breakLines(lines); 
  4 }

And of course the HTML to add the buttons, etc, which I won't bore you with today. Anyway, here is the demo.

Demo

line rectangle erase line erase rectangle        

Why Are Web Frameworks So Bad

I debated what punctuation was appropriate for this post. Should it be a period because I this post will explain the answer? Should it be a question mark because I am trying to understand? Should it be an exclamation point because I am surprised? After a little bit of thought, I think it should be "Why are web frameworks so bad?!?!?!?!?!?!" because I want to rant!

Oh, and as a quick caveat, I am talking about the two environments that are primarily used in the business world today, i.e. .NET and Java.

ASP.NET

ASP.NET tries to just extend Windows Forms programming so that creating a web app is just like creating a desktop app. The promise being that the legion of Windows programmers will suddenly be able to create rich web apps without learning anything new. The reality - programming for the web has different constraints than programming for the desktop, and while ASP.NET tries to hide it reality leaks through. Any time you go off the beaten path you risk getting bitten. Unless you truly understand the seven stages of the page life-cycle, problems can arise like losing user input.

What It Gets Right
Code Behind
An ASP.NET page is actually two files.  There is the .aspx file which is where you put your HTML with a minimal amount of code.  The other file is the .aspx.cs file (assuming C#) which has specific methods that will be called prior to displaying the .aspx.  You can put the meat of your code in this C# file, and populate variables which can be used in the .aspx.  This makes for a good separation of concerns between coding and markup.

Components
It is also easy to create a custom ASP.NET component with its own markup (.ascx) and code behind (.ascx.cs) files.  These components can then be fairly easily embedded into your pages (or other components).  This works fairly well.

What It Gets Wrong
Wow - where to start.  I guess I'll limit myself to the three biggest complaints that I have.

Complexity
When you create a page in ASP.NET you are logically building a tree of Components. The HTML is generated by walking this tree. So far so good. The complication comes in that the HTML form variables that are posted back are specified and accessed via these components. So after the user performs an action, the webserver must be able to exactly recreate the Component tree from before so that your ASP code can access any user modified values. Recreating this tree is no trivial task, and while it just works most of the time, if you do something that causes it to break - understanding and tracking down your bugs can be a nightmare. And dynamically creating components based on user input is likely to cause this breakage unless you *really* understand what is going on. Ugh.

Doesn't fit the web model
ASP.NET really tries to mimic non web GUI programming. A .aspx page is a single Form containing lots of Components. What this translates to is a single HTML form that typically has all its buttons post back to the same page. So if you want to logically have different forms on your web page that go to different places, you can't do it. You can fake it, via redirects after the postback, but this is really a perversion of web semantics. Oh, plus the built in components that try to hide the fact that they really just turn into a <div> or an image tag or what not, don't give you full access to the HTML properties of those tags. i.e. ASP.NET forces (strongly encourages?) you to write web pages in a very specific way whether that makes sense for the end user or not.

Page Bloat
ASP.NET adds a hidden input variable called __VIEWSTATE to the pages it creates. This variable contains serialized data that is used after a post to help it recreate the Component tree exactly. This can be potentially quite large, which slows down page load time. Even though broadband is fairly common, many connections don't have a high upload speed, and this data is both downloaded and uploaded with every page view, often causing website to load slowly. To make matters worse, if you don't really understand how this variable is used (and you can create sites without even being aware of its existence), it is really easy to end up with a lot of extra data in this variable that isn't even needed.

Java

Java provides multiple option. First there were Servlets and JSPs, which are functional but often require you to mix your code and your mark up and write generally ugly code. To solve this a number of frameworks which either sit on top of or replace JSPs have come out like Struts, Facelets, JSF, and Seam. Seam is actually a framework that uses other frameworks, just in case this wasn't confusing enough.  For this conversation I'll be talking about Seam using Facelets since that is what I am currently playing with.

What It Gets Right
Hmm... Well, I guess these frameworks are much better than the original Servlet/JSP approach for separating HTML markup and code.

What It Gets Wrong
Again, I'll pick three complaints to highlight.

Dependency Injection Magic
In Seam you can use annotations to give a Name to your class.  You now have access to a variable of that name in the xhtml front end markup.  Some people would probably feel that this belongs in the "what it gets right" category, however I think it is too much magic for my taste.  When I am reading an xhtml file and I come across a variable, there is no easy way to know what it is.  I have to go to every class to find the one with the appropriate annotation.  This does not make for easy to understand code.

Too Many Config Files
Seam claims to have greatly improved the "too many config files" problem, but my current project has:

• components.xml
• faces-config.xml
• jboss-web.xml
• pages.xml
• web.xml
• Plus a page.xml file for every .xhtml page

As you've probably noticed, in addition to a lot of files every single one of these config files is in XML which means there is also a lot of extra verbosity.

Ugly Syntax
Do you remember back when you learned C?  You write printf("hello world\n"); inside a main and it doesn't compile.  Why not?  Oh, you need to tell the compiler to include the standard i/o library.  Pretty soon you just automatically put #include <stdio.h> at the top of all of your programs.  Similarly, with our facelet code we have includes so that we can have access to the special tags in our xhtml.  Here is an example of the concise and easy to remember way this is specified:

<ui:composition xmlns="http://www.w3.org/1999/xhtml"
  xmlns:ui="http://java.sun.com/jsf/facelets"
  xmlns:h="http://java.sun.com/jsf/html"
  xmlns:f="http://java.sun.com/jsf/core"
  xmlns:a="http://richfaces.org/a4j"
  xmlns:rich="http://richfaces.org/rich"
  xmlns:s="http://jboss.com/products/seam/taglib">

I don't think anything further needs to be said.

What Do I Want
This is probably a topic for a whole other post, but here are a couple quick thoughts.

• Simple and clear separation of code and markup so I can minimize the amount of code that is intermingled with html
• A library of useful existing components
• Easy to write my own html components
• Makes it easy to do the common web stuff (session management, cookies, parameter passing, url building, security precautions, etc.)
• Does NOT hide any aspects of the web, just SIMPLIFY it
• I want to know how and what parameters are passed
• I want to know how they go in/out of components libraries
• I want it to be easy to integrate components (e.g. javascript libraries) that were written without any knowledge of this framework.
• I want to be able to control the specific HTML that is generated.
• Good documentation - something Java does well is good JavaDoc documentation on the supplied system libraries.  I want my frameworks to have similar quality documentation.
• Is transparent about what it does, so when I have a bug I can easily find it by reading the aforementioned document, rather than having to do Google searches in the hope of finding a blog post or stackoverflow question which describes *and* answers my problem.

Breadth First Search for Moving Icons

While I can move icons around on a grid, they aren't really moving the way I want. For the app that I am envisioning, icons should only be allowed to move in the four cardinal directions and the four diagonals. This post is about how I enforce that, and about setting some things in place for future enhancements.

To help I've created a Map class and a Cell class. A map consists of a bunch of cells that are connected. The cells correspond to the squares in a grid that the icons are allowed to be and they are connected along the paths that they are allowed to move. Until I've added support for drawing walls, each cell is connected along the 8 directions around it. The exception, of course, are along the 4 edges where the cells are only connect to the cells that exist.

To calculate distance, I follow the D & D convention and round the diagonal from √2 to 1.5. But since I like integer arithmetic I make the four cardinal directions have a distance of 2 and the diagonals have a distance of 3. Now that I have a map, rather than just drawing a straight line from the start to the finish, I calculate the shortest legal path and make these moves.

  1 IconControls.prototype.click = function(x, y){
  2   var point = this.iconLayer.getGridPoint(x, y);
  3   var cell = this.map.getCell(point);
  4   var icon = this.iconLayer.findIcon(point);
  5   if (icon) { 
  6     this.activeIcon = icon; 
  7     this.lastCell = cell; 
  8   } else if (this.activeIcon) {
  9     var path = this.map.shortestPath(this.lastCell, cell);
 10     if (path) { 
 11       for (var i in path) {
 12         this.activeIcon.moveTo(path[i].point);
 13       } 
 14       this.lastCell = cell; 
 15     } else { 
 16       alert("destination is unreachable.");
 17     } 
 18   } 
 19 }

In the above code, lines 6-7 handle the case where you click on an icon and lines 9-17 move the icon. The shortestPath method call on line 9 returns a contiguous set of cells that comprise a path from start to finish, if one exists.  The loop in lines11-13 then moves the icon to each of these cells in turn.  Line 16 warns the user if no path exists.  This isn't possible yet, but will be once we start adding walls to our grid.

To calculate the shortest path, I set the destination cell as having a cost of 0 and all of the other cells as having a large cost. I now do a breadth first search from the destination to the source, recording the distance in each cell along the way.  I can now calculate the path from source to destination with a greedy algorithm.  Note that since the triangle inequality holds, the shortest path will have as few or few steps than any other path, and so a breadth first search is good enough and I don't need to use Djikstra's algorithm.  If, in the future, this condition does not hold, I will have to rewrite this code.

  1 Map.prototype.shortestPath = function(src, dest){
  2   for (var i in this.cells) {
  3     this.cells[i].cost = this.MAX_COST;
  4   } 
  5   dest.cost = 0; 
  6   var queue = new PriorityQueue();
  7   queue.push(dest, 0); 
  8   while (!queue.isEmpty()) { 
  9     var cell = queue.pop(); 
 10     if (cell == src) return this.createPath(src, dest);
 11     var choices = cell.getNeighbors(); 
 12     for (var i in choices) {
 13       var move = choices[i]; 
 14       var cost = cell.cost + move.cost; 
 15       if (cost >= move.cell.cost) continue;
 16       move.cell.cost = cost; 
 17       queue.push(move.cell, cost); 
 18     } 
 19   } 
 20   return null; // no such path
 21 }

Lines 2-7 initialize our state while line 8-19 is the main loop of the search. getNeighbors returns the list of valid neighbors of this cell and the cost to move there (2 for the cardinal directions, and 3 for the diagonals) and this list is sorted by cost.  On line 15 we check if the cost of moving to a cell from the current location is lower than any previously considered path.  If it is, we set the cost on line 16 so we won't try another path with the same cost and on line 17 we push that node into our priority queue of nodes to consider.  The createPath call on line 10 calculates the path using the stored cost in each cell.

  1 Map.prototype.createPath = function(src, dest){
  2   var list = [src]; 
  3   while (src != dest) { 
  4     var cost = this.MAX_COST;
  5     var next; 
  6     var moves = src.getNeighbors(); 
  7     for (var i in moves) {
  8       var cell = moves[i].cell; 
  9       if (cell.cost < cost) { 
 10         next = cell; 
 11         cost = cell.cost; 
 12       } 
 13     } 
 14     list.push(next); 
 15     src = next; 
 16   } 
 17   return list; 
 18 }

As describe above, this algorithm just greedily chooses nodes closer to the destination until it reaches the destination.  The loop in lines 7-13 makes the greedy calculation and it is added to the path on line 14.

Demo

This demo is just like the previous demo, except the icons will move only along the 8 main directions.  As before click an icon, click a destination, lather, rinse, and repeat.

Tell it to the Bear

In 1992, I was on a team that was one of the finalists for SuperQuest and we spent three weeks that summer at Reed College to work on our projects. While there, we were told a story about solving computer problems that has stuck with me.

Reed College's computer lab had a couple of TAs on hand so that students who were stuck on their programming assignments could get help. However, there was due diligence that you had to do first. Outside the TAs' office, there was a desk. On the desk was a teddy bear. Before you could go in to see the TA you had to explain your problem to the stuffed animal. Only if the bear couldn't solve your problem were you allowed to talk to the TA. Apparently they had one smart bear, as a good percentage of the students who talked to the bear never went on to the TA and sometimes there was a line to talk to the bear even when it was off hours and there were no TAs on duty.

On the surface this seems insane - how could a stuffed bear solve programming problems? And yet, I suspect many of you are nodding along and not surprised at all that this works. I have, on numerous occasions, when stuck, explained my problem to someone else, and figured out the solution before they even said anything to me. I have also been the bear for many other people, watching them solve their problem as they tell it to me.

it's a very specific way of thinkingSo why does this work so well? Obviously explaining your problem to anyone (anything) makes you stop and think. However, it is more than just random thinking, it's a very specific way of thinking.  You have to explain not just your solution, but the problem to the listener. This forced thinking through of the problem will often show a part of the problem that your incorrect solution is ignoring. You are also forced to be orderly, go over every part of the solution, and explain any shortcuts that you took and the assumptions made. Explaining your assumptions will often highlight errors and actually verbalizing the steps taken can show when steps are missing. The other thing that happens when you are talking, is it forces you to slow your thoughts down. This can sometimes be enough to pop you out of your rut and let your brain come up with a better idea.

So should we all have a teddy bear to have on our desk at work? I'll be honest, I am not sure I have the courage to have a conversation with a stuffed animal where coworkers could see and hear me. However, I think there is a business opportunity here. You could sell Answer Bears to organizations and then sell consulting services (at an outrageous rate, of course) to firms to set up the bear's desk, procedures for talking to the bear, etc. If you can make it the next technology fad, you'll get rich!  Until someone does this though, if you don't have anyone to talk through problems with, it is worth going through the steps as if you were.