Getting back to maze creation, I thought it might be interesting to create animations of the maze growing algorithms, as an aid to debugging and just for general coolness. The easiest way to do that is to save an animated GIF file, because those can be viewed in any web browser without any added software. The only problem is that I didn’t know how to do it. Google is your friend, however, and I found an example of how to create an animated GIF on the Java Forums.

The example has a problem. It animates a GIF of four frames by pulling in four images from the web, and it so happens that the links to those images are now dead. Consequently, you end up with a run-time error. Not to worry; I massaged the code so that it creates a number of small images in memory an animates those. Here’s my proof of concept:

Not fancy, but it works nicely.

Here’s yet another maze, produced by a method called recursive backtracking. Unlike the previous algorithm, which is something I came up with myself, this is a well-known algorithm with rather delightful properties, as you can see for yourself.

The algorithm is straightforward:

• Create a new, blank maze in which all cells are free. (A free cell is connected to no other cell). You can think of the free cells as square rooms with a closed door in each of the four walls.
• Initialize an empty stack of cells.
• Let C be a cell chosen randomly.
• Repeat:
  • If there is at least one free cell next to C,
    • Let D be a free cell next to C, chosen randomly.
    • Open a door from C to to D.
    • Push C onto the stack.
    • Let C = D.
  • Otherwise,
    • Pop an old C from the top of the stack.
• Until the stack is empty.

The maze shown above uses a slight variant called “inertia”, which makes it a little more likely that the next free cell chosen will be in the same direction as the previous. This makes the straight corridors just a little longer.

Like the previous algorithm, it produces a “dendritic” maze: one in which each cell is connected to every other cell by exactly one path. That’s cool if you’re printing the maze on a place mat, but a little boring if you’re using the maze in a game, so the next step is to take a maze like this and modify it in various ways.

For Mark Lambert, here’s a bigger maze with an entrance and an exit.

Kardde was curious how it was produced.

First, a maze is represented as a rectangular array of cells. Each cells is square, and has a wall on each side, and each wall has a door. When the algorithm begins, all of the doors are closed. The algorithm proceeds by judiciously opening doors into neighboring cells until all of the cells are reachable. A cell with all of its doors still closed is said to be “free”. Here’s the algorithm:

• First, create a maze in which all of the doors are closed.
• Pick a cell randomly, and add it to the list of growth candidates. (It will be the only entry.)
• While there is at least one cell in the list of growth candidates,
  • Take a cell, C, from the list of candidates.
  • Find any free cells adjacent to C (north, south, east, or west), and pick one randomly. Call it F. If there are none, continue with the next candidate cell.
  • Let D be the direction from C to F.
  • Randomly pick a number N, from 1 to 4.
  • Beginning at cell C, drive in direction D, opening doors into free cells, until you’ve reached the Nth room, or the edge of the map, or a cell that’s not free.
  • If there are still free cells left adjacent to C, add it to the list of candidates.
  • Add the last cell to the list of candidates.
• When no candidates remain, all cells are connected, and the maze is complete.

There are a number of things you can change about this. In particular, you can change how you pick the next candidate: the first entry, the second entry, a random entry, and so forth. Different choices will result in different looking mazes. Second, you can vary the number of steps to drive while opening cells. In the maze shown above, you drive up to four cells, random chosen from 1 to 4. Again, different numbers of cells make a difference. For example, suppose that instead of choosing a number from 1 to 4, I simply always choose 4:

As you’ll note, it looks quite a bit different.

Here is the first real maze produced by my new Java code. It’s not a great maze (there are better algorithms), but I learned a lot from doing it.

I’m a long time Tcl programmer; I can make Tcl sit up and beg. It’s been brought home to me, though, that the demand for making Tcl sit up and beg is low where I work. If funding were cut for my current project and I had to jump to another, my Tcl experience might not count for much. (One doesn’t always have the luxury of starting a new project and picking the infrastructure one wants.) Java, on the other hand, is widely used; and though I’ve done some work in Java it’s been around eight years. A Lot Can Happen in Eight Years, and in the case of Java it has. When I last used Java, it was Java 1.4 (or maybe even Java 1.3; I seem to recall that 1.4 was brand new). Java 6 is fairly standard today, and Java 7 is picking up steam.

I didn’t like Java 1.4 much, but Java 5 (i.e., Java 1.5; they dropped the “1.” around then) added a bunch of nifty new features that make the language much nicer to work with:

• Parameterized Types (i.e., Generics)
• A colllections library based on Generics
• Annotations
• Enum Classes
• Auto-boxing and unboxing

(And no, I’m not going to describe all of those.)

More than that, I did all of my work at the command line, using the Emacs editor; all the cool kids these days seem to be using this Integrated Development Environment called Eclipse. Seems that if I want to fit in on an existing project, I’d better learn that too. So that’s my new project for awhile: rediscovering Java and learning how to use Eclipse.

I don’t know how much I’ll blog about it, but I thought I’d show the fruits of my first morning’s work: an image rendered by a short Java program.

Some years ago I wrote a little old-school dungeon-crawling game called Ramble, and I put together some algorithms for creating random dungeon mazes. I’m thinking that I’ll try re-implementing some of those in Java, as a first project; and save the finished mazes as PNG images. Think of the above as the proof-of-concept: how to draw an image and save it to disk.

A friend once told me, “Will, you can go from 0 to Geek faster than anybody I know.” Let the reader beware.

I’m a software engineer by profession. That means that my number one tool, the tool I spend hours a day using, is a text editor. Not a word processor (though I use those, too), and not just any text editor; a programmer’s text editor. Notepad is a text editor, but comparing it to a programmer’s editor is like comparing a letter opener to a Leatherman tool.

Some programmers prefer to use an Integrated Development Environment (IDE), that combines a text editor with all sorts of ancillary tools, including the language compiler. But long-time programmers tend to have an old favorite, the editor of their youth, that not only does everything they need but which is graven into their very soul. IDEs come and go, but the classic programmer’s editors live on. Better to stick with the tried and true than to master one set of quirks after another.

My favorite editor, the one that I’ve used since the early 90’s, is Emacs. I’ve used Emacs on Windows PCs, on Mac OS X, and on a variety of flavors of Unix. One of the things I like about Emacs is that it’s the same on all these platforms. If its conventions are different from those of most other applications, it’s because it’s older than they are; and anyway, I’m used to its quirks. That said, getting Emacs to run on OS X has always been a bit of a chore. I’ve generally had to find the Emacs sources, download them, and build Emacs myself; and then, when I upgrade my OS, my build always breaks and I have to download it again. Some while back, though, the Free Software Foundation finally produced an OS X-native version of GNU Emacs: a genuine OS X application. When I upgraded to OS X Leopard, this was the version that was available, and I downloaded it. And yea, verily, it stanketh. All sorts of little things didn’t work quite right; and maddeningly, the cursor would occasionally leave ghost copies of itself as I moved around a text file. And because there was now an official GNU pre-release, the sources I’d relied on for Mac-specific build instructions had all dried up.

To be fair to the FSF folks, the OS X release was alpha software; but it was the only release of GNU Emacs that was available, and it was a real pain to use.

This past October, a little after I started working on Robbie the Robot, I began looking at alternatives. Now, there are other versions of Emacs, but I discounted these immediately. I could probably have found an OS X-specific version of Xemacs; but I’ve never liked Xemacs. There’s another version called Aquamacs, which makes Emacs look even more like a standard OS X application; but it changes the standard behavior to do so. My goal is to use one and the same editor on every platform I use; and I use Windows, Linux, and OS X. So that was out.

Next, since I use a lot of ActiveState software, I decided to try KomodoEdit, the free version of ActiveState’s Komodo IDE. It’s available on all three platforms, and is pretty much the same on all of them. I used it for the rest of October and most of November, and I have to say that there’s a lot to like about it. I got comfortable with it, once I got all my quirky preferences dialed in, and was quickly productive. I have to give the ActiveState guys credit; they nearly got me long-term. In the end, I abandoned KomodoEdit for three reasons:

• There are functions that I use regularly, such as incremental search, that are just slow enough to be annoying. I want my editor to be faster than I am.
• Most programmer’s editors let you remap the keystrokes to do what you want, and Komodo is no exception. In fact, I really like the interface it uses for this. But Emacs lets you change the keystrokes depending on what kind of file you’re editing. For every kind of programming language, you can have the precise tools you need at your finger tips. If Komodo can do this, it wasn’t obvious.
• Keystroke macros execute much more slowly than in Emacs (orders of magnitude more slowly!), and are buggy besides.

KomodoEdit worked for me most of the time; but there were times when I found myself falling back to Emacs because getting the job done in Komodo was just too painful.

So what next? Alas, there was one obvious choice remaining…a name I shudder to speak. For an Emacs user to even think about it is rather like Luke Skywalker going over to the Dark Side. Yes, it was time to take a look at….Vim!

For those of you who came in late, the two (2) (count ’em, two) classic programmer’s are Emacs and VI. (The names stand for “Editing Macros” and “Visual Interface”.) Both were written to convert editors designed for use on teletype machines into something that was more pleasant to use on a CRT screen. In doing so, they took radically different approaches. And both have evolved considerably since then, meeting the needs of successive generations of programmers. The classic “vi” is still available on pretty much every Unix system, but most “vi” programmers these days use ViM (VI iMproved), which is has considerably more functionality.

I’ve never been a “vi” user; I know just enough to some very simple editing and save a program. But it’s the preferred tool of millions of programmers, and perhaps it was time to take another look. Like Emacs, ViM is an old-school editor, proven on the field of battle; like Emacs, it’s available on every platform; and, as I quickly discovered, the OS X version is compatible with the versions on the other platforms, and stable to boot. So I spent the second have of November giving ViM a try.

Much though it pains me to say it, it’s a good tool. I was able to configure it to work the way I wanted, and I was able to be productive in it. I got it to work identically on Linux and on OS X. It had some quirks that I didn’t like; but Emacs has some quirks that I don’t like. I’m just used to them.

In the end, though, I returned to Emacs. Not because it’s as familiar as an old glove, surprisingly, but because ViM was becoming too familiar. How can that be, you say? As I mentioned above, Emacs and VI took very different approaches to managing a screen interface. And the plain, simple fact of the matter is, Emacs won. The applications that you non-programmer types use that involve editing text—word processors, especially, but also e-mail programs and so forth—owe a lot more to the Emacs-style of editing than to VI. In fact, I can remember a number of applications in days gone by that took a VI-like approach to text; does anyone remember the “Select” word-processor? Ultimately they all tanked.

The basic difference can be described as follows. In Emacs, as in almost every other application, typing a letter on the keyboard inserts that letter into your document. You move around using the arrow keys and so forth. You use control-keys, function keys, and menus to perform more complicated operations. In ViM, your keyboard is like a giant game-pad of editing functionality. Every key does something amazing and magical. If I type “%d” on a line containing a left-parenthesis, for example, ViM will select and delete everything from the left-parenthesis to the matching right-parenthesis, taken into account any nested parenthesis, quotations, and so forth. In order to actually input text, rather than edit it, I need to type “i” (or any of a dozen other key sequences), enter the text, and then press Escape to go back to command mode.

Frankly, this odd scheme works. It works well. Once you become fluent, you can accomplish amazing things with much less typing than in other editors. But! It doesn’t work in anything else, no matter how often you try. It is very disconcerting to be writing an e-mail, need to edit something you’ve typed, and have your fingers try to use the ViM commands to get the job done. Cognitive dissonance, they call it.

So I decided, somewhat reluctantly, to give ViM a pass. I gave up on having the same editor on all three platforms; I’d use KomodoEdit on the Mac, and Emacs everywhere else, and maybe someday the FSF guys would release a stable, non-stinky version of Emacs for OS X.

And so, last week, just before implementing this decision, I did a quick web-search—and, lo and behold, there’s a new stable release of Emacs, 23.1. And it works just great on OS X. Glory, glory, hallelujah, I’m back in business. Bye, bye, ViM. Bye, bye, KomodoEdit. It was nice knowing you, but it’s good to be back home.

I’m just back from the 16th Tcl/Tk Programming Conference, which was held in Portland, Oregon. Good conference. I learned a thing or two, but more importantly, I got to see the whole gang. I figured out yesterday that I’ve been to nine of the sixteen conferences, i.e., just over half; I’ve made a lot of good friends that I only get to see once a year. (I won’t list them; there are too many of them, and I’d be sure to miss one or two.)

The conference was a little bigger this year than last, continuing a trend; and as usual I was impressed by the international presence. There were two from Australia, at least two from Great Britain, one from the Netherlands, at least two from Poland, and several from Germany. Oh, and Jeff and Andreas from ActiveState, which is in Canada. (It was good to see Andreas; I met him at the first Tcl/Tk conference I went to, and we’ve had regular contact over the years, but seldom face-to-face.)

There’s neat stuff coming down the pike. Tcl/Tk 8.6 is nearly complete, with a bunch of new features (TclOO, coroutines, among lots of others), and there was much talk about Tcl 9. It’s a good time to be using Tcl.

For any Tcl/Tk programmers/students who happen by here, here’s a noticed posted earlier by Jeff Hobbs and Andreas Kupries of the Tcl Core Team:

Just an FYI that the Tcl/Tk community application to be a mentor organization and participate in the Google Summer of Code 2008 has been accepted. You can see the full list of organizations at:

http://code.google.com/soc/2008/

and Tcl/Tk’s info:

http://code.google.com/soc/2008/tcl/about.html

Now begins phase 2 – drumming up students interested in the ideas. The details are in the first link, but students may start applying for particular projects next Monday, March 24th.

If you have any connections to universities or other compsci student groups that might be interested, point them in the direction of our ideas list and encourage an application.

Thanks,

Jeff, et al