del

We've come a long way, baby

Way back in the '80s I took a couple of high school computer programming classes. They were taught using old Apple II computers and BASIC. Even though I was a total n00b and had no prior exposure to other computing platforms or environments, I intuitively knew that the whole process of writing software on those machines was really complicated and awful. Just to print out some text, write branching constructs, and do simple loops meant jumping through all kinds of syntactic loops.

To enter a BASIC program in Apple's DOS you'd have to literally type the program at the DOS prompt, entering each line of code into the computer's memory, complete with line numbers. If you needed to change the program you could LIST it out to the screen and retype the code lines but there was really no editing in the modern sense:

In the above Virtual ][ screenshot I entered a two line Applesoft BASIC program that simply prints the string "HELLO, WORLD." To make sure my program was actually there I LIST'ed my two lines of source code to the screen. I then decided to change the "HELLO, WORLD" string to "HELLO, APPLE II HERE" by retyping that line. Finally, I LISTed the modified program and ran it. As expected, the string "HELLO, APPLE II HERE" appeared on the console.

Archaic, huh? But in a nostalgic sort of way it's kinda cool nonetheless.

For simple programs it was okay but it got unwieldy for really big BASIC programs. And god help you if you needed to insert more lines of code than you had numbers for, i.e. you needed to insert six new lines of code between lines 5 and 10 of your program. There were programs you could use to redo the line numbers in your program but it still sucked.

The editing environment was bad but the BASIC language at that time was simply awful. Whereas in modern Visual Basic.NET you can do something like this

        For counter As Integer = 1 To 10
            If counter Mod 2 = 0 Then
                Console.WriteLine(counter & " EVEN")
            Else
                Console.WriteLine(counter & " ODD")
            End If
        Next

in Applesoft BASIC you had to do this:

        10 FOR C = 1 TO 10 STEP 1
        20 LET R = C = INT (C / 2) * 2
        30 IF R = 0 THEN PRINT C,"EVEN": GOTO 50
        40 IF R = 1 THEN PRINT C,"ODD": GOTO 50
        50 NEXT C
        60 END

Yuck.

They do the same thing (print if an integer between 1 and 10 is odd or even) and in about the same number of source lines but one is a whole lot more readable. Note the lack of a Modulus operator in the Applesoft version!

It gets worse. If you wanted to interface with the operating system - what little there was of it - then you had to resort to PEEK'ing and POKE'ing values into and out of arcane memory locations. Any non-trivial program's source code would be littered with hardcoded memory locations, making them all but impossible to understand. So, in one sense you were working in a high level language (BASIC) but if you needed to do anything with the machine then you immediately found yourself working very close to the "metal" as they say.

Fortunately, back in the later half of the '80s our programming teacher must've realized that learning the guts of a decade old personal computer was a pointless waste of time and I never learned what all those PEEK and POKE addresses were for. I suspect that the only reason we were still using Apple IIs and not IBM PCs was budgetary problems. The school probably got a big technology grant a few years before and someone filled the classroom full of good old Apple IIs.

Okay, so that's your trip down memory lane for this Sunday morning.

Making change in Lisp

In case you were waiting with bated breath for a Common Lisp version of the greedy recursive change-maker program, here it is:

;; Recursive greedy change-maker
(defun make-change (amount coins)
  (if (null coins)
      (format t "~%") ; hit bottom
      (let ((times (floor (/ amount (car coins)))))
        (if (eql 0 times)
            (make-change amount (cdr coins))
            (progn
              (format t "~A (~A) " times (car coins))
              (make-change (- amount (* times (car coins))) (cdr coins)))))))

If you load it into your Common Lisp (I use AquaMacs, SBCL, and SLIME) and run it you should get something like this:

CL-USER> (make-change 123 '(25 10 5 1))
4 (25) 2 (10) 3 (1) 
NIL

This means that is takes 4 quarters, 2 dimes, and 3 pennies to make change for $1.23 (the 123 in the parameter list for make-change).

You can make up your own coin denominations in this version simply by fooling around with the list of coins you pass in. For example, if you're from a country with 79, 18, 11, 7, and 1-cent denominated coins you can run:

CL-USER> (make-change 123 '(79 18 11 7 1))
1 (79) 2 (18) 1 (7) 1 (1) 
NIL

and get some odd-looking but correct counts back.

What's your hobby language?

So what's your "hobby" language? Do you have one? Or are you a "one computer language" sort of programmer?

For me that language is Perl. When I'm poking around with programming ideas or building one-off scripts for use on my Macs I always seem to turn to Perl. I know the language well enough to get most things done without too much hair-pulling and there's an active community to turn to for help if I get in over my head. And it runs on all the platforms I have access to.

Unfortunately, I don't get to write much Perl code at work anymore as most of what we're doing is Windows-only and PowerShell is the scripting language du joir at the moment. Personally, I have a love-hate relationship with PowerShell: I love having access to the .NET framework from a scripting language but I (really) hate its lame error handling and plethora of bugs and nonsense that's par for the course in a version 1.0 product. At least in its current state it's no Perl.

But I digress.

So what makes a good hobby language for those fun little projects we do in our spare time? I think the following might be a good place to start when selecting a hobby language:

• Should be powerful and expressive enough to actually accomplish what we want.
• Language-specific concepts and syntax should be easy to learn and easy to remember. Most hobby projects are done during spare time so fighting the language is a waste.
• There must be a reasonably active Internet community to turn to for support.
• Ideally will be open-source or at least available in a "free" version.
• You should have some interest in it.

If you're a programmer by trade you'll probably be tempted to just use whatever language and/or environment you're using at work. I think this is a mistake for a couple of reasons. First, who the hell wants to spend their free time essentially working in the same environment as they do for 8+ hours a day during the workweek? And secondly - and most importantly - your chances for learning something new are reduced.

So I'll go out on a limb here and state bluntly that your hobby language:

• Must be significantly different from what you use at your day job.

If you're a Visual C++ programmer then you probably shouldn't be tinkering and playing in any of the Microsoft languages. Select something like Perl, Ruby, or JavaScript. Anything that breaks you out of the .NET environment. And if you're a Linux/Unix guy at work then by all means, bring up a Windows machine at home and get cracking with Visual Studio and any of the CLR-based languages it offers. The idea here is to learn something new, work in something different, and above all, have fun!

Greedy recursive change-maker

After a little more thought I cooked up another version of the recursive change-making program. This one uses a greedy algorithm to always try to use the largest possible denomination of coins while making change. The end result is very similar to how humans make change.

Here's the Perl code:

#!/usr/bin/perl
use strict;
use POSIX;

# Coin denominations

my @allcoins = (100, 50, 25, 10, 5, 1);

sub makechange {
 my $remainder = shift @_;
 my @coins = @{ shift @_ };

 # If we've exhausted the list of coins then bail
 if ( $#coins == -1 ) {
 print "\n";
 return;
 }

 # How many of the next element of the coins array

 # will fit?


 my $coin = shift @coins;
 my $times = floor($remainder / $coin);

 if ( $times == 0 ) {
 # This coin won't fit.
 # Try next lower denomination
 &makechange($remainder, \@coins);
 }
 else {
 # The coin fits at least once.
 printf( "%d (%.2f) ", $times, $coin / 100 );

 # Recurse down to the next lower denomination
 &makechange($remainder - $times * $coin, \@coins);
 }
}

#####
# Make change for some amount entered on the command
# line.

my $change = $ARGV[0] * 100.00;
&makechange($change, \@allcoins);

Save the code out to a file and run it like this:

% perl r_greedy.pl 45.20
45 (1.00) 2 (0.10)

The output means it would use 45 silver dollars and 2 dimes to make change for $45.20. If you don't like the idea of it using silver dollars and fifty-cent pieces then shorten the @allcoins array to (25, 10, 5, 1) and it will only use quarters, dimes, nickels, and pennies.

% perl r_greedy.pl 18.39
73 (0.25) 1 (0.10) 4 (0.01)

To make change for $18.39 it would use 73 quarters, 1 dime, and 4 pennies. That's quite a pocket full of change!

[Edit: finally figured out how to post source code through TypePad.]

Recursive change-making

In my previous post I said I'd produce a recursive version of the change-making program. After spending a couple of lunch-hours experimenting with it I came up with this bit of Perl code:

#!/usr/bin/perl
use strict;

# Coin denominations
my @coins = (100, 50, 25, 10, 5, 1);

sub a_total {
  my $total = 0;
  foreach my $coin (@_) { $total += $coin; }
  return $total;
}

sub makechange {
  my $change = shift @_;
  my @solution =  @{ shift @_ };
  my $total = &a_total(@solution);

  # If we've found a solution then print it
  if ( $total == $change ) {
    print join(',', @solution) ."\n";
    return;
  }
 
  # Try each coin to see if it'll fit
  foreach my $coin (@coins) {
    # Don't use coins that push our total
    # over the amount we're making change
    # for.
    if ( ($coin + $total) <= $change ) {
      # Make a copy of the solution so far and
      # recurse down.
      my @tsolution = @solution;
      push @tsolution, $coin;
      &makechange( $change, \@tsolution);
    }
  }
}

# Make change for $1
&makechange(100, []);

The recursive version of the program uses two functions, one called a_total() that adds up the coin values of a potential solution and returns the total and the recursive change-maker function, makechange(). The program works by iterating through each type of coin (silver dollar through penny), subtracting that coin from the running total, and recursively calling itself against the remainder until it reaches zero (i.e. no remainder left), after which it's found a solution. If it can find no more coins that'll fit then the recursion stops and it bounces back up one level.

The code is somewhat easier to read than the iterative version but the solution space it builds is incorrect. Here is a sample of the first few lines of output:

100
50,50
50,25,25
50,25,10,10,5
50,25,10,10,1,1,1,1,1
50,25,10,5,10
50,25,10,5,5,5
50,25,10,5,5,1,1,1,1,1
50,25,10,5,1,5,1,1,1,1

Can you see the problem?

The program starts out by finding several very good solutions (single silver dollar (100¢), couple of half-dollar pieces, etc) but then begins spitting out permutations of essentially the same solutions. For example, it gives us 50,25,10,10,5 and 50,25,10,5,10 which are pretty much the same save for the ordering of the coins. This is technically correct but not useful for our purposes.

The reason the recursive version doesn't work the way we expect is because each successively deeper function call has no idea what went on in other branches so it can't prune the solution tree. The iterative for-loop-based version doesn't have to worry about that as there is no recursion.

We could fix this version using a global array to check possible solutions against but we'd still need to generate all those permutations, and that turns out to be an excessively expensive operation. We'll stick with iterative version, thank you very much!

Brother, can you spare some change?

The other day when I was at the local grocery store I paid for some stuff with cash and one of those change-making machines clicked out a couple of quarters and a few pennies as change. I've done this many times over the course of my life and never thought much about it. But this time was different. For some reason it struck me that that change-maker was actually a pretty intelligent device. Not only do these machine need to make change quickly and accurately but they need to do it in such a way that store customers don't leave with their pockets bulging with pennies when a couple of quarters would work just as well. In other words, they're not just blindly spitting out the first solution they find but are actually looking for an optimal solution to a difficult real-world problem.

A search on the google quickly confirmed my suspicion that making change intelligently and optimally is no easy task. See the side bar on the Wikipedia article on Greedy Algorithms article. To find the best possible solution requires dynamic programming and an exhaustive search of the entire solution space. By solution space I mean all possible combinations of coins that add up to our desired total. So, for example, if you're making change for $1 then that solution space contains 293 combinations, assuming you are using the six currently circulating U.S. coins (silver dollars, half dollars, quarters, dimes, nickels, and pennies). The solution space will be smaller if you're looking to make change for values less than a dollar (i.e. 54¢) or if you don't allow certain coins like the silver dollar or half dollar.

Like a lot of computer science problems, generating all the possible combinations of U.S. coins that add up to some value can be done in two ways: iteratively and recursively. For this post I'll go with the iterative method because it's slightly easier to understand. In a later post I'll switch to a recursive version for readability and code succinctness.

Here's some Perl code you can use to iteratively print out the complete $1 change-making solution space:

#!/usr/bin/perl
use strict;

my $change = 100; # 1$ = 100 pennies

for (my $sd=0; ($sd*100) <= $change; $sd++) { 
  for (my $hd=0; ($hd*50) <= ($change - $sd * 100); $hd++) {
    for (my $q=0; ($q*25) <= ($change - $sd * 100 - $hd * 50); $q++) {
      for (my $d=0; ($d*10) <= ($change - $sd * 100 - $hd * 50 - $q * 25); $d++) {
        for (my $n=0; ($n*5) <= ($change - $sd * 100 - $hd * 50 - $q * 25 - $d * 10 ); $n++) {
          printf("%d Silver Dollars, %d Half Dollars, %d Quarters, %d Dimes, %d Nickels, %d Pennies\n",
                 $sd, $hd, $q, $d, $n, ($change - $sd * 100 - $hd * 50 - $q * 25 - $d * 10  - $n * 5) );
        }
      }
    }
  }
}

[TypePad clipped the longest lines off but if you select the code with your mouse and paste it into a text editor it's not actually gone; it just looks that way. ]

As you can see, the code is nothing but five nested for-loop statements, each one corresponding to successively smaller coin denominations. Each nested for-loop simply computes the combinations of coins needed to add up to the remainder of the previous loop's running total. By the way, that last sentence should clue you in to the recursive solution to this problem.

If you paste the code into a source code file and run it through Perl you'll get 293 lines similar to this:

0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 0 Nickels, 100 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 1 Nickels, 95 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 2 Nickels, 90 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 3 Nickels, 85 Pennies
0 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 4 Nickels, 80 Pennies
...
1 Silver Dollars, 0 Half Dollars, 0 Quarters, 0 Dimes, 0 Nickels, 0 Pennies

On my 2.4GHz iMac this code takes about 10 milliseconds to run. That's really fast.

If you want to compute the solution space for values other than $1 then simply modify the value of $change in the third line from 100 (100 pennies) to something else, like say 54 (i.e. 54¢). Doing that yields a much smaller solution space of 50 combinations. Conversely, boosting it up to a larger value like 1,000 ($10), gives us a significantly larger solution space of 2.1 million combinations. Taking it up to $20 (2,000 pennies) bloats the solution space to over 53 million possible combinations. $30 has about 380 million combinations and $50 has 4.5 billion combinations. That last $50 run kept my iMac busy for almost 35 minutes while it crunched through all those coins.

My point here is to show how quickly the solution space for something seemingly simple like making change can grow. Exhaustively searching through all those combinations for a good solution is not going to cut it when you start adding domain-specific constraints like differing numbers of available coins, scarcity of available coins with which to dispense change, random change-making values, unknown daily transaction volumes, etc.

In my next post we'll switch to a recursive change-making program, add some constraints, and get "greedy" to help cut down on the search space.

WinTVCap Scheduler 1.0.6

Out of the blue I got a request for an old software app that I wrote a couple of years ago. For some reason it didn't get moved over when I switched from my old homepage to this blog. It's called WinTVCap Scheduler and is good if you have one of the supported Hauppauge capture cards and don't want to bother with a heavyweight TV recording suite like Windows Media Center. It's getting kind of crufty but some folks still find it useful.

WinTVCap Scheduler 1.0.6

So I'm NOT an Unprofessional Hack After All?

Paul Graham has an interesting essay on his website on Holding a Program In One's Head. Paul is one of my favorite essayists and his writings on Lisp and other programming topics are most excellent. If you're a programmer I highly recommend that you go check out Paul's writings.

Anyway, the first few paragraphs of his latest article basically sums up the way I write software:

A good programmer working intensively on his own code can hold it in his mind the way a mathematician holds a problem he's working on. Mathematicians don't answer questions by working them out on paper the way schoolchildren are taught to. They do more in their heads: they try to understand a problem space well enough that they can walk around it the way you can walk around the memory of the house you grew up in. At its best programming is the same. You hold the whole program in your head, and you can manipulate it at will.

That's particularly valuable at the start of a project, because initially the most important thing is to be able to change what you're doing. Not just to solve the problem in a different way, but to change the problem you're solving.

Your code is your understanding of the problem you're exploring. So it's only when you have your code in your head that you really understand the problem.

Most of the problems I'm tasked with aren't so large that one programmer working alone can't solve them. And if they are large I usually get plenty of time to work on them so I can tinker with the code for however long it takes. I guess I'm lucky in that respect; a lot of programmers work in the high-tech equivalent of sweatshops.

When I write software I start with the problem, envision how a solution to the problem might work, and then start coding it from both the top and the bottom. I write high level functions and classes that simulate the desired problem solution and then iteratively flesh them out from the lowest, most specific levels towards the top level stuff. Data structures and classes get written somewhere in there and evolve over time as I translate the amorphous proto-solution held in my imagination toward the final code running in silicon. The low level functions become a sort of meta-programming-language for the higher stuff. Through experience I've learned that that's the best way to protect yourself from shifting design requirements and gives you agility as you get closer to a finished product.

I've always thought of this loose "by the seat of the pants" software engineering methodology as a kind of "crystallization" process. I've also always thought it was wrong to do it this way. Not having the program pre-planned out in flow charts, use case diagrams, and Visio UML documents to the n-th degree before implementing seemed like an unprofessional, hack-ish way of building software. Yet, none of the projects I've worked on where I did this failed. The ones where I tried to plan everything out using something like waterfall or the horribly brain-damaged and totally un-fun MSF (Microsoft Solutions Framework) were either stillborn or the time spent in the envisioning and specifications phases turned out to be wasted because the requirements shifted later. The hard, inflexible designs were brittle and couldn't adapt to even the smallest changes.

So I feel a little better about using this sort of software engineering methodology. I mean, if someone as smart as Paul Graham says this is how geniuses work, who am I to doubt it? Hah hah. However, I do realize that it probably wouldn't work in a situation where you had to work in a large team or the project was so complex a single programmer couldn't understand the solution completely. Those multi-million-line banking software projects or air traffic control systems come to mind. Although, even in those situations I bet you could still have the lone genius forging ahead; he'd just have to be positioned higher up the leadership chain. As long as they could clearly enunciate their desires to the programmers working under them it'd still work.

The Making of "Desert Labyrinth"

In my other two maze postings I was concentrating on generating the maze and getting it to work in various web browsers. First I developed the maze in Perl and then I ported the Perl to client-side JavaScript. The JavaScript version enabled you to view the maze inside your browser. While functional the appearance of the final maze was somewhat boring. I decided that something needed to be done about that.

So without further ado I give you Desert Labyrinth, the product of about 25 hours of tinkering:

This new version of the maze offers an isometric 3D view of the labyrinth as it would appear centered around the viewer. Go walk around the maze for a while and when you get bored (mazes really are quite boring unless you're actually trapped inside one and then they're pretty freaking scary!) come back here and I'll explain how I made it.

Back already? Okay!

Building the Maze

The maze itself is generated using a slightly modified version of the previous JavaScript code (ain't code reuse grand?!). The 3D view is a complex aggregation of HTML DIVs, CSS z-order layering, and a whole bunch of GIF background images with transparency settings applied to them. Each wall, shadow, and character view was painstakingly rendered in LightWave 7.5d into its own .GIF file, cropped, given transparency attributes, placed in an HTML DIV tag, and then positioned and layered with CSS. There are actually about a hundred individual images in all.

I used three different pieces of software:

• LightWave 7.5 for 3D rendering
• PaintShop Pro 8 for image editing and cropping
• Macromedia Dreamweaver 8 for HTML editing

Rendering with LightWave

Here's a screen shot I took of LightWave while I was laying out the labyrinth in 3D space:

Of course, I wasn't able to render the scene all at once like you see in the screen shot. The process of rendering in LightWave actually went something like this:

For every wall segment visible to the camera:

• Hide everything but the ground plane.
• Render the wall segment's shadow falling on the ground plane.
• Hide the ground.
• Make the wall segment visible and render it.
• If another wall segment's shadow could fall across the current wall segment then turn on that segment's shadow and render the current segment again with the other wall's shadow falling across it.

Depending on where the wall segment was located in the view port you need to render at least 2 views of it, one with shadows on it, one without.

Yes, it was tedious. And no, I wouldn't want to do it again unless I was being paid to do so. Once I realized how much work was involved it was only a grim sort of "I want this thing done!" persistence that enabled me to finish.

Pay No Attention to the Man Behind the Curtain

As you move through the maze and the wall configuration around the viewer changes the JavaScript code modifies the visibility and background image properties of the DIVs appropriately. This creates the illusion of a 3D environment. If you outline block-level elements in FireFox you can see that it's really just smoke and mirrors:

Other than the original LightWave rendering process no actual 3D is going on here.

Layering the Wall Segments and Shadows

Layering the DIVs is easy. You simply do something like this:

<style type="text/css">

#x02y02_twall {
    position:absolute;
    left:5px;
    top:0px;
    width:94px;
    height:50px;
    background-image: url(images/x02y02_twall.gif);
    visibility: hidden;
    z-index:3;
}

</style>

blah blah blah

<div id="x02y02_twall"></div>

The most import part is getting the CSS absolute positioning coordinates correct so the GIF is shown at the right place in the view port. If you misplace it the wall will be shown in the wrong area. If you're lucky the misplaced wall segment will obviously be out of place because it's perspective will be "off". If you're NOT lucky then it'll be moved by only a pixel or two and ten DIVS down the road you'll be wondering why the walls don't quite match up.

Only slightly less important is getting the layering correct. The DIVs must be "stacked" atop each other in a three-dimensional "back to front" order. This require some 3D thinking but LightWave has a great measuring tool that can help with that. For example, to get the walls to display correctly you must first draw the flat ground at layer zero so it will be drawn below all the other layers:

Then, on top of the ground, beginning at z-order one, you start stacking the shadow DIVs. The "back to front" layering ensures that any overlapping shadows fall across each other properly:

 

(Sorry about the poor JPEG compression on the above pop-up images. I was trying to save space on TypePad and set the compression too high. The images below are slightly better.)

You then place the character's shadow on top of the wall shadows:

Once all the shadows are visible you enable the wall at the top of the cell, taking into account the wall to its immediate left and choosing either the shadowed or non-shadowed version of it:

Then, you turn on the character, selecting one of the four different versions based on the direction he is facing:

And finally, you enable the rest of the walls and the illusion of a complete 3D maze cell is complete:

Of course, this is somewhat oversimplified because it only takes into account the walls immediately around the character. A labyrinth with only four walls is not really a maze at all: it's a prison cell!

To reiterate: the important thing is to work from the back of the scene towards the camera layering stuff on top of each other. If you do it right the "close" stuff will cover the "far" stuff, giving a convincing illusion of depth. Transparency settings in the "close" GIF files allows lower images to show through in the right places.

It's Not Perfect

There were several "gotchas" that I ran into while developing this:

1. Because the wall segments (and wall shadows) are separate entities and must be displayed (or not displayed) individually based on the maze configuration, it is vitally important that they NOT overlap in 3D space. When I was positioning the walls in LightWave I just started out by building one room centered around the character and then just sort of expanded into the other rooms, not being especially careful on how the walls fit together.
   
   I didn't think doing it this way would be a problem because after all, we're just re-creating the LightWave scene in a browser using DIVs. As long as it looks good in LightWave it'll look good in HTML. Right?
   
   Wrong!
   
   Later (much later), when it came time to start drawing random wall sections I ran into  problems with the walls not fitting together seamlessly. You can see the results of the overlapping walls in the strange seams, "floating" walls, and poor joins at some of the corners.  Ideally, the wall segments should NEVER touch in 3D-space, and smooth, 90-degree corners accomplished through corner "patch" GIFs that would hide the places where the walls meet. This, of course, would've added additional renderings to the project and increased the complexity of the display code.
2. Transparency in the GIF format is imperfect and will lead to "halo"-like effects if the transparency color is too different from the overall image average. I was using a bright Red color at first and noticed a slight 1-pixel red halo. Fixing it required changing the transparency color to a closer-to-average color. For the images in this project that was a soft, golden brown color. There are still a few visual glitches but you don't really notice them unless you know they're there.
   
   It's possible that using a more advanced image format like PNG would've solved some of this. But after doing some test renderings I realized that using PNG was out of the question because the resulting image file sizes were just too large. Using PNG would've increased bandwidth requirements by at least an order of magnitude.
3. My camera view was too large and encompassed too wide a field of view. By moving the camera slightly closer to the character I could've eliminated the need to render about 10 walls from the project. Also, by zooming in a bit, there would be no need to keep track of such a large number of wall segments and the JavaScript display code could've been simpler.
   
   An interesting phenomenon related to this is that if a wall segment (even if it's just a tiny "sliver" barely visible at the extreme top of the view port) is missing, your eye will fixate on it immediately. You may not realize exactly what's wrong but you'll still know that something is "off" with what you're looking at. There were several tiny "slivers" of off-the-map walls that I ended up rendering to stop this.
4. The Safari browser on the Macintosh seems to have trouble with the maze generation code. Since I don't have access to a Mac I can't troubleshoot the problem an further. Unless some kind soul driving a Macintosh can test it out and tell me where in the JavaScript code it's blowing up there isn't much I can do about it.

Of the "gotchas" the most serious by far is the slightly overlapping walls. Making that "right" would require re-rendering everything and basically amounts to starting over from scratch. Unfortunately I didn't realize the overlap was going to be a problem until I was already 10 hours deep and I sure wasn't about to start over. Rather than scrap the project I decided to just keep plugging ahead and see what happened. The result, while not perfect, is "good enough" for a hobby project.

It's Not Really a Game - It's a Technology Demonstration

I'll close with an apology of sorts. When I show Desert Labyrinth to others the first thing they ask is invariably some disappointed variant of:

"Where are the monsters?"

You're probably wondering the same. The only person so far that hasn't reacted that way was a web-developer friend of mine who immediately began asking questions about how I did it and how it works. Almost everyone else needed to have the significance of Desert Labyrinth explained to them.

So for those that haven't figured it out yet and were about to post a comment asking where are the monsters? I will clarify what the point behind Desert Labyrinth is. Despite the 3D veneer it is NOT a game and was never meant to be. It's main purpose grew out of my desire to learn CSS and client-side JavaScript, not to write the next great web-game. So if you were expecting Doom 3 then you're probably disappointed. Then again, if you got this far in this posting hoping for some hack-n-slash, then you've got other problems.

With that in mind, I may eventually add some game-like aspects to Desert Labyrinth. But for now my motivation to continue working on maze-based projects is flagging so don't expect anything soon.

Desert labyrinth

This post is for discussion of Desert Labyrinth, the culmination of my JavaScript maze generation project. Try it out and if you like it, post a comment here. If you don't like it, post a comment, too. Criticism is appreciated as long as it's constructive!

The object of Desert Labyrinth is simply to escape the maze. Use the glowing buttons (upper right side of the window) or use your keyboard's arrow keys to navigate. As you move through the maze the walls should update accordingly.

If you're hopelessly lost or feel like cheating click the compass button for an overhead map showing your current location. Click it again to hide the map.

The question mark button takes you here to this blog posting.

Couple of things:

Desert Labyrinth is based entirely around CSS, JavaScript, and XHTML. If you've disabled JavaScript or CSS in your browser than this isn't going to work for you. If it's just a jumble of images or nothing at all is happening it's likely that something is disabled or your browser doesn't support some feature I'm using.

Right now the maze doesn't work in the Safari browser on the Macintosh platform. I'm not sure why but I don't have access to a Mac for further testing. It should be fine in all Mozilla-based browsers (Firefox, Netscape), IE7, and Opera 9+. Other browsers that support modern versions of CSS and JavaScript should also work but no guarantees.

There are about 2.5MB's of image files required to display the maze in your browser. Depending on your bandwidth it may take a while for the maze to load. The wall segments load on-demand so until you've moved around the maze a bit you may notice some delays. Once everything is cached it should be snappy, though.

And finally, if you're interested in how I made Desert Labyrinth I have another blog posting discussing the maze in a more technical manner. Otherwise, have fun getting lost in the maze.