Gerry

Gus Van Zant’s 2003 movie “Gerry” about two friends lost in the desert has elicited opinions from adoration to disdain to deep ambivalence.

As much as I loved this hauntingly beautiful film, it’s easy to see why many people find it devoid of any real substance. With little dialog and no real plot, it is more a meditation on nature’s sublime pitilessness; how it can strengthen the bond between friends, and ultimately crush it into irrelevancy.

There are moments of great subtlety—such as the faintest hint of a smile that briefly appears on Casey Affleck’s face during a long, close-in shot of their faces as they monotonously trudge across the xeriscape. Anyone who has been on a long and difficult journey with a close companion can identify with the feelings that seem to surface here: physical toil and mental fatigue can evoke a detachment that may bring sparks of joy at the recognition of a profound friendship or perhaps the ridiculousness of the entire situation.

The monastically spare music of the great Arvo Pärt and the cinematography of Harris Savides take on larger roles as the characters’ will begins to fade along with the already minimal dialog.

Large Maze Support

Okay, this has started to turn into a bit of an obsession. While making human-scale mazes was fine, generating ones that push the browser to its limits proved to require extensive rework of the code. The fundamental issue with the more basic code is that it absorbed all the resources of the browser and provided no feedback as to where it was in the generation process. Worse yet, browsers such as Firefox pop up modal dialog boxes warning that the script is unresponsive.

The current code is now limited only by the browser’s memory which allows for mazes on the scale of half a million cells or more—say 2500 rows by 200 columns on a reasonable-sized system.

Generator: here. Updated source: here.

The solution is to yield time back to the processor which is tricky with JavaScript since it doesn’t directly support such a mechanism universally. This required replacing the row and column iterators with a generalized loop counter with Continuation-passing style (CPS) support.

function iter(f, done, fc, fp)
{
    var max   = 50; // a reasonable number
    var count = 0;    

    /* a functor that manages calls to f() */
    var loop = function (state)
    {
        while((state = f(state)) != done)  {   
            if (count < max)  {
                count++;
            } 
            else  {
                count = 0;
                setTimeout(function() {loop(state)}, 0);
                break;
            }
        }
        
        if(fp) {
            fp(state, done);
        }
          
        if(fc && (state == done)) {
            setTimeout(function() {fc()}, 0);
        }
    }
    
    /* call the loop function with the initial state */
    loop(0);
}

The above code calls a function f(i) until it returns a result that indicates processing is complete. The value “state” passed to f() is the result of the previous call to f(). Every “max” iterations, processing is yielded to allow responsiveness.

f

a function that takes a state parameter and returns an updated state

done

the final state that indicates that iteration is complete

fc

an optional continuation function that is called when processing is complete

fp

an optional callback function used to indicate progress though the iteration

Maze Solver

This is entirely gratuitous, but I couldn’t let go of the maze generator without adding in the code that actually solved the maze also. The solution code uses the same depth-first search algorithm as the generator, leaving a trail of “breadcrumbs” as it goes and rolling them back up when it hits a dead-end.

Generator: here. Source code here.

As before, I was forced to use an iterative algorithm in place of the more natural recursive one because of browser limitations. The major difference in behavior between the solver and the generator is that I wanted the search path to be displayed dynamically on the screen as it worked through the solution.

The only major change from the generation code is that the outer while{} loop had to be replaced with a timer. Each iteration of the logical loop then is done on an interval, which gives the browser the chance to reflow the page. IE was the only browser with any real issues: for whatever reason it is very slow when solving the maze. I may take a look at that if I get the chance, but I think I’m done with this exercise for now.

Update: The issue with IE has been resolved.

Maze Generator

My son has been interested in mazes recently. This seemed like the perfect opportunity to show that I could actually do something useful on the computer (in his eyes), so I decided to put together a maze generator. Maze generation is actually relatively trivial and it is often one of the first examples of a recursive algorithm given to computer science students.

Generator: here. Main source code: here.

I’ve always found the idea of recursion magical in some way—its one of the things that really hooked me into programming.

I wanted something that would be rendered at the client using only standard HTML and CSS. This requires no server-side resources, demands no plug-ins and allows for the mazes to be printed out easily and with good quality.

This implementation uses a standard depth-first search algorithm. It’s one of the simplest, but has the benefit of generally creating the most difficult mazes.

I was able to put together the recursive function pretty quickly, but soon realized that the standard browsers all limit the depth of recursion they allow. Since tail-recursive algorithms can be reworked using iteration, I was forced to change things around to use that technique instead. An examination of the source code shows that this basically means the stack must be managed by hand instead of automatically.

Update: I recently added code to solve the maze also.

Update: Support for for very large mazes was added. While large mazes could be made previously, the browser would be unresponsive, and in some cases warning dialogs appeared stating that the script was taking too long. The code has been reworked to give time back to the processor, so this should not happen. Mazes are now limited only by available memory and the particular browser. In practice the limit is on the order of 200,000 to 500,000 total cells, say 1000 rows by 200 columns, etc.